| OpSys Spring 2006 - HW4 |
| OpSys Home | Assignment | Algorithms | Requirements | Submitting | Resources | FAQ |
- VM Simulator
The objectives of this assignment are:
You are to write a simulator for a virtual memory system. The simulator will support a number of different page-replacement algorithms (listed below) and will be able to report some statistics after each run. A run will be defined by a sequence of lines of text which your simulator will read from STDIN - each line in the input file corresponds to either a memory access by a process, the beginning of a (simulated) process or the end of a (simulated) process.
The input contains a series of lines, each line conforms to one of the patterns shown below. You can easily generate and store sample input sequences in a file, then run your simulator with input redirected from this file. Note that as part of the testing of your program, we will generate some input files that are not available to you during development (although we will provide some sample input files). The format of the input files is simple enough that you should consider writing a program that can generate a file according to some model of a pattern of virtual memory accesses by some number of processes.
| Operation | Syntax | Description |
|---|---|---|
| Start process | start pid |
Corresponds to the creation of a new process. The pid is a number that is used to refer to this specific processs. It is possible that pids will be re-used after termination, (you may come across two process 7's - they are different processes!). At any time there can be up to 10 active processes (pids 0 -9). |
| Terminate process | terminate pid |
Corresponds to the termination of an existing process. The pid indicates which process is to be completely removed from memory (this simulates a process exit). All pages used by the process should now be available. |
| Memory Read | read pid address |
Corresponds to a memory read operation by the process corresponding to the given pid. The address specified (in decimal) is a byte address, so you will need to convert this to a page address (as far as your simulation is concerned, there is no difference between accesses that are in same virtual page). |
Your simulator must support the command line options described
below (using the syntax described below). You probably should use
getopt to process the command line, there is a sample
program that uses getopt available:
getoptexample
./hw4 [-v] [-p pagesize] [-n numpages] [-a algorithm] [-t timestep]
-v If the -v option is included on
the command line your program should be verbose. This means
that the program should print one line out for each input line
processed, the output should indicate what action was taken as a
result of the input line (to provide a trace of all the virtual memory
operations and process start/termination).
If there is no -v option on the command line, the
program should not be verbose (must not print out a trace of every
operation, only output statistics at the end of the run).
-p pagesize The -p command line
option indicates the size of each page (page frame) in your
simulation. The size is given in bytes, and only powers of two are
allowed. You can assume that the maximum page size is 1024 bytes.
The page size default should be 32 bytes.
-n numpages The -n command line option
allows the user to specify the number of simulated page frames (number
of pages of physical memory). The number of pages must be a power of
two, and the maximum value is 8192. The default number of pages
should be 32. NOTE: The total memory size of your simulated physical
memory is the number of pages * the page size.
-a algorithm The -a command line
option is used to indicate which replacement algorithm should be used.
The choices are listed below (refer to the text for a complete
description of each algorithm):
-a ideal Optimal Algorithm.
-a lru Least Recently Used.
-a clock Clock algorithm (Second Chance).
IMPORTANT:In all cases, your replacement algorithms should use a global allocation policy.
-t timestep The -t command line
option is used to indicate the number of memory operations (read or
write) that correspond to a clock interrupt period.
The clock page replacement algorithm
requires that the OS clear all the R bits every time a clock
interrupt occurs - you should simulate this by pretending a clock
interrupt occurs every timestep memory operations. The default
value for this is 10.
Command line example: The following command line would run the simulator with the page size set to 32 bytes, a total of 8 pages of physical memory, simulating a clock interrupt every 100 memory operations, using the clock page-replacement algorithm and reading simulation commands from the file "sim1":
./hw4 -n 8 -t 100 -a clock < sim1
Below is a small sample of the kind of input that will be given to your simulator:
Your simulator should always generate the following output:
Page size in bytes
Number of page frames in the memory
Total # memory read/write operations
Total # page faults
Here is the kind of output we expect:
./hw4 -a clock -n 8 < samp1 Page Size: 32 # page frames: 8 Replacement Algorithm: clock Memory operations: 42 Faults: 9
Here is the kind of stuff we want to see when using verbose:
./sim.pl -v -a clock -n 8 < samp1 Starting process 0 Starting process 1 Starting process 3 READ 1 29 (virtual page 0): MISS, place in physical page 0 READ 0 20 (virtual page 0): MISS, place in physical page 1 READ 3 38 (virtual page 1): MISS, place in physical page 2 READ 1 26 (virtual page 0 is in physical page 0): HIT READ 0 38 (virtual page 1): MISS, place in physical page 3 READ 0 49 (virtual page 1 is in physical page 3): HIT READ 0 45 (virtual page 1 is in physical page 3): HIT READ 3 1 (virtual page 0): MISS, place in physical page 4 READ 3 35 (virtual page 1 is in physical page 2): HIT Starting process 2 READ 2 16 (virtual page 0): MISS, place in physical page 5 READ 1 14 (virtual page 0 is in physical page 0): HIT READ 1 32 (virtual page 1): MISS, place in physical page 6 READ 3 16 (virtual page 0 is in physical page 4): HIT READ 3 13 (virtual page 0 is in physical page 4): HIT ...
- Page Replacement Algorithms
When grading, we will compare the output of your program to ours, so you need to make sure that you understand how each algorithm works. Below is a brief description of each algorithm and a reference to where in the textbook you can find the details.
Ref: Page 215 in the text
The optimal algorithm can see into the future, and removes the page that will be idle the longest. In order to implement this algorithm you will need to process the input twice (once to record the memory reference string so you know what happens and when, a second time to actually simulate virtual memory). Your program will only be given the input once, so it needs to record the input! When using the recorded memory reference string to look ahead in time, don't ignore the possibility that a process named 0 may be started and then terminate, and later another process 0 may be started (this second one has nothing to do with the first process 0, we are just reusing the process number).
Ref: Page 218 in the text
LRU keeps track of the relative order of pages according to when they have last been accessed. When a page needs to be removed, the page that has been idle for the longest time is removed. You need to implement a complete LRU (not an approximation), so you need to update the page order every memory reference.
Ref: Page 217,218 in the text
The FIFO algorithm always removes the page that has been around the longest. Clock operates much like FIFO, except that instead of always removing the oldest page, it first checks to see if the page was recently used (used during the current time interval). If it has been used recently, the page gets a second chance and the second oldest page is now considered for removal. If the second oldest page has not been recently accessed, it is removed, otherwise we move on to the third oldest page, and so on. If the algorithm goes through all the pages and they have all been used recently, the algorithm will go back and take the oldest page and remove it.
To implement Clock you need to keep some information about the relative order of when pages are assigned to physical memory, and you need to keep track of the R bits for each page (that indicate whether the page has been accessed during the current time interval).
- Project Requirements
The following are the requirements for the project:
Your program must compile and run on the CS department
FreeBSD machines (freebsd.remote.cs.rpi.edu). You can
use any language you want, as long as we can test the code on the
FreeBSD machines. If you want to consider something other than C,
C++, Java, Perl, Ruby or Scheme - please ask Dave first.
Your simulator must support the command line options listed above.
Your simulator must correctly implement all three page-replacement algorithms mentioned above (Ideal, Clock and LRU). The text has a complete description of each.
Your simulator must be able to work with input files as described above - don't simply make up your own input file format.
Your submission must include instructions on how to build and run your simulator.
Your submission must include a file named README that includes the following information:
Grading: Your code will be graded according to the formula below. Note that to get full credit we must be able to understand your code (it must be commented!)
| 30% | Basic simulator functionality (processes command line properly and reads, processes input lines correctly, etc). |
|---|---|
| 60% | Page replacement algorithm implementations (20% each). |
| 10% | Code quality (comments, organization, how hard is it to understand ?). |
You can get partial credit for any part.
If you code does not compile and run under FreeBSD, you will lose at least 1/2 the relevant points ( partial credit will be awarded based on visual inspection of the code).
- How to Submit
Log in to WebCT at webct.rpi.edu using your RCS id and password. Once you get to MyWebCT click on "Operating Systems", and from there go to the homework drop boxes. Submit your files (individually, zipped or tarred) to the drop box labeled HW4.
-Resources