The Gateway to Computer Science Excellence
+21 votes
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
in Operating System by Boss (30.7k points)
edited by | 2.7k views

2 Answers

+27 votes
Best answer
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 by
+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
+9 votes

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)
Answer:

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,741 questions
57,252 answers
198,061 comments
104,698 users