Consider that a process has been allocated 3 frames and has a sequence of page…
2019
Consider that a process has been allocated 3 frames and has a sequence of page referencing as 1,2,1,3,7,4,5,6,3,1.
What shall be the difference in page faults for the above string using the algorithms of LRU and optimal page replacement for referencing the string?
- A.
2
- B.
0
- C.
1
- D.
3
Attempted by 15 students.
Show answer & explanation
Correct answer: A
Reference string: 1, 2, 1, 3, 7, 4, 5, 6, 3, 1
LRU (3 frames):
Access 1 → frames = [1] (page fault, total faults = 1)
Access 2 → frames = [1, 2] (page fault, total faults = 2)
Access 1 → frames = [1, 2] (hit, total faults = 2)
Access 3 → frames = [1, 2, 3] (page fault, total faults = 3)
Access 7 → frames = [1, 3, 7] (evict 2 as it is least recently used) (page fault, total faults = 4)
Access 4 → frames = [3, 7, 4] (evict 1) (page fault, total faults = 5)
Access 5 → frames = [7, 4, 5] (evict 3) (page fault, total faults = 6)
Access 6 → frames = [4, 5, 6] (evict 7) (page fault, total faults = 7)
Access 3 → frames = [3, 5, 6] (evict 4) (page fault, total faults = 8)
Access 1 → frames = [3, 1, 6] (evict 5) (page fault, total faults = 9)
Total page faults using LRU = 9.
Optimal (3 frames):
Access 1 → frames = [1] (page fault, total faults = 1)
Access 2 → frames = [1, 2] (page fault, total faults = 2)
Access 1 → frames = [1, 2] (hit, total faults = 2)
Access 3 → frames = [1, 2, 3] (page fault, total faults = 3)
Access 7 → frames = [1, 3, 7] (evict 2 because it is not used again) (page fault, total faults = 4)
Access 4 → frames = [1, 3, 4] (evict 7 because it is not used again) (page fault, total faults = 5)
Access 5 → frames = [1, 3, 5] (evict 4) (page fault, total faults = 6)
Access 6 → frames = [1, 3, 6] (evict 5) (page fault, total faults = 7)
Access 3 → frames = [1, 3, 6] (hit, total faults = 7)
Access 1 → frames = [1, 3, 6] (hit, total faults = 7)
Total page faults using Optimal = 7.
Difference (LRU − Optimal) = 9 − 7 = 2.
Therefore the correct answer is 2.
A video solution is available for this question — log in and enroll to watch it.