Description
In class, we have been discussing various page replacement algorithms that an Operating System
implementer may choose to use. In this project, you will compare the results of three different
algorithms on traces of memory references. While simulating an algorithm, you will collect statistics
about its performance, such as the number of page faults that occur and the number of dirty frames
that had to be written back to disk. When you are done with your program, you will write up your
results and provide a graph that compares the performance of the various algorithms.
The three algorithms for this project are:
OPT – Simulate what the optimal page replacement algorithm would choose if it had perfect
knowledge
Least Recently Used (LRU)– Simulate least recently used, whereby you will track when pages
were last accessed and evict the least recently used page.
Second Chance Algorithm – Candidate pages are considered for removal in a round robin
manner, and a page that has been accessed between consecutive page faults will not be evicted.
The page will be replaced if it has not been accessed since its last consideration. That is, each
page gets a “second chance” before it is replaced. In the worst case, if the second chance bit is
set for all pages, the bit is cleared and second chance algorithm degenerates to FIFO.
You may write your program in C/C++, Java, Perl, or Python as long as it runs on thoth.cs.pitt.edu.
Implement a page table for a 32-bit address space. All pages will be 4KB in size. The number of frames
will be a parameter to the execution of your program.
Project Details
You will write a program called vmsim that takes the following command line arguments:
./vmsim –n -a <opt|lru|second> The program will then run through the memory references of the file and decide the action taken for
each address (hit, page fault – no eviction, page fault – evict clean, page fault – evict dirty).
When the trace is over, print out summary statistics in the following format:
Algorithm: LRU
Number of frames: 8
Total memory accesses: %d
Total page faults: %d
Total writes to disk: %d
CS/COE 1550 – Introduction to Operating Systems
3
Implementation
We are providing three sample memory traces. The traces are available at /u/OSLab/original/ in the
files gzip.trace.gz, swim.trace.gz, and gcc.trace.gz. We will use more trace files to test your
program.
Each trace is gzip compressed, so you will have to copy each trace to your directory under
/u/OSLab/USERNAME/ and then decompress it like:
gunzip bzip.trace.gz
Your simulator takes a command-line argument that specifies the trace file that will be used to compute
the output statistics. The trace file will specify all the data memory accesses that occur in the sample
program. Each line in the trace file will specify a new memory reference. Each line in the trace will
therefore have the following two fields:
Access Type: A single character indicating whether the access is a load (‘l’) or a store (‘s’). The ‘s’
mode modifies the address and sets the dirty bit to true.
Address: A 32-bit integer (in unsigned hexadecimal format) specifying the memory address that
is being accessed. For example, “0xff32e100” specifies that memory address 4281524480 (in
decimal) is accessed.
Fields on the same line are separated by a single space. Example trace lines look like:
l 0x300088a0
s 0x1ffffd00
If you are writing in C, you may parse each line with the following code:
unsigned int address;
char mode;
fscanf(file, “%c %x”, &mode, &addr);
Important Notes
1. Evicting a page happens by identifying the page to evict and writing the page to the disk (if
dirty), or abandoning the page (if clean).
2. Implementing OPT in a naïve fashion will lead to unacceptable performance. It should not take
more than 5 minutes to run your program.
3. In case of a tie, in the OPT algorithm, break the tie by selecting the least recently used page.
If you are using Python, name your file vmsim and add the following shebang line at the
beginning of the file: #!/usr/bin/env python
Write Up
Part 1: For each of your three algorithm implementations, describe in a document the resulting page
fault statistics for 8, 16, 32, and 64 frames. Use this information to determine which algorithm you think
CS/COE 1550 – Introduction to Operating Systems
4
might be most appropriate for use in an actual operating system. Use OPT as the baseline for your
comparisons.
Part 3: For Second Chance, with the three traces and varying the total number of frames from 2 to 100,
determine if there are any instances of Belady’s anomaly. Discuss in your writeup.
Part 3: Discuss the implementation and runtime of the OPT algorithm
File Backups
One of the major contributions the university provides for the AFS filesystem is nightly backups.
However, the /u/OSLab/ partition on thoth is not part of AFS space. Thus, any files you modify under
your personal directory in /u/OSLab/ are not backed up. If there is a catastrophic disk failure, all of your
work will be irrecoverably lost. As such, it is my recommendation that you:
Backup all the files you change under /u/OSLab to your ~/private/ directory frequently!
Loss of work not backed up is not grounds for an extension.
Requirements and Submission
You need to submit onto Gradescope:
• Your well-commented program’s source
• A document (.DOC or .PDF) detailing the results of your simulation as described above
• DO NOT submit the trace files!
No matter which language you select, the autograder should be able to run your program as:
./vmsim –n -a <opt|lru|second> Grading Sheet/Rubric
Item Grade
Program runs with command-line parsing and correct output format
as tested by an empty trace file.
10%
OPT implementation 20%
LRU implementation 20%
Second Chance implementation 20%
Writeup (The graph plotting the number of page faults versus the number of
frames and your conclusions on which algorithm would be best to use in a real OS)
10%
Writeup (Second Chance Analysis) 10%
Writeup (OPT implementation) 10%
