FIFO Page Replacement

Virtual memory lets a process address more memory than physically exists. Its address space is cut into fixed-size pages; physical memory is cut into equally sized frames. Only the pages currently needed are loaded, and a page table records where each one lives.

When a process touches a page that is not resident, the hardware raises a page fault. The OS finds the page on disk, loads it into a free frame, updates the page table and restarts the faulting instruction. If there is no free frame, it must evict something first — and *which* page it evicts is the whole subject.

A page fault costs milliseconds against nanoseconds for a hit. A fault rate of even a few percent dominates the average access time entirely, which is why these policies matter so much.

Reference string

The sequence of page numbers a process touches, e.g. 7, 0, 1, 2, 0, 3… Every policy is evaluated against the same string so the comparison is fair.

Frame

One page-sized slot of physical memory. The number of frames a process gets is fixed in these examples.

Hit / page fault

The referenced page is resident, or it is not. Faults are what we are counting.

Fault rate

Faults ÷ total references. Lower is better, and it is the only score that matters.

Thrashing

When a process has so few frames that it faults constantly and spends all its time paging rather than computing.

Keep the resident pages in a queue ordered by load time. On a fault with memory full, evict the page at the head — the one that has been resident longest — and push the new page onto the tail. A single pointer implements it; no hardware support, no per-access bookkeeping.

The flaw is stated just as easily: age is not usage. A page loaded early and referenced constantly — a hot loop, a shared library — is exactly as evictable as one loaded early and never touched since.

You would expect more memory to mean fewer faults. Under FIFO that is not guaranteed. On the reference string 1 2 3 4 1 2 5 1 2 3 4 5:

Adding a frame made it worse. This is Belady's anomaly, and it happens because FIFO's set of resident pages with n frames is not necessarily a subset of the set with n + 1 frames — the eviction order genuinely changes shape.

Policies that cannot suffer it are called stack algorithms, and LRU and Optimal are both in that class. FIFO is not.

FIFO is too crude to ship, but it is nearly free, so real systems patch it rather than replace it. Second-chance (the clock algorithm) keeps the FIFO queue but consults each page's hardware reference bit before evicting: if the bit is set, clear it and move on rather than evicting. Pages that are actually being used survive; pages that are merely old do not. That is FIFO's cost with something close to LRU's behaviour, and it is what most kernels really use.