Page Replacement Algorithms

[!NOTE] This module explores the core principles of Page Replacement Algorithms, deriving solutions from first principles and hardware constraints to build world-class, production-ready expertise.

1. The Problem: RAM is Full

When Physical RAM is full and a process needs a new page, the OS must evict an existing page to disk (Swap) to make room. This is a Page Replacement Policy.

The goal is to minimize Page Faults. Accessing RAM takes ~100ns. Accessing Disk takes ~10ms (10,000,000ns). A single bad decision can kill performance.

---

2. The Impossible Ideal: OPT (Optimal)

• Algorithm: Evict the page that will not be used for the longest period of time.
• Reality: Impossible to implement because the OS cannot predict the future.
• Use Case: Used as a benchmark to measure how good other algorithms are.

3. FIFO (First-In, First-Out)

• Algorithm: Evict the oldest page in memory.
• Pros: Simple (Queue).
• Cons: The oldest page might be libc.so (used constantly). Evicting it causes immediate thrashing.
• Belady’s Anomaly: In FIFO, increasing the number of Frames can sometimes increase the number of Page Faults.

4. LRU (Least Recently Used)

• Algorithm: Evict the page that hasn’t been used for the longest time.
• Logic: “If I used it recently, I’ll probably use it again” (Temporal Locality).
• Pros: Excellent performance, close to OPT.
• Cons: Expensive. You need to update a timestamp or move a node in a Linked List on every single memory access.

5. The Clock Algorithm (Second Chance)

A practical approximation of LRU used in real systems (like Linux).

• Setup: Arrange pages in a circular buffer.
• Bit: Each page has a “Reference Bit” (set to 1 by hardware when accessed).
• The Hand: A pointer iterates through the circle.
  1. If RefBit == 1: Set to 0 and move on (Give it a second chance).
  2. If RefBit == 0: Evict this page.

---

6. Interactive: Eviction Simulator

Compare FIFO vs LRU on a sequence of page requests.

• Sequence: A B C A D B E
• Capacity: 3 Frames

Next Request: A

FIFO

Hits: 0 | Faults: 0

LRU

Hits: 0 | Faults: 0

---

7. Code Example: Implementing an LRU Cache

Implementing an LRU Cache is a classic interview question. The optimal structure is a Hash Map (for O(1) lookup) combined with a Doubly Linked List (for O(1) ordering).

package main

import (
	"container/list"
	"fmt"
)

type LRUCache struct {
	Capacity int
	Cache    map[int]*list.Element
	List     *list.List
}

type Pair struct {
	Key   int
	Value int
}

func Constructor(capacity int) LRUCache {
	return LRUCache{
		Capacity: capacity,
		Cache:    make(map[int]*list.Element),
		List:     list.New(),
	}
}

func (this *LRUCache) Get(key int) int {
	if elem, found := this.Cache[key]; found {
		// Move accessed element to front (Most Recently Used)
		this.List.MoveToFront(elem)
		return elem.Value.(Pair).Value
	}
	return -1
}

func (this *LRUCache) Put(key int, value int) {
	if elem, found := this.Cache[key]; found {
		// Update and move to front
		this.List.MoveToFront(elem)
		elem.Value = Pair{Key: key, Value: value}
	} else {
		// Add new
		if this.List.Len() >= this.Capacity {
			// Evict LRU (Back of list)
			lru := this.List.Back()
			this.List.Remove(lru)
			delete(this.Cache, lru.Value.(Pair).Key)
		}
		newElem := this.List.PushFront(Pair{Key: key, Value: value})
		this.Cache[key] = newElem
	}
}

func main() {
	lru := Constructor(2)
	lru.Put(1, 1)
	lru.Put(2, 2)
	fmt.Println(lru.Get(1)) // returns 1
	lru.Put(3, 3)           // evicts key 2
	fmt.Println(lru.Get(2)) // returns -1 (not found)
	lru.Put(4, 4)           // evicts key 1
	fmt.Println(lru.Get(1)) // returns -1 (not found)
	fmt.Println(lru.Get(3)) // returns 3
	fmt.Println(lru.Get(4)) // returns 4
}

import java.util.LinkedHashMap;
import java.util.Map;

// Java has a built-in LRU capability via LinkedHashMap!
public class LRUCache extends LinkedHashMap<Integer, Integer> {
    private final int capacity;

    public LRUCache(int capacity) {
        // accessOrder = true enables LRU mode
        super(capacity, 0.75f, true);
        this.capacity = capacity;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
        // Evict if size exceeds capacity
        return size() > capacity;
    }

    public static void main(String[] args) {
        LRUCache lru = new LRUCache(2);

        lru.put(1, 1);
        lru.put(2, 2);
        System.out.println(lru.get(1)); // 1

        lru.put(3, 3); // Evicts 2
        System.out.println(lru.get(2)); // null

        lru.put(4, 4); // Evicts 1
        System.out.println(lru.get(1)); // null
        System.out.println(lru.get(3)); // 3
        System.out.println(lru.get(4)); // 4
    }
}