CREATE OWN LIBRARY

GATE Question FIFO page replacement algorithm

GATE:2015:SET1:Q47

Consider the main memory with five page frames and the following sequence of page references: 3, 8, 2, 3, 9, 1, 6, 3, 8, 9, 3, 6, 2, 1, 3. which one of the following is true with respect to page replacement policies First-In-First-Out (FIFO) and Least Recently Used (LRU)?

(A) Both incur the same number of page faults
(B) FIFO incurs 2 more page faults than LRU
(C) LRU incurs 2 more page faults than FIFO
(D) FIFO incurs 1 more page faults than LRU

Solution:

They are asking page fault for FIFO and LRU.

You should know:

Least Recently Used (LRU) algorithm, GATE question on LRU, FIFO page replacement algorithm.

First we calculate page faults for FIFO:

Page References: 3, 8, 2, 3, 9, 1, 6, 3, 8, 9, 3, 6, 2, 1, 3. The number of frames in the main memory is 5.

So, the number of page faults = 9.

Note: For details about FIFO please follow: FIFO page replacement algorithm

Shortcut method:

But in examination it is not possible to solve it by this elaborative way we can do it by a single frame like below:

Page references: 3, 8, 2, 3, 9, 1, 6, 3, 8, 9, 3, 6, 2, 1, 3.

So, the number of page faults = 9.

Now we calculate page fault using LRU policy:

Before seeing the solution please follow previous chapters:

Least Recently Used (LRU) algorithm, GATE question on LRU

Page References: 3, 8, 2, 3, 9, 1, 6, 3, 8, 9, 3, 6, 2, 1, 3. The number of frames in the main memory is 5.

So, the number of page faults = 9.

Shortcut method:

But in examination it is not possible to solve it by this elaborative way we can do it by a single frame like below:

Page references:3, 8, 2, 3, 9, 1, 6, 3, 8, 9, 3, 6, 2, 1, 3.

So, the number of page faults = 9.

Final answer:

Number of page faults using FIFO policy = 9

Number of page faults using LRU policy =  9

So, option (A) is correct.