Paging & Page Replacement (FIFO, LRU, Optimal)

Paging in one minute

Programs see a big, continuous virtual memory. The OS splits it into fixed-size pages (e.g. 4 KB) and RAM into equal-size frames. A page table maps each page to the frame that holds it:

virtual address = page number | offset
physical address = frame number | offset      (frame looked up in the page table)

Not every page needs to be in RAM at once. If a program touches a page that isn’t loaded, the hardware raises a page fault, and the OS loads the page from disk. Disk access is about 100,000× slower than RAM, so we want as few faults as possible.

Page replacement

When RAM is full and a new page is needed, the OS must evict a victim page. The rule it uses is the page replacement algorithm. In the 3D model, the RAM frames are on the left, and the grid shows the frame contents after each reference — H for hit, F for fault.

FIFO — First In, First Out

Evict the page that has been in memory the longest. Easy (just a queue), but it might throw out a page that’s used constantly.

LRU — Least Recently Used

Evict the page that hasn’t been used for the longest time. It relies on temporal locality: recently used pages are likely to be used again soon. Usually much better than FIFO. Real hardware approximates it with “reference bits” (the clock / second-chance algorithm).

Optimal (OPT / Belady’s algorithm)

Evict the page that will be used furthest in the future (or never). It gives the minimum possible number of faults — but needs to know the future, so it’s only a benchmark.

Worked example (3 frames)

Reference string 7 0 1 2 0 3 0 4 2 3 0 3 2:

Run all three in the model to watch where they differ.

Belady’s anomaly

You’d expect more RAM to always help. With FIFO it sometimes doesn’t! For the string 1 2 3 4 1 2 5 1 2 3 4 5, FIFO makes 9 faults with 3 frames but 10 with 4 frames. LRU and Optimal never show this anomaly (they are stack algorithms).

Code

def page_faults(refs, frames, policy="lru"):
    memory, faults, last_used, loaded = [], 0, {}, {}
    for i, p in enumerate(refs):
        if p in memory:
            last_used[p] = i                 # hit
            continue
        faults += 1                          # page fault
        if len(memory) == frames:
            if policy == "fifo":
                victim = min(memory, key=lambda q: loaded[q])
            elif policy == "lru":
                victim = min(memory, key=lambda q: last_used[q])
            else:                            # optimal
                future = refs[i + 1:]
                victim = max(memory, key=lambda q: future.index(q) if q in future else float("inf"))
            memory.remove(victim)
        memory.append(p)
        loaded[p] = last_used[p] = i
    return faults

refs = [7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2]
for pol in ("fifo", "lru", "opt"):
    print(pol, page_faults(refs, 3, pol))

Thrashing

If processes don’t have enough frames for their working set (the pages they actively use), almost every reference faults, and the system spends all its time swapping pages instead of doing work — thrashing. Fixes: give processes more frames, run fewer processes at once, or use the working-set model.

Common mistakes

• Counting the first loads into empty frames as hits — they are faults too (compulsory misses).
• In LRU, forgetting to update the “last used” time on a hit.
• Confusing pages (virtual, fixed-size) with segments (variable-size).