A process, has been allocated page frames. Assume that none of the pages of the process are available in the memory initially. The process makes the following sequence of page references (reference string):
Least Recently Used (LRU) page replacement policy is a practical approximation to optimal page replacement. For the above reference string, how many more page faults occur with LRU than with the optimal page replacement policy?
View worked solution
Answer: C
To find the difference in page faults, we trace the page allocation for both policies with initially empty frames.
1. Optimal Page Replacement Policy:
Replaces the page that will not be used for the longest period in the future.
- 1 → [1, -, -] (Fault 1)
- 2 → [1, 2, -] (Fault 2)
- 1 → [1, 2, -] (Hit)
- 3 → [1, 2, 3] (Fault 3)
- 7 → [1, 7, 3] (Fault 4) — 2 is replaced as it is never used again
- 4 → [1, 4, 3] (Fault 5) — 7 is replaced
- 5 → [1, 5, 3] (Fault 6) — 4 is replaced
- 6 → [1, 6, 3] (Fault 7) — 5 is replaced
- 3 → [1, 6, 3] (Hit)
- 1 → [1, 6, 3] (Hit)
Total Optimal Page Faults = 7
2. Least Recently Used (LRU) Policy:
Replaces the page that has not been used for the longest period of time.
- 1 → [1, -, -] (Fault 1)
- 2 → [1, 2, -] (Fault 2)
- 1 → [1, 2, -] (Hit)
- 3 → [1, 2, 3] (Fault 3)
- 7 → [1, 7, 3] (Fault 4) — 2 is replaced
- 4 → [4, 7, 3] (Fault 5) — 1 is replaced
- 5 → [4, 7, 5] (Fault 6) — 3 is replaced
- 6 → [4, 6, 5] (Fault 7) — 7 is replaced
- 3 → [3, 6, 5] (Fault 8) — 4 is replaced
- 1 → [3, 6, 1] (Fault 9) — 5 is replaced
Total LRU Page Faults = 9
The number of extra page faults with LRU is .
Free practice · Your answers on this page are not saved.