Memory Management in Operating Systems: Page Replacement Algorithms (FIFO, LRU, OPT)

Memory Management in Operating Systems: Page Replacement Algorithms (FIFO, LRU, OPT)

1. Problem Background
Virtual memory allows part of a process's pages to reside in physical memory, while the rest are stored on disk. When a page being accessed is not in memory, a "Page Fault" occurs. At this point, the operating system needs to select a page in memory to swap out to disk, making space for the requested page. How to choose the page to be swapped out? This is the problem that Page Replacement Algorithms aim to solve.

2. Core Objective
Minimize the Page Fault Rate, avoid frequent disk I/O, and improve system performance.

3. Detailed Explanation of Common Algorithms

（1）First-In, First-Out (FIFO)

  • Idea: Swap out the page that entered memory the earliest.
  • Implementation: Use a queue to record the order of page entry. Swap out the page at the head of the queue, and add new pages to the tail.
  • Example:
    Assuming physical memory capacity is 3, page reference sequence: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
    • Access pages 1, 2, 3: 3 page faults, memory state [1,2,3] (queue order 1→2→3)
    • Access page 4: Swap out 1 (earliest entry), 1 page fault, memory [2,3,4]
    • Access page 1: Swap out 2, 1 page fault, memory [3,4,1]
    • ... (continue simulation)
  • Disadvantage: May swap out frequently used pages (e.g., pages that entered early but are used often), leading to "Belady's Anomaly" (increasing the number of memory frames may increase the page fault rate).

（2）Least Recently Used (LRU)

  • Idea: Swap out the page that has not been accessed for the longest time, based on the "Principle of Locality" (recently used pages are likely to be used again).
  • Implementation:
    • Maintain a linked list or stack: Move accessed pages to the head; the page at the tail is the least recently used.
    • Or use hardware counters: Record the last access time for each page.
  • Example (memory capacity 3, same sequence as FIFO example):
    • Access 1,2,3: 3 page faults, memory [1,2,3] (sorted by access time)
    • Access 4: Swap out 1 (least recently used), memory [2,3,4]
    • Access 1: Swap out 2, memory [3,4,1]
    • Access 2: Swap out 3, memory [4,1,2]
    • Advantage: Better aligns with access patterns than FIFO, resulting in a lower page fault rate.
  • Disadvantage: High hardware implementation cost (requires maintaining precise access history).

（3）Optimal Replacement (OPT)

  • Idea: Swap out the page that "will not be used for the longest time in the future." It is an idealized theoretical algorithm.
  • Implementation: Requires knowledge of the future page reference sequence. Select the page that will be accessed latest (or not at all) in the future to swap out.
  • Example (memory capacity 3, same sequence as above):
    • Access 1,2,3: 3 page faults
    • Access 4: According to the future sequence (1,2,5...), page 1 next appears at the 5th access, page 2 at the 6th, page 3 is latest (11th). Therefore, swap out 3 → memory [1,2,4]
    • Access 1: Hit, no swap
    • Access 2: Hit
    • Access 5: In the future sequence, page 1 next appears at the 8th access, page 2 at the 9th, page 4 never appears again. Therefore, swap out 4 → memory [1,2,5]
  • Significance: Serves as the performance upper bound for other algorithms (lowest possible page fault rate), but is not practically realizable (cannot know the future).

4. Algorithm Comparison

  • FIFO: Simple but inefficient, may suffer from Belady's Anomaly.
  • LRU: Performance close to OPT, commonly used in practice (with approximations like the Clock algorithm).
  • OPT: Theoretically optimal, used to evaluate other algorithms.

5. Summary
Choosing a page replacement algorithm requires balancing implementation complexity and performance. Modern operating systems often use variants of LRU (such as the Second-Chance algorithm or Clock algorithm), balancing efficiency and overhead with hardware support.