Page Replacement Algorithms: FIFO, Belady's Anomaly, LRU & Optimal
“From the illusion of infinite memory to page fault service cycles, thrashing dynamics, and replacement heuristics.”
1.The Core Motivation: Why Physical RAM Is Not Enough & What Virtual Memory Is
§ 7.1.Consider the memory management schemes studied in Module 6 (Contiguous Allocation, Segmentation, Pure Paging). All of them shared one crippling assumption: the entire executable image of a process had to be loaded into physical RAM before execution.
In real-world computing, this assumption breaks down completely. If a computer has 4 GB of physical RAM, how can it execute an 8 GB database engine, or run an IDE, web browser, and music player simultaneously when their combined memory footprints exceed 12 GB? Furthermore, real software contains massive amounts of code that are rarely executed during a given run — error-handling routines, initialization sequences, and unused configuration options. Forcing the entire program into expensive, scarce physical RAM is tremendously wasteful.
Virtual Memory is an architectural technique that decouples User Logical Memory from Physical Memory. It provides each running process with the illusion of an enormous, private, uniform, and contiguous address space — regardless of how much physical RAM is actually installed.
Sparse Address Spaces: In a standard process address space (Module 2), the Text and Data segments reside at low addresses, the Heap grows upward, and the Stack grows downward. In a 32-bit address space, the gap between the highest heap address and the lowest stack address is several gigabytes of empty virtual territory. In Virtual Memory, this is a sparse address space — it requires zero physical RAM frames until the process actually accesses memory at runtime.
Virtual memory frees the software engineer from physical hardware boundaries. An application sees a private, flat, continuous universe of memory. The operating system, in cooperation with the hardware MMU, silently maps active pieces to physical RAM and leaves dormant pieces on secondary storage.
2.Paging as the Enabler & The Dual-Role Valid/Invalid Bit
§ 7.2.How does the operating system implement virtual memory? It builds directly upon the hardware paging mechanism introduced in Module 6. The CPU generates a Logical (Virtual) Address, split into a Virtual Page Number (p) and an Offset (d). Physical memory is partitioned into matching fixed-size Frames (f).
In a pure physical paging system, every page table entry (PTE) was assumed to point to a valid frame in RAM. In a Virtual Memory system, however, the Valid/Invalid Bit in the Page Table Entry is given a critical dual role:
• Bit = 1 (Valid / Resident): The page is legal AND is currently resident in physical RAM. The MMU translates the address to physical frame f at full hardware speed without interrupting the CPU.
• Bit = 0 (Invalid / Non-Resident): The address either does not belong to the address space (triggering a Segmentation Fault / SIGSEGV), OR the page is legal but currently resides on secondary storage (the paging/swap file).
The Demand Paging Philosophy: Instead of loading all pages into RAM when starting, the OS utilizes Demand Paging: a page is brought into physical memory only when an instruction actually references it. A process starting with zero resident pages uses Pure Demand Paging.
3.The Complete 6-Step Page Fault Service Routine
§ 7.3.When the CPU executes an instruction that references a virtual address whose Page Table Entry has its Valid/Invalid bit set to 0, the Memory Management Unit (MMU) cannot translate the address. The MMU hardware halts execution and raises an internal exception called a Page Fault Trap.
The operating system handles this hardware trap through a deterministic 6-step service sequence:
Step 1 — Hardware Trap & Context Save: The CPU hardware switches from User Mode to Kernel Mode (mode bit 1 → 0), pushes the program counter (PC) and processor registers onto the kernel stack, and transfers execution to the OS Page Fault Handler.
Step 2 — Address Legality Check: The OS queries the process's internal PCB memory map. If the address violates permissions, the OS delivers a SIGSEGV signal. If legal, the page is simply residing on backing store (disk).
Step 3 — Find a Free Frame: The OS inspects its internal Free-Frame List. If no free frame exists, the OS must invoke a Page Replacement Algorithm to select an existing 'victim' frame and evict it to swap storage.
Step 4 — Disk I/O Transfer: The OS schedules a disk read to copy the page from swap space into the physical frame. Because disk I/O is slow, the process moves to BLOCKED / WAITING state so the CPU scheduler can dispatch another ready process.
Step 5 — Page Table & Internal State Update: When the disk controller finishes, an I/O completion interrupt fires. The OS updates the PTE: sets Frame Number to newly loaded frame, flips Valid bit from 0 → 1, and resets the dirty bit.
Step 6 — Instruction Restart: The OS moves the process back to the READY queue. When dispatched again, the OS restores saved registers and restarts the exact machine instruction that triggered the fault from the beginning.
4. Worked Numerical: Effective Memory Access Time (EMAT) with Page Faults
| Memory Access Time (t_m)100 ns | Page Fault Service Time (S)8 ms = 8,000,000 ns | Maximum Allowable EMAT110 ns (10% slowdown) |
With probability (1 - p), the referenced page is resident in physical RAM and requires 1 memory access (t_m). With probability p, a page fault occurs, requiring full page fault service time (S) plus the eventual memory access.
Expand the terms using nanoseconds: EMAT = (1 - p) 100 + p 8,000,000 = 100 - 100p + 8,000,000p = 100 + 7,999,900p ns.
Set EMAT ≤ 110 ns: 100 + 7,999,900 * p ≤ 110 7,999,900 * p ≤ 10 p ≤ 10 / 7,999,900 ≈ 1.25 * 10^(-6).
5.Thrashing, Locality of Reference & The Working Set Model
§ 7.5.Why does demand paging work at all if a single page fault incurs an 80,000× speed penalty? The answer lies in the Principle of Locality:
• Temporal Locality: If a memory location is accessed, it will likely be accessed again in the near future (e.g., loop variables, subroutine code, stack frames).
• Spatial Locality: If a memory location is accessed, memory locations with nearby addresses will likely be accessed soon (e.g., sequential code execution, array elements).
Because programs access memory in localized clusters, a process only needs a small subset of its pages resident in RAM at any given moment to make rapid progress.
What is Thrashing? If a process does not have enough physical frames allocated to hold its active locality, it will page fault almost immediately. It will evict a page that it needs again two instructions later, causing another page fault. When processes spend more time paging (swapping pages in and out of disk) than executing instructions, the system is Thrashing.
The Fatal Feedback Loop: When thrashing begins, processes get blocked waiting for disk I/O. The CPU scheduler sees CPU utilization plunge toward 0%. In early operating systems, the kernel scheduler would incorrectly increase the degree of multiprogramming, accelerating total system collapse.
The Working Set Model (Peter Denning): To prevent thrashing, the OS tracks the Working Set of each process — the set of pages referenced in the most recent \Delta memory references. The OS must guarantee: \sum WSS_i ≤ Total Physical Frames. If total demand exceeds physical capacity, the OS suspends (swaps out) an entire process to free its frames for others.
6. Interactive Page Replacement Simulator
Now that you understand the page fault cycle and free-frame shortages, simulate FIFO, LRU, and Optimal algorithms on an actual reference string. Toggle between 3 and 4 frames to test Belady's Anomaly live!
Page Replacement & Belady's Anomaly Laboratory
Notice on the classic reference string: with FIFO, increasing frames from 3 to 4 increases page faults from 9 to 10 (Belady's Anomaly)! LRU and Optimal never suffer from this anomaly.
| Ref: | 1 | 2 | 3 | 4 | 1 | 2 | 5 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| F0 | 1 | 1 | 1 | 4 | 4 | 4 | 5 | 5 | 5 | 5 | 5 | 5 |
| F1 | - | 2 | 2 | 2 | 1 | 1 | 1 | 1 | 1 | 3 | 3 | 3 |
| F2 | - | - | 3 | 3 | 3 | 2 | 2 | 2 | 2 | 2 | 4 | 4 |
| Status | M | M | M | M | M | M | M | H | H | M | M | H |
7. Algorithm Comparison: FIFO vs. Belady's Anomaly vs. LRU vs. Optimal
When all physical frames are occupied and a page fault occurs, the OS must choose a victim frame to evict. Here is how the primary algorithms compare.
| Feature / Aspect | FIFO (First-In, First-Out) | LRU (Least Recently Used) |
|---|---|---|
| Eviction Heuristic | Evicts the page that has resided in physical memory the longest time (oldest timestamp). | Evicts the page that has not been accessed for the longest period in the past. |
| Belady's Anomaly | VULNERABLE. In 1969, Laszlo Belady proved that increasing frames from 3 to 4 can increase faults from 9 to 10. | IMMUNE. Belongs to the class of Stack Algorithms; mathematically guaranteed never to suffer from Belady's Anomaly. |
| Hardware & Runtime Cost | Trivial: Maintained via a simple FIFO circular queue or pointer. Zero hardware support required. | High: Requires either an incrementing 64-bit hardware clock on every memory access or a double-linked stack. |
| Stack Property M(n) ⊆ M(n+1) | Fails stack property. The set of pages in n frames is NOT guaranteed to be a subset of pages in n+1 frames. | Satisfies stack property: M(n) ⊆ M(n+1) for all n at every reference instant. |
| Optimal (OPT / MIN) Benchmark | Far from optimal. Frequently evicts heavily used global variables simply because they were loaded early. | Approximates Optimal by using the past as an empirical predictor of the future (Principle of Locality). |
✎ Takeaway: Optimal Algorithm (Belady's MIN) evicts the page that will not be used for the longest time in the FUTURE. It provides the theoretical lower bound on page faults, but cannot be implemented in general-purpose OSs because the future is unknown.
8. GATE Lens & Verified PYQs
Syllabus focus, recurring numerical patterns, common traps, and clearly labelled exam practice. Questions remain source-pending until an official paper and answer key are attached.
Page Replacement, Belady's Anomaly, and EMAT with Page Faults appear in virtually every GATE CS/IT paper, accounting for 2 to 4 marks.
- •Given a reference string and k frames, calculate the exact number of page faults and page hits under FIFO, LRU, and Optimal.
- •Numerical questions calculating Effective Memory Access Time (EMAT) given page fault rate p and service time S.
- •Theoretical identification of Stack Algorithms and Belady's Anomaly conditions.
- •Belady's Anomaly CANNOT occur in LRU or Optimal algorithms! It can occur in FIFO, Second-Chance, and Random.
- •When tracing reference strings, don't confuse Page Hits with Page Faults. Always verify whether the incoming page is already present in any allocated frame.
- •Dirty/Modify Bit: An evicted victim page only needs to be written to disk if its dirty bit is 1. If clean (0), eviction requires zero disk writes!
Exam Practice / Source Verification Required
2 problemsConsider the page reference string: 1, 2, 3, 4, 2, 1, 5, 6, 2, 1, 2, 3, 7, 6, 3, 2, 1, 2, 3, 6. Which of the following page replacement algorithms does NOT suffer from Belady's anomaly?
In a computer system with demand paging, memory access time is 200 ns and page fault service time is 10 ms. If the page fault rate is 1 out of 10,000 memory references, what is the Effective Memory Access Time (in ns)?
9. 1-Minute Panic Revision
“Virtual Memory decouples logical address space from physical RAM via Demand Paging. Page Fault = accessing a non-resident page (Valid bit = 0). Page Replacement = selecting a victim frame when RAM is full.”
- •EMAT = (1 - p) t_m + p S (where S is page fault service time, p is fault rate).
- •FIFO: Evict oldest loaded frame. Suffers from Belady's Anomaly.
- •LRU: Evict frame unreferenced for longest past duration. Stack algorithm (no Belady's anomaly).
- •Optimal: Evict frame unreferenced for longest FUTURE duration (Theoretical lower bound).
- •Working Set Condition for No Thrashing: sum(WSS_i) <= Total Physical Frames.
- •Belady's Anomaly = More frames → MORE page faults (can occur in FIFO, never in LRU or Optimal).
- •Dirty/Modify Bit: An evicted victim page only needs a slow disk write-back if its Dirty Bit = 1.
- •Thrashing: CPU utilization collapses while disk queue is 100% full. Fix by REDUCING multiprogramming!
Primary Academic References & Exam Sources
Every concept in Notes From a B.Tech Brain is synthesized from authoritative academic texts, seminal peer-reviewed research, verified exam archives, and renowned university lectures.
Official Chapter 10 slides detailing demand paging, page-fault handling sequence, FIFO, Optimal, LRU, and thrashing.
Free chapter analyzing Cache Management, FIFO vs Random vs LRU, and the Clock algorithm approximation.
If the textbook derivation did not click immediately, consult these targeted video lessons:
Tabular walkthrough showing how to track hits, misses, and replacement order across frame slots.
Walks through the classic 12-page reference string proving why 4 frames produce more page faults than 3 frames.
Curated lectures on Demand Paging, Page Fault Handling, FIFO, LRU, Optimal & Belady's Anomaly:
Clear, foolproof tabular layouts for tracking frames during page replacement exams.
The canonical reference string demonstration showing why FIFO is not a stack algorithm.
Deriving page fault overhead equations and disk transfer delay calculations.
Theoretical depth on CPU utilization drops and operating system thrashing prevention.