GATE 2022 CS Q.64: solution and answer

Official answer: 0.6Source: Official answer key, GATE 2022 CS (IIT Kharagpur)

1. There are 4 frames and $15$ references. Simulate LRU, evicting the page whose last use is oldest.

2. $$\begin{array}{cccc}\text{Ref}& \text{Result}& \text{Evicted}& \text{Frames after}\\ 7& \text{fault}& -& 7\\ 2& \text{fault}& -& 7,2\\ 7& \text{hit}& -& 7,2\\ 3& \text{fault}& -& 7,2,3\\ 2& \text{hit}& -& 7,2,3\\ 5& \text{fault}& -& 7,2,3,5\\ 3& \text{hit}& -& 7,2,3,5\end{array}$$

3. Reference 4 (position 8): the frames are full. Last uses are 7 at position 3, 2 at 5, 5 at 6 and 3 at 7, so 7 is least recently used. Fault, evict 7. Frames: 2,3,5,4.

4. Reference 6 (position 9): last uses are 2 at 5, 3 at 7, 5 at 6 and 4 at 8, so evict 2. Fault. Frames: 6,3,5,4.

5. Reference 7 (position 10): last uses are 3 at 7, 5 at 6, 4 at 8 and 6 at 9, so evict 5. Fault. Frames: 6,3,7,4. The next 7 (position 11) is a hit.

6. Reference 1 (position 12): last uses are 3 at 7, 4 at 8, 6 at 9 and 7 at 11, so evict 3. Fault. Frames: 6,1,7,4.

7. Reference 5 (position 13): last uses are 4 at 8, 6 at 9, 7 at 11 and 1 at 12, so evict 4. Fault. Frames: 6,1,7,5. The last two references, 6 and 1, are hits.

8. Faults occur on 7, 2, 3, 5, 4, 6, 7, 1, 5, which is $9$ faults in $15$ accesses.

9. $$\text{Page fault rate}=\frac{9}{15}=0.6$$