CSC 420 Programming Assignment #2

Description

Write a C++ program that simulates the operation of 3 page replacement algorithms used in a virtual memory management system:

• First In First Out (FIFO) algorithm
• Least Recently Used (LRU) algorithm
• Optimal algorithm

You will simulate each algorithm on the input data sets and report the performance of each. A description of each of these algorithms appears in Chapter 10 of our text.

Input

Your program must take two arguments:

prog02 <data_file> <num_frames>

These arguments are:

• <data_file> - a file containing the input reference string for the simulation (further defined below)
• <num_frames> - the number of frames to use for the simulation

Program arguments can either be specified at the command line, or preferably input by the user after the program starts running.

Each data file will contain one reference string. The reference string represents an ordered list of page references. So, for example, the string:

4 5 4 6

means that page #4 is referenced, then page #5, then page #4 again, then finally page #6.

Output

First, echo the input for this simulation, including the data file name, reference string, and frame number.

Then, for each data set, you should output the following for each of the three algorithms:

Each field means:

• Algorithm: - either FIFO, LRU, or Optimal
• Page faults: - report the number of page faults using this data set and algorithm
• Page Table: - report contents of the page table (page and their assigned frame) at the end of the simulation. Obviously, this will only be done for pages that have frames at the end of the simulation.

Simulation

Some simulation pointers:

• See page 321, 322 in our textbook for an overview of page replacement and also for implementation ideas.
• Please assume that page numbers have 8 bit addresses. This means that the page table will be 2⁸, or 256, entries long.
• Your program should be able to handle a "bad" page reference in the reference string. A "bad" page reference is one that exceeds the size of virtual memory. What to do? Just report the offending page number and die, er, ah, exit gracefully.
• Initially, the page table is empty, so the first reference to any page will cause a page fault.
• Please allocate frames starting with the lowest frame number first (so, we have similar results). Oh, frame and page numbers start at 0.

You will be expected to run your program on a set of data files of this format. These files will be located in the CSC 420 k: drive common folder:

k:/02SP/CSC420/Common Area/prog02/data/

Deliverables and Schedule

Program #2 is worth 50 points, or 5% of your class grade.

Please place your source code, executable, and output data in a folder called prog02 on your k: drive.

Design Phase [10 points]

Your design of Program #2 is due Thurs May 9. This is just like program #1, so please hand-in:

1. C++ header files defining the public interface for each "important" class, including comments describing each class and public method.
2. Pseudo-code describing your program's execution flow; this is probably your main() function.
3. Your main.cpp file should include all the headers that you have defined, and it should successfully compile.

Also,  please print your headers and pseudo-code for grading/review.

Program Finale [40 points]

Program #2 is due Thursday May 16.

Deliverables include:

1. Source code - commented and beautiful, of course
2. Executable  - I must be able to run your program and get your results
3. Output files - for each data set
4. A README file - for organization notes or things I need to know when reviewing your program

Grading will be similar to Program #1:

• Correctly running the first data set for each algorithm (20 points)
• Correctly running the second data set for each algorithm (5 points)
• The overall quality of your solution including: clean readable code including comments,  clear organization, and object-oriented design practices (10 points)

I am less interested in:

• Efficiency - I won't be grading how fast or efficient your simulation is
• Error handling - Don't worry about trapping all kinds of bad data; just run on the datasets given
• I/O - I don't care how elegantly you handle program parameters and don't bother gussying-up the output

Notes

The first data set is page335.txt and can be found on the k: drive. It's also here:

page335.txt

I'll publish the other data sets next week.

My implementaion probably includes the following classes:

• VMSimulator - the guy who runs the simulation... using the PageTable and FrameList classes to properly implement virtual memory.
• PageTable - the page table... you can probably implement this as an array since the number of possible pages never changes.
• FrameList - the list of free frames... you can do this either as a list or an array where frames are marked used or free.

My solution will probably use the list and queue data types from the STL. For STL examples, try the "Help" menu in Visual C++ and search for STL. Also, you can spot my usage of STL components queue, list and iterator in my implementation of program #1 on the k: drive.

I would tackle the FIFO algorithm first, then LRU, then Optimal. Optimal is probably the hardest because you have to use the whole reference string to determine which page is replaced.

May 9, 2002

OK, please run the following simulations:

• Run data set page335.txt with 4 frames
• Run data set err1.txt with 8 frames
• Run data set big1.txt with 8 frames

The data set files are available in the Common Area/prog02/data folder.

I would like to add one more requirement to your output file for each simulation run. For each page reference write an abbreviated version of the page table, showing the (page, frame) for each page currently in memory. For example, it may look something like this:

Page table (page,frame): (0,1) (1,2) (2,3) (7,0)

I request that you do this, 1) to force you to create a way to debug and verify your results, and 2) make it easier for me to understand incorrect results.