Memory Management

Page Replacement

Least Recently Used (LRU) page replacement algorithm maintaining page frames in virtual memory.

What is Page Replacement?

Page Replacement algorithms manage memory paging tables by selecting which page in active RAM frames to replace when a page fault occurs. Least Recently Used (LRU) replaces the page that has not been referenced for the longest duration, utilizing temporal locality to minimize total page faults.

Key Characteristics:

  • Relies on the heuristic that pages used recently will be used again.
  • Stack-based algorithm: not subject to Belady's Anomaly.
  • Requires updating access time flags/histories dynamically.
  • Performs near optimal allocation on average workloads.

Complexity Analysis

Avg Time Complexity: O(N * F) where N is stream size and F is frame capacity
Space Complexity: O(F) frame storage size
Best Case: O(N) (all hits; no page faults occur)
Worst Case: O(N * F) (continuous page faults forcing frame eviction sweeps)

How it Works Step-by-Step

  1. Check Presence: Look up incoming page index in the current memory frames.
  2. Frame Hit: If present, update its priority (recently used) and proceed.
  3. Page Fault: If not present, count a page fault. Check if empty frame slots exist.
  4. Allocation/Eviction: If a slot exists, insert the page. Otherwise, evict the least recently used frame, and replace with the new page.
  5. Repeat: Iterate for the entire page reference stream.

Code Implementation

Worked Trace Example

With capacity 3, page stream [7, 0, 1, 2, 0]:
- 7 -> Fault: frames [7]
- 0 -> Fault: frames [7, 0]
- 1 -> Fault: frames [7, 0, 1]
- 2 -> Fault: evict 7 (least recently used), frames [0, 1, 2]
- 0 -> Hit: frames [1, 2, 0] (0 moved to recently used)
Result: 4 Page Faults.

Ready to Understand Page Replacement Visually?

Don't just read about it. Launch our interactive, premium OS visualizer to see the processes, memory blocks, Page replacement queues, or disk head movements update in real-time.

Launch Page Replacement Visualizer →