Page replacement: FIFO, LRU, and optimal
Count page faults for three replacement policies and see Belady's anomaly with FIFO.
def fifo(refs, frames):
memory, faults = [], 0
for page in refs:
if page not in memory:
faults += 1
if len(memory) == frames:
memory.pop(0)
memory.append(page)
return faults
def lru(refs, frames):
memory, faults = [], 0
for page in refs:
if page in memory:
memory.remove(page)
else:
faults += 1
if len(memory) == frames:
memory.pop(0)
memory.append(page)
return faults
def optimal(refs, frames):
memory, faults = [], 0
for i, page in enumerate(refs):
if page in memory:
continue
faults += 1
if len(memory) == frames:
future = refs[i + 1:]
victim = max(memory, key=lambda p: future.index(p) if p in future else len(future) + 1)
memory.remove(victim)
memory.append(page)
return faults
refs = [7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1]
print(fifo(refs, 3), lru(refs, 3), optimal(refs, 3))
belady = [1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5]
print(fifo(belady, 3), fifo(belady, 4))15 12 9 9 10
Explanation
With demand paging, a process's pages are loaded into physical memory frames only when they are used. When a page that is not in memory is accessed, a page fault occurs. If every frame is full, the operating system must choose a victim page to evict. The replacement policy decides which one.
FIFO evicts the page that has been in memory longest. LRU (least recently used) evicts the page that has gone unused for the longest time, assuming the recent past predicts the near future. The optimal policy evicts the page whose next use is farthest in the future. It cannot be implemented in a real system because it needs the future, but it gives a lower bound to compare against.
For the classic reference string with three frames, FIFO causes 15 faults, LRU 12, and optimal 9. FIFO also shows Belady's anomaly: for some reference strings, giving the process more frames produces more faults. The program prints 9 faults for three frames and 10 for four on one such string. LRU and optimal are stack algorithms and cannot show the anomaly. Real systems approximate LRU, for example with the clock algorithm, because exact LRU is costly to maintain.
Explore the dry run
def fifo(refs, frames): memory, faults = [], 0 for page in refs: if page not in memory: faults += 1 if len(memory) == frames: memory.pop(0) memory.append(page) return faults def lru(refs, frames): memory, faults = [], 0 for page in refs: if page in memory: memory.remove(page) else: faults += 1 if len(memory) == frames: memory.pop(0) memory.append(page) return faults def optimal(refs, frames): memory, faults = [], 0 for i, page in enumerate(refs): if page in memory: continue faults += 1 if len(memory) == frames: future = refs[i + 1:] victim = max(memory, key=lambda p: future.index(p) if p in future else len(future) + 1) memory.remove(victim) memory.append(page) return faults refs = [7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1]print(fifo(refs, 3), lru(refs, 3), optimal(refs, 3))belady = [1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5]print(fifo(belady, 3), fifo(belady, 4))Follow the example
Start to inspect the source, values, and output. These prepared steps explain the published sample; grouped loop steps describe multiple iterations.
View the complete dry-run table
| Step / line | What happens | State after step | Output so far |
|---|---|---|---|
| FIFO evicts the oldest resident page, the one at the front of the list. | — | — | |
| LRU moves a re-used page to the most-recent end, so the front is always the least recently used. | — | — | |
| Optimal evicts the page used farthest in the future, or never again. | uses the future reference string | — | |
| On the classic string with 3 frames: FIFO 15, LRU 12, optimal 9 faults. | uses the future reference string | 15 12 9 | |
| FIFO with 4 frames faults more than with 3: Belady's anomaly. | uses the future reference string | 15 12 9 9 10 |
Cost and common mistakes
Each policy here is O(n·f) for n references and f frames because of list searches. Optimal adds a scan of the remaining references on each fault.
- Optimal is a benchmark, not an algorithm a kernel can run, because it requires knowing future references.
- Exact LRU needs bookkeeping on every memory access, so hardware and kernels approximate it with reference bits.
- Thrashing happens when a process has too few frames: it spends more time handling page faults than executing.
Try it yourself
How many faults does LRU produce for the Belady string with 3 frames, and with 4 frames?
Reveal answer and reasoning
10 faults with 3 frames and 8 with 4 frames. LRU is a stack algorithm, so adding frames can never increase the number of faults.