optimal page replacement
Imagine you could peek at the rest of the day before deciding which book to put back: you would obviously remove the book you will not need for the longest time. The optimal page-replacement algorithm — called OPT or MIN — does exactly that. When it must choose a victim, it evicts the page that will not be referenced again for the longest time into the future. By definition this produces the fewest possible page faults for a given reference string and frame count.
The procedure is simple to state. On a fault with full memory, look ahead in the reference string for each resident page and find when each will next be used; evict the one whose next use is farthest away (or that is never used again). For example, with frames holding pages that will next be needed at steps 6, 9, and 14, you evict the page needed at step 14. Repeat at every fault. Because it always makes the best individual choice given perfect foresight, no other algorithm can ever beat its fault count.
Why it matters even though it cannot be built: OPT needs to know the future — the exact sequence of pages a program will touch — which is impossible for a real, running program. So it is never used for actual replacement. Instead it is the gold-standard benchmark: you run OPT on a recorded reference string to learn the theoretical minimum number of faults, then measure how close a real algorithm like LRU comes to that floor. OPT also happens to be a stack algorithm, so it never suffers Belady's anomaly.
Frames = 3 hold pages 2, 0, 3. The upcoming references are 0, 4, 2, 3, 0. Page 0 is used next (soon), page 2 a bit later, page 3 later still, and 4 is brand new. To load 4 OPT evicts 3 — the resident page used farthest in the future.
Evict the page whose next use is farthest away — provably the fewest faults.
Optimal cannot be implemented because it requires knowledge of the future; its only real role is as the unbeatable lower bound that practical algorithms (like LRU) are measured against.