2.7k views

Consider a main memory with five-page frames and the following sequence of page references: $\text{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)?

1. Both incur the same number of page faults
2. FIFO incurs $2$ more page faults than LRU
3. LRU incurs $2$ more page faults than FIFO
4. FIFO incurs $1$ more page faults than LRU

edited | 2.7k views

Requested Page references are $3, 8, 2, 3, 9, 1, 6, 3, 8, 9, 3, 6, 2, 1, 3$ and number of page frames is $5$.

In FIFO Page replacement will take place  in sequence in pattern First In first Out, as following$$\small \begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline \textbf{Request} & \textbf{3} & \textbf{8} & \textbf{2} & \textbf{3} & \textbf{9} & \textbf{1} & \textbf{6} & \textbf{3} & \textbf{8} & \textbf{9} & \textbf{3} & \textbf{6} & \textbf{2} & \textbf{1} & \textbf{3} \\\hline \textbf{Frame 5} & \text{} & \text{} & \text{} & \text{} & \text{} & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\\hline \textbf{Frame 4} & \text{} & \text{} & \text{} & \text{} & 9 & 9 & 9 & 9 & 9 & 9 & 9 & 9 & 2 & 2 & 2\\\hline \textbf{Frame 3} & \text{} & \text{} & 2 & 2 & 2 & 2 & 2 & 2 & 8 & 8 & 8 & 8 & 8 & 8 & 8 \\\hline \textbf{Frame 2} & \text{} & 8 & 8 & 8 & 8 & 8 & 8 & 3 & 3 & 3 & 3 & 3 & 3 & 3 & 3 \\\hline \textbf{Frame 1} & 3 & 3 & 3 & 3 & 3 & 3 & 6 & 6 & 6 & 6 & 6 & 6 & 6 & 6 & 6 \\\hline \textbf{Miss/hit} & \text{F} & \text{F} & \text{F} & \text{H} & \text{F} & \text{F}&\text{F}& \text{F}& \text{F} & \text{H}& \text{H}& \text{H} & \text{F} & \text{H} & \text{H} \\\hline \end{array}$$Number of Faults $= 9.$ Number of Hits $= 6$

Using Least Recently Used (LRU) page replacement will be the page which is visited least recently (which is not used for the longest time), as following:$$\small \begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline \textbf{Request} & \textbf{3} & \textbf{8} & \textbf{2} & \textbf{3} & \textbf{9} & \textbf{1} & \textbf{6} & \textbf{3} & \textbf{8} & \textbf{9} & \textbf{3} & \textbf{6} & \textbf{2} & \textbf{1} & \textbf{3} \\\hline \textbf{Frame 5} & \text{} & \text{} & \text{} & \text{} & \text{} & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 2 & 2 & 2 \\\hline \textbf{Frame 4} & \text{} & \text{} & \text{} & \text{} & 9 & 9 & 9 & 9 & 9 & 9 & 9 & 9 & 9 & 9 & 9 \\\hline \textbf{Frame 3} & \text{} & \text{} & 2 & 2 & 2 & 2 & 2 & 2 & 8 & 8 & 8 & 8 & 8 & 1 & 1 \\\hline \textbf{Frame 2} & \text{} & 8 & 8 & 8 & 8 & 8 & 6 & 6 & 6 & 6 & 6 & 6 & 6 & 6 & 6 \\\hline \textbf{Frame 1} & 3 & 3 & 3 & 3 & 3 & 3 & 3 & 3 & 3 & 3 & 3 & 3 & 3 & 3 & 3 \\\hline \textbf{Miss/hit} & \text{F} & \text{F} & \text{F} & \text{H} & \text{F} & \text{F}&\text{F}& \text{H}& \text{F} & \text{H}& \text{H}& \text{H} & \text{F} & \text{F} & \text{H} \\\hline \end{array}$$Number of Faults $= 9.$ Number of Hits $= 6$

So, both incur the same number of page faults.

Correct Answer: $A$
by Active (1.8k points)
edited
+1
There is a minor mistake in fifo calculation ... i guess ...
+1

There is a mistake in FIFO page fault sequence ,  although answer will be same(9 page faults), correct sequence will be like below, as Arjun Sir mentioned in his answer

 F F F H F F F F F H H H F H H

FIFO:

3 -3 :1 page fault
8 -3 8 :2 page faults
2 -3 8 2 :3 page faults
3 -3 8 2 :3 page faults
9 -3 8 2 9 :4 page faults
1 -3 8 2 9 1 :5 page faults
6 -8 2 9 1 6 :6 page faults
3 -2 9 1 6 3 :7 page faults
8 -9 1 6 3 8 :8 page faults
9 -9 1 6 3 8 :8 page faults
3 -9 1 6 3 8 :8 page faults
6 -9 1 6 3 8 :8 page faults
2 -1 6 3 8 2 :9 page faults
1 -1 6 3 8 2 :9 page faults
3 -1 6 3 8 2 :9 page faults

LRU:

3 -3 :1 page fault
8 -3 8 :2 page faults
2 -3 8 2 :3 page faults
3 -8 2 3 :3 page faults
9 -8 2 3 9 :4 page faults
1 -8 2 3 9 1 :5 page faults
6 -2 3 9 1 6 :6 page faults
3 -2 9 1 6 3 :6 page faults
8 -9 1 6 3 8 :7 page faults
9 -1 6 3 8 9 :7 page faults
3 -1 6 8 9 3 :7 page faults
6 -1 8 9 3 6 :7 page faults
2 -8 9 3 6 2 :8 page faults
1 -9 3 6 2 1 :9 page faults
3 -9 6 2 1 3 :9 page faults

So, option A.

by Veteran (430k points)