PROBLEM DESCRIPTION

Write a program to compare the performance of the LRU and FIFO page replacement algorithms. Test each of the algorithms for a range of resident set sizes. Use a pure demand fetch policy in which every page, including the first, is loaded as the result of a page fault. For each case keep track of the number of page faults generated and the page fault frequency, (number of page faults / total number of page references).

GENERAL REQUIREMENTS

Implement the algorithms using a linked FIFO queue representation. You can implement the linked list anyway you choose as long as it is a true FIFO queue .

For FIFO replacement the page at the head of the list represents the oldest page in memory, and the tail of the list is the newest page in memory. If a page reference causes a page fault the new page is linked to the tail of the list. If a page replacement is required (all frames are full; i.e., the length has reached the maximum length for this case) the page at the head of the list is removed. If a memory reference doesnt cause a page fault there is no change to the list.

For Least Recently Used (LRU) the page at the head of the list is always the least recently used page in memory, and the tail of the list is the most recently used. If a page reference causes a page fault the new page is linked to the tail of the list. If a page replacement is required (all frames are full) the page at the head of the list is removed. If a memory reference doesnt cause a page fault, update the list as follows:

search it for the referenced page

delete the page from its current place in the list

add the page to the tail of the list (its now the most recently used)

The virtual address space has a maximum of 16 pages, numbered 0 - 15. The physical address space or resident set size (RSS) will vary. If the resident set size = N, the maximum size of the page list will also be N. Run the program for RSS = 3, 5, 7 .

You can write two separate programs, one for each algorithm, or one program that includes both algorithms.

Write the program in C/C++

EVERY TIME YOU ADD A NEW PAGE TO THE LIST, COUNT IT AS A PAGE FAULT.

EXAMPLE: For a 4-page resident set and after the following string of page references

1, 1, 1, 1, 0, 3, 1, 1, 3, 5, 1, 8

FIFO List: Head 0 3 5 8 Tail

LRU List: Head 3 5 1 8 Tail

INPUT

Data Set 1: Use this set for initial testing

1, 1, 1, 1, 0, 3, 1, 1, 3, 5, 1, 8, 1, 3, 5, 13, 15, 6, 1, 1, 3, 6, 7, 8, 9, 3, 1, 1, 4, 4, 4, 1, 2

Data Set 2: I will give this to you at a later date .

OUTPUT - GENERAL

For each data set there will be two sets of output, one for FIFO and one for LRU. For each set of output there will be 3 individual cases, one for each resident set size.

Label your output as follows, and organize it order by cases:

Data Set 1: FIFO, RSS =5 (Two sets of output)

Data Set 1: LRU, RSS =3 (Two sets of output for each resident set size; 6 sets in all)

Data Set 1: LRU, RSS =5

Data Set 1: LRU, RSS =7

OUTPUT - SPECIFIC

For all 7 cases (as enumerated above) print the identifying information (Data Set 1, FIFO, resident set = 5; etc.), followed by the number of page faults, and page fault frequency.

In addition, if the resident set size =3 create a table with a line for each page fault that takes place in the first 25 page references. Information should include (1) the page that was faulted in, (2) the page that was faulted out (if any) and (3) a copy of the page list after the page fault has been processed. Do this for both algorithms. Make this table neat and easy to read. The table should have headings, for example: New Page Page Replaced Current Page List

Print a summary table for each data set based on the individual case data. There will be two of these. The table should look something like this: CASE 1: Resident # of Faults FIFO Page Fault # of Faults LRU Page Fault Set Size using FIFO Frequency using LRU Frequency If its easier, you can prepare this table in Word, using the output from step 1. The program must generate the actual values and output them directly and you must turn in the raw output.