Page Replacement

Definition

Page Replacement: Process of selecting which page to remove from physical memory when new page needed but memory full. Critical for virtual memory performance.

When Page Replacement Happens

Page Fault

Scenario: RAM full, all frames occupied
Process accesses page not in memory
Page Fault! (interrupt)

OS Response:
1. Find page to replace (victim selection)
2. Write victim to disk (if dirty)
3. Load new page from disk
4. Update page table
5. Resume process

Victim Selection

Choosing which page to evict:

Page Table:
Virtual Page | Frame | Valid | Modified | Time Last Used
────────────┼───────┼───────┼──────────┼────────────────
     0      |   5   |   1   |    0     | 1000ms ago
     1      |   8   |   1   |    1     | 100ms ago
     2      |   3   |   1   |    0     | 5000ms ago
     3      |  10   |   1   |    0     | 200ms ago

Which to replace?

If page 2: Least recently used
If page 0 or 3: Not modified (faster)
Different algorithms choose differently

Dirty Bit (Modified Bit)

Purpose

Track if page modified since loaded:

Page Loaded from Disk:
Modified Bit = 0 (clean)

Process writes to page:
Modified Bit = 1 (dirty)

Page Replacement:
Dirty = 0: Just discard (no write needed!)
Dirty = 1: Must write to disk (saves changes)

Performance Impact

Replace clean page: ~5ms (no disk write)
Replace dirty page: ~10ms (read new + write old)

Prefer clean pages for performance!

Swap Space

Location where pages written on disk:

/var/swap (Linux)
C:\pagefile.sys (Windows)

Contains:
- Pages written from memory
- Available space for new pages
- Managed by OS

Size: Usually 1-4x RAM
Example: 512MB RAM → 1-2GB swap space

Page Replacement Algorithms

Goal

Minimize page faults (maximize hits)

Measurement

Page Fault Rate: $$\text{Fault Rate} = \frac{\text{Number of page faults}}{\text{Total memory references}}$$

Lower is better!

Example:

1000 memory accesses
5 page faults
Fault rate: 5/1000 = 0.5% = very good!

Common Algorithms

1. Optimal Page Replacement

Algorithm: Replace page that won’t be used for longest time

Pages in memory: [A, B, C]
Incoming pages: D, A, B, A, C, D, B

D arrives: Replace C (not used until position 5)
A arrives: Already in memory
B arrives: Already in memory
A arrives: Already in memory
C arrives: Replace B (not used until position 6)

Page faults: 2

This is the best possible!

Problem: Future unknown at runtime!

Use: Theoretical benchmark (never implement)

Faults: Minimum possible for given sequence

2. First In First Out (FIFO)

Algorithm: Replace oldest page (first loaded)

Frames available: 3
Incoming: A, B, C, D, A, E, A, B, F

Load A (frames: [A])
Load B (frames: [A, B])
Load C (frames: [A, B, C])
D arrives: Remove A (oldest)
            (frames: [B, C, D])
A arrives: Remove B (oldest)
           (frames: [C, D, A])
E arrives: Remove C (oldest)
           (frames: [D, A, E])
A arrives: Already in
B arrives: Remove D (oldest)
           (frames: [A, E, B])
F arrives: Remove A (oldest)
           (frames: [E, B, F])

Faults: A, B, C, D, E, B, F = 7 faults

Characteristics:

• ✓ Simple to implement
• ❌ Poor performance (doesn’t consider usage)
• ❌ FIFO anomaly: More frames can mean more faults!

FIFO Anomaly:

Reference sequence: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5

With 3 frames: 9 faults
With 4 frames: 10 faults (worse!)

Adding memory caused more page faults!
Only FIFO has this pathology

3. Least Recently Used (LRU)

Algorithm: Replace page not used for longest time

Frames available: 3
Incoming: A, B, C, D, A, E, A, B, F, A, B

Load A (frames: [A])
Load B (frames: [A, B])
Load C (frames: [A, B, C])
D arrives: Remove A (not used since loaded)
           (frames: [B, C, D])
A arrives: Remove B (not used for longest)
           (frames: [C, D, A])
E arrives: Remove C (not used since loaded)
           (frames: [D, A, E])
A arrives: Already in (refresh timestamp)
B arrives: Remove D (not used for longest)
           (frames: [A, E, B])
F arrives: Remove E (not used for longest)
           (frames: [A, B, F])
A arrives: Already in
B arrives: Already in

Faults: A, B, C, D, E, B, F = 7 faults

(Better than FIFO for many sequences)

Characteristics:

• ✓ Good performance (exploits temporal locality)
• ✓ No anomalies
• ❌ Expensive to implement (track access time for each page)
• ✓ Common in practice

Implementation:

Option 1: Counter:

Each page has timestamp (logical clock)
On access: timestamp = current_clock++
On replacement: Find minimum timestamp
Cost: Memory for timestamps, search on fault

Option 2: Stack:

Keep stack of page reference order
On access: Move page to top
On replacement: Remove from bottom
Cost: Stack maintenance on every access

4. Least Frequently Used (LFU)

Algorithm: Replace page used least often

Pages with access counts:
A: 5 accesses
B: 2 accesses
C: 8 accesses
D: 1 access

Replace D (used only 1 time)

Characteristics:

• ✓ Considers frequency
• ❌ Doesn’t consider recency
• ❌ Popular past page kept even if unused now

Problem:

Page loaded long ago, accessed 100 times, then unused
vs
Page loaded recently, accessed 1 time

LFU: Keep old page (100 > 1)
Should: Prefer recent page (temporal locality!)

5. Clock Algorithm (Second Chance)

Algorithm: Approximation of LRU, simpler implementation

Mechanism:
Pages arranged in circular list
Pointer advances like clock hand
Each page has reference bit (0 or 1)

On page access: Set reference bit = 1

On replacement:
Scan from current position
If reference bit = 0: Replace (hasn't been used)
If reference bit = 1: Set to 0, advance (second chance)
Continue scanning

Characteristics:
- Reference bit = 1 means "used recently"
- Bit reset to 0 on scan (gives second chance)
- Simple implementation
- Reasonable performance (LRU approximation)

Example:

Frames (circular): [A(0), B(1), C(0), D(1)]
Pointer: at A

New page E arrives:

Scan A: Ref=0 → Replace A with E
Result: [E(0), B(1), C(0), D(1)]
Pointer: at E (next)

Reference bits reset on scan:
[E(0), B(0), C(0), D(0)]

Algorithm Comparison

Working Set Model

Concept

Process uses subset of pages (working set) at any time:

Working set: Pages actively used now
Example:
Loop iterates over array pages 10-20
Recursive function uses stack pages 100-110
Working set = pages 10-20 + 100-110

Other pages: Can be evicted (not used now)
Working set pages: Should stay in memory

Optimal Replacement

Keep working set in memory, evict rest:

Working set size: 50 pages
RAM available: 60 pages
Result: All working set in memory, no faults

Working set size: 50 pages
RAM available: 40 pages
Result: Some working set evicted, faults occur
System thrashes!

Working Set Window

Look back at last $\tau$ accesses:

$\tau$ = 10,000 memory references (time window)

If page accessed within last 10,000 references:
In working set
If not accessed in last 10,000 references:
Not in working set (can evict)

Thrashing

Definition

Excessive paging: system spends more time paging than computing

Low memory: Working set doesn't fit in RAM
Page fault: Load page A, evict page B
Next access: Need page B (not in memory)
Another fault: Load page B, evict page A
Loop: A, B, A, B, A, B, ...

100% time paging, 0% computing!
System paralyzed!

Prevention

1. Sufficient RAM:

Working set size × number of processes ≤ RAM
If violated: Thrashing

Solution: More RAM

2. Page Replacement Algorithm:

Good algorithm (LRU): Keep working set
Bad algorithm (FIFO): Evict working set

3. Admission Control:

Monitor working set size
Prevent process if insufficient space
Suspend process until space available

Summary

Page replacement selects victim when RAM full and page fault occurs. Optimal replaces page used furthest in future (unimplementable). FIFO simple but poor, suffers anomalies. LRU good but expensive. Clock algorithm practical approximation. Working set model explains optimal page replacement. Thrashing occurs when working set exceeds RAM. Understanding algorithms crucial for performance analysis. Modern systems use LRU or clock approximation. Choice affects overall system performance significantly.