FIFO: just evict the oldest
From guide 1 you have the whole stage set: a reference string of pages a process touches, a fixed number of frames, and a score — the page-fault rate — that we want to push as low as possible. Now we need an actual rule for choosing the victim. The simplest imaginable rule is FIFO, first-in first-out: when a frame must be freed, evict whichever page has been resident the longest — the one that came in earliest. Picture a queue at a bakery counter: the customer who has waited longest is served and leaves first, no matter who they are.
The appeal of FIFO is that it is almost free to implement. The OS keeps the resident pages in a simple queue: every time a page is loaded, append it to the tail; when it is time to evict, remove from the head. No bit-watching, no timestamps, no scanning — just a pointer to the oldest page. That cheapness is the whole reason FIFO is worth knowing. But cheapness has a cost hiding inside it: FIFO measures only one thing, how long ago a page arrived, and pays no attention at all to whether the page is still being used.
That blind spot is FIFO's fatal flaw. Think of a page holding a program's core loop, or a heavily-used global variable: it gets touched on almost every instruction, yet by FIFO's clock it is simply old. FIFO will happily evict that busy page just because it was loaded early — and then the very next reference faults it right back in. A page can churn out and in repeatedly while staying constantly in use, which is exactly the kind of waste a good policy must avoid. So FIFO is the honest baseline: trivial to build, but it confuses old with useless, and those are not the same thing.
Tracing FIFO by hand
Nothing makes a policy concrete like walking a reference string by hand, so let us trace FIFO with 3 frames on the string 7 0 1 2 0 3 0 4. We read it left to right; at each step a page already resident is a hit, while a page not resident is a fault that loads the page, evicting the oldest if all three frames are already full. Keep one fact in your head as we go: the oldest resident page is whoever FIFO will evict next.
- References 7, 0, 1 (steps 1-3): the three frames start empty, so each new page just faults in and takes a slot. Frames now hold {7, 0, 1}, with 7 the oldest. Three faults so far.
- Reference 2 (step 4): a fault, and all frames are full. FIFO evicts the oldest, which is 7, and 2 takes its place. Frames now {2, 0, 1}, with 0 the oldest. Four faults.
- Reference 0 (step 5): page 0 is still resident, so this is a hit — our only one on the whole string. Nothing is loaded or evicted.
- Reference 3 (step 6): a fault. The oldest is now 0, so FIFO evicts 0 even though it was just used at step 5. Frames now {2, 3, 1}. Five faults.
- Reference 0 then 4 (steps 7-8): 0 was just thrown out, so it faults straight back in (evicting 1); then 4 faults too. The wasted round-trip on 0 — out at step 6, back at step 7 — is FIFO's age-only rule doing damage. Final tally: 7 faults in 8 references.
OPT: the policy that cheats with the future
How good could a policy be? To answer that we need a yardstick that no real policy can beat, and there is exactly one: the optimal algorithm, usually written OPT (or MIN). Its rule is breathtakingly simple to state — when you must evict, throw out the page that will not be needed for the longest time into the future. Look ahead in the reference string, find which resident page's next use is furthest away (or never comes), and evict that one. Intuitively this is obviously right: the page you will need soonest is the one you most want to keep.
Let us run OPT on the same string, 7 0 1 2 0 3 0 4 with 3 frames, and compare. The first three references fill the frames (3 faults), just like before. At step 4, page 2 faults with frames holding {7, 0, 1}; look ahead — 7 is never used again, 0 is used next at step 5, 1 is never used again. Both 7 and 1 are 'never again', so either is a fine victim; evict 7. Step 5 (0) is a hit. At step 6, page 3 faults with {2, 0, 1}; looking ahead, 0 is used again at step 7, while 2 and 1 are never used again — so evict 2 or 1, not 0. Crucially OPT keeps 0, so step 7 (0) is now a hit. OPT scores 5 faults to FIFO's 7 on the very same string.
Belady's anomaly: when more memory hurts
Guide 1 promised a surprise, and here it is. Common sense says more frames means fewer faults: give a process more room and it should hold more of its pages, so it should miss less. For most policies this holds. But for FIFO it can fail outright — adding a frame can make the fault count go up. This is Belady's anomaly, discovered by László Bélády in 1969, and it feels like it cannot be true until you watch it happen.
Belady's anomaly with FIFO string: 1 2 3 4 1 2 5 1 2 3 4 5 --- 3 frames --- --- 4 frames --- ref frames F/H ref frames F/H 1 1 F 1 1 F 2 1 2 F 2 1 2 F 3 1 2 3 F 3 1 2 3 F 4 2 3 4 F 4 1 2 3 4 F 1 3 4 1 F 1 1 2 3 4 H 2 4 1 2 F 2 1 2 3 4 H 5 1 2 5 F 5 2 3 4 5 F 1 1 2 5 H 1 3 4 5 1 F 2 1 2 5 H 2 4 5 1 2 F 3 2 5 3 F 3 5 1 2 3 F 4 5 3 4 F 4 1 2 3 4 F 5 3 4 5 F 5 2 3 4 5 F 3 frames -> 9 faults 4 frames -> 10 faults (!)
Count the F's: with 3 frames FIFO faults 9 times, but with 4 frames it faults 10 times. More memory made it worse. Why does this happen? Because FIFO's victim choice depends on arrival order, and changing the frame count reshuffles that order entirely — the set of pages resident with 4 frames at a given moment is not just the 3-frame set plus one extra. The two configurations make genuinely different eviction decisions, and FIFO has no rule forcing the bigger one to be a superset of the smaller. So the bigger pool can happen to evict a page right before it is needed in a way the smaller pool did not.
What FIFO and OPT teach us
Stand back and these two policies bracket the whole problem from below and above. OPT is the floor on faults — the best any policy could ever do on a given string — but it is unbuildable because it needs the future. FIFO is the cheapest thing that works at all — trivial to implement — but it can be poor and, worse, it can misbehave with Belady's anomaly. Every realistic page-replacement policy lives in the gap between them, and the engineering question is always the same: how close to OPT can we get using only information we actually have?
The decisive clue is what each policy looks at. OPT looks at the future (impossible). FIFO looks at arrival order (cheap, but irrelevant to whether a page is still useful). The missing ingredient is recent use — and the reason recent use is such a good guide is locality of reference, which you met back in the demand-paging rung: a program that touched a page recently is very likely to touch it again soon. The past, in other words, is a cheap and usually-honest forecast of the near future. That single insight is the bridge to the next guide.
So the plan for guide 3 writes itself: approximate OPT's look-into-the-future by looking into the past instead — evict the page that was used least recently, the policy called LRU. We will see that true LRU matches OPT's good behaviour (no Belady's anomaly) but is too expensive to implement exactly in hardware, which forces us into clever cheap approximations: aging, and the second-chance or clock algorithm that quietly rescues FIFO's busy pages from eviction. FIFO and OPT were the two extremes; everything practical lives in between.