Assignment 5

Note: You must complete this assignment alone. The assignment is due 2:40pm, Friday, November 9. You will submit a written report for this assignment.

Objectives

Problem

In this assignment, you will implement the LRU paging policy and run a simulation on prerecorded access traces to see how changing the number of page frames affects the frequency of page faults the process encounters. Our traces come from research by two University of Wisconsin PhD students.

http://www.cs.wisc.edu/~plakal/javatraces/overview.html
To generate these traces, the researchers modified the JVM to record each memory access and then ran traces on a selection of programs.

I have downloaded and simplified four of these traces for your simulations. The following table lists the names of the four files, the number of distinct pages accessed, and the total number of memory accesses.

trace pages # accesses
javac 94 8,411,453
linpack 186 7,144,147
wordfreq 638 11,657,125
javacc 830 17,323,761
You can get these traces from the directory
/usr/people/classes/writeups/LabStuff/350/traces
(Do not attempt to copy these files into your directory. Each file is many megabytes large.)

Each file contains a number on each line, representing the page of a memory access. All page numbers are between 1 and 1000. (The traces have fewer lines than the number of accesses in the trace, because adjacent accesses to the same page have been removed to save space and time. Such duplicate references do not affect the number of faults incurred by the program.)

Write a program that reads in a trace and counts how many page faults the LRU algorithm would encounter. (I'd have the number of page frames in memory as a command-line argument.) Hand in this program using handincs 350 5.

It's not important that your program service page faults efficiently. In my solution, the page table was an array of integers, each representing the line number in which the page was last accessed (or $-1$ if the page would not be in memory). Then, when a page fault occurred, I went through the entire table to find which page to eject from the cache. My program was just 38 lines long.

For your written report, include the following for each of two traces. (You are assigned traces as follows: If your last name falls before Grinch, you get javac and wordfreq. Otherwise, you get linpack and javacc.)