Page Replacement Need

When physical memory is exhausted and a process needs a page that isn't in memory, the operating system faces a classical resource allocation problem: something must yield for something else to be served.

This isn't merely a technical challenge—it's a problem of profound consequences. The page we choose to evict will determine whether the system runs smoothly or descends into a cascade of additional page faults. Choose well, and the evicted page won't be needed for a long time. Choose poorly, and we'll immediately fault it back in, having wasted two disk I/O operations for nothing.

Page replacement is where virtual memory theory meets operational reality. This page explores the fundamental concept, mechanics, and critical decisions involved in this pivotal operating system operation.

Page replacement is the process by which an operating system selects a page currently resident in physical memory, removes it, and uses the freed frame to satisfy a new page request.

Formal Definition:

Given:

• A set F of physical frames, all currently allocated
• A page fault for virtual page p not in memory
• Page p must be loaded from backing store

Page Replacement is the operation of:

1. Selecting a victim page v currently occupying frame f
2. Removing the mapping of v to f
3. (Optionally) Saving v to backing store if modified
4. Loading p into frame f
5. Establishing mapping of p to f

The core challenge is step 1: victim selection. This is where page replacement algorithms differ and where performance is won or lost.

Why "Replacement" Instead of "Allocation"?

The term "replacement" emphasizes that we're not finding new resources—we're reallocating existing ones. Unlike initial page allocation where we simply use a free frame, replacement forces us to dispossess one page to accommodate another. This zero-sum nature is fundamental to understanding why the choice matters so much.

The Page Replacement Problem:

Formally stated, the page replacement problem asks:

Given a sequence of page references R = r₁, r₂, r₃, ..., rₙ and a fixed number of frames k, determine which pages to keep in memory at each step to minimize the total number of page faults.

This is a classic online algorithm problem—we must make decisions without knowing future references. The theoretically optimal solution (Bélády's OPT) requires future knowledge, making it impossible to implement but useful as a benchmark.

Dimensions of the Problem:

Understanding page replacement requires tracing through the complete sequence of events, from the initial page fault to the resumption of the faulting process.

Phase 1: Page Fault Detection

The process begins when a memory access cannot be satisfied from physical memory:

1. CPU executes instruction accessing virtual address VA
2. MMU consults page table entry for VA's page
3. Valid bit is 0 → page not in memory
4. MMU raises page fault exception
5. CPU saves state and transfers to kernel page fault handler

Phase 2: Page Identification

The kernel must determine what page is needed and where it resides:

1. Extract faulting virtual address from CPU register
2. Identify faulting process from current context
3. Look up page in process's virtual memory map
4. Determine page source:
   - Anonymous page → allocate zeroed or from swap
   - File-backed page → identify file and offset
   - Private mapping → may be copy-on-write

Phase 3: Frame Acquisition

The kernel attempts to obtain a free frame:

1. Check free frame list
2. If frames available → skip to Phase 5
3. If no free frames → proceed to Phase 4 (replacement)

Phase 4: Victim Selection and Eviction

This is the heart of page replacement:

1. Invoke page replacement algorithm to select victim
2. Lock victim frame to prevent concurrent modification
3. Check if victim page is modified (dirty bit)
4. If dirty:
   a. Determine write-back location (swap or file)
   b. Initiate disk write
   c. Wait for I/O completion
   d. Clear dirty bit
5. Update victim's page table entry:
   - Clear valid bit (page no longer in memory)
   - Store disk location for future reference
6. Remove frame from any caching structures
7. Frame is now logically free

Phase 5: Page Load

1. Initiate disk read to load new page into frame
2. Wait for I/O completion
3. Page contents now in frame

Phase 6: Mapping Establishment

1. Update faulting process's page table entry:
   - Set frame number field
   - Set valid bit = 1
   - Clear reference bit
   - Clear dirty bit
   - Set protection bits as appropriate
2. Flush TLB entry for this page (if cached)

Phase 7: Process Resumption

1. Return from page fault handler
2. CPU restores saved state
3. Original instruction is re-executed
4. This time, page table lookup succeeds
5. Memory access completes normally

Let's trace through a concrete example of a page fault requiring replacement. This detailed walkthrough illuminates every data structure and operation involved.

Scenario Setup:

• System has 4 physical frames (numbered 0-3)
• All frames are currently occupied
• Process A faults on virtual page 7
• Page 7 is in swap at block 42

Initial State:

Physical Memory (4 frames):
┌─────────┬─────────────┬─────────┬───────┬───────────┐
│ Frame # │ Contents    │ Process │ VPage │ Dirty Bit │
├─────────┼─────────────┼─────────┼───────┼───────────┤
│    0    │ Code page   │ A       │   2   │     0     │
│    1    │ Stack page  │ B       │  15   │     1     │
│    2    │ Heap data   │ A       │   5   │     1     │
│    3    │ Shared lib  │ Shared  │  N/A  │     0     │
└─────────┴─────────────┴─────────┴───────┴───────────┘

Process A's Page Table:
┌─────────┬───────┬───────┬─────────┐
│ VPage # │ Valid │ Frame │ Dirty   │
├─────────┼───────┼───────┼─────────┤
│    2    │   1   │   0   │    0    │
│    5    │   1   │   2   │    1    │
│    7    │   0   │  N/A  │   N/A   │ ← Page to load
└─────────┴───────┴───────┴─────────┘

Free Frame List: [empty]

Step-by-Step Execution:

Step 1: Page Fault Occurs

• Process A executes: MOV AX, [page7_address]
• MMU checks page table: VPage 7, Valid = 0
• Page fault trap to kernel

Step 2: Kernel Analyzes Fault

• Fault address indicates VPage 7
• Look up in Process A's virtual memory structures
• Find: anonymous page, currently in swap at block 42

Step 3: Check Free Frames

• Free frame list is empty
• Must invoke page replacement

Step 4: Select Victim (Example: Choose Frame 0)

• Replacement algorithm selects Frame 0 (Process A, VPage 2)
• Note: Frame 0 is clean (dirty bit = 0)

Step 5: Evict Victim

• Frame 0 contains Process A's VPage 2
• Dirty bit = 0 → no disk write needed
• Update Process A's page table: VPage 2 valid = 0
• Frame 0 is now available

Step 6: Load New Page

• Initiate disk read from swap block 42
• Block for I/O completion (~10ms HDD, ~50μs SSD)
• VPage 7 contents now in Frame 0

Step 7: Update Page Table

• Process A's page table: VPage 7 → Frame 0, valid = 1

Step 8: Resume Process

• Return from page fault handler
• Instruction re-executes successfully

Final State:

Physical Memory (4 frames):
┌─────────┬─────────────┬─────────┬───────┬───────────┐
│ Frame # │ Contents    │ Process │ VPage │ Dirty Bit │
├─────────┼─────────────┼─────────┼───────┼───────────┤
│    0    │ New page 7  │ A       │   7   │     0     │ ← Changed
│    1    │ Stack page  │ B       │  15   │     1     │
│    2    │ Heap data   │ A       │   5   │     1     │
│    3    │ Shared lib  │ Shared  │  N/A  │     0     │
└─────────┴─────────────┴─────────┴───────┴───────────┘

Process A's Page Table:
┌─────────┬───────┬───────┬─────────┐
│ VPage # │ Valid │ Frame │ Dirty   │
├─────────┼───────┼───────┼─────────┤
│    2    │   0   │  N/A  │   N/A   │ ← Now invalid (evicted)
│    5    │   1   │   2   │    1    │
│    7    │   1   │   0   │    0    │ ← Now valid
└─────────┴───────┴───────┴─────────┘

Outcome Analysis:

• Selected clean victim → only 1 disk I/O operation
• Had we selected Frame 2 (dirty) → 2 disk I/O operations
• Good choice saved ~10-50ms of page fault latency

Page replacement involves several critical decisions that significantly impact system performance. Understanding these decisions is essential for appreciating why different algorithms exist and how operating systems are configured.

Decision 1: When to Replace?

There are two fundamental approaches:

On-Demand Replacement:

• Replace only when a page fault finds no free frames
• Simpler implementation
• May cause latency spikes when frames depleted

Anticipatory Replacement (Background Reclamation):

• Maintain a reserve of free frames
• Background daemon (e.g., Linux's kswapd) proactively evicts pages
• Page faults usually find free frames immediately
• Trades background CPU/I/O for foreground latency

Most modern systems use anticipatory replacement with on-demand as fallback.

Decision 2: Replacement Scope—Local vs Global

This decision determines the pool of pages eligible for eviction:

Local Replacement:

• Only evict pages from the faulting process
• Each process has a fixed frame allocation
• Processes cannot steal frames from each other
• Provides isolation but may underutilize memory

Global Replacement:

• Any page in memory is a candidate for eviction
• Frames flow to processes that need them
• Better overall utilization
• One process can impact another's performance

Partitioned Schemes:

• Hybrid approaches dividing memory into pools
• Critical processes get dedicated pools
• Background processes share a common pool

Local Replacement:
┌──────────────────────────────────────────────┐
│ Process A Pool │ Process B Pool │ Kernel Pool │
│   [5 frames]   │   [5 frames]   │ [6 frames]  │
│    Isolated    │    Isolated    │  Protected  │
└──────────────────────────────────────────────┘
A can only evict from its own 5 frames.

Global Replacement:
┌──────────────────────────────────────────────┐
│          Shared Replaceable Pool             │
│   [All user frames - 10 total]               │
│   Any page can be evicted for any process    │
└──────────────────────────────────────────────┘
A can cause B's page to be evicted.

Decision 3: What to Replace?

This is where page replacement algorithms come in. The goal is to evict the page least likely to be needed soon. Common strategies:

Each algorithm trades accuracy for implementation cost. We'll explore these in detail in subsequent modules.

Decision 4: How to Handle Dirty Pages?

When a dirty page is selected for eviction:

Synchronous Write-Back:

• Write page to disk before declaring frame free
• Simple but adds latency to page fault

Asynchronous Write-Back:

• Write page in background before it becomes victim
• When evicted, page is already clean
• Reduces page fault latency
• Requires tracking and scheduling infrastructure

Modern systems use page cleaning daemons (like Linux's pdflush or flush workers) to write dirty pages asynchronously, so when replacement is needed, more pages are clean.

How do we measure whether a page replacement algorithm is working well? Several metrics capture different aspects of performance.

Primary Metric: Page Fault Rate

The most fundamental measure is the page fault rate—the fraction of memory accesses that result in page faults:

Page Fault Rate = Number of Page Faults / Total Memory References

For a reference string of length n with f faults:

PFR = f / n

Lower is better. Typical values:

• Excellent: < 0.001 (1 fault per 1000 accesses)
• Good: 0.001 - 0.01
• Acceptable: 0.01 - 0.1
• Poor: > 0.1 (approaching thrashing)

Page Fault Rate Example:

Reference string: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 With 3 frames:

• FIFO: 9 faults → PFR = 9/12 = 0.75
• LRU: 10 faults → PFR = 10/12 = 0.83
• OPT: 7 faults → PFR = 7/12 = 0.58

Effective Access Time Calculation:

EAT combines normal memory access time with the cost of page faults:

EAT = (1 - p) × memory_access_time + p × page_fault_time

Where:
  p = probability of page fault (page fault rate)
  memory_access_time ≈ 100 nanoseconds
  page_fault_time ≈ 10 milliseconds (HDD) or 100 microseconds (SSD)

Example Calculation (HDD):

p = 0.001 (1 fault per 1000 accesses)
memory_access = 100 ns
fault_time = 10 ms = 10,000,000 ns

EAT = (0.999)(100) + (0.001)(10,000,000)
    = 99.9 + 10,000
    = 10,099.9 ns ≈ 10 μs

Even with a 0.1% fault rate, access time increases by 100x!

Example Calculation (SSD):

p = 0.001
memory_access = 100 ns
fault_time = 100 μs = 100,000 ns

EAT = (0.999)(100) + (0.001)(100,000)
    = 99.9 + 100
    = 199.9 ns ≈ 200 ns

SSD reduces the impact to a 2x slowdown—demonstrating why SSDs dramatically improve system responsiveness under memory pressure.

Page replacement algorithms implement a specific interface that the memory management subsystem invokes. Understanding this interface clarifies what information algorithms receive and what decisions they must make.

The Conceptual Interface:

/**
 * Page Replacement Algorithm Interface
 * 
 * The memory manager calls these functions at specific points
 * in the page lifecycle.
 */

// Called when a page fault occurs and no free frames exist
// Returns: the frame to evict (the victim)
frame_t select_victim(void);

// Called when a page is first loaded into a frame
void page_loaded(frame_t frame, page_t page);

// Called when a page is accessed (may be used for LRU tracking)
void page_accessed(frame_t frame);

// Called when a page is modified (write reference)
void page_modified(frame_t frame);

// Called when a page is explicitly freed (process exits, munmap)
void page_freed(frame_t frame);

Information Available to Algorithms:

Algorithms have access to various metadata to make decisions:

Hardware Support Requirements:

Efficient page replacement requires specific hardware support:

Reference Bit:

• MMU sets to 1 when page is accessed
• OS can clear it periodically
• Essential for Clock and LRU approximations

Dirty (Modify) Bit:

• MMU sets to 1 when page is written
• Indicates page must be saved before eviction
• Critical for avoiding unnecessary I/O

Both bits are per-page table entry:

Page Table Entry (simplified):
┌─────────────────────────────────────────────────────────┐
│ Frame # │ Valid │ Reference │ Dirty │ Protection │ ... │
│  20 bit │ 1 bit │   1 bit   │ 1 bit │   3 bit    │     │
└─────────────────────────────────────────────────────────┘

Software-Only Alternatives:

Some architectures lack hardware reference bits. Software simulation:

1. Mark page as invalid in page table
2. Any access causes page fault
3. Fault handler sets software reference bit, marks page valid
4. Significant overhead but allows LRU-like behavior

This technique was used extensively on older systems and remains available as fallback.

Page replacement seems conceptually simple—pick a victim and swap pages. In practice, numerous edge cases and challenges complicate implementation.

Challenge 1: Pinned/Locked Pages

Some pages cannot be evicted:

Non-evictable pages:
- Kernel code and data pages
- Pages undergoing DMA transfers
- Pages locked by mlock() system call
- Real-time application pages
- File system journal pages

Algorithms must skip these when scanning for victims.

Challenge 2: Shared Pages

Pages shared between processes have multiple PTE references:

Frame 42 is mapped by:
- Process A, VPage 10 (read-only)
- Process B, VPage 7 (read-only)  
- Process C, VPage 12 (read-only)

Eviction must:
1. Update ALL three page table entries
2. Flush TLB entries for ALL processes
3. Track reverse mappings from frames to PTEs

Challenge 3: Concurrent Page Faults

Multiple CPUs may fault simultaneously:

CPU 0: Faults on page P1, selects frame F
CPU 1: Faults on page P2, also selects frame F

Without synchronization:
- Both load pages into F
- One clobbers the other
- Silent corruption

Solution: Frame-level locks, atomic victim selection

Challenge 4: NUMA Considerations

On Non-Uniform Memory Access systems, not all frames are equal:

NUMA Node 0 (CPU 0-3):
  - Local memory: 16 GB, access time: 100ns
  - Remote memory (Node 1): access time: 300ns

NUMA Node 1 (CPU 4-7):
  - Local memory: 16 GB, access time: 100ns
  - Remote memory (Node 0): access time: 300ns

Replacement implications:
- Prefer evicting remote pages (less costly to re-fault)
- Try to keep process pages on local node
- Balance memory pressure across nodes

Challenge 5: Large Pages (Huge Pages)

2 MB or 1 GB pages complicate replacement:

2 MB huge page = 512 standard 4 KB pages

Evicting one huge page:
- Frees 512 frames at once (good)
- Internal fragmentation if only part needed
- May evict actively-used sub-regions
- Shattering: break huge page into small pages first

Modern systems support transparent huge page (THP) with dynamic promotion/demotion, adding complexity to replacement decisions.

We've established a comprehensive understanding of page replacement as a concept. Let's consolidate the key points:

What's Next:

With a solid understanding of the page replacement concept, we now turn to the critical question: how do we choose which page to evict? The next page explores victim selection—the heart of every page replacement algorithm and the decision that most directly impacts system performance.