CSE 120 Spring 2002 Project 3
Due 7 June 2002

Overview

In this project, you will compare the efficacy of six different page replacement schemes.

The directory /ieng9/solaris/ieng9/cs120e/p3/ contains code and data that you will need for this project.

The p3 directory contains the file refs.rs that holds a reference string generated from an execution of gcc. Only the first 11,695,204 references were recorded. There are 355 distinct pages referenced in this string. We have renumbered the pages so that they are dense (that is, their values range from 0 to 354). Doing so makes it easier for you to design your data structures, but it removes information that could be used to analyze the benefit of prefetching. Since we are not considering prefetching in this exercise, the renumbering does not pose any problems.

The file consists of 3,000,000 records with the following format:
 

struct record {
    short page;
    short refs;
    long next;
};


Such a record indicates that the next refs references are to page, and page is subsequently referenced in record number next. If next equals -1 then page is not subsequently referenced in the reference string.

For example, consider the following reference string:
 

0 0 1 1 1 0 0 2 2 0 0 3 3 3 2 0 0 0


It would be represented by the following eight records:
 

{ 0, 2, 2 }    two references of page 0. page 0 next appears in record 2
{ 1, 3, -1 }   three references of page 1. page 1 doesn't appear again
{ 0, 2, 4 }    two references of page 0. page 0 appears again in record 4
{ 2, 2, 6 }    two references of page 2. page 2 appears again in record 6
{ 0, 2, 7 }    two references of page 0. page 0 appears again in record 7
{ 3, 3, -1 }   three references of page 3. page 3 doesn't appear again
{ 2, 1, -1 }   one reference of page 2. page 2 doesn't appear again
{ 0, 3, -1}    three references of page 0. page 0 doesn't appear again


The file refs.rs is formatted in binary. We've provided some routines that will help you enumerate the records of the file. Again in the p3 directory, take a look at getrefs.h. The source and compiled object file (using gcc) are available in the same directory.

Finally, p3 has the program rsdump that allows you to dump a segment of a reference string file. This program takes three parameters: the name of the file, the starting record number to dump, and the number of records to dump. If you run rsdump with no parameters it will print out a minimally helpful message that will remind you of the parameters it requires. Warning!! If you try to dump the entire file without piping the output through more, then you will be unhappy.

The source rsdump.c of rsdump is in p3. It uses getrefs.h, and so you might use rsdump.c as a prototype of your own programs.

You may find it useful to create a link to the following two files in the directory in which you are working, e.g.,
 

ln /ieng9/solaris/ieng9/cs120e/p3/refs.rs .
ln /ieng9/solaris/ieng9/cs120e/p3/rsdump .


You might instead wish to copy over the other files, e.g.
 

cp /ieng9/solaris/ieng9/cs120e/p3/getrefs.* .

The Experiments

You will be performing four different experiments, detailed below.

Part 1: The working set of the reference string

Plot the size of the working set as a function of reference time. You will need to choose an appropriate window size t. Describe how you choose t and why you think that it is appropriate.

Note that if you aren't careful, you will generate a lot of data. Recall that the reference string contains over eleven million references. You don't want to generate a file that contains over ll million lines. You might only produce the points at which the value of the working set changes, and you may want to start by examining only a prefix of the string.

Part 2: The performance of LRU, and OPT.

Plot the miss ratio as a function of the number of page frames for the LRU and Optimal demand page replacement policies. Vary the number of page frames from 1 to 355. Verify the endpoints of these curves from the information above describing the reference string (11,695,204 references, 3,000,000 records and 355 distinct pages referenced).

Use the stack algorthm technique described in lecture and in the web notes to generate the data for these curves. By doing so, you should be able to generate the graph for each policy with only one pass through the reference string.

Part 3: The performance of FIFO, RAND, LIFO and CLOCK.

Plot the miss ratios as a function of the number of page frames for the four demand page replacement strategies given above. For random, choose a page with uniform probabilty to discard when a page needs to be replaced (don't worry about running multiple experiments to obtain a distribution). You won't be able to use the stack algorithm approach that you used for Part 2, and so you will need to consider each value of the number of page frames separately. You may not wish to run all 355 simulations, and so choose the points for which you do measure the miss ratio with some care.

For extra credit, design, argue the correctness of, and use a one-pass algorithm for computing the miss ratios for LIFO for all 355 possible page frame sizes.

Producing Graphs

You can use the program gnuplot to produce your graphs. In p3 is an of using gnuplot. The file graph.gnu assumes that you have a file called ws.gnu containing points to be plotted plot. A point is just a line in the file, with first the x coordinate and then the y coordinate. For example, if ws.gnu contains

    1    1.0
    2    2.0
    3    3.0
    4    4.0

then the graph would be the straight line going through (1, 1) and (4, 4).

You will want to have a separate graph file for each graph you create, such as fifo.gnu and opt.gnu. You'll need to change your version of graph.gnu appropriately.

Lines in graph.gnu starting with # are comments. Note that graph.gnu contains the two lines

    set logscale y
  show logscale

which you will want to use for your graphs of miss ratios. These lines produce a graph with the y scale logarithmic rather than linear. For the working set graph, however, you will want to comment these lines out.

You use gnuplot in the standard Unix manner, e.g. gnuplot graph.gnu. To find out more about gnuplot, just type the command gnuplot, and then type help.

Turning In

You should hand in: These files should be encoded as a uuencoded compressed tar file and submitted using the turnin command by 11:59 PM PST on 7 June 2002.

last edited 28 May 2002 by kam