Loading learning content...
Read aloud is unavailable in this browser.
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.
By the end of this page, you will understand the fundamental principles of FIFO page replacement, including why it was historically attractive, how it conceptualizes page residency, and the theoretical assumptions underlying its design. You will develop the intuition necessary to reason about FIFO's behavior before examining its implementation, anomalies, and performance in subsequent pages.
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.
Every page replacement algorithm is fundamentally a prediction algorithm. It's trying to guess which pages won't be needed soon, using only past and present information. Different algorithms use different heuristics for this prediction. FIFO's heuristic is the simplest possible: older residence implies lower future utility.
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:
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:
| Property | FIFO Behavior | Implication |
|---|---|---|
| Selection criterion | Page loaded earliest | Only considers arrival time, not usage patterns |
| Information needed | Load timestamp per page | Minimal metadata requirement |
| Ordering | Strict temporal queue | Deterministic, reproducible behavior |
| On page hit | No action required | Zero overhead for memory accesses |
| On page miss (eviction) | Remove front of queue | O(1) victim selection |
| Stack property | Does not satisfy | Susceptible to Belady's anomaly |
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:
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.
FIFO is ideally suited for streaming workloads where data is touched exactly once. In such scenarios, the oldest page is always the most useless page, and FIFO achieves optimal performance. Real-world examples include video transcoding, log processing, and ETL (Extract-Transform-Load) pipelines.
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:
A program cycles through pages 1, 2, 3, 4 repeatedly with only 3 frames available.
——The Core Problem:
FIFO conflates two distinct concepts:
| Concept | What It Means | What FIFO Assumes |
|---|---|---|
| Age (residence time) | How long since page was loaded | High age → low utility |
| Recency (last access) | How long since page was used | (Not considered at all) |
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:
Both have the same age; FIFO treats them identically.
FIFO ignores usage patterns entirely. It cannot learn from access behavior. Whether a page is accessed once or a million times after loading, FIFO treats it the same way based solely on when it arrived. This blindness to actual usage is FIFO's critical weakness.
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:
| Algorithm | Selection Criterion | Information Used | Overhead | Quality |
|---|---|---|---|---|
| Random | Any page (random) | None | O(1), trivial | Poor baseline |
| FIFO | Oldest by load time | Load timestamp | O(1), minimal | Variable |
| LRU | Least recently used | Access timestamps | O(n) or costly | Good |
| LFU | Least frequently used | Access counters | O(n) or costly | Good for some patterns |
| Clock (2nd Chance) | Oldest w/o recent access | Reference bits | O(1) amortized | Near-LRU |
| Optimal (OPT) | Farthest future use | Future knowledge | N/A (theoretical) | Theoretical best |
FIFO's Position:
FIFO occupies a unique position in this spectrum:
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.
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.
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:
| Situation | FIFO Behavior | Performance |
|---|---|---|
| Frames ≫ Working Set | All working set pages fit | Good (few page faults) |
| Frames ≈ Working Set | Working set barely fits | Unstable (variable performance) |
| Frames < Working Set | Cannot hold working set | Poor (constant page faults) |
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 performance is fundamentally tied to working set dynamics. For processes with stable, long-lived working sets, FIFO is dangerous—it will eventually evict every working set page simply because they're old. For processes with rapidly shifting working sets, FIFO may be adequate since old pages are genuinely 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:
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:
While FIFO is rarely used for production page replacement today, it remains crucial for education. Understanding FIFO—its simplicity, its limitations, and especially Belady's anomaly—provides deep insight into the nature of caching and the importance of informed eviction policies.
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:
You now understand the theoretical foundation of FIFO page replacement—why it was designed, what assumptions it makes, when those assumptions hold or fail, and how it compares to alternatives. Next, we'll translate this understanding into concrete implementation.