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:

• Input: A reference trace, which is a file that contains a log of the memory addresses referenced by an executing program.
• Processing: For each memory address in the reference trace, some leading number of bits are taken as the page number. An LRU queue of page numbers should be maintained. Specifically, when a particular page number is read from the reference trace, the simulator should attempt to find that page number in the queue.

  If that page number is found in the queue, the simulator should note the position number in the queue at which it was found. Specifically, the simulator should keep a reference histogram, where each entry in the histogram should indicate the number of times a page number was found in the corresponding position in the LRU queue. Thus, upon finding a page number in the LRU queue, the corresponding histogram entry should be incremented, and that page number should be moved to the front of the LRU queue.

  If the desired page number is not found in the LRU queue, then no change should be applied to the histogram, and the page number should simply be inserted at the front of the queue.

• Output: After processing the entire reference trace, the simulator should emit the reference histogram.

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:

• The reference trace should be read from standard input (stdin). I recommend using the scanf() function.
• Remember that the reference trace will contain full addresses. Thus, each referenced address can be divided in a page number (upper bits) and an offset into that page (lower bits). For this assignment, assume that the 20 upper bits are the page number, and the 12 lower bits are the offset. It is the responsibility of the simulator to use bit shifting or masking operations to isolate the page number.
• The reference histogram should similarly be emitted to standard output (stdout). Again, I recommend the use of the printf() function.
• The reference histogram should be stored either as an array of unsigned int or as an STL vector of unsigned int.
• The reference histogram should be capable of dynamically resizing itself if a particular reference pattern causes the LRU queue size to exceed the reference histogram size at any moment.
• Note the change!: The emitted reference histogram should list only those entries with non-zero values.
• The emitted reference histogram should take the following form:

  1 513
  2 373
  3 77
  ...

  That is, the first column contains histogram position numbers, and the second column contains the actual number of reference to that position. Values should be emitted as text and in decimal, and a space should separate the fields on each line.

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.