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 keep you busy. Each trace only
consists of one million memory accesses taken from the beginning of each program. The traces are the
following (linked from the Canvas project): 1. bzip.trace 2. sixpack.trace
Operating Systems COP4600, Spring 2022 Programming Assignment 2
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
31348900 W
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 corresponding
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
:
- FIFO
- LRU
- Segmented FIFO (see 1981 paper on Canvas)
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 reasonable decision.
Sample Solution