Page Replacement Algorithms

Write a C program that implements the FIFO LRU, and optimal (OPT) page-replacement algorithms. Have your program initially generate a random page-reference string (of length 100) where page numbers range from 0 to 9. Apply the generated random page-reference string to each algorithm and record the number of page faults incurred. Pass the number of frames and the seed used to generate the page reference string, to the program at startup.

Use the following reference string for testing purpose. 2 8 7 2 0 3 1 7 3 1 9 3 6 1 8 4 5 1 8 8 3 4 4 3 4 2 0 6 6 7 0 1 0 9 3 6 4 6 8 0 4 6 2 3 5 7 8 0 3 2 0 0 0 4 6 9 1 4 3 8 8 0 0 9 7 0 7 0 9 7 7 3 8 8 9 2 7 2 1 2 0 9 1 1 1 5 0 7 1 4 9 1 9 5 8 4 4 7 9 6 -

If the test string is used, only one argument is provided (number of frames).

We have the output:

./a.out 5

Algorithm # Page faults

FIFO 52

LRU 50

OPT 32

- Otherwise, the program takes two arguments: number of frames and the seed. An example of use would be:

./a.out 5 1234 // with 5 frames, seed = 1234

Algorithm #Page faults

FIFO 49

LRU 48

OPT 33