FIFO page replacement

FIFO replacement is the simplest possible rule, and it is the one a queue at a bakery already teaches you: first come, first served, and first to leave. The page that has been sitting in memory the longest is the one we evict next, no matter how useful it still is. Imagine a single line of pages, oldest at the front; when you must make room, you remove the page at the front and add the newcomer at the back.

The implementation needs almost nothing: the OS keeps the resident pages in a FIFO queue ordered by arrival time. On a page fault with no free frame, it removes the page at the head of the queue (the oldest), loads the new page, and puts the new page at the tail. There is no need to track usage, no timestamps to update on every access — just a queue. That cheapness is FIFO's only real virtue.

Why it matters mostly as a warning. FIFO ignores how heavily a page is being used, so it can happily evict a page the program references constantly just because that page arrived early — a classic case being a long-lived loop or a global variable that loaded first. Worse, FIFO is not a stack algorithm, so it can suffer Belady's anomaly: giving it more frames can actually cause more faults, which is deeply counterintuitive. For these reasons real systems do not use pure FIFO; they use LRU approximations like second-chance, which is itself a small fix bolted onto FIFO.