CSE 451 Extra Credit Programming Assignment: Page Replacement

THIS ASSIGNMENT MAY BE DONE FOR EXTRA CREDIT. Since this is extra credit, there is no penalty for not doing it. If you expect that your final course grade may need a "lift" to help overcome a blown exam question, or a missed homework or two, it might be a good idea to do try to tackle this. Consequently, I need to ask you to work individually (although you may consult with your partners, or other members in the class).

This assignment will be worth the equivalent of one question from the final exam.

For this assignment, you will be comparing the effectiveness of 3 different page replacement strategies in your VM implementation. The strategies are:

RANDOM
Select victim page at random.
FIFO
Replace the page resident the longest.
FIFO+SECOND CHANCE
Give a candidate page a "second chance" to be referenced. [NOTE: an easy way to do this is to add a second queue, whose size is to remain equal to a fixed fraction of physical memory -- 10% is a good size -- whenever the queue shrinks below this threshold, move pages from the FIFO queue to the second chance queue; whenever a page is referenced on the second chance queue, move it to the end of the FIFO queue].

For each of these algorithms, run the test program below 4 times - once with 64 physical pages, once with 128 physical pages, once with 256 physical pages, and once with 512 physical pages. and collect:

Total number of memory reads performed by your program
Total number of memory writes performed by your program
Total number of read page faults serviced by your VM system
Total number of write page faults serviced by your VM system
% of read faults that required going to disk
% of write faults that required going to disk

From these, compute:

Probability of a page fault that requires going to disk
Probability of a page fault that does not require going to disk
Effective memory access time (assume: memory access time is 1 usec, a page fault is 100 usecs, and going to disk is 10 milliseconds).

WHAT TO TURN IN:

A single C file that contains your three replacement algorithms. Please highlight and mark the relevant code for each implementation.

For each run (64 pages, 128 pages, 256 pages, 512 pages), a table structured as shown

STRATEGY  |  #Reads   #Writes   #ReadFaults   #WriteFaults   %ReadToDisk   %WriteToDisk   Eff.Acc.Time
----------+-------------------------------------------------------------------------------------------
RANDOM    |
FIFO      |
FIFO+2dCh.|

A graph comparing the three strategies. The x-axis should be size of physical memory (64, 128, 256, 512 pages), and the Y axis should be effective access time. Draw a curve for each of the strategies.

DUE DATE: This assignment is due 5pm Friday, end of finals week, and should be turned in as hardcopy to Bershad's office.

TEST PROGRAM

#include <stdio.h>
#include "mtio.h"

int i, j;

main() {
unsigned A[128][1024];
unsigned B[1024][1024];

  printf("Starting...\n");
  fflush(stdout);

  for(i=0; i<1024; i++)
      B[i][0] = i;
  for(i=0; i<128; i++) {
      for(j=i*7; j<128+i*7; j++)
	  A[i][0] += B[j][0];
      printf("+");
      fflush(stdout);
  }
  printf("\nDone\n");
  fflush(stdout);

  _exit();
}