FIFO, LRU, and Optimal: Three Different Bets on the Future
When physical memory frames are full and a new page needs to be loaded, an operating system must evict something — page replacement algorithms are really different strategies for guessing which page is safest to remove. FIFO evicts whichever page has been in memory longest, regardless of how recently or often it's been used — simple to implement, but can evict a heavily-used page purely because it happened to load first.
LRU (Least Recently Used) evicts the page that hasn't been accessed in the longest time, on the reasonable assumption that recent access predicts near-future access — this generally performs better than FIFO but requires tracking access recency, which has real implementation overhead. Optimal evicts whichever page won't be needed again for the longest time in the future — provably the best possible strategy, but requires knowing the future reference sequence in advance, making it purely a theoretical benchmark other algorithms are measured against, not something implementable in a real running system.
Comparing hit/miss counts across all three on the identical reference string is exactly how operating systems courses illustrate why LRU's added complexity is usually worth it over FIFO's simplicity.
Worked example
The classic reference string 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 with 3 frames gives:
- FIFO: 15 page faults and 5 hits (25% hit ratio)
- LRU: 12 page faults and 8 hits (40% hit ratio)
- Optimal: 9 page faults and 11 hits (55% hit ratio)
Optimal is the lower bound that no real algorithm can beat, and LRU lands between it and FIFO.
Belady's anomaly
With the reference string 1 2 3 4 1 2 5 1 2 3 4 5, FIFO makes 9 faults with 3 frames but 10 faults with 4 frames: more memory, more faults. LRU and Optimal are stack algorithms, so adding frames never increases their faults (LRU goes from 10 faults to 8 on the same string). Load the Belady example to see it in the faults-vs-frames row.
LFU, MFU and Second Chance
LFU evicts the page referenced the fewest times since it was loaded; MFU evicts the one referenced the most, on the theory that a heavily used page has finished its work. Both need a tie-break, and this calculator uses loading order (the oldest of the tied pages goes), the usual exam convention. A page's count restarts at 1 each time it is loaded again. On the classic string with 3 frames, LFU makes 13 faults and MFU 15.
Second Chance (the Clock algorithm) is FIFO with a reference bit per frame. A hit sets the bit to 1. On a fault the clock hand sweeps the frames: a page with bit 1 gets a second chance (its bit is cleared and the hand moves on), and the first page with bit 0 is replaced. A newly loaded page starts with bit 0. The table shows every frame's bit after each step, and the working names each page that was spared. Some textbooks start a new page at bit 1 instead, which can change the count, so check which rule your course uses.
Showing your working
Exams give marks for the working, not just the fault count. The step-by-step list gives one line per reference, for example: "Fault: 7 is replaced in frame 1 because it is the least recently used (last used at step 1)". Copy that reasoning alongside the frame table.
Where this fits
Page replacement decides which page leaves RAM when a new one is needed. The same question comes up one level up, between cache and RAM, in the cache mapping calculator, and one level down, when a process first asks for memory, in the memory allocation calculator (first, best, worst and next fit). The rest of the operating-systems toolkit covers CPU scheduling and disk scheduling.