p2-memsim
Operating Systems COP4600, Spring 2021 Programming Assignment 2
Assignment 2: Measuring the Performance of Page
Replacement Algorithms on Real Traces
Due date: Monday, March 1, 2021 at 11:59pm on Canvas.
Learning Objective:
• Understand the costs of page replacement algorithms
• Observe the effect of memory traces and the effect of page replacement algorithms on
system performance.
In this project you are to evaluate how real applications respond to a variety of page replacement
algorithms. For this, you are to write a memory simulator and evaluate memory performance
using provided traces from real applications.
You may work in teams of 2, or you can work alone. If working in teams of 2, only one
submission per team is sufficient.
The deliverables of this project are:
1. A report (in PDF) that includes:
o Your name(s).
o A short presentation of the problem you address (hopefully not cut and pasted from
this document or the paper, but written in your own words).
o A report of the results and detailed interpretation of the results.
o An estimation of the time (each of) you spent working on the project.
There is no requirement on the length of your report: you’ll be graded based on how well
your report shows your understanding of the problem.
2. A zip file with all of your files in one folder with your name(s). The zip file needs to
include the following:
o A makefile for easy compilation, the C program(s). The makefile target
executable should be called memsim.
o A README file that describes how to run your project (e.g., arguments, etc).
o Code that implements the objectives of this project. Please do not include your
name in the code.
Memory Traces
You are provided with memory traces to use with your simulator. 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
Operating Systems COP4600, Spring 2021 Programming Assignment 2
keep you busy. Each trace only consists of one million memory accesses taken from the
eginning of each program. The traces are the following (linked from the Canvas project):
1. bzip.trace
2. sixpack.trace
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:
0041f7a0 R
13f5e2c0 R
05e78900 R
004758a0 R
XXXXXXXXXXW
Note, to scan in one memory access in this format, you can use fscanf() as in the following:
unsigned addr;
char rw;
...
fscanf(file,"%x %c",&addr,&rw);
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 co
esponding page is loaded. If not, it should choose a page to remove from memory.
If the page to be replaced is “dirty” (that is, previous accesses to it included a Write access), it
must be saved to disk. Finally, the new page is to be loaded into memory from disk, and the page
table is updated. Assume that all pages and page frames are 4 KB (4096 bytes).
Of course, this is just a simulation of the page table, so you do not actually need to read and write
data from disk. Just keep track of what pages are loaded. When a simulated disk read or write
must occur, simply increment a counter to keep track of disk reads and writes, respectively.
Implement the following page replacement algorithms to replicate the experimental evaluation in
this 1981 paper11:
1. FIFO
2. LRU
3. Segmented FIFO (see 1981 paper on Canvas)
1 Rollins Turner and Henry Levy XXXXXXXXXXSegmented FIFO page replacement. In Proceedings
of the 1981 ACM SIGMETRICS conference on Measurement and modeling of computer systems
(SIGMETRICS '81). Association for Computing Machinery, New York, NY, USA, 48–51.
DOI:https:
doi.org/10.1145/ XXXXXXXXXX
Operating Systems COP4600, Spring 2021 Programming Assignment 2
Structure and write your simulator in any reasonable manner. You may need additional data
structures to keep track of which pages need to be replaced depending on the algorithm
implementation. Think carefully about which data structures you are going to use and make a
easonable decision.
You need to follow strict requirements on the interface to your simulator so that we will be able
to test and grade your work in an efficient manner. The simulator (called memsim) should take
the following arguments:
memsim
The first argument gives the name of the memory trace file to use (thus, can be any
file in the format described above and in the trace files provided. The second argument gives the
number of page frames in the simulated memory. The third argument gives the page replacement
algorithm to use. The fourth argument may be "debug" or "quiet" (explained below.)
If the fourth argument is "quiet", then the simulator should run silently with no output until the
very end, at which point it should print out a few simple statistics like this (follow the format as
closely as possible):
total memory frames: 12
events in trace: XXXXXXXXXX
total disk reads: 1751
total disk writes: 932
If the fourth argument is "debug", then the simulator should print 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 third argument is "vms", you have to take an extra parameter that indicates the percentage
of the total program memory to be used in the secondary buffer. In that case, the simulator
should take the following arguments:
memsim
“p” will be a number between 1 to 100.
Use separate functions for each page replacement algorithm, i.e., your program must declare the
following high level functions: fifo(), lru(), segmented-fifo().
Project Report
Operating Systems COP4600, Spring 2021 Programming Assignment 2
An important component of this project will be to write a report describing and evaluating your
work and presenting your results using both tables and plots (use Excel or Matlab or another tool
of your choice). You should think of this project as if it were a lab experiment in a physics or
chemistry class. Your goal is to use the scientific method to learn as much as you can about the
provided memory traces. For example, how much memory does each traced program actually
need? What is the working set of each program? Which page replacement algorithm works best?
Does one algorithm work best in all situations? If not, what situations favor what algorithms?
Use the paper that described Segmented FIFO as guidance for how to present your experimental
data. Do your observations confirm the results of the paper?
Your report should have the following sections:
1. Introduction: A section that explains the essential problem of page replacement and
iefly summarizes the structure and implementation of your simulator. Do not copy
and paste text from this project description. In your own words, describe the overall
structure and purpose of the experiment.
2. Methods: A description of the experiments that you performed in order to learn
something about each memory trace. Of course, it is impossible to run your simulator
with all possible inputs, so you must think carefully about what measurements you
need to answer the questions above. 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. For instance, you may want to think strategically of what values you
use for the parameter. On one hand, you want to cover enough of the
memory space to see when (a) your "process" does not have enough physical memory
(thus, a lot of misses!); (b) when your process' working set fits in the memory; and (c)
where increasing the allocated memory does not improve performance significantly.
On the other hand, the more values for you test with, the more hours
you'll spend sta
ing at the computer. To help you decide, think of number of frames
as power of 2. So perhaps a sequence of 1, 2, 22, 23, 24, ..., 210 might be better than 1,
2, 3, 4, 5, 6, 7, 8, 9, 10, for example. Also, think of what x
means for today's processes – perhaps an allocation of 2 TB of memory for a process
is not particularly common these days (and neither is a physical memory of 32KB).
3. Results: A description of the results obtained by running your experiments. Present
the results using tables and plots that show the performance of each algorithm over a
ange of available memory. For instance, include a plot of hit rate vs. memory size for
each algorithm. In the text, summarize what each plot or table shows and point out
any interesting or unusual data points. Compare the results obtained from the two
trace files – are there any differences in the performance you see? What might explain
these differences? Which is the algorithm that shows the biggest difference? What do
you think happens?
4. Conclusions: Describe what you have learned from the experimental results. What
have you learned about the memory traces? What