FIFO — Page Replacement

Overview

What this concept solves

FIFO — First-In, First-Out — is the simplest replacement rule there is: evict the page that has been in memory the longest. Treat the frames as a queue. A new page joins the back; when you need space, you drop whatever is at the front, regardless of how useful it still is.

It's appealing because it needs almost no bookkeeping. You don't track how often a page is used or when it was last touched — just the order pages arrived. A single queue (or a pointer that wraps around the frames) is enough.

The catch is that age is a bad proxy for usefulness. A page loaded early might be the one your program hits on every iteration — a configuration table, a hot loop's data — yet FIFO will happily evict it just because it's old. That blind spot is why FIFO is mostly a teaching baseline and the starting point the other algorithms improve on.

Mechanics

How it works

The rule, step by step

Page already in a frame? It's a hit. Do nothing — FIFO doesn't even reorder the queue on a hit.
Not in memory, but a frame is free? Load it into the free frame and put it at the back of the queue.
Not in memory and all frames full? Evict the page at the front of the queue (the oldest), load the new page, and put it at the back.

Belady's anomaly: more memory, more faults

You'd expect that giving a cache more frames can only help. For FIFO, that's not always true. On certain reference strings, going from 3 frames to 4 produces more page faults, not fewer. This is Belady's anomaly, and FIFO is the famous example. It happens because FIFO's eviction order isn't a 'stack' — the set of pages it keeps with 4 frames isn't guaranteed to be a superset of what it keeps with 3. LRU and Optimal are 'stack algorithms' and never suffer this. Run the prototype's Belady's anomaly preset at 3 frames, then bump it to 4.

Because FIFO ignores usage entirely, its worst case is brutal: a loop that cycles through slightly more pages than you have frames will fault on every single access, evicting each page just before it's needed again. The Worst case preset shows this.

Interactive prototype

Run it. Break it. Tune it.

Sandboxed simulation embedded right in the page. No setup, no install.

simulation › FIFO

About this simulation

Memory frames shown as a FIFO queue: pages enter at the right and leave from the left. Type a reference string, set the frame count, and step through. Each request is a hit (page already in a frame), a fault into a free frame, or a fault that evicts the oldest page. Try the Belady's anomaly preset, then raise the frame count and watch the faults go up.

Hands-on

Try these on your own

Open the prototype above, run each experiment, predict the answer, then verify.

try 01

Watch the queue evict the oldest

Load the Classic textbook preset and step forward. Watch the 'next out' tag sit on the front (oldest) frame and the 'just in' tag on the back. Notice FIFO never reorders on a hit — a page that gets reused still ages out on schedule.

try 02

Reproduce Belady's anomaly

Select the Belady's anomaly preset (it runs at 3 frames). Step to the end and note the total page faults. Now change the frame count to 4 and press Apply. Count the faults again — there are more with 4 frames than with 3. That's the anomaly: extra memory hurt FIFO.

try 03

Break it with a loop

Run the Worst case preset (a 5-page loop in 3 frames). Every access is a fault — FIFO evicts each page one step before it's needed again. Then try the Loop (warm cache) preset, where the working set fits, and watch the fault rate collapse. Same algorithm, opposite outcome, decided entirely by whether the loop fits.

In practice

When to use it — and what you give up

When FIFO is enough

As a baseline — to measure how much smarter policies actually buy you. If LRU isn't beating FIFO on your workload, recency may not be a useful signal.
When metadata is genuinely too expensive — in tiny embedded systems where you can't spare a bit per page or a timestamp, insertion order is free.
When access is roughly streaming — if pages really are used once in arrival order (a sequential scan), FIFO and the fancy policies behave about the same.
Avoid it for looping or hot-page workloads — anywhere a small working set is reused, FIFO will evict exactly the pages you're about to need.

Where you'll actually see it

Pure FIFO is rare in production replacement, precisely because of its blind spot and Belady's anomaly. But it's the skeleton of Second Chance and Clock, which keep FIFO's cheap queue and add a single 'was this used recently?' bit to fix the worst of its mistakes. Understanding FIFO is the prerequisite for understanding those.

Pros

Dead simple — a queue and nothing else; trivial to implement and reason about.
Minimal metadata — no timestamps, counters, or usage bits.
O(1) per access — enqueue/dequeue, no scanning.
Fair in one narrow sense — every page gets exactly the same lifetime before eviction.

Cons

Ignores usage — evicts hot pages just for being old.
Belady's anomaly — adding frames can increase faults, which breaks intuition and capacity planning.
Terrible on loops — can fault on every access when a working set barely exceeds memory.
Rarely competitive — a single reference bit (Second Chance / Clock) beats it for nearly the same cost.

Reference

Code & further reading

A minimal reference implementation and pointers worth bookmarking.

fifo.ts

// FIFO page replacement: evict the oldest-loaded page.
class FIFO {
  private frames: number;
  private resident = new Set<number>(); // pages currently in memory
  private queue: number[] = [];         // arrival order, front = oldest
  faults = 0;
  hits = 0;

  constructor(frames: number) { this.frames = frames; }

  access(page: number): "hit" | "fault" {
    if (this.resident.has(page)) {       // already in memory
      this.hits++;
      return "hit";                       // FIFO doesn't reorder on a hit
    }
    this.faults++;
    if (this.resident.size >= this.frames) {
      const victim = this.queue.shift()!; // evict the front (oldest)
      this.resident.delete(victim);
    }
    this.resident.add(page);
    this.queue.push(page);                // new page joins the back
    return "fault";
  }
}

References & further reading

4 sources

Knowledge check

Did the prototype land?

Quick questions, answers revealed on submit. No scoring saved.

question 01 / 03

On a page hit, what does FIFO do to its queue?

question 02 / 03

What is Belady's anomaly?

question 03 / 03

Why does FIFO perform so badly on a loop whose working set is one page larger than memory?

0/3 answered