GATE CS 2012 Q42 — Memory Management and Virtual Memory

We are given the page reference string: 1, 2, 3, 2, 4, 1, 3, 2, 4, 1 with $3$ initially empty page frames.

1. OPTIMAL Page Replacement
Replaces the page that will not be used for the longest period of time in the future.

• 1 → [1] (Fault)
• 2 → [1, 2] (Fault)
• 3 → [1, 2, 3] (Fault)
• 2 → [1, 2, 3] (Hit)
• 4 → [1, 4, 3] (Fault) — 2 is replaced as its next reference is furthest
• 1 → [1, 4, 3] (Hit)
• 3 → [1, 4, 3] (Hit)
• 2 → [1, 4, 2] (Fault) — 3 is replaced as it is not used again
• 4 → [1, 4, 2] (Hit)
• 1 → [1, 4, 2] (Hit)

Total $\text{OPTIMAL}$ faults = $5$

2. FIFO Page Replacement
Replaces the oldest page in the memory.

• 1, 2, 3 → [1, 2, 3] (3 Faults)
• 2 → [1, 2, 3] (Hit)
• 4 → [4, 2, 3] (Fault) — 1 replaced
• 1 → [4, 1, 3] (Fault) — 2 replaced
• 3 → [4, 1, 3] (Hit)
• 2 → [4, 1, 2] (Fault) — 3 replaced
• 4, 1 → [4, 1, 2] (2 Hits)

Total $\text{FIFO}$ faults = $6$

3. LRU Page Replacement
Replaces the page that has not been used for the longest period of time.

• 1, 2, 3 → [1, 2, 3] (3 Faults)
• 2 → [1, 3, 2] (Hit)
• 4 → [4, 3, 2] (Fault) — 1 replaced
• 1 → [4, 1, 2] (Fault) — 3 replaced
• 3 → [4, 1, 3] (Fault) — 2 replaced
• 2 → [2, 1, 3] (Fault) — 4 replaced
• 4 → [2, 4, 3] (Fault) — 1 replaced
• 1 → [2, 4, 1] (Fault) — 3 replaced

Total $\text{LRU}$ faults = $9$

Comparing the page faults: $5 < 6 < 9$, which gives $\text{OPTIMAL} < \text{FIFO} < \text{LRU}$.