Page Replacement Algorithms: OPT, FIFO, LRU, CLOCK, and LFU

A brief review of virtual memory technology, based on the principle of locality, can be summed up in two statements: when the CPU needs information not present in memory, the operating system loads it from secondary storage; if memory is insufficient, the OS swaps out pages that are not currently needed.

The process of deciding which pages to swap out and which to bring in is handled by page replacement algorithms .

Optimal (OPT) Page Replacement Algorithm

The optimal algorithm selects for eviction the page that will not be used for the longest future interval, guaranteeing the lowest possible page‑fault rate. An example with three physical frames and a reference string demonstrates that OPT incurs 9 page faults and 6 replacements.

First‑In First‑Out (FIFO) Page Replacement Algorithm

FIFO evicts the page that has been in memory the longest, implementing a simple queue. Using the same reference string, FIFO performs 12 replacements—about twice as many as OPT.

FIFO can exhibit Belady’s anomaly, where increasing the number of frames leads to more page faults.

Least Recently Used (LRU) Page Replacement Algorithm

LRU evicts the page that has not been accessed for the longest time, approximating future behavior based on past accesses. It requires hardware support such as registers or a stack to track usage.

Method 1 (Register‑based) : each page has an 8‑bit shift register that is set on access and periodically shifted right. The smallest register value indicates the LRU page.

0000 0010

Method 2 (Stack‑based) : a stack holds page numbers; on each access the page is moved to the top. The bottom of the stack holds the LRU page.

LRU offers good performance but incurs higher overhead.

CLOCK Page Replacement Algorithm

The simple CLOCK algorithm approximates LRU by maintaining a circular list of pages with a reference bit (R). When a replacement is needed, the algorithm scans the list: if R=0 the page is evicted; if R=1 the bit is cleared and the scan continues.

Improved CLOCK Algorithm

The enhanced version also considers the modified bit (M). Pages are classified into four categories: Class 0: R=0, M=0 (best candidate) Class 1: R=0, M=1 (second choice) Class 2: R=1, M=0 (likely to be used again) Class 3: R=1, M=1 (most likely to be used again) The algorithm first scans for a Class‑0 page; if none is found, it rescans for a Class‑1 page, clearing R bits on the way.

Least Frequently Used (LFU) Page Replacement Algorithm

LFU maintains a counter for each page, incrementing on each access; the page with the smallest counter is evicted. To avoid stale pages staying too long, counters can be periodically right‑shifted to implement exponential decay.

While conceptually simple, LFU requires per‑page counters, which can be costly.

Overall, the algorithms can be compared as follows:

OPT: best performance, not implementable.

FIFO: easy to implement, poor performance.

LRU: near‑optimal performance, higher implementation cost.

CLOCK (and variants): aim to achieve LRU‑like performance with lower overhead.

LFU: frequency‑based, may suffer from long‑term bias.