ITPEC FE Subject A October 2025 Question 15

LRU Page Replacement — determine which page is evicted when memory is full.

Given: page capacity = 3, reference string = {1, 2, 3, 2, 1, 4, 5}, using LRU.

Step-by-step simulation:

• •1 → memory: [1]
• •2 → memory: [1, 2]
• •3 → memory: [1, 2, 3] — full
• •2 → hit → LRU order: 1, 3, 2
• •1 → hit → LRU order: 3, 2, 1
• •4 → miss → evict 3 (least recently used) → memory: {2, 1, 4}
• •5 → miss → evict 2 (least recently used) → memory: {1, 4, 5}

Answer: page 2 is replaced on the last reference.

Why not others:
- (a) 1 — was accessed at step 5, still recent
- (c) 3 — already evicted at step 6
- (d) 4 — loaded at step 6, most recent

Key rule: LRU evicts the page that has gone the longest without being accessed. Track recency by updating the "last used" timestamp on every access (including hits).

AI-generated — may contain errors