Skip to content
Tutorials Center
My learning

Topics

Lesson 43 of 66 ยท Virtual Memory

Page Replacement Algorithms: FIFO, LRU, Optimal and Clock

Compare FIFO, optimal, LRU, second-chance (clock) and LFU page replacement on the same reference string, and see Belady's anomaly happen in a Python simulation.

When a page fault occurs and no frame is free, the OS must choose a victim: a page to evict so its frame can hold the new page. A good choice keeps pages that will be needed soon; a bad choice evicts a page that is needed right away, causing another fault. The rule used to choose the victim is the page replacement algorithm.

If the victim is dirty (modified since it was loaded), it must be written back to disk first, doubling the cost of the fault. Systems prefer clean victims when they can.

We compare algorithms on a reference string: the sequence of page numbers a process touches. A page already in memory is a hit; otherwise a fault. The goal is the lowest number of faults for a given number of frames.

FIFO

First in, first out: evict the page that has been in memory the longest. It is easy (a queue) but ignores usage: a heavily used page that was loaded early is thrown out just for being old.

Optimal (OPT or MIN)

Evict the page that will not be used for the longest time in the future. It gives the lowest possible fault count and is a lower bound that no real algorithm beats, but it needs knowledge of the future, so it cannot be implemented. Its role is as a yardstick.

LRU: least recently used

Approximate OPT by looking at the past: evict the page that has not been used for the longest time. It rests on locality: pages unused for a long time are probably not needed soon. A true LRU requires tracking the order of every access (a counter per page or a stack that is updated on each memory reference), which hardware rarely offers cheaply.

Python FIFO, LRU and OPT on one reference string

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

OPT is never worse than the others, as it must be. More frames means fewer faults for all three here. That is the normal behaviour, but not a guarantee for every algorithm.

Belady's anomaly

Surprisingly, for FIFO adding frames can increase the number of faults. This is Belady's anomaly. It occurs because FIFO's contents with N + 1 frames need not be a superset of its contents with N frames. LRU and OPT are stack algorithms: the set of pages in memory with N frames is always a subset of the set with N + 1 frames, so they can never suffer the anomaly.

Python Belady's anomaly

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Approximating LRU with a reference bit

Real hardware gives each page-table entry a reference bit, set to 1 on any access. The OS can clear it periodically. That tells which pages were used recently, not in what order, but it is enough for cheap approximations.

Second chance (the clock algorithm)

Arrange the frames in a circle with a pointer (the clock hand). To find a victim, examine the page under the hand:

  • If its reference bit is 0: evict it.
  • If it is 1: clear the bit to 0 (a "second chance") and advance the hand.

If every page is referenced, the hand goes round once clearing all bits and then behaves like FIFO. Pages that are used often keep getting their bit set and stay.

An enhanced version also considers the dirty bit: classes (referenced, dirty) = (0,0) best victim, (0,1) next, (1,0), (1,1) worst, preferring pages that are unused and clean. This is the idea behind the "not recently used" (NRU) algorithm.

Python The clock algorithm

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Clock stays close to LRU while needing just one bit per page and a pointer. Variants of it are used in Linux, BSD and Windows (which keep active and inactive lists with the same spirit).

Counting-based algorithms

  • LFU (least frequently used): evict the page with the smallest use count. A page used heavily early in a program, then never again, stays forever unless counts are aged.
  • MFU (most frequently used): argues that a page with a small count was probably just brought in and will be used. Rarely used.

Neither approximates OPT well, so they are uncommon as primary algorithms.

Page buffering

Systems add tricks on top of the algorithm: keep a pool of free frames so a faulting process need not wait for a victim to be written out; write dirty pages in the background when the disk is idle; and remember which page was in a free frame, so that if it is needed again before the frame is reused it can be reclaimed without disk I/O.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Why can't the optimal algorithm be implemented in a real OS?

    OPT evicts the page whose next use is farthest away, which requires future knowledge. It serves as a benchmark.
  2. 2. What is Belady's anomaly?

    For certain reference strings, FIFO with more frames incurs more faults. Stack algorithms like LRU never do.
  3. 3. In the clock algorithm, what happens when the hand reaches a page with reference bit 1?

    A set bit earns a second chance: it is cleared and the page is looked at again only after the hand comes around.
  4. 4. Which algorithm needs a record of the exact order of recent accesses?

    True LRU must update ordering information on every memory reference, which is costly without hardware support.
  5. 5. Why prefer evicting a clean page over a dirty one?

    A dirty page must be written to disk before its frame is reused, which doubles the I/O of the fault.

Summary

  • A page-replacement algorithm picks the victim when no frame is free; the metric is the number of faults for a reference string.
  • FIFO is simple but can suffer Belady's anomaly; OPT is the unreachable optimum; LRU approximates it from the past.
  • Reference bits give cheap approximations: second chance (clock) and enhanced versions using the dirty bit.
  • Real systems add free-frame pools, background writing and reclaiming of recently freed frames.

Next: Frame Allocation, Thrashing and the Working Set