The objectives of this assignment are:

1. Understanding of the basic operations involved with a virtual memory system.
2. Understand how various page replacement algorithms work.
3. Analysis of page replacement algorithms.

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, or the beginning or end of a (simulated) process.

Simulation Input

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 to 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	S pid	Corresponds to the creation of a new process. The pid is a number that is used to refer to this specific processs.
Terminate process	T 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).
Memory Read	R 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 as long as they are on the same virtual page).
Memory Write	W pid address	Corresponds to a memory write 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 writes as long as they are on the same virtual page).

Simulator Command Line

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

./vmsim [-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).

  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 fifo First-in, First-out.

  • -a clock Clock algorithm.

  • -a nfu Not frequently Used - LRU approximation.

  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 inputs lines that corresponds to a clock interrupt period. Some of the page replacement algorithms require that the OS clears some status bits every time a clock interrupt occurs - you should simulate this by pretending a clock interrupt occurs every timestep lines of input. 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 lines of input, 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 feed to your simulator, note a few complete (and larger ) files will be available soon...

S 0
S 1
S 3
R 1 29
R 0 20
R 3 38
R 1 26
R 0 38
R 0 49
R 0 45
R 3 1
R 3 35
S 2
R 2 16
R 1 14
W 2 37
R 1 32
R 3 16
R 3 13
R 0 0
R 0 11
R 2 8
R 0 2
R 1 4
R 1 55
R 1 41
W 0 24
R 0 30
R 2 2
T 2
R 1 3
R 3 5
R 1 18
R 1 7
R 3 41
R 3 38
S 2
R 2 15
R 2 10
R 2 39
R 1 33
R 1 41
W 1 5
R 3 55
R 1 42
R 1 9
R 2 50
R 2 7
R 1 31
R 2 7
R 2 21

Simulator Output

Your simulator should always generate the following output:

• Page size in bytes

• Number of page frames in the memory

• Number of lines of input processed

• Total # memory read/write operations

• Total # page faults

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 or Perl - 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 (FIFO, Clock and NFU). 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. A Makefile must be included for C, C++ or Java)

• Your submission must include a file named README that includes the following information:

  • Your name
  • A 1 line description of each file you are submitting
  • A description of any problems you had, known bugs or deficiencies.
  • Anything else you want us to know.

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).

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.

Sample getopt program