Determine the number of page faults when references to pages occur in order -…

Concept: LRU Page Replacement

The Least Recently Used (LRU) policy evicts the resident page whose last reference is furthest in the past, on the assumption that a page unused for the longest interval is least likely to be needed again soon. Every reference to a page resets its recency to “most recently used”; when a requested page is absent and every frame is occupied, the page carrying the oldest last-use time is the one discarded. This differs from FIFO, which evicts strictly by arrival order and ignores how recently a resident page was actually re-used.

Application: Initial Conditions

• Main memory capacity: 3 frames.

• Initial state: memory already holds {1, 2}.

• Recency order: page 1 was brought in earlier than page 2, so 1 is currently the least-recently-used of the two and 2 is the most-recently-used.

Step-by-Step Trace

Reference string: 1, 2, 4, 5, 2, 1, 2, 4.

1. Ref 1: already resident → Hit. Recency updates to [2, 1] (2 older, 1 newer). Faults so far: 0.

2. Ref 2: already resident → Hit. Recency updates to [1, 2] (1 older, 2 newer). Faults so far: 0.

3. Ref 4: not resident, a frame is still free → Fault (compulsory miss). Memory becomes [1, 2, 4], recency order 1 < 2 < 4. Faults so far: 1.

4. Ref 5: not resident, memory full; least-recently-used page is 1 → Fault, evict 1, load 5. Memory becomes [5, 2, 4], recency order 2 < 4 < 5. Faults so far: 2.

5. Ref 2: already resident → Hit. Recency updates to order 4 < 5 < 2. Faults so far: 2.

6. Ref 1: not resident (it was evicted earlier), memory full; least-recently-used page is 4 → Fault, evict 4, load 1. Memory becomes [5, 1, 2], recency order 5 < 2 < 1. Faults so far: 3.

7. Ref 2: already resident → Hit. Recency updates to order 5 < 1 < 2. Faults so far: 3.

8. Ref 4: not resident (it was evicted earlier), memory full; least-recently-used page is 5 → Fault, evict 5, load 4. Memory becomes [4, 1, 2], recency order 1 < 2 < 4. Faults so far: 4.

Cross-Check

• The reference string has 8 entries. Counting independently: hits occur at positions 1, 2, 5 and 7 (4 hits); faults occur at positions 3, 4, 6 and 8 (4 faults). 4 hits + 4 faults = 8, matching the length of the string, so no reference was skipped or double-counted.

• Every fault is justified by the LRU rule at that step — the two later faults each evict the page with the oldest last-use time at that point (4 and then 5, not any of the frequently-revisited page 2), consistent with the concept stated above.

Final Result

The total number of page faults for the given sequence, under LRU with 3 frames, is 4.