Session 5.2 – Page Replacement Policies

Learning Objectives

By the end of this session, you will be able to:

Understand the need for page replacement in virtual memory systems
Analyze and implement FIFO, Optimal, LRU, and Clock replacement algorithms
Compare the performance characteristics of different algorithms
Explain Belady's Anomaly and its implications
Evaluate trade-offs between implementation complexity and performance
Calculate page fault rates for different replacement strategies

Introduction to Page Replacement

When all physical memory frames are occupied and a page fault occurs, the operating system must select a victim page to replace. The choice of which page to evict significantly impacts system performance.

                                    The Problem
                                    Physical memory is limited
All frames are occupied
New page needs to be loaded
Must choose victim page to evict
Goal: Minimize future page faults

                                

                                    Design Goals
                                    Low page fault rate
Simple implementation
Low computational overhead
Fair resource allocation
Predictable behavior

                                

Page Replacement Scenario

Before Replacement

Frame 0: Page A

Frame 1: Page B

Frame 2: Page C

All frames occupied!

Need to load Page D

Replacement Decision

Frame 0: Page A
Victim?

Frame 1: Page B
Victim?

Frame 2: Page C
Selected!

Algorithm decides victim

After Replacement

Frame 0: Page A

Frame 1: Page B

Frame 2: Page D
Newly loaded

Page C evicted

Page D loaded

FIFO (First-In-First-Out) Algorithm

FIFO replaces the page that has been in memory the longest. It maintains a queue of pages in the order they were loaded.

FIFO Algorithm

FIFO Page Replacement:
1. Maintain a queue of pages in memory
2. When new page arrives:
   - If memory has free frame: insert page, add to queue
   - If memory is full: remove oldest page (front of queue)
   - Insert new page at rear of queue
3. Page at front of queue is always the victim

Data Structure:
Queue: [Page1, Page2, Page3, ...]
       ↑                    ↑
    Victim              Last loaded

Time Complexity:
- Page fault: O(1)
- Memory access: O(1) with proper implementation

FIFO Advantages

Simple to understand and implement
Fair - treats all pages equally
Low overhead - constant time operations
No complex data structures required
Predictable behavior

FIFO Disadvantages

Ignores page usage patterns
May remove frequently used pages
Suffers from Belady's Anomaly
Poor performance with some access patterns
No consideration of locality

FIFO Algorithm Example

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

Number of Frames: 3

Step	Page	Frame 0	Frame 1	Frame 2	Result	Queue State
1	7	7	-	-	Fault	[7]
2	0	7	0	-	Fault	[7, 0]
3	1	7	0	1	Fault	[7, 0, 1]
4	2	2	0	1	Fault	[2, 0, 1]
5	0	2	0	1	Hit	[2, 0, 1]
6	3	2	3	1	Fault	[2, 3, 1]

Page Faults: 15 out of 20 references = 75% fault rate

Optimal (OPT) Algorithm

The optimal algorithm replaces the page that will not be used for the longest period in the future. This provides the theoretical minimum page fault rate but is impractical since it requires future knowledge.

Optimal Algorithm

Optimal Page Replacement:
1. For each page in memory, find when it will be referenced next
2. Select the page that will be referenced farthest in the future
3. If a page will never be referenced again, choose it immediately
4. Replace the selected page with the new page

Algorithm Steps:
- Look ahead in the reference string
- Calculate future distance for each current page
- Choose page with maximum future distance
- Break ties arbitrarily

Properties:
- Provides minimum possible page faults
- Used as benchmark for other algorithms
- Not implementable in practice (requires future knowledge)

Optimal Properties

Minimum page fault rate (proven optimal)
No Belady's Anomaly
Best possible performance
Serves as performance upper bound
Useful for algorithm comparison

Practical Limitations

Requires future knowledge
Cannot be implemented in real systems
Only useful for theoretical analysis
Complex to simulate (requires look-ahead)
May not reflect real-world patterns

Optimal Algorithm Example

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

Step 4: Need to replace for page 2

Current frames: [7, 0, 1]

Future analysis:

Page 7: Next used at position 18 (distance = 14)
Page 0: Next used at position 5 (distance = 1)
Page 1: Next used at position 14 (distance = 10)

Decision: Replace page 7 (farthest future use)

Step	Page	Frame 0	Frame 1	Frame 2	Result	Decision Logic
1	7	7	-	-	Fault	Cold start
4	2	2	0	1	Fault	Replace 7 (next at pos 18)
6	3	2	0	3	Fault	Replace 1 (next at pos 14)

Page Faults: 9 out of 20 references = 45% fault rate (optimal)

LRU (Least Recently Used) Algorithm

LRU replaces the page that has been unused for the longest time. It approximates the optimal algorithm by using past behavior to predict future behavior.

LRU Algorithm

LRU Page Replacement:
1. Keep track of when each page was last used
2. On page fault, select page with oldest "last used" time
3. Update timestamps on every page access

Implementation Options:
1. Counter-based: Timestamp on each page
2. Stack-based: Stack of page numbers
3. Linked List: Move accessed page to front

LRU Stack Algorithm:
- On page reference: move page to top of stack
- On page fault: victim is at bottom of stack
- Stack always contains pages in LRU order

LRU Advantages

Good approximation of optimal
Exploits temporal locality
No Belady's Anomaly
Generally good performance
Intuitive and predictable

LRU Disadvantages

High implementation overhead
Requires hardware support or software bookkeeping
Counter overflow issues
Performance depends on access patterns
May not work well with sequential scans

LRU Implementation Methods

1. Counter Method

Page | Counter
-----|--------
  A  |   105
  B  |   103
  C  |   107  ← Most recent
  D  |   101  ← LRU (victim)

Update: Increment global counter
        Set page counter = global

2. Stack Method

Stack (top = most recent):
[C]  ← Most recent
[A]
[B]  
[D]  ← LRU (victim)

Update: Move accessed page to top
        Others shift down

3. Hardware Method

Use matrix or reference bits:
- Reference bit per page
- Shift register per page
- Hardware updates on access
- Find LRU from bit patterns

Example: 8-bit shift register
Page A: 11000010 (recent)
Page B: 00110001 (LRU)

LRU Algorithm Trace

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

Step	Page	Frame 0	Frame 1	Frame 2	Result	LRU Order
1	7	7	-	-	Fault	[7]
5	0	2	0	1	Hit	[0, 2, 1]
6	3	2	0	3	Fault	[3, 2, 0] (Replace 1)

Page Faults: 12 out of 20 references = 60% fault rate

Clock (Second Chance) Algorithm

The Clock algorithm is an approximation of LRU that uses a reference bit to give pages a "second chance" before replacement. It's also known as the Second Chance algorithm.

Clock Algorithm

Clock Page Replacement:
1. Arrange pages in circular list (like clock face)
2. Each page has a reference bit (set on access)
3. Clock hand points to next candidate for replacement
4. On page fault:
   - If current page's reference bit = 0: replace it
   - If current page's reference bit = 1: 
     * Set bit to 0 (second chance)
     * Move to next page
   - Repeat until find page with reference bit = 0

Reference Bit Management:
- Set to 1 when page is accessed
- Cleared to 0 by clock algorithm
- Hardware or software can maintain bits

Clock Advantages

Simple implementation
Low overhead (just reference bits)
Good approximation of LRU
Works well with hardware support
No complex data structures
Reasonable performance

Clock Variations

Enhanced Clock: Uses reference + dirty bits
N-th Chance: Multiple reference bits
Clock-Pro: Hot/cold page distinction
Adaptive: Dynamic hand speed
Multi-level: Different clocks for different types

Clock Algorithm Visualization

A
R=1

B
R=0

C
R=1

D
R=0

E
R=1

F
R=0

Hand currently pointing at Page A

Clock Algorithm Steps

Need to replace a page:

Check Page A: R=1 → Set R=0, move hand
Check Page B: R=0 → Replace Page B!

After replacement:

Page B is replaced with new page
Hand moves to next position (Page C)
Page A gets second chance (R=0 now)

Enhanced Clock Algorithm

Uses both reference (R) and dirty (D) bits for better decisions:

Priority	R Bit	D Bit	Description	Action
1 (Best)	0	0	Not recently used, not dirty	Replace immediately
2	0	1	Not recently used, but dirty	Replace (need to write)
3	1	0	Recently used, not dirty	Give second chance
4 (Worst)	1	1	Recently used and dirty	Last resort

Algorithm Comparison

Performance Comparison

Algorithm	Implementation	Overhead	Performance	Belady's Anomaly	Best Use Case
FIFO	Very Simple	Very Low	Poor	Yes	Simple systems, uniform access
Optimal	Impossible	N/A	Perfect	No	Theoretical benchmark
LRU	Complex	High	Very Good	No	General purpose, good locality
Clock	Simple	Low	Good	No	Practical systems, hardware support

Typical Performance Rankings

Page Fault Rate Comparison (typical workload):

Algorithm    | Fault Rate | Relative Performance
-------------|------------|--------------------
Optimal      |    45%     |     100% (best)
LRU          |    60%     |      75%
Clock        |    67%     |      67%
FIFO         |    75%     |      60% (worst)

Implementation Cost Ranking:
1. FIFO      - O(1) time, minimal space
2. Clock     - O(1) time, 1 bit per page  
3. LRU       - O(log n) time, complex structures
4. Optimal   - Impossible to implement

Real-world Choice:
Clock algorithm often chosen as best trade-off between 
performance and implementation complexity.

Algorithm Selection Guide

Choose FIFO when:

Simplicity is paramount
Very limited resources
Uniform access patterns
Embedded systems

Choose Clock when:

Need good performance
Hardware reference bits available
General-purpose systems
Balance of simplicity and performance

Belady's Anomaly

The Anomaly Phenomenon

Belady's Anomaly: Some page replacement algorithms (notably FIFO) can experience more page faults when given more physical memory frames.

Example: FIFO with reference string [1,2,3,4,1,2,5,1,2,3,4,5]

With 3 frames:
Step | Ref | Frame0 | Frame1 | Frame2 | Fault?
-----|-----|--------|--------|--------|-------
1    | 1   |   1    |   -    |   -    |   F
2    | 2   |   1    |   2    |   -    |   F  
3    | 3   |   1    |   2    |   3    |   F
4    | 4   |   4    |   2    |   3    |   F
5    | 1   |   4    |   1    |   3    |   F
6    | 2   |   4    |   1    |   2    |   F
7    | 5   |   5    |   1    |   2    |   F
8    | 1   |   5    |   1    |   2    |   H
9    | 2   |   5    |   1    |   2    |   H  
10   | 3   |   3    |   1    |   2    |   F
11   | 4   |   3    |   4    |   2    |   F
12   | 5   |   3    |   4    |   5    |   F

Total Page Faults: 9

With 4 frames (more memory!):

Step | Ref | F0 | F1 | F2 | F3 | Fault?
-----|-----|----|----|----|----| -------
1    | 1   | 1  | -  | -  | -  |   F
2    | 2   | 1  | 2  | -  | -  |   F
3    | 3   | 1  | 2  | 3  | -  |   F
4    | 4   | 1  | 2  | 3  | 4  |   F
5    | 1   | 1  | 2  | 3  | 4  |   H
6    | 2   | 1  | 2  | 3  | 4  |   H
7    | 5   | 5  | 2  | 3  | 4  |   F
8    | 1   | 5  | 1  | 3  | 4  |   F
9    | 2   | 5  | 1  | 2  | 4  |   F
10   | 3   | 5  | 1  | 2  | 3  |   F
11   | 4   | 5  | 1  | 2  | 3  |   F
12   | 5   | 5  | 1  | 2  | 3  |   H

Total Page Faults: 10 (worse!)

Algorithms with Anomaly

FIFO: Exhibits the anomaly
Random: Can exhibit anomaly
Other simple algorithms

Why it happens: Adding frames can change the entire replacement pattern, leading to worse decisions.

Algorithms without Anomaly

Optimal: Provably no anomaly
LRU: Stack algorithm property
Clock: Approximates LRU

Stack Algorithm Property: Set of pages in memory with n frames is always a subset of pages with n+1 frames.

Implementation Details

FIFO Implementation

C Implementation:
typedef struct {
    int *frames;
    int size;
    int next_victim;
} FIFO_Buffer;

int fifo_replace(FIFO_Buffer *buf, int page) {
    int victim = buf->frames[buf->next_victim];
    buf->frames[buf->next_victim] = page;
    buf->next_victim = (buf->next_victim + 1) % buf->size;
    return victim;
}

Time Complexity: O(1)
Space Complexity: O(n)

Clock Implementation

C Implementation:
typedef struct {
    int page;
    int reference_bit;
} ClockPage;

int clock_replace(ClockPage *pages, int size, 
                  int *hand, int new_page) {
    while (pages[*hand].reference_bit == 1) {
        pages[*hand].reference_bit = 0;
        *hand = (*hand + 1) % size;
    }
    int victim = pages[*hand].page;
    pages[*hand].page = new_page;
    pages[*hand].reference_bit = 1;
    *hand = (*hand + 1) % size;
    return victim;
}

Time Complexity: O(n) worst case, O(1) average

LRU Implementation (Stack)

Stack-based LRU:
typedef struct Node {
    int page;
    struct Node *next;
    struct Node *prev;
} Node;

void lru_access(Node **head, int page) {
    Node *current = find_page(*head, page);
    if (current) {
        // Move to front
        remove_node(current);
        add_to_front(head, current);
    } else {
        // Replace LRU (at tail)
        Node *lru = get_tail(*head);
        lru->page = page;
        remove_node(lru);
        add_to_front(head, lru);
    }
}

Time Complexity: O(n)
Can optimize with hash table to O(1)

Hardware Support

Hardware Enhancements:

1. Reference Bits:
   - Set by hardware on page access
   - Cleared by OS periodically
   - Used by Clock algorithm

2. Age Registers:
   - Shift registers per page
   - Hardware shifts on timer
   - Approximate LRU ordering

3. TLB Integration:
   - Reference bits in TLB
   - Automatic bit management
   - Fast access tracking

OS Responsibilities:
- Manage replacement policy
- Handle page faults
- Update page tables
- Interface with hardware

Comprehensive Example

Algorithm Performance Comparison

Scenario:

Reference String: 1, 2, 3, 4, 2, 1, 5, 6, 2, 1, 2, 3, 7, 6, 3, 2, 1, 2, 3, 6

Number of Frames: 4

FIFO Results

Final State: [6, 3, 2, 1]

Page Faults: 14
Hit Rate: 30%
Fault Rate: 70%

Issues Observed:
- Replaced page 1 early, needed again
- No consideration of usage patterns
- Consistent but suboptimal performance

LRU Results

Final State: [6, 3, 2, 1]

Page Faults: 10
Hit Rate: 50%  
Fault Rate: 50%

Advantages Observed:
- Better handling of repeated accesses
- Exploited temporal locality well
- Good performance on this pattern

Clock Results

Final State: [6, 3, 2, 1]

Page Faults: 12
Hit Rate: 40%
Fault Rate: 60%

Performance:
- Good approximation of LRU
- Simple reference bit management
- Reasonable overhead

Optimal Results

Final State: [6, 3, 2, 1]

Page Faults: 8
Hit Rate: 60%
Fault Rate: 40%

Theoretical Minimum:
- Best possible performance
- Benchmark for other algorithms
- Not implementable in practice

Performance Summary

Algorithm	Page Faults	Hit Rate	Relative Performance	Implementation Cost
Optimal	8	60%	100% (best)	Impossible
LRU	10	50%	80%	High
Clock	12	40%	67%	Low
FIFO	14	30%	57%	Very Low

Session Summary

Key Concepts

Page Replacement: Choose victim when memory is full
FIFO: Simple but suboptimal queue-based approach
Optimal: Theoretical minimum, requires future knowledge
LRU: Good approximation using recent usage
Clock: Practical approximation of LRU
Belady's Anomaly: More memory can mean worse performance

Design Principles

Exploit Locality: Recent usage predicts future usage
Balance Complexity: Simple algorithms vs performance
Hardware Support: Reference bits improve efficiency
Avoid Anomalies: Use stack algorithms when possible
Consider Workload: Different patterns need different algorithms
Measure Performance: Profile and optimize for real usage

Next Session Preview

Session 5.3 will cover File System Concepts, exploring file and directory structures, file attributes, and directory implementation techniques that form the foundation of modern file systems.