The Replacement Decision

On a page fault with no free frame, the OS must evict a page. Goal: choose the page least likely to be referenced soon to minimize future faults.

Reference String

We will analyse this reference string with 3 frames: 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1.

1. FIFO

Evict the page that has been in memory longest (queue order).

Total faults = 15. FIFO suffers from Belady's anomaly — adding more frames can increase faults.

2. Optimal (MIN)

Evict the page that will not be used for the longest time in the future. Theoretical lower bound; needs future knowledge — used as a benchmark.

For the same reference string, optimal yields 9 faults.

3. LRU (Least Recently Used)

Evict the page not used for the longest time in the past. Approximates optimal under locality. Implementations:

• Counters — each PTE has a "last used" timestamp.
• Stack — move referenced page to top of a doubly-linked list; bottom is the LRU victim.

For our string, LRU yields 12 faults.

4. LFU (Least Frequently Used)

Counts references per page; evicts the smallest count. Issue: a page heavily used early but never again sticks around.

5. MFU (Most Frequently Used)

The opposite — argues that low-count pages were just paged in and should stay.

6. Counting Algorithms

Maintain reference counts; LFU and MFU are examples. Often combined with aging — counters shifted right periodically to forget old usage.

Approximations of LRU

True LRU is expensive. Common approximations:

• Reference bit + Second-chance (Clock) — circular queue, skip pages whose reference bit is 1, clear the bit, evict the first one with bit 0.
• NRU (Not Recently Used) — categorize pages by (reference, modified) bits and evict from the lowest category.

Comparison

Summary

• Optimal is the theoretical best; LRU and Clock are practical and good.
• FIFO is simple but exhibits Belady's anomaly.
• Real Linux uses a variant of two-list LRU (active + inactive).