Project 2

Due: Last Day Of Class

Simulation - Page Replacement Algorithms

Write a simulation to calculate number of page faults under various page replacement algorithms and conditions.

Different Algorithms to use: FIFO (First In First Out), LRU (Least Recently Used), MFU (Most Frequently Used).

Each page is 4 bytes.

You will calculate number of page faults for:

Code Segment 1:

byte memory[256][256];
int i,j;
for(i=0;i<256;i++){
    for(j=0;j<256;j++){
        memory[i][j] = i * j;
    }
}

And Code Segment 2:

byte memory[256][256];
int i,j;
for(i=0;i<256;i++){
    for(j=0;j<256;j++){
        memory[j][i] = i * j;
    }
}

You are not allowed to modify or optimize the loops (they have to be as they are; accessing that memory location).

Run the simulation for the above algorithms (FIFO, LRU, MFU) with both code segments provided, for physical memory sizes: 1024 bytes, 4096 bytes, 16384 bytes, 32768 bytes, and 65536 bytes.

In the end, you should have a total of 30 simulations (3 algorithms * 5 memory sizes * 2 code fragments).

(note that you only need to write 1 simulation; just make sure you can run it with 30 different setups; parameters)

You should present the output in a clear fashion, with 30 lines with name of method/setup etc., and number of page faults for that setup.

What to submit:

Submit ALL source code with detailed instructions on how and where to compile it, and how to make it run. I will test some of the code to make sure the numbers are not imagined. (note that this time, everyone in class should get identical output---so I should get 40 different programs that produce identical output).

Submit traces of execution (the trace of execution of each algorithm; each algorithm in separate files, etc.). e.g. printing out the steps of what your program is doing.

Submit a document illustrating the project output (30 various methods/setups and their page fault counts).

Submit a 1-2 page paper describing the project and any problems/comments/ideas etc.

Submit a file named: description.txt that describes what and where all the information is stored. (which file does what, which file contains results of which algorithm, etc.)

As before, organize and design the project and know what you're doing before you start coding. (and don't wait until the last weekend to do it!).

Good Luck!

© 2006, Particle