What is number of page faults by least recently used page replacement for a…

Concept

LRU (Least Recently Used) replacement: on a page reference, if the page is already resident it is a hit; otherwise it is a page fault. When all frames are full and a fault occurs, the page that was used farthest back in time (the least recently used) is evicted to make room. The key discipline is to track the recency of each resident page, because that alone decides who is evicted — and an eviction can force a later re-reference of that same page to fault again.

Application — trace with 4 frames

Reference string = 2, 0, 1, 2, 4, 0, 5, 1, 4, 6, 4, 2, 1, 3, 0 (frames = 4). The bracket shows the resident set after each access.

1. 2: [2] → Fault (1)

2. 0: [2, 0] → Fault (2)

3. 1: [2, 0, 1] → Fault (3)

4. 2: [2, 0, 1] → Hit

5. 4: [2, 0, 1, 4] → Fault (4)

6. 0: [2, 0, 1, 4] → Hit

7. 5: [2, 0, 4, 5] — evict 1 (least recently used) → Fault (5)

8. 1: [0, 4, 5, 1] — evict 2 (least recently used) → Fault (6)

9. 4: [0, 4, 5, 1] → Hit

10. 6: [4, 5, 1, 6] — evict 0 → Fault (7)

11. 4: [4, 5, 1, 6] → Hit

12. 2: [4, 1, 6, 2] — evict 5 → Fault (8)

13. 1: [4, 1, 6, 2] → Hit

14. 3: [4, 1, 2, 3] — evict 6 → Fault (9)

15. 0: [1, 2, 3, 0] — evict 4 → Fault (10)

Why the count is 10, not 9: at the access to 5, the four resident pages are {2, 0, 1, 4} and their last-use times make 1 the least recently used, so 1 is evicted. The very next access is to 1, which is therefore no longer resident — it faults. Evicting any other page here (for example 2, which was used more recently) would be an LRU violation and is the usual source of the undercount.

Cross-check

Counting the fault markers above: faults occur at references 2, 0, 1, 4, 5, 1, 6, 2, 3, 0 — ten of the fifteen accesses miss, leaving five hits (at 2, 0, 4, 4, 1). Total page faults = 10.