CS 502 Operating Systems WPI,
Spring 2006
Hugh C. Lauer Project
3 (30 points)
Assigned: Monday, March 6, 2006 Due:
Monday, March 27, 2006
Write a program to simulate a paging system and to implement, experiment with, and evaluate page replacement algorithms in your simulated environment. You must implement FIFO, LRU, and at least one other page replacement policy described in class, in the textbook,[1] or in the scientific literature.
Your program should take as input
· The name of a page replacement algorithm
· Information about the number of physical page frames in the simulated system
· A path name of a file containing a reference string of virtual page numbers
Your program should “execute” the reference string, swapping in new pages as needed and throwing out old pages according to the selected replacement policy. In the first part of the project, you will simply execute a short reference string with each algorithm and print out a chart show the actual page replacements that your algorithm makes. In the second part, you will execute longer reference strings with each of your algorithms and create one or more charts or graphs showing page fault rate versus number of frames. Finally, you should report on what you have discovered about the working sets of the reference strings and on the efficacy of the different replacement algorithms.
The purpose of this part is to debug your paging system. Your program for this part, called pager1, should have a command line interface resembling the following:–
% pager1 policy n refString.txt
where policy is one of FIFO, LRU, and your other chosen page replacement algorithm, where n is the number of physical page frames available to hold virtual pages, and where refString.txt is the file containing the reference string.
The output chart should resemble the chart in Figure 4-25 of the textbook, but rotated 90 degrees so that time is in the vertical direction. Each line should show the page numbers in physical memory and, if applicable, the virtual page numbers of the pages swapped in and evicted. You need not repeat lines that are identical for consecutive page references, but if there is a string of references that can be satisfied by the pages in physical memory, you should indicate the number of references in that string.
The file containing the reference string will be a simple list of integers separated by white space (possibly new line characters). Each integer refers to a virtual page number that is being referenced on that step. If a particular virtual page is not in physical memory, you must swap it in. If there is not enough room in physical memory to hold the page, you must evict another page according to your policy.
Hint: Keep the reference string in this part short for debugging purposes. Print out or display the sequence of page references and replacements, inspect them, and make sure that your algorithm behaves the way you expect to behave.
A set of reference strings for use with this project can be found on
http://www.cs.wpi.edu/~cs502/s06/Project3Data
Please watch this URL for additional reference strings.
In this part, you will execute each of your replacement algorithms with a range of physical memory sizes. Your goal is to determine how well each algorithm works for each reference string. You should also determine what the working set size of each reference string is and when thrashing begins. Your program, pager2, should have a command line interface along the lines of
% pager2 policy m n refString.txt
where policy and refString.txt are the same as before and where m and n are lower and upper bounds on the sizes of physical memory, respectively. Execute the reference string at least five times for different sizes of physical memory between m and n. Your program should print out
· at the beginning of each session, the name of the policy, the reference string, and
· for each execution of the reference string, the physical memory size and the number of pages faults — i.e., the number of times that a page had to be swapped in.
In addition, you should accumulate the pairs
(physical memory size, number of page faults)
in a file that can be read by Microsoft Excel or some other graphing/charting tool. Plot the data with physical memory sizes on the x-axis and number of page faults on the y-axis. Plot three different lines on your graph, one for each page replacement algorithm.
If there is not enough information in the graph to draw useful conclusions, run pager2 again with a more narrow range of physical memory sizes. Add these results to the previously plotted data points to improve your chart or graph. If your results just don’t make sense at all, try running a part of the reference string on you first program, pager1, and look at its page fault pattern to see if you can figure out what is going on.
If the reference string exhibits sufficient locality and if the replacement algorithm is sufficiently good, you should be able to estimate its working set size by inspection from the graph. If there is insufficient locality or the algorithm is weak, explain in a few sentences what you think is happening. Also explain if you spot something unusual about the working set.
This project is NOT a team project; it is to be done individually.
Note that while these are application programs, you should assume that you are writing code suitable for inclusion in an operating system. For example, you should never assume that the user always submits correct input.
All code must be clearly commented. All output and printouts must be easy to understand and cleanly formatted.
For this assignment, please use the turnin program, i.e., the command line tool for turning in assignments on CCC computers. Information about this tool can be found on
http://web.cs.wpi.edu/Help/turnin.html
This class is ‘cs502’, and the assignment is ‘project3’. Therefore, the “turnin” command would be
/cs/bin/turnin submit cs502 project3
<your files>
Your submission should include
1. Identify the third page replacement algorithm that you have selected. If it is not in the textbook, please include a reference and a short description.
2. The files containing the code for all parts of this assignment.
3. The makefiles for building the executable programs and information on the system on which your program is built.
4. The test files or input that you use.
5. Files that capture the input and output for building and running and testing the programs.
6. Your charts or graphs for Part 2 in Excel or PDF format.
Also, you should bring a printed copy of your work to class on the due date. Make sure that your name is clearly visible on your work.