The samples have been revised

There is no reading for the on-line assignment this week. You just have to do a really fun simulation of virtual memory to test some page replacement algorithms. For Troy students, this is due on Monday October 25 at midnight. For off-campus students, the project is due on Monday Nov 1 at midnight.

This program requires no system calls, so it should be completely platform independent; develop it whereever you feel most comfortable.

Your program will read in a file called data.txt. This file will consist of a long series of page references. Each line of the file will consist of four integer values, delimited by a space. The first field is the process number, the second is the address of the instruction in the text segment, the third is a memory reference, and the fourth is a char, either R or W. If this char is a W, the memory reference was modified.

The page table should have a referenced bit and a dirty bit for each page. You may want to include other data as well.

All words are 16 bits, so all processes have a logical address space of 64K. All addresses read in from the file will be in the range 0 .. 65535. Each page is 512 bytes, so each process has a page table of size 128. In other words, in each logical address, the first (most significant) 7 bits determine the page frame, and the last 9 bits determine the offset of the address within the page frame. (Hint: to get the page frame number of a particular logical address, divide by 512).

There are 32 physical pages in memory for use by user programs.

You have to keep track of two statistics, the total number of page faults and the total number of disk references. Every page fault has at least one disk reference, but if the page to be replaced is dirty, then there will be two disk references, one to copy the dirty page back to the disk and one to load the new page.

Each process has its own page table, so address 12340 in process 1 is different from address 12340 in process 2.

In order to make this program easily gradable, the results should be deterministic. The answer for some of the input files will be provided for you.

You should have a global variable int debug. If the program is run with any arguments (if argc > 1) then debug is set to 1, otherwise, set it to zero. If debugging is on, your program should display information about each page fault whenever a page fault occurs. It should list the line that generated the page fault, the physical page being replaced, the process number, the logical page, and whether or not the page being replaced was dirty.

Simulation 1

In the first simulation, you will simulate a simple Not Recently Used Algorithm (p 216 of the text). Whenever a page is referenced, its referenced bit is set to 1. After executing every 200 instructions, your program should set all of the referenced bits to zero.

When a page fault occurs, first look for an unused page (this will only happen early in your simulation). Then look for an unreferenced page where the dirty bit is off and replace this page. Then look for an unreferenced page where the dirty bit is on and replace that page. If none is found, look for a referenced page where the dirty bit is off and replace that page. Finally, you will have to replace a page which is both referenced and dirty.

In order to make result deterministic, always replaced the lowest numbered page in a particular category.

Simulation 2

The second version of your program should simulate the clock algorithm (p 218). Whenever a page fault occurs, the hand of the clock starts to move. As it visits each page, it sets the referenced bit to zero. When it comes to a page where the referenced bit is zero, it replaces that page, regardless of whether or not it is dirty.

Simulation 3

The third version will be to use a Least Recently Used algorithm (p 218); i.e. keep track of the cycle where each page was last referenced, and replace that page that was used least recently. If there are two pages with the same value, replace one which is not dirty. If both pages or neither page is dirty, replace the lower numbered page.

Submit a brief README file with your conclusions.

Here is a link to the first test file and Here is a link to a second test file

Here are my three simulations. You can use these to make sure that your answer and my answer are the same. These run on solaris only. These have a feature that if you pass in a second argument, this will be interpreted as a breakpoint for debugging, and the program will display very detailed information about what is happening from that line on.
These were the original simulations
Simulation 1
Simulation 2
Simulation 3

Here is a revision of all three simulations, with the following changes:

• The earlier simulation tested for both pages before calling a page fault on either one. In this simulation, if the text page is not loaded, a page fault occurs before checking whether or not the memory page loaded.
• In super debugging mode (2 args) it displays the contents and status of each physical page at every page fault. However, it does this for only 100 lines after the breakpoint and then it quits. (Otherwise the output would be enormous).