Page Replacement Algorithms: Who Gets Kicked Out When Memory Is Full?

Imagine a phone with only 1 GB of free memory; opening an app triggers an "out of memory" warning, forcing the system to decide which running applications to terminate. This decision is made by a page replacement algorithm, which swaps out pages from physical memory to disk when memory is full.

Core Concepts

Page replacement aims for the highest hit rate (evicted pages are never needed again) while keeping algorithmic overhead low. Hit rate is defined as hits / total accesses .

1. OPT (Optimal) Algorithm

Theoretically optimal algorithm evicts the page whose next use is farthest in the future. It cannot be implemented in practice because it requires knowledge of future references.

def opt(references, frames):
    """OPT algorithm (ideal, unrealizable)"""
    memory = []
    page_faults = 0
    for ref in references:
        if ref not in memory:
            page_faults += 1
            if len(memory) < frames:
                memory.append(ref)
            else:
                future = {r: i for i, r in enumerate(references[references.index(ref)+1:])}
                farthest = -1
                victim = None
                for page in memory:
                    if page not in future:
                        victim = page
                        break
                    elif future[page] > farthest:
                        farthest = future[page]
                        victim = page
                memory.remove(victim)
                memory.append(ref)
    return page_faults

2. FIFO (First‑In‑First‑Out)

FIFO evicts the page that entered memory earliest.

def fifo(references, frames):
    """FIFO algorithm: evict the oldest page"""
    memory = []
    page_faults = 0
    for ref in references:
        if ref not in memory:
            page_faults += 1
            if len(memory) >= frames:
                memory.pop(0)  # evict oldest
            memory.append(ref)
    return page_faults
# Example reference string: [7,0,1,2,0,3,0,4] with frames=3

FIFO suffers from the Belady anomaly: increasing the number of frames can increase page faults. Example reference string [1,2,3,4,1,2,5,1,2,3,4,5] causes 9 faults with 3 frames but 10 faults with 4 frames.

3. LRU (Least Recently Used)

LRU evicts the page that has not been used for the longest time.

def lru(references, frames):
    """LRU algorithm: evict least recently used page"""
    memory = []
    page_faults = 0
    for ref in references:
        if ref in memory:
            memory.remove(ref)
            memory.append(ref)  # update recency
        else:
            page_faults += 1
            if len(memory) >= frames:
                memory.pop(0)  # evict oldest (LRU)
            memory.append(ref)
    return page_faults

4. Approximate LRU

4.1 Second Chance

def second_chance(references, frames):
    """Second‑Chance algorithm (FIFO + reference bit)"""
    memory = []  # [(page, R_bit)]
    page_faults = 0
    for ref in references:
        # set reference bit if page already in memory
        for i, (page, r) in enumerate(memory):
            if page == ref:
                memory[i] = (page, 1)
                break
        else:
            page_faults += 1
            if len(memory) >= frames:
                # give second chance to pages with R=1
                while memory[0][1] == 1:
                    page, _ = memory.pop(0)
                    memory.append((page, 0))
                memory.pop(0)  # evict with R=0
            memory.append((ref, 1))
    return page_faults

4.2 Clock Algorithm

def clock(references, frames):
    """Clock algorithm: circular list implementing Second Chance"""
    memory = [None] * frames
    use_bits = [0] * frames
    pointer = 0
    page_faults = 0
    for ref in references:
        # hit: set use bit
        for i in range(frames):
            if memory[i] == ref:
                use_bits[i] = 1
                break
        else:
            page_faults += 1
            while True:
                if memory[pointer] is None:
                    memory[pointer] = ref
                    use_bits[pointer] = 1
                    break
                if use_bits[pointer] == 0:
                    memory[pointer] = ref
                    use_bits[pointer] = 1
                    break
                use_bits[pointer] = 0  # give second chance
                pointer = (pointer + 1) % frames
        pointer = (pointer + 1) % frames
    return page_faults

5. Belady Anomaly

Only FIFO exhibits the anomaly where adding more frames can increase page faults; LRU and OPT never show this behavior.

Practical Applications

Scenario 1: Linux Page Replacement

# View memory and swap
free -h
# Monitor page replacement statistics
vmstat 1
# Sample output fields:
# si: pages swapped in per second
# so: pages swapped out per second

Scenario 2: JVM Garbage Collection (analogy)

// Young Generation ~ FIFO
//   Eden: newly created objects
//   Survivor: objects surviving a GC cycle
// Old Generation ~ LRU
//   Long‑living objects, Full GC when space runs low
// Heap size example: -Xms256m -Xmx1024m
// Collector choices:
//   Serial GC   – simple, FIFO‑like
//   Parallel GC – optimized FIFO
//   CMS / G1    – pause‑time focused, LRU‑like

Scenario 3: Redis Memory Eviction Policies

# Configure max memory
redis-cli CONFIG SET maxmemory 256mb
# Choose eviction policy (similar to page replacement)
redis-cli CONFIG SET maxmemory-policy allkeys-lru   # LRU for all keys
# Other policies: noeviction, allkeys-random, volatile-lru, volatile-ttl, etc.

Algorithm Comparison (summary)

OPT : Ideal, evicts farthest‑future page; impossible in practice because it needs future knowledge.

FIFO : Simple, evicts oldest page; suffers Belady anomaly.

LRU : Good performance, evicts least recently used; more complex to implement.

Clock : Approximate LRU, easy to implement, moderate performance.

LFU : Evicts least frequently used; suits hotspot workloads but ignores recency.

Key Takeaway

Page replacement algorithms decide which objects to discard when memory is full; OPT is ideal, FIFO is simplest, LRU is most common, and Clock is a lightweight LRU approximation.