Project 4: Page Replacement Algorithms

Introduction

One of the important factors in determining the effectiveness of any paging mechanism is the page replacement algorithm being used. The objective of this programming project is to simulate the six different page replacement algorithms that we covered in class: Optimal, FIFO, LRU, LRU approximation, LFU and the third-chance algorithm.

Details

In this project, you will be calculating the page fault rate of the different page replacement algorithms for one process only.

Main Program: Your main program should accept two arguments, which are the names of an input file and an output file. The input file contains all specifications concerning arrivals, resource requests and display events. Name your executable pagerepsim. Sample usage is   $ pagerepsim input.dat output.dat   where input.dat refers to the input file and output.dat is the name of the output file.

Input file details: The first line in the input file contains a single number that indicates the size of the primary memory in terms of block size. So a number 10 will indicate that there are 10 blocks of primary memory available for this process.

The subsequent numbers in the input file indicate the page reference stream in terms of pages for the process. Assume that the program size is 100 pages, the pages being numbered from 0 to 99. This implies that no number in the reference stream will fall outside that range. Each number will be followed by the character 'c' or 'n'. The 'c' indicates that the page has been modified while being referenced. The 'n' indicates that the page has not been modified. These two characters are used in the third chance algorithm. These numbers and characters could be separated by any number of white space characters and will be spread over multiple lines. There will be exactly 100,000 references in the page reference stream.

Output file details: The output file should print out the page fault rates for each of the six page replacement algorithms specified above based on the input page reference stream at intervals of 20000 pages. Sample output format is shown below. For example, the column under 80000 lists the page fault rates for the first 80000 page references for all algorithms. Note that these are just sample values. 

               Page Replacement Algorithm Simulation
               =====================================
                                               Page fault rates
 Algorithm   Final Page faults 20000   40000   60000   80000   100000
----------------------------------------------------------------------
 Optimal           2500        0.276   0.298   0.287   0.220    0.250
 
 FIFO              3387        0.338   0.298   0.387   0.320    0.339

 LRU               3109        0.310   0.298   0.307   0.320    0.311

 LRU Approx        3201        0.300   0.298   0.287   0.220    0.320

 LFU               3000        0.290   0.298   0.287   0.279    0.300
 
 Third-Chance      3400        0.340   0.298   0.287   0.220    0.340
----------------------------------------------------------------------

Assumptions and Errors

  1. Each number in the input reference stream is guaranteed to be in the range of 0 to 99.

Important Note

Additional information or clarification about the project specs, including elaboration of the input and output formats, will be given in class. It is your responsibility to attend class and get this information.

Design and Implementation Considerations

Submission details

Create a directory called p4. Put all your source code files and a Makefile in this directory. Also include a file called honorpledge.txt in this directory with the statements shown below. 

On my honor:
- I have
not discussed my homework solution or program code with anyone other than
  my instructor or the GTA assigned to this course.

- I have not used programs or code obtained from another student, or 
  any other unauthorized source, either modified or unmodified.

- If any code or documentation used in my homework submission
  was obtained from another source, such as a text book or course
  notes, that has been clearly noted with a proper citation in
  the comments of my program.

- I have not designed this program or submission in such a
  way as to defeat or interfere with the normal operation network
  services and/or the method by which assignments are fetched.
Print your name as the last line of this file. You should submit your source files, associated Makefile and the honorpledge.txt as a tared and gzipped file called pid.gz where pid is replaced by your student pid. The tar command should be run on the directory. Make sure that it contains only the necessary files. Do not include any executable or extraneous files. One way of creating the gzipped file is to execute the following sequence of operations on your directory p4 from one directory level above. $ tar -cvf pid p4 $ gzip pid This should generate a file called pid.gz in your directory. This is the file that you should submit. It is your responsibility to make sure that the Makefile compiles each file and generates the executable. You will lose points if you do not submit a Makefile.

You will use the automated curator for submitting your pid.gz file. To submit your program, go to the web page at http://www.cs.vt.edu/curator. Enter your university pid and type in the password that got mailed to you from curator@cs.vt.edu account, select the appropriate section and upload your pid.gz file.

Grading Criteria

Seventy will be assigned for program functionality, while thirty points will be for program documentation. Remember that your program is not self-documenting, and that you need to write code that is easily readable and consequently maintainable. Follow the documentation style shown here.
© Mir Farooq Ali, 2003.