Aim
By doing this practical work, you will learn how to implement page replacement algorithms, gain experience in creating and evaluating a simple simulator, and develop your skills in scientific writing.
Introduction
In class, we have explored a variety of page replacement algorithms for managing virtual memory.
In this practical, you will evaluate how real applications respond to a variety of page replacement algorithms. Of course, modifying a real operating system to use different page replacement algorithms is quite a technical mess, so we will simulate it instead. You will extend a program that simulates the behaviour of a memory system using a variety of page replacement algorithms.
Then, you will use memory traces from real applications to evaluate your algorithms properly. A main outcome of your work will be a report. The report itself counts for 60% of this assignment, so you should be sure to spend time thinking about what to measure, and what the significance of your results are.
Memory Traces
We provide you with four large memory traces to use for your evaluation. Each trace is a real recording of a running program, taken from the SPEC benchmarks. Real traces are enormously big: billions and billions of memory accesses. However, a relatively small trace will be more than enough to keep you busy. Each trace only consists of one million memory accesses taken from the beginning of each program. Each trace is compressed with gzip, so you will have to uncompress it with a command like this:
> gunzip –d gcc.trace.gz
Each trace is a series of lines, each listing a hexadecimal memory address followed by R or W to indicate a read or a write. For example, gcc.trace trace starts like this:
0041f7a0 R
13f5e2c0 R
05e78900 R
004758a0 R
31348900 W
Simulator Requirements
Your job is to build a simulator that reads a memory trace and simulates the action of a virtual memory system with a single level page table. Your simulator should keep track of what pages are loaded into memory. As it processes each memory event from the trace, it should check to see if the corresponding page is loaded. If not, it should choose a page to remove from memory. Of course, if the page to be replaced is dirty, it must be saved to disk. Finally, the new page is to be loaded into memory from disk, and the page table is updated. The current simulator fixes the pages and page frames size to 4 KB (4096 bytes).
This is just a simulation of the page table, so you do not actually need to read and write data from disk. When a simulated disk read or write must occur, simply increment a counter to keep track of disk reads and writes, respectively. You must implement three different page replacement algorithms. rand replaces a page chosen completely at random. lru always replaces the least-recently-used page. esc (enhanced second chance) performs the replacement algorithm described in the textbook section 9.4.5.3.
- The simulator accepts 4 arguments as follows
- the name of the memory trace file to use.
- the number of page frames in the simulated memory.
- the page replacement algorithm to use : rand/lru/esc
- the mode to run: quiet/debug
If the mode is “debug”, the simulator prints out messages displaying the details of each event in the trace. You may use any format for this output, it is simply there to help you debug and test your code. If the mode is “quiet”, then the simulator should run silently with no output until the very end, at which point it prints out a summary like this:
total memory frames: 12
events in trace: 1002050
total disk reads: 1751
total disk writes: 932
page fault rate: 0.83
Your solution will be run as shown :
> java Memsim trace1 32 lru debug
In the tarfile provided there is a code skeleton called Memsim.java that reads the parameters, processes the trace files and for each access it generates a page read or write request. Your job is to implement the memory management unit for each replacement policy. You should start thinking how you can keep track of what pages are loaded, how to find if the page is resident or not, and how to allocate frames to pages. Some short traces (trace1, trace2 and trace3) are provided to facilitate testing of your code.
Alternatively, if you prefer to use the C language, there is an equivalent skeleton of the simulator called memsim.c in the folder.
You simulator code should be saved in an svn directory, and submitted using the web submission system, by the code deadline.
Report
An important component of this practical is a report describing and evaluating your work. Your goal is run the simulator to learn as much as you can about the four memory traces (swim, bzip, gcc and sixpack). For example, how much memory does each traced program actually need? Which page replacement algorithm works best when having a low number of frames? Does one algorithm work best in all situations? What is the size of the working set?
Think carefully about how to run your simulator. Do not choose random input values. Instead, explore the space of memory sizes intelligently in order to learn as much as you can about the nature of each memory trace. Your report should have the following sections:
Introduction: A section that explains the essential problem of page replacement and briefly summarizes the structure and implementation of your simulator. Do not copy and paste text from this project description. Describe it using your own words.
Methods: A description of the experiments that you performed. As it is impossible to run your simulator with all possible inputs, so you must think carefully about what measurements you need. Make sure to run your simulator with an excess of memory, a shortage of memory, and memory sizes close to what each process actually needs.
Results: A description of the results obtained by running your experiments. Present and compare the performance of each algorithm on each memory trace using graphs that show the page fault rate over a range of available memory sizes. In the text, explain what each graph or table shows and point out any interesting or unusual data points.
Conclusions: Describe what you have learned from the results.
Report length: use enough space to say what needs to be said; a one page report is probably too short; a six page report is too long. Your report must be well structured and free of typos and errors. Each group must submit a PDF file by the due date.