Calculate the page fault for a given string with the help of LRU & FIFO page replacement algorithm, Size of frames = 4 and string 1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 1 2 3 6

The reference string has 20 page numbers and there are 4 frames. A page fault happens when the needed page is not in any frame.

FIFO removes the page that has been in memory the longest. The frames below are listed from the oldest to the newest page.

LRU removes the page that was used least recently. The frames below are listed from the least recently used to the most recently used.

Counting the faults in each column gives

$$\text{FIFO faults} = 14, \qquad \text{LRU faults} = 10$$

The first four faults in both are compulsory, because the frames are empty at the start. FIFO has 6 hits, so its hit ratio is $6/20 = 0.30$. LRU has 10 hits, so its hit ratio is $10/20 = 0.50$.

Therefore, with 4 frames, FIFO gives 14 page faults and LRU gives 10 page faults. LRU does better here because it keeps the pages 1, 2 and 3, which are used again and again. FIFO throws out a page just because it is old, even when it is still in use. For example, FIFO removes page 2 and page 1 early, and has to fetch them again.

LRU needs extra hardware or counters to track the last use, while FIFO needs only a simple queue. LRU is also free from Belady's anomaly, where more frames can give more faults under FIFO.

A larger number of frames normally lowers the page faults, so with 4 frames both algorithms do better than they would with 3 frames on the same string.