Page Replacement Algorithms

Overview

Previous topic introduced page replacement concepts. This topic provides detailed algorithm walkthroughs, performance analysis, and comparative studies.

FIFO (First In First Out)

Algorithm Details

Data Structure:
Queue of pages (ordered by load time)

On Page Fault:
1. Check if page already loaded (hit)
2. If not loaded (miss):
   a. If free frame available: Load page
   b. If no free frame: Remove queue head, load new page
3. Add new page to queue tail

Detailed Example

Memory: 3 frames (initially empty)

Reference String: 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2

Frame: │  1  │  2  │  3  │
Queue: │     │     │     │

Ref 7:
Frames: [7, _, _]
Fault! (load 7)

Ref 0:
Frames: [7, 0, _]
Fault! (load 0)

Ref 1:
Frames: [7, 0, 1]
Fault! (load 1)

Ref 2:
Queue head = 7, remove and replace
Frames: [0, 1, 2]
Fault! (load 2)

Ref 0:
Already in memory
Hit!
Frames: [0, 1, 2]

Ref 3:
Queue head = 0, remove and replace
Frames: [1, 2, 3]
Fault! (load 3)

Ref 0:
Not in memory (evicted)
Frames: [2, 3, 0]
Fault! (load 0)

Ref 4:
Queue head = 1, remove and replace
Frames: [3, 0, 4]
Fault! (load 4)

Ref 2:
Not in memory
Frames: [0, 4, 2]
Fault! (load 2)

Ref 3:
Already in memory
Hit!

Ref 0:
Already in memory
Hit!

Ref 3:
Already in memory
Hit!

Ref 2:
Already in memory
Hit!

Total Faults: 9 out of 13 references
Fault Rate: 69%

Characteristics

LRU (Least Recently Used)

Algorithm Details

Concept: Replace page not used for longest time

Track: Access timestamp for each page

On Page Fault:
1. Check page already loaded (hit)
2. If not loaded (miss):
   a. Find page with minimum timestamp (oldest)
   b. Remove that page
   c. Load new page
   d. Set timestamp = current_time

Detailed Example

Reference String: 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2

Frames (with timestamp): 3 frames total

Time 1, Ref 7:
Frames: [7(1)]
Fault! Load 7

Time 2, Ref 0:
Frames: [7(1), 0(2)]
Fault! Load 0

Time 3, Ref 1:
Frames: [7(1), 0(2), 1(3)]
Fault! Load 1

Time 4, Ref 2:
Find oldest: 7(1)
Remove 7, add 2
Frames: [0(2), 1(3), 2(4)]
Fault! Load 2

Time 5, Ref 0:
Already in memory
Update timestamp: 0(5)
Frames: [1(3), 2(4), 0(5)]
Hit!

Time 6, Ref 3:
Find oldest: 1(3)
Remove 1, add 3
Frames: [2(4), 0(5), 3(6)]
Fault! Load 3

Time 7, Ref 0:
Already in memory
Update: 0(7)
Frames: [2(4), 3(6), 0(7)]
Hit!

Time 8, Ref 4:
Find oldest: 2(4)
Remove 2, add 4
Frames: [3(6), 0(7), 4(8)]
Fault! Load 4

Time 9, Ref 2:
Not in memory
Find oldest: 3(6)
Remove 3, add 2
Frames: [0(7), 4(8), 2(9)]
Fault! Load 2

Time 10, Ref 3:
Not in memory
Find oldest: 0(7)
Remove 0, add 3
Frames: [4(8), 2(9), 3(10)]
Fault! Load 3

Time 11, Ref 0:
Not in memory
Find oldest: 4(8)
Remove 4, add 0
Frames: [2(9), 3(10), 0(11)]
Fault! Load 0

Time 12, Ref 3:
Already in memory
Update: 3(12)
Frames: [2(9), 0(11), 3(12)]
Hit!

Time 13, Ref 2:
Already in memory
Update: 2(13)
Frames: [0(11), 3(12), 2(13)]
Hit!

Total Faults: 8 out of 13 references
Fault Rate: 62%

(Better than FIFO: 8 vs 9 faults)

Implementation Approaches

Counter Approach

Each page entry: timestamp field
On access: timestamp = current_time (increment counter)
On replacement: Find page with minimum timestamp

Overhead:
- Memory: One timestamp per page
- Time: Search through all pages to find minimum

Stack Approach

Maintain stack of page references
On access: Move referenced page to top
On replacement: Remove page from bottom

Example after time 7:
Stack (top to bottom): 0, 2, 3, 1, 7

On access 0:
Stack: 0, 2, 3, 1, 7 (already at top, no change)

On replacement:
Remove 7 (bottom)

Characteristics

LFU (Least Frequently Used)

Algorithm Details

Track: Access frequency for each page

On Page Fault:
1. Find page with minimum access count
2. Remove that page
3. Load new page
4. Set frequency = 1

Example

Reference String: 1, 2, 3, 1, 4, 1, 2

Initial: 3 frames, empty

Ref 1: Load 1
Frames: [1(freq=1)]

Ref 2: Load 2
Frames: [1(freq=1), 2(freq=1)]

Ref 3: Load 3
Frames: [1(freq=1), 2(freq=1), 3(freq=1)]

Ref 1: Already loaded
Frames: [1(freq=2), 2(freq=1), 3(freq=1)]
Hit!

Ref 4: Not loaded, all full
Remove page with min frequency (2 or 3)
Choose 2 (arbitrary)
Frames: [1(freq=2), 4(freq=1), 3(freq=1)]

Ref 1: Already loaded
Frames: [1(freq=3), 4(freq=1), 3(freq=1)]
Hit!

Ref 2: Not loaded
Remove page with min frequency: 4 or 3
Choose 4
Frames: [1(freq=3), 2(freq=1), 3(freq=1)]

Total Faults: 4 out of 7
(Page 1 kept because accessed 3 times)

Problem

Scenario:
Page A loaded long ago, accessed 100 times, then unused
Page B loaded recently, accessed 1 time

LFU chooses: Keep A (100 > 1)
Reality: B probably next accessed (temporal locality)

LFU ignores recency!

Characteristics

Optimal Algorithm

Concept

Replace page used furthest in future

Future reference string: a, b, c, a, d, b, e

Current memory: [a, c, d]
New reference: e

What to replace?
- a: Next used at position 3
- c: Next used at position beyond visible
- d: Next used at position beyond visible

Replace a (used soonest)? No! Replace page used furthest.
Replace c or d (used furthest)

Actually:
- a used at distance 3
- c used at distance beyond 7 (never)
- d used at distance beyond 7 (never)

Replace c or d

Optimal replaces page never used again!

Calculation

For reference string: 1, 2, 3, 1, 4, 1, 2, 5

Ref 1: Position 0, next at 3
Ref 2: Position 1, next at 6
Ref 3: Position 2, next at ∞ (never)
Ref 1: Position 3, next at 5
Ref 4: Position 4, next at ∞ (never)
Ref 1: Position 5, next at ∞ (never)
Ref 2: Position 6, next at ∞ (never)
Ref 5: Position 7

Use: Theoretical benchmark (cannot implement - future unknown!)

Practical Performance Analysis

Real Reference String: 100 references

Algorithm | Faults | Hit Rate | Speed
──────────┼────────┼──────────┼──────
Optimal   |  20    |  80%     | Theory
LRU       |  25    |  75%     | Slow
Clock     |  26    |  74%     | Fast
LFU       |  28    |  72%     | Medium
FIFO      |  32    |  68%     | Very fast
Random    |  35    |  65%     | Very fast

LRU near-optimal but expensive Clock good compromise FIFO poor but simple

Choosing Algorithm

System Type          Algorithm       Reason
────────────────────────────────────────
Batch processing     FIFO            Simple, adequate
Timesharing         LRU             Good performance
Real-time           Clock           Bounded latency
Performance-critical LRU            Near-optimal
Memory-constrained   Clock          Low overhead

Anomalies

Belady’s Anomaly (FIFO only)

More frames → More page faults!

Example:
3 frames, reference string: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5

Faults: 1, 2, 3, 4, 5, 3, 4, 5 = 8 faults

4 frames, same string:
Faults: 1, 2, 3, 4, 5, 5, 5, 3 = ? (more!)

Only FIFO exhibits this pathology
LRU, Optimal don't have this issue

Summary

FIFO simple but poor performance, suffers anomalies. LRU good performance but expensive to implement (find minimum each fault). LFU ignores recency, less practical. Optimal replaces page used furthest but unimplementable. Clock algorithm practical compromise: simpler than LRU, better than FIFO. Real systems use LRU or clock approximation. Choice between speed (FIFO) and performance (LRU) depends on system. Understanding algorithms essential for OS design. No perfect algorithm - trade-offs always exist.