edited by
18,910 views
25 votes
25 votes

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 by

2 Answers

Best answer
35 votes
35 votes
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$
edited by
14 votes
14 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. 

Answer:

Related questions

48 votes
48 votes
6 answers
4
makhdoom ghaya asked Feb 12, 2015
12,167 views
The following two functions $P1$ and $P2$ that share a variable $B$ with an initial value of $2$ execute concurrently.$$\begin{array}{|l|l|}\hline \text{P1() \{ } & \tex...