Lesson 4 · Memory management

FIFO Page Replacement and Belady's Anomaly

Evict the page that has been resident longest. The simplest policy there is — and the one that can get worse when you give it more memory.

What the FIFO Page Replacement Algorithm Is

The FIFO page replacement algorithm evicts the page that has been in memory the longest. Frames form a queue: a newly loaded page joins the tail, and when a victim is needed the page at the head — the oldest arrival — is removed.

Maintain the resident pages in arrival order, oldest at the head.
On a reference to a resident page, do nothing at all a hit does not move the page in the queue.
On a fault with a free frame, load the page and append it at the tail.
On a fault with no free frame, evict the page at the head, then append the new page at the tail.
Repeat. The victim is always the page that has been resident longest, regardless of use.

It is the cheapest policy to implement. One pointer into a circular array of frames is enough, no per-access bookkeeping is needed, and the choice of victim costs constant time.

The flaw is in what it measures. FIFO page replacement ranks pages by arrival time, and arrival time carries almost no information about future usefulness. A page loaded during startup and referenced on every iteration since is, by FIFO's reckoning, the oldest thing in memory and the first to go.

Crucially, a hit does not reorder the queue. Referencing a resident page under FIFO changes nothing about its eviction position — the queue records only when a page arrived, never how heavily it is used.

Decision rule: evict the oldest arrival
O(1) per fault, no hardware support required
Hits are invisible to the policy
Implemented as a circular buffer with a single pointer

FIFO Page Replacement Algorithm Example

This fifo page replacement algorithm example runs the standard string 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2 through three frames. Read the frame column left to right as the queue: head on the left, tail on the right.

The first three references fault into empty frames, leaving the queue [7, 0, 1]. Then the algorithm starts making decisions.

Reference 2 — fault, frames full. The head is 7, so 7 is evicted. Queue becomes [0, 1, 2]. Reference 0 — hit, and note carefully that the queue does not change: 0 stays at the head even though it was just used.

Reference 3 — fault. The head is 0, the page referenced one step earlier, and FIFO evicts it anyway. Queue [1, 2, 3]. This single decision is where FIFO loses to LRU: the very next reference is to 0.

Reference 0 — fault again, because FIFO just threw it out. Evict the head 1. Queue [2, 3, 0]. LRU, which would have kept 0, takes a hit here instead.

The run continues: 4 evicts 2, 2 evicts 3, 3 evicts 0, 0 evicts 4. The last two references, 3 and 2, are hits.

Total: 10 faults, 3 hits. LRU takes 9 on the same string, OPT takes 7. The whole one-fault gap to LRU traces back to that one decision at reference 3.

FIFO on 7,0,1,2,0,3,0,4,2,3,0,3,2 with 3 frames — queue shown head-first
Ref	Queue after (head → tail)	Event	Note
7	7	fault	empty frame
0	7 0	fault	empty frame
1	7 0 1	fault	empty frame
2	0 1 2	evict 7	oldest arrival
0	0 1 2	hit	queue unchanged — this is the flaw
3	1 2 3	evict 0	evicts a page used one step ago
0	2 3 0	evict 1	0 faults again immediately
4	3 0 4	evict 2	oldest arrival
2	0 4 2	evict 3	oldest arrival
3	4 2 3	evict 0	oldest arrival
0	2 3 0	evict 4	oldest arrival
3	2 3 0	hit	—
2	2 3 0	hit	—
Total	—	10 faults	LRU 9 · OPT 7

10 faults, 3 hits on the standard string
The hit at reference 4 leaves the queue completely unchanged
Evicting 0 at reference 5 causes an immediate re-fault
Seven of the ten faults required an eviction

Key reference

Terms, operations, and practical uses

The rule

DecisionEvict the page at the head — the oldest arrival.
Hits ignoredUsing a page does not move it in the queue.
CostO(1) per fault; one pointer into a circular buffer.
StructureA plain FIFO queue: new pages join the tail.

Belady's anomaly

The string1,2,3,4,1,2,5,1,2,3,4,5 — the classic demonstration.
3 frames9 faults.
4 frames10 faults — more memory, worse result.
CauseFIFO's resident sets do not nest as frames are added.

Cost and use

10 faultsOn the standard string; LRU takes 9, OPT 7.
The flawArrival order does not predict future usefulness.
Still usefulFine where there is no temporal locality to exploit.
DescendantsSecond-chance and clock are FIFO plus a reference bit.

Implementation

FIFO on the standard reference string

from collections import deque


def fifo(refs, frames):
    """FIFO page replacement. Returns (faults, hits).

    The queue records arrival order only. A hit deliberately does not reorder
    it -- that omission is the algorithm, and the reason it can be beaten.
    """
    queue, resident, faults, hits = deque(), set(), 0, 0

    for page in refs:
        if page in resident:
            hits += 1
            continue  # a hit changes nothing about eviction order

        faults += 1
        if len(queue) == frames:
            evicted = queue.popleft()
            resident.remove(evicted)

        queue.append(page)
        resident.add(page)

    return faults, hits


refs = [7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2]
print(fifo(refs, 3))  # (10, 3)

# Belady's anomaly: more frames, more faults.
belady = [1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5]
print(fifo(belady, 3)[0], fifo(belady, 4)[0])  # 9 10

#include <deque>
#include <iostream>
#include <unordered_set>
#include <vector>
// FIFO page replacement: evict the oldest arrival. A hit does not reorder
// the queue, which is exactly why FIFO evicts pages that are still hot.
int fifo(const std::vector<int>& refs, int frames, int& hits) {
    std::deque<int> queue;
    std::unordered_set<int> resident;
    int faults = 0;
    hits = 0;
    for (int page : refs) {
        if (resident.count(page)) {
            ++hits;
            continue;
        }
        ++faults;
        if (static_cast<int>(queue.size()) == frames) {
            resident.erase(queue.front());
            queue.pop_front();
        }
        queue.push_back(page);
        resident.insert(page);
    }
    return faults;
}
int main() {
    std::vector<int> refs = {7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2};
    int hits = 0;
    std::cout << fifo(refs, 3, hits) << " faults\n"; // 10 faults
    // Belady's anomaly.
    std::vector<int> belady = {1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5};
    std::cout << fifo(belady, 3, hits) << " vs " << fifo(belady, 4, hits) << "\n";
    return 0;
}

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashSet;
import java.util.Set;
public class FifoPageReplacement {
    /** Evicts the oldest arrival. Hits never reorder the queue. */
    static int fifo(int[] refs, int frames) {
        Deque<Integer> queue = new ArrayDeque<>();
        Set<Integer> resident = new HashSet<>();
        int faults = 0;
        for (int page : refs) {
            if (resident.contains(page)) {
                continue;
            }
            faults++;
            if (queue.size() == frames) {
                resident.remove(queue.removeFirst());
            }
            queue.addLast(page);
            resident.add(page);
        }
        return faults;
    }
    public static void main(String[] args) {
        int[] refs = {7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2};
        System.out.println(fifo(refs, 3) + " faults");
        // Belady's anomaly: 3 frames beat 4.
        int[] belady = {1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5};
        System.out.println(fifo(belady, 3) + " vs " + fifo(belady, 4));
    }
}

Watch it run

Step through it

Running on refs 7,0,1,2,0,3,0,4,2,3,0,3,2 · 3 frames

Output

Belady's Anomaly: More Frames, More Faults

Intuition says more memory cannot hurt. Belady's anomaly is the demonstration that under FIFO it can — adding a frame can increase the number of page faults. It is a genuine property of the algorithm, not an artefact of a badly chosen example.

The classic string is 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5. Run it under FIFO with three frames and you take 9 faults. Run the identical string with four frames and you take 10. A hardware upgrade makes the system measurably worse.

The mechanism is that FIFO's resident set is not nested. With three frames the pages held at a given moment are not guaranteed to be a subset of those held with four frames, so a larger memory can hold a different — and worse — collection of pages, not merely a superset.

Algorithms whose resident sets do nest are called stack algorithms, and they are provably immune. LRU and OPT are both in this class: with them, more frames can never mean more faults. FIFO is not, and neither is clock in general, though the effect is rare in practice.

1,2,3,4,1,2,5,1,2,3,4,5 under FIFO — the anomaly in numbers
Frames	Faults	Expected	Result
3	9	—	baseline
4	10	≤ 9	one fault worse with more memory

3 frames → 9 faults; 4 frames → 10 faults
Caused by FIFO's resident sets not nesting as frames grow
Stack algorithms (LRU, OPT) cannot exhibit it
A favourite exam question — know the string and both counts

Where FIFO Still Makes Sense

FIFO survives where its weakness does not apply. When accesses have no temporal locality — a sequential scan through a file touching each block exactly once — recency predicts nothing, so LRU's extra bookkeeping buys nothing and FIFO's simplicity wins.

It also anchors the hybrids. Second-chance is FIFO plus one reference bit: the queue is still FIFO, but a page whose bit is set is moved to the tail rather than evicted. Clock is the same idea implemented as a circular buffer, and it is what real kernels approximate.

In teaching, FIFO's role is to establish why replacement is hard. It is the natural first guess, it is easy to trace by hand, and its failure — evicting a page that was used one step ago — motivates every algorithm that follows.

Fine where there is no temporal locality to exploit
The base that second-chance and clock build on
Used in some buffer pools where predictable cost matters more than hit rate
The standard teaching baseline for page replacement