Page Replacement Algorithms (FIFO, LRU, Optimal)

When Physical Memory Is Full, Something Must Be Removed

Since virtual memory (covered earlier in this section) can exceed physical RAM, sometimes a page currently in memory must be swapped out to disk to make room for a newly needed page - the specific rule for choosing which page to remove is what a page replacement algorithm decides.

FIFO: Remove Whichever Page Has Been in Memory Longest

Page requests: 1, 2, 3, 4, 1, 2, 5

Memory (3 frames), FIFO:
1        -> [1]
2        -> [1,2]
3        -> [1,2,3]
4        -> [2,3,4]  (1 removed - it entered first)
1        -> [3,4,1]  (2 removed - it entered first among remaining)
2        -> [4,1,2]  (3 removed)
5        -> [1,2,5]  (4 removed)

FIFO simply removes whichever page has been sitting in memory the longest, regardless of how recently or frequently it's actually been used - simple to implement, but can remove a page that's still being actively used, purely because it happened to arrive first.

LRU: Remove Whichever Page Was Used Longest Ago

Same requests: 1, 2, 3, 4, 1, 2, 5

Memory (3 frames), LRU:
1        -> [1]
2        -> [1,2]
3        -> [1,2,3]
4        -> [2,3,4]  (1 removed - least recently used)
1        -> [3,4,1]  (2 removed - least recently used)
2        -> [4,1,2]  (3 removed - least recently used)
5        -> [1,2,5]  (4 removed - least recently used)

LRU (Least Recently Used) removes whichever page hasn't been accessed for the longest time, based on the reasonable assumption that a page unused recently is less likely to be needed again soon - generally performs noticeably better than FIFO in practice, though it requires tracking access history, which adds real overhead.

Optimal: A Theoretical Best Case, Not Actually Implementable

The Optimal algorithm removes whichever page won't be needed again for the longest time in the future - genuinely the best possible choice, but it requires knowing the future sequence of page requests in advance, which is impossible in a real running system. It exists purely as a theoretical benchmark to measure how close other, actually-implementable algorithms come to ideal performance.

Comparing the Three