For this assignment, you'll be implementing a simulator
that models the virtual memory components of a computer system.
We'll use the electronic turnin program for this assignment.
For each source code file that you turn in, please put your name
and your section in a comment at the top of the file.
Your program will simulate all the major components of the virtual
memory system: the TLB, the operating system page tables, and the
paging file. Further detail about how to simulate each of these
components is provided below.
The Trace File
As input, your simulator will read in an address trace file named
"trace.in". This
file contains a list of addresses and operations, and this represents
the memory reference behavior of a program running on the simulated
machine.
Each reference is categorized as either a read or a write. The format
of the trace file is: one entry per line, with an operation
field (r = read and w = write), a single space, an address
category (i = instruction and d = data), a single space, and finally
an address field (the ASCII decimal representation of the address
being referenced). You should use the atoi() function from the
standard C library to assist with reading the trace file.
To illustrate, here is a very short sample trace file that contains only
4 references:
r i 440
w d 410
r i 76
r d 348
The first line says that the instruction at address 440 was read, and
second line says that the data at address 410 was written. The values
read or written at these addresses are NOT contained in trace file,
since they are irrelevant for simulating the virtual memory system.
Simulating the TLB
The TLB structure that you will simulate is a split TLB. The page size
for the simulated machine is 4KB. The instruction
TLB (ITLB) will have 16 entries and is 4-way set associative. The replacement
policy you should implement for the ITLB is LRU. The data TLB (DTLB) will
have 32 entries, and is 4-way set associative. You should use a random
replacement policy for the DTLB. You should use the srandom() and
random() functions from the standard C library to implement your
random replacement policy, and you should use an initial seed value
of 14897 (this requirement is needed so that everyone's DTLB will
behave identically for testing purposes). Since random() returns
an unsigned random value between 0 and 2^32-1, you should take
that value modulo 4 to generate a random number between 0 and 3.
During the simulation, you should record the # of accesses to
each TLB, as well as the # of hits.
Output from your simulator
At the end of the simulation, you should print out the
miss rate (as a percentage) for both the ITLB and the DTLB.
Your simulator, when invoked with the "-verbose" option,
should print out the contents of both the ITLB and the DTLB when
the simulation ends.
Simulating the OS Page Tables
The page table structure that you will simulate is a linear page
table (as opposed to the inverted page tables or the hierarchical
page tables described in the book). To reduce the storage requirements
for your page table, you should assume that bits 26 through 31 of
the virtual address are always 0 (in other words, that maximum address
value that will be in the trace file is 2^26-1). Each page table
entry should contain a valid bit, a physical page number, and a
dirty bit.
You should use an LRU replacement policy to simulate how main memory
is managed. The size of main memory on the machine you are simulating
is 256 pages. Initially, main memory should be empty (so your virtual
memory system page freelist contains every physical page). Your page
allocation policy should simply hand out the physical pages in order
of increasing page number (starting at 0), until the freelist is
empty. From that point on, all physical pages will be obtained by
page replacements. In our simulation, pages will never be added
back to the freelist since we're only simulating a single process
and it never dies.
Output from your simulator
The output of your simulation for this component should be the
total number of page faults. When your simulator is
invoked with the "-verbose" option, it will print out the
contents of all the valid entries in the page table when the
simulation ends.
Simulating the Paging File
You do not have to model the actual placement of virtual pages on
disk (a more accurate simulation would record the disk block
number for all those entries in the page table where the valid
bit is not set). Instead, you should simply keep track of the
number of disk read and write operations that are needed to
handle the page faults. You can assume that the disk block size
matches the 4KB page size, so it only takes 1 disk read operation
to load a 4KB page from disk.
Output from your simulator
When the simulation ends, you should print out the total number
of disk read operations and the total number of disk write operations
that were needed to handle all the page faults.
Implementation
You should build your implementation of the TLB simulator on
the instructional Alpha machines. You should implement your
simulator in C, not MIPS assembly. There are two C compilers
on the Alpha: /usr/bin/cc and /usr/local/bin/gcc, either one
is fine. There are two debuggers available on the Alpha,
/usr/bin/dbx and /usr/local/bin/gdb. If you choose gcc as
your compiler, I highly recommend using gdb as your debugger.
When you use turnin, you should submit the source
code for your simulator, as well as the compiled version
so that I don't have to build it.