GATE CSE 2015 | Set 1 | Question: 47

Question

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)?

• 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

Comments

Level : Easy 

---

calculating PAGE HISTS  & using QUEUE in fifo might save time in exam

---

i mistakenly did it for 3 frames
and still same answer
why so?

---

@Kshitij Sharma bro your LRU implimentation is wrong, 6 got replaced with 8 not with 3, you almost simulate FIFO implementation in LRU.

Answer 1

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$

Comments

There is a minor mistake in fifo calculation ... i guess ...

---

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

Answer 2

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.