CS 39 Fall 2003 -- Project 0


A note on Academic Honesty

For these assignments, you are allowed to discuss the problem, and your thoughts on the solution, with others. You are not allowed to exchange, in any way, code or anything like it.


An LRU Simulator

Note that for this assignment, you do not need a deep understand of what an LRU Simulator is, nor what uses it is put. It is only critical at this moment that you understand how one works, as described here.

An LRU Simulator tracks the pattern in which memory addresses are used by a given program, and emits at the end some aggregate statistics about that pattern. Here is a high-level overview of the characteristics of such a simulator:


Your assignment (specifically)

Implement two LRU simulators. (Note: In class I had described three different simulators. I am only required two, as described here.) Each simulator must be implemented in C++, and must conform to the standards given below. First, however, there are some important characteristics that are common to both simulators:

Here is a description of the two simulators, where the difference between the two is the manner in which each will store and manipulate the LRU queue.

  1. For the first simulator, the LRU queue should be stored as a doubly linked list of your own creation. Each link in the list should have previous and next pointers, as well as an unsigned int to store the page number itself. How you choose to implement the linked list beyond that aspect is up to you.
  2. For the second simulator, the LRU queue should be stored as an STL list (which will also happen to be doubly linked). You need only create a list<unsigned int> and use that to keep the order of the page numbers.

Note that there is no use of an STL hash_map. Feel free to examine and test that and other template classes offered by STL, but do not use them in this project. Check the STL documentation for more information, but beware that it is not an easy read. For a gentler example on STL list and hash_map use, see this sample STL use page.


Sample reference traces

There are sample reference traces available to help you debug your solution. Because one of the reference traces being made available is a large file (nearly 200 MB), it is not available on this web page. Instead, you will be able to find it in the following directory:

~sfkaplan/public/cs39

You can switch into this directory and read the files in it. Do not make copies of the files in this directory: The purpose of making this directory available, rather than posting its files on this page, is to avoid having needless multiple copies of large files on algol.

You will find three pairs of files in this directory. Within each pair, the file ending with the .rt suffix is the reference trace itself, and the file ending with the .refhist suffix is the reference histogram output from processing the reference trace. Thus, you can check the output of your solution against the output in the .refhist file. Here are descriptions of the pairs:

  1. Small sample: A small handful of references to four pages. You should easily be able to write out, with paper and pencil, how the LRU queue and reference histogram should change with each reference, and thus know what the final output will be.

  2. Truncated p2c: Taken from a real execution of the p2c program, this is the first 1,000 references from a larger reference trace. This represents a larger number of references, but no so many that you cannot find a specific reference and track the progress of your simulator.

  3. p2c: This is the full reference trace of the p2c program from which the above was taken. It's a much larger file (nearly 200 MB), and contains 34,135,250 references. It is likely to take your simulator a minute or two to process this trace. If your results from this trace are correct, it is likely that your code contains at worst very subtle errors.

Although you should not make copies of these files (particularly p2c.rt -- you may copy the others), you can use symbolic links. Specifically, if you are in your own directory for your simulator, you can do the following:

ln -s ~sfkaplan/public/cs39/p2c.rt .

You will have a file named p2c.rt in your own directory that serves as a pointer to the real file. You can then simply specify the link's name when running your simulator.


Code quality and evaluation

First, note that for this assignment you will be working individually. Later projects will be done in pairs, but not this one.

Second, not that this project and those that follow should be generously commented. Remember that you are communication not only with the machine, but with me and others who may view your code. Also know that I expect to be easily able to follow the structure and flow of your code. Choose a style and stick to it! Consistently name classes, methods, variables, etc. Be consistent with the use of vertical and horizontal space in the formatting of your code. Remember that there is an aesthetic aspect to code files, and it should be easy for an experienced programmer to scan a file and find what she seeks. Create your files accordingly.


Submitting your work

When your work is complete, you will be able to use (on algol.cs.amherst.edu) a special program to submit your work and to be sure that it was received. As an example of using this submission program, let us assume that you've created four files that are named Foo.hh, Foo.cc, Quux.hh, and Quux.cc. You would then submit them for this project like so:

(algol)> cs39-submit project-0 Foo.hh Foo.cc Quux.hh Quux.cc

Be sure to check the output of this program careful for error messages. If you want to be doubly sure that your submission was received, you can do the following:

(algol)> cs39-check-submission project-0

This program will indicate to you whether or not you have successfully submitted work for project-0. Note that if you submit more than once, the most recent submission will clobber any previous submissions. Thus, if you want to correct something about your work, be sure to submit your entire set of files each time.

This project is due on Thursday, September 11th at 11:59 pm!

Scott F. Kaplan
Last modified: Sat Sep 13 13:17:52 EDT 2003