Page Replacement Algorithms: FIFO, LRU, Optimal and Clock
When Memory Is Full, What Gets Thrown Out?
When memory runs out, page replacement algorithms decide what the operating system throws out. With virtual memory, programs are divided into fixed-size blocks called pages, and only some of them fit in RAM at once. When a program needs a page that is not in memory, a page fault occurs: the operating system must fetch the page from disk, which is thousands of times slower than reading RAM. If memory is already full, it must first choose a page to evict. A good choice keeps the pages that will be needed soon; a bad one causes more faults and a slow, struggling computer. This tutorial simulates the classic algorithms (FIFO, Optimal, LRU and the Clock or second-chance algorithm) in Python on the same reference string, counts the page faults, demonstrates Belady's anomaly, and explains thrashing. All outputs come from running the code.
Key Terms
- Frame: a slot in physical memory that can hold one page.
- Reference string: the sequence of page numbers a program accesses, used to compare algorithms.
- Page hit: the page is already in a frame. Page fault: it isn't, and must be loaded.
- Fewer faults means a better algorithm for that workload. The hit ratio is hits ÷ references.
We use a classic textbook reference string and 3 frames throughout:
from collections import deque, OrderedDict
REFS = [7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1]
FRAMES = 3
def show(name, faults, history):
print(f"{name}: {faults} faults out of {len(REFS)} references")
print(" " + " ".join(history))
In the history line, each fault shows the page that was loaded, and each hit shows a dot.
FIFO: First In, First Out
Evict the page that has been in memory the longest, using a simple queue. It is easy to implement but ignores how often or how recently a page is used.
def fifo(refs, frames):
memory, queue = set(), deque()
faults, history = 0, []
for page in refs:
if page in memory:
history.append(".")
continue
faults += 1
history.append(str(page))
if len(memory) == frames:
memory.remove(queue.popleft()) # oldest arrival leaves
memory.add(page)
queue.append(page)
return faults, history
show("FIFO", *fifo(REFS, FRAMES))
Output:
FIFO: 15 faults out of 20 references 7 0 1 2 . 3 0 4 2 3 0 . . 1 2 . . 7 0 1
FIFO evicted page 0 at the 6th reference even though page 0 was used again immediately afterwards, causing an extra fault.
Optimal (OPT): The Theoretical Best
Evict the page that will not be used for the longest time in the future. This gives the minimum possible number of faults, but a real operating system can't use it, because it can't see the future. It is the benchmark other algorithms are measured against.
def optimal(refs, frames):
memory, faults, history = [], 0, []
for i, page in enumerate(refs):
if page in memory:
history.append(".")
continue
faults += 1
history.append(str(page))
if len(memory) < frames:
memory.append(page)
continue
future = refs[i + 1:]
# distance to next use; pages never used again count as infinitely far
def next_use(p):
return future.index(p) if p in future else float("inf")
victim = max(memory, key=next_use)
memory[memory.index(victim)] = page
return faults, history
show("Optimal", *optimal(REFS, FRAMES))
Output:
Optimal: 9 faults out of 20 references 7 0 1 2 . 3 . 4 . . 0 . . 1 . . . 7 . .
LRU: Least Recently Used
LRU approximates Optimal by looking at the past instead of the future: evict the page that hasn't been used for the longest time. Programs tend to reuse recently used pages (locality of reference), so this usually works well. An OrderedDict keeps pages in order of last use:
def lru(refs, frames):
memory = OrderedDict()
faults, history = 0, []
for page in refs:
if page in memory:
memory.move_to_end(page) # mark as most recently used
history.append(".")
continue
faults += 1
history.append(str(page))
if len(memory) == frames:
memory.popitem(last=False) # least recently used is at the front
memory[page] = True
return faults, history
show("LRU", *lru(REFS, FRAMES))
Output:
LRU: 12 faults out of 20 references 7 0 1 2 . 3 . 4 2 3 0 . . 1 . 0 . 7 . .
LRU's 12 faults sit between Optimal's 9 and FIFO's 15. The catch is cost: exact LRU must update a record on every memory access, which is far too expensive to do in software for real RAM, so hardware and operating systems use approximations.
The Clock (Second-Chance) Algorithm
The Clock algorithm is the practical approximation of LRU used, in variations, by real operating systems. Each frame has a reference bit, which the hardware sets to 1 whenever the page is accessed. Frames are arranged in a circle with a "hand" pointing at one of them. To find a victim:
- if the frame under the hand has reference bit 1, clear it to 0 (giving the page a second chance) and move the hand on;
- if the bit is 0, evict that page.
def clock(refs, frames):
pages = [None] * frames
ref_bit = [0] * frames
hand, faults, history = 0, 0, []
for page in refs:
if page in pages:
ref_bit[pages.index(page)] = 1
history.append(".")
continue
faults += 1
history.append(str(page))
while ref_bit[hand] == 1: # skip recently used pages, clearing their bits
ref_bit[hand] = 0
hand = (hand + 1) % frames
pages[hand], ref_bit[hand] = page, 1
hand = (hand + 1) % frames
return faults, history
show("Clock", *clock(REFS, FRAMES))
Output:
Clock: 14 faults out of 20 references 7 0 1 2 . 3 . 4 2 . 0 3 . 1 2 0 . 7 . 1
On this short string the Clock algorithm does only slightly better than FIFO, because with three frames almost every page gets its reference bit set. On real workloads with more frames, it performs close to LRU at a tiny fraction of the cost: it only needs one bit per frame, set by the hardware.
Comparing the Page Replacement Algorithms
for frames in [2, 3, 4, 5]:
results = {name: f(REFS, frames)[0] for name, f in
[("FIFO", fifo), ("LRU", lru), ("Clock", clock), ("OPT", optimal)]}
print(frames, "frames:", results)
Output:
2 frames: {'FIFO': 15, 'LRU': 17, 'Clock': 15, 'OPT': 13}
3 frames: {'FIFO': 15, 'LRU': 12, 'Clock': 14, 'OPT': 9}
4 frames: {'FIFO': 10, 'LRU': 8, 'Clock': 9, 'OPT': 8}
5 frames: {'FIFO': 9, 'LRU': 7, 'Clock': 9, 'OPT': 7}
More frames generally means fewer faults, and Optimal is always lowest. With 3 or more frames LRU stays close to Optimal (with 5 frames it matches it). But with only 2 frames, LRU does worse than FIFO on this string: no practical algorithm wins on every workload, which is why designers test them on realistic traces. Adding memory also has diminishing returns once the program's working set fits.
Belady's Anomaly
You would expect more frames always to mean fewer (or equal) faults. Surprisingly, for FIFO this is not always true:
belady = [1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5]
for frames in [3, 4]:
print(f"FIFO with {frames} frames: {fifo(belady, frames)[0]} faults; "
f"LRU: {lru(belady, frames)[0]} faults")
Output:
FIFO with 3 frames: 9 faults; LRU: 10 faults FIFO with 4 frames: 10 faults; LRU: 8 faults
With FIFO, going from 3 frames to 4 increases the faults from 9 to 10. This is Belady's anomaly, discovered by László Bélády in 1969. LRU and Optimal never suffer from it: they are "stack algorithms", meaning the set of pages kept with n frames is always contained in the set kept with n + 1 frames.
Thrashing
If the processes running together need more pages than there are frames, almost every access causes a page fault. The computer spends nearly all its time moving pages between disk and memory and almost none doing useful work. This is thrashing, the reason a laptop with too many browser tabs open can suddenly become unusably slow, with the disk light constantly on. Remedies include running fewer programs at once, adding RAM, and operating system policies based on each process's working set (the pages it has used recently), which suspend some processes when the total working set exceeds memory.
Summary
- A page fault happens when a needed page is not in memory; page replacement algorithms choose which page to evict.
- FIFO evicts the oldest page: simple, but it can evict busy pages and suffers from Belady's anomaly.
- Optimal evicts the page used furthest in the future: the minimum faults, but impossible in practice.
- LRU evicts the least recently used page and performs close to Optimal; Clock (second chance) approximates it cheaply with reference bits.
- Too little memory for the working sets causes thrashing.