When physical memory becomes full and the operating system must bring in a new page, it faces a fundamental decision: which existing page should be evicted? This decision—seemingly simple—has profound implications for system performance, user experience, and overall computing efficiency.

Among the many strategies devised to answer this question, the First-In, First-Out (FIFO) algorithm stands as the most intuitive approach. Just as customers in a queue are served in the order they arrived, FIFO evicts pages in the order they were loaded into memory. The page that has been resident the longest becomes the victim when space is needed.

This elegance of concept, however, conceals surprising complexity in practice. FIFO's simplicity comes with trade-offs that reveal deep truths about memory access patterns, the limitations of age-based reasoning, and the counterintuitive nature of caching systems.

Before diving into FIFO specifically, let's establish the context in which page replacement algorithms operate. This foundation is essential for understanding why FIFO was designed as it was and what problems it attempts to solve.

The Over-Allocation Problem:

Virtual memory systems allow processes to have address spaces larger than physical RAM. This creates a fundamental tension: at any moment, the sum of all virtual addresses in use may exceed available physical frames. The operating system maintains the illusion of abundant memory by keeping only actively-used pages in RAM and storing the rest on disk.

This illusion persists until a process references a page not currently in memory—a page fault. When a page fault occurs with no free frames available, the OS must choose a victim page to evict. This choice is the page replacement decision.

The Information Asymmetry:

The fundamental challenge of page replacement is an information asymmetry. The optimal algorithm (OPT) would evict the page that won't be used for the longest time in the future. But the operating system cannot see the future—it can only observe the past and present.

This creates a design space where algorithms must use observable information (when pages were loaded, when they were last accessed, how often they've been accessed) to predict future behavior (which pages will be needed again soon).

FIFO represents the simplest possible approach to this prediction problem: it uses only the arrival time of each page, assuming that pages loaded long ago are less likely to be needed than pages loaded recently.

The First-In, First-Out principle is rooted in a specific hypothesis about memory access patterns:

The FIFO Hypothesis: Pages that have been resident in memory for a long time are less likely to be accessed in the near future than pages that arrived recently.

This hypothesis treats residence time as a proxy for future access probability. It assumes that when a page is first loaded, it represents a currently active part of the workload. As time passes and newer pages arrive, older pages represent increasingly obsolete portions of the program's execution.

The Queue Mental Model:

FIFO maintains an implicit or explicit ordering of pages by their arrival time. Conceptually, this forms a queue:

• When a page is loaded, it enters the back of the queue (most recently arrived)
• When a victim is needed, the page at the front of the queue is evicted (longest resident)
• Pages in the middle are ordered by arrival time, with older pages closer to the front

Formal Definition:

Let t(p) denote the time at which page p was loaded into memory. Given that we must evict one page from the set of currently resident pages R, FIFO selects:

victim = argmin{t(p) : p ∈ R}

In other words, FIFO always evicts the page with the smallest (earliest) load time.

Key Properties of FIFO:

The FIFO hypothesis—that older pages are less useful—is sometimes valid. Understanding when it holds helps us predict where FIFO will perform well.

Scenario 1: Sequential Linear Access

Consider a program that processes a large file or dataset sequentially:

for each record in file:
    process(record)
    move to next

Each record is accessed once and never again. Older pages contain already-processed data. FIFO naturally evicts these obsolete pages, performing optimally in this workload.

Scenario 2: Phase-Based Execution

Some programs execute in distinct phases, where each phase uses a different working set:

• Initialization phase: loads configuration, sets up data structures
• Processing phase: operates on a different set of data
• Cleanup phase: writes results, releases resources

When phases are sequential and non-overlapping, pages from earlier phases become obsolete when later phases begin. FIFO's age-based eviction aligns with this pattern.

Unfortunately, many real workloads violate the FIFO hypothesis catastrophically. The assumption that older pages are less useful breaks down in several common scenarios.

Scenario 1: Frequently Accessed Old Pages

Consider a program with a main loop that repeatedly calls core functions:

while not done:
    result = core_computation(data)  # Same pages every iteration
    data = get_next_input()          # Different pages each time

The code pages for core_computation were loaded early (they're old), but they're accessed every single iteration. FIFO might evict these critical pages to make room for transient input data, causing repeated page faults for the most frequently used pages.

Scenario 2: Looping Access Patterns

Programs often iterate through data structures repeatedly:

The Core Problem:

FIFO conflates two distinct concepts:

Recency is typically a much better predictor of future access than age. A page loaded an hour ago but accessed one millisecond ago is likely more useful than a page loaded one second ago but never accessed since.

FIFO cannot distinguish between:

• An old page that's used constantly (high value, should keep)
• An old page that was used once and abandoned (low value, should evict)

Both have the same age; FIFO treats them identically.

To fully understand FIFO, it helps to position it relative to other page replacement strategies. Each algorithm makes different trade-offs between simplicity, overhead, and quality of victim selection.

The Algorithm Spectrum:

FIFO's Position:

FIFO occupies a unique position in this spectrum:

1. One step above random: Unlike random replacement, FIFO has a consistent, deterministic policy. Given the same sequence of page references, FIFO always produces the same eviction decisions.

2. One step below usage-aware: Unlike LRU or LFU, FIFO doesn't track how pages are used after loading. This makes it simpler but less adaptive.

3. Much simpler than optimal: OPT requires future knowledge; FIFO requires only past knowledge (specifically, just one piece of data: load time).

The Trade-off FIFO Makes:

The concept of the working set provides crucial insight into when FIFO succeeds or fails.

Working Set Definition:

The working set W(t, Δ) at time t with window Δ is the set of pages referenced during the time interval (t - Δ, t). Informally, it's "the set of pages a process is actively using."

For most programs, the working set size varies over time but remains much smaller than the total address space. A process might touch thousands of pages over its lifetime, but at any given moment, only a small subset is actively needed.

FIFO's Relationship to Working Set:

FIFO's behavior relative to the working set determines its effectiveness:

The Critical Insight:

When there are significantly more frames than the working set size, most algorithms—including FIFO—perform well. There's enough memory to hold everything important, so evicting old pages rarely causes problems.

The algorithms diverge when memory is tight. When frames approximately equal or are less than the working set size, the quality of eviction decisions becomes critical. Here, FIFO's inability to identify actually-needed pages becomes a serious liability.

Working Set Stability:

Programs with stable working sets (the same pages stay active for extended periods) can suffer badly under FIFO. The oldest pages might be the most important ones—they've been in the working set since the beginning.

Programs with shifting working sets (new phases bring entirely new page sets) may fare better under FIFO. When new phases begin, old pages genuinely become obsolete.

FIFO's simplicity made it attractive in early computing systems where resources for complex page replacement logic were limited.

Early Systems and Resource Constraints:

The first virtual memory systems emerged in the 1960s (Atlas, Multics, IBM System/360 Model 67). These systems had:

• Limited Memory: Tiny by modern standards (kilobytes to low megabytes)
• Slow Processors: Couldn't afford complex per-access bookkeeping
• Simple Hardware: Limited or no hardware support for access tracking
• Pressing Need: Any page replacement was better than program crashes

In this context, FIFO was attractive: it required minimal overhead, no special hardware, and was trivial to implement correctly.

Evolution of Understanding:

As systems grew more sophisticated, the limitations of FIFO became apparent:

• 1967: IBM's research on working sets (Peter Denning) formalized the importance of locality
• 1969: Belady's anomaly was discovered, showing FIFO's counterintuitive behavior
• 1970s: LRU and its approximations became preferred in production systems
• 1980s onwards: Hardware reference bit support enabled practical LRU approximations

We've established the foundational understanding of the FIFO page replacement algorithm. Let's consolidate the key concepts:

What's Next:

In the following pages, we will:

• Page 2: Simple Implementation — Build a complete FIFO implementation, examining the queue data structure and the mechanics of page loading and eviction.
• Page 3: Belady's Anomaly — Discover the surprising phenomenon where adding more memory increases page faults—a counterintuitive result unique to certain algorithms including FIFO.
• Page 4: Performance Issues — Analyze FIFO's performance characteristics quantitatively, comparing against optimal and LRU across various workloads.
• Page 5: Queue Management — Explore practical considerations for managing the FIFO queue efficiently in real systems.