CSC 1600 Assignment
Page Replacement Simulation


Deepen your understanding of page replacement algorithms through implementation and interpretation of results.


Each process has its own virtual address space, partitioned into chunks called pages. The memory is logically divided into frames of the same size, ready to hold any virtual memory pages. Not all pages are loaded into the memory at the same time -- only the ones that are needed by the process to run. When a process accesses a page that is not in the memory, a page fault is generated and the requested page must be brought into the memory. If there is no free memory frame to host the new page, then a victim page must be evicted from memory to make room for the new page, so that the process can continue execution. The selection of the victim page is made according to a specific page replacement policy.

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.
The page-replacement algorithms you will be simulating are:
  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.


The input data is stored in a file with a format similar to the following one:

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


The output of your program should result in two columns. The first column indicates the page that has been referenced, and the second column shows a snapshot of the pages loaded in memory immediately after the page reference. Here is a sample output for the reference stream 0 1 2 0 3 0 4 2 3 2 :

  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:

    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

In your csc1600 directory create another directory called vm (for virtual memory). Yoir source code vm.c should be in this directory. In your csc1600/vm directory create a text file named readme (not readme.txt, or README, or Readme, etc. ) that contains:
  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.
Descriptions of your code should not be in the readme file. Instead they should be integrated into your code as comments.

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.


35     Total points possible
10 Program compiles successfully and runs
10 FCFS produces the correct output
10 RR produces the correct output
  5 Your readme file is present and includes all required components

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!