Topic 8.4 · Paging, Segmentation & Virtual Memory

Page Replacement Algorithms & Belady's Anomaly

4 min read1 question to test yourself

1Definition

Page Replacement Algorithms are OS kernel strategies used during a Page Fault to decide which physical frame's page to swap out when all physical RAM frames are occupied. Common algorithms include FIFO (First-In, First-Out), Optimal Page Replacement, LRU (Least Recently Used), LFU (Least Frequently Used), and MFU (Most Frequently Used). Belady's Anomaly is a counter-intuitive phenomenon in FIFO where increasing the number of physical frames increases the total number of page faults.

2Simple Explanation

When a Page Fault occurs and RAM is completely full, the OS must evict an old page to make room for the new page.

  • FIFO: Evicts the oldest page brought into RAM. (Easy, but suffers from Belady's Anomaly).
  • Optimal: Evicts the page that will not be used for the longest time in the future. (Mathematically perfect, but impossible to implement in real life because the OS cannot predict the future!).
  • LRU: Evicts the page that has not been used for the longest period in the recent past. (Uses recent past as an approximation of the future; best practical algorithm!).
  • LFU / MFU: Evicts pages based on how few or many times they have been referenced.

3Real-Life Example / Analogy

Managing a Small Desk Workspace: Your desk fits 3 books. You need a 4th book.

  • FIFO: Putting away the book you placed on the desk first, even if you are currently using it.
  • Optimal: Predicting the future perfectly and putting away the book you won't open for the rest of the week.
  • LRU: Checking the clock and putting away the book you haven't opened in the last 3 hours.

4Diagram / Visual Representation

Yes

No

Requested page is needed

Is a free frame available?

Load page into free frame

Run replacement algorithm
FIFO · Optimal · LRU

Select victim page

Swap victim out if required

Load requested page into frame

5Working / How It Works

  • LRU Implementation Techniques:
    1. Counter Approach: Every Page Table entry has a Time-of-Use counter field. When a page is referenced, copy the CPU clock counter into its entry. During replacement, search for the page with the smallest counter value.
    2. Stack Approach: Maintain a doubly linked list stack of page numbers. When a page is referenced, remove it from the middle of the stack and push it to the top. The bottom of the stack is always the LRU page!

6Types / Components / Characteristics

  • Page Replacement Algorithms Comparison:
Algorithm Replacement Criteria Belady's Anomaly? Implementation Feasibility Performance
FIFO Replaces oldest page in RAM YES (Faults can increase with more frames) Extremely Easy (Queue) Poor / Unpredictable
Optimal Replaces page referenced farthest in future No Impossible (Requires future reference knowledge) Theoretical Best (Minimum Faults)
LRU Replaces page unused for longest recent time No Complex (Requires Hardware Counters / Stack) Excellent (Best practical algorithm)
LFU Replaces page with smallest reference count No Moderate (Reference Counters) Moderate / Rarely used
MFU Replaces page with largest reference count No Moderate (Reference Counters) Moderate / Rarely used

7Solved Examples / Problems

Problem: Given the Page Reference String: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5, trace FIFO with 3 Frames vs 4 Frames to demonstrate Belady's Anomaly.

Solution:

  • Execution with 3 Frames (FIFO):

    • 1: [1, -, -] (Fault 1)
    • 2: [1, 2, -] (Fault 2)
    • 3: [1, 2, 3] (Fault 3)
    • 4: Replaces 1 -> [4, 2, 3] (Fault 4)
    • 1: Replaces 2 -> [4, 1, 3] (Fault 5)
    • 2: Replaces 3 -> [4, 1, 2] (Fault 6)
    • 5: Replaces 4 -> [5, 1, 2] (Fault 7)
    • 1: Hit! [5, 1, 2]
    • 2: Hit! [5, 1, 2]
    • 3: Replaces 1 -> [5, 3, 2] (Fault 8)
    • 4: Replaces 2 -> [5, 3, 4] (Fault 9)
    • 5: Hit! [5, 3, 4]
    • Total Page Faults (3 Frames) = 9 Faults.
  • Execution with 4 Frames (FIFO):

    • 1: [1, -, -, -] (Fault 1)
    • 2: [1, 2, -, -] (Fault 2)
    • 3: [1, 2, 3, -] (Fault 3)
    • 4: [1, 2, 3, 4] (Fault 4)
    • 1: Hit! [1, 2, 3, 4]
    • 2: Hit! [1, 2, 3, 4]
    • 5: Replaces 1 -> [5, 2, 3, 4] (Fault 5)
    • 1: Replaces 2 -> [5, 1, 3, 4] (Fault 6)
    • 2: Replaces 3 -> [5, 1, 2, 4] (Fault 7)
    • 3: Replaces 4 -> [5, 1, 2, 3] (Fault 8)
    • 4: Replaces 5 -> [4, 1, 2, 3] (Fault 9)
    • 5: Replaces 1 -> [4, 5, 2, 3] (Fault 10)
    • Total Page Faults (4 Frames) = 10 Faults!
  • Conclusion: Increasing frames from 3 to 4 increased page faults from 9 to 10! This proves Belady's Anomaly in FIFO.

8Advantages, Disadvantages & Applications

  • LRU Advantages: Zero Belady's Anomaly, near-optimal performance in practice.
  • LRU Disadvantages: Requires hardware support (counters or doubly linked stacks) to update on every memory reference.

9Important Points to Remember

  • Belady's Anomaly occurs in FIFO, but NEVER occurs in LRU or Optimal algorithms (Stack Algorithms).
  • Optimal algorithm gives the theoretical minimum page fault rate.

10Test Your Understanding

  1. MCQ: Belady's Anomaly is a phenomenon where the number of page faults increases as the number of allocated physical frames increases. Which algorithm exhibits this anomaly?
    • A) Least Recently Used (LRU)
    • B) Optimal Page Replacement
    • C) First-In, First-Out (FIFO)
    • D) Working Set Model
    Show answer
    C.
  2. Conceptual Question: Explain the Stack Approach used to implement LRU page replacement.
  3. Application Question: Trace the LRU page replacement algorithm for reference string 7, 0, 1, 2, 0, 3, 0, 4 with 3 frames.

Finished this topic?

0 of 27 topics read in Operating Systems

Handwritten notes for the exam

Unit-wise SPPU notes and PYQs for this subject.

Helpful? Share it with your class

Free for everyone, no login needed.

Share topic