CSC 1600 Assignment
Page Replacement Simulation

Objective

Background

Page replacement algorithms assume a fixed number of memory frames. We will work under the following assumptions:

1. The virtual memory of the process consists of NP pages, numbered 0 through NP-1.
2. A page reference stream is a sequence of integers ranging from 0 to NP-1. Each integer represents one reference to page.
3. The main memory consists of NF frames, numbered 0 through NF-1. This is represented as an array Frames. Each entry in the array Frames contains the number of the page currently residing in that frame.

1. FIFO (First-In, First-Out): the first page brought in is the first to be removed.
2. LRU (Least Recently Used): the least recently accessed page is the one to be removed.

Input

 # The first integer represents the length of the reference stream.
 # Subsequent integers constitute the reference stream.
 # The reference stream consists of a list of pages which
 # will be accessed in the order from left to right.
    
 10 0 1 2 0 3 0 4 2 3 2

Lines beginning with '#' are comments and should be ignored. There is exactly one non-comment line per file. The first number in this line represents the length of the reference stream, and the remaining numbers represent the reference stream. In the example above, the length of the reference stream is 10, and the reference stream is 0 1 2 0 3 0 4 2 3 2.

Output

  0 --> [0]
  1 --> [0 1]
  2 --> [0 1 2]
  0 --> [0 1 2]
  3 --> [0 3 2]  page fault
  0 --> [0 3 2]
  4 --> [0 3 4]  page fault
  2 --> [0 2 4]  page fault
  3 --> [3 2 4]  page fault
  2 --> [3 2 4]
        
  Total number of page faults is 4. 

As indicated above, your program should also compute the total number of page faults.

Implementation Steps

1. Your program should take three parameters on the command line, the first for number of frames, the second for which algorithm to use, and the third for the filename to examine. The possible values for the first argument are 3, 4, and 5, the possible values for the second argument are FIFO and LRU, and the third parameter can be any valid filename. Make sure you handle invalid arguments. For instance, a valid run of your program might look like

       ./a.out 3 FIFO data1.txt

   but if the user calls it as

       ./a.out 3 BOOM data2.txt

   you should print an error message and exit.

   Do not move on to the next step before you've thoroughly tested the code from the current step.

   ---

2. Implement a function

       void ReadReferenceStream(char * filename);

   that reads the reference stream from the input file and saves it in the Pages array. You need to allocate memory dynamically for the Pages array to store exactly np integers, where np is the first integer in the input file (that is not in a comment).

   Do not move on to the next step before you've thoroughly tested the code from the current step. To do so, you might need to implement another function

       void PrintReferenceStream() 

   to be invoked in the main function to verify that you have correctly saved the reference stream in the Pages array.

   ---

3. Implement a function

       int PageInMemory(int pageno);

   that returns 1 if pageno is in the Frames array and 0 otherwise. This function will come in handy later.

   Do not move on to the next step before you've thoroughly tested the code from the current step. To do so, you may initialize the Frames array with some arbitrary page number values, and test the behavior of the PageInMemory function on this array.

   ---

4. Write the main function that combines all steps above to implement the FIFO page replacement algorithm. The structure of your main program should look something like this:

     4.1 Process command line arguments
     4.2 Read in the data file and store each number in the reference stream in an array of references
     4.3 for( each page reference ) {
             if( the page is not currently in the Frames buffer )  {
                 Choose a victim page using the FIFO page replacement algorithm
                 Replace the page in the Frames buffer with the new page
             }
             Print out the Frames buffer
         }
     4.4 Output statistics

   You should run your algorithm on each of the following four input data files, for 3, 4, and 5 frames:

   • Input File 1
   • Input File 2
   • Input File 3
   • Input File 4

   Thus the total number of runs is 4*3 = 12. Mark down the total number of page faults in each case (for future comparison with the LRU algorithm).

   Do not move on to the next step before you have verified that your FIFO page replacement implementation works correctly.

   ---

5. Implement a function

       int SelectLRUVictim(int pageindex);

   that selects the victim page to be evicted from the Frames array based on the LRU (Least Recently Used) policy. Here pageindex is the index in the reference stream of the page that just generated a page fault. This function should determine the oldest page in the Frames array by scanning the reference stream backwards from the position indexed by pageindex, and return the index position of this page in the Frames array. For example, if the Frames contents are

         8 12 17 

   and the page reference stream is

         9 11 17 8 12 10 11 9

   then the call SelectFIFOVictim(5) would scan the substream 9 11 17 8 12 backwards to determine that 17 is the oldest page in the Frames array. In this case, the function would return the value 2 (index of page 17 in Frames).

   You may add arguments to this function as necessary to simplify your implementation (if needed).

   Do not move on to the next step before you've thoroughly tested the code from the current step.

   ---

6. Modify the main function to implement the LRU page replacement algorithm (for now, comment out the code specific to FIFO). Run your program on each of the four input data files listed above for 3, 4, and 5 frames. Mark down the total number of page faults in each case. Compare the results with the ones produced by the FIFO algorithm.

   Which algorithm performs better in what situations?

   ---

7. Modify the main function to work with both FIFO and LRU. The specific algorithm to be used should be specified in the command line.

Submission Guidelines

1. Your name and assignment number.
2. The statistics collected from running your code and your observations on the results.
3. A description of whatever help (if any) you received from others outside of class.
4. An indication of how much time you spent doing the assignment outside of class.
5. Your assessment of the assignment: Did it help you to learn? What did it help you to learn? Do you have any suggestions for improvement? Etc.
6. Any information that will help us to grade your work in the most favorable light. In particular you should describe all known bugs.

Your readme file should be a plain text file. Do not create your readme file using Microsoft Word or any other word processor.

Turn in a printout copy of the readme and vm.c files, and a sample output. You will need to copy and paste your code into a text or a Word document in Windows, since you cannot print directly from Unix.

Leave the source code for all exercises in your directory csc1600/vm. Do not make any changes to these files after the due date for this assignment.

Grading

Important note: If your program is not in the correct location in your Unix account, or if it does not compile, or if it produces a segmentation fault when running, you will receive zero credit for this assignment. Make sure that your code compiles and runs on both felix and tanner.

Have fun!