Page Replacement Algorithms: short notes (Operating Systems)

Revision mode

Introduction

When a page fault occurs and no frame is free, the operating system must evict a page already in memory: the victim. The choice matters. Evicting a page that is needed again soon causes another fault almost at once; a major, disk-backed fault can cost milliseconds (see Virtual Memory and Demand Paging). A page-replacement algorithm decides which page to evict, and the measure of its quality is the number of page faults it causes on a reference string with a given number of frames.

FIFO, the optimal algorithm, LRU and its hardware approximations (reference bits, second chance and clock, the enhanced second-chance classes) and the counting algorithms LFU and MFU are run on the same reference string so the results can be compared directly. Belady's anomaly and the stack property that rules it out are developed on that comparison and on a second string in the mathematical explanation.

Prerequisites

Virtual Memory and Demand Paging: page faults, the dirty and reference bits, frame allocation and the cost of a fault.

Core concepts

Reference strings and counting conventions

A reference string is the sequence of page numbers referenced. Consecutive repeats of the same page are usually collapsed, because an immediate repeat always hits; for FIFO, OPT, LRU and clock this changes nothing, but for LFU and MFU it lowers the use counts, so keep the repeats if a question gives them. Faults are counted under these conventions unless a question says otherwise:

Cold start: all frames start empty, and the first reference to each page is a fault that fills a free frame without a replacement. Some questions ask for "page replacements" instead, which excludes these initial faults; the two counts differ by the number of frames filled.
Lower bound: no algorithm can have fewer faults than the number of distinct pages in the string.
Upper bound: no more faults than references.
If the number of frames is at least the number of distinct pages, every algorithm faults exactly once per distinct page.

Trace display convention used in these notes. Frames are drawn as fixed slots; the incoming page takes the victim's slot. FIFO, LRU and the others differ only in which slot is chosen.

The algorithms

Algorithm	Victim	Needs	Belady's anomaly possible?
FIFO	The page loaded earliest	A queue of load order	Yes
Optimal (OPT, MIN)	The page whose next use is farthest in the future (or never)	Knowledge of the future	No
LRU	The page whose last use is the oldest	A time stamp per access or a stack	No
Second chance, clock	FIFO, but a page with reference bit 1 is spared once (bit cleared)	One reference bit per frame	Yes
LFU	The page with the smallest use count	A counter per page	Yes (with counts discarded on eviction, as here)
MFU	The page with the largest use count	A counter per page	Yes (same convention)

Tie rules. OPT: if several pages are never used again, evict the one loaded earliest. LFU: among pages with the same count, evict the one loaded earliest (FIFO tie-break); the count of a page starts at 1 when it is loaded and is discarded when it is evicted.

How the algorithms work: one reference string

Reference string (12 references), 3 frames, cold start:

3\ 2\ 4\ 5\ 2\ 3\ 1\ 2\ 3\ 2\ 4\ 3

There are 5 distinct pages, so every algorithm has at least 5 faults.

FIFO: 9 faults

The first three references fill the frames: [3, 2, 4]. Then 5 replaces 3 (oldest), 2 hits, 3 replaces 2, 1 replaces 4, 2 replaces 5, 3 and 2 hit, 4 replaces 3 and 3 replaces 1. Final frames [2, 4, 3]; faults at references 1, 2, 3, 4, 6, 7, 8, 11 and 12: 9 faults.

Optimal: 6 faults

At reference 4 (page 5) the next uses are: 3 at reference 6, 2 at reference 5, 4 at reference 11. Page 4 is used farthest in the future, so it is evicted: [3, 2, 5]. Then 2 and 3 hit; 1 replaces 5, which is never used again; 2, 3, 2 hit; 4 replaces 2 (never used again; 1 is also never used again, and 2 was loaded earlier); 3 hits. 6 faults, the minimum possible for this string with 3 frames.

LRU: 7 faults

At reference 4, the least recently used page is 3: [5, 2, 4]. Reference 6 (page 3) evicts 4, reference 7 (page 1) evicts 5, giving [1, 2, 3], which then hits on 2, 3, 2. Reference 11 (page 4) evicts 1, the least recently used, and reference 12 (page 3) hits. 7 faults.

FIFO, optimal and LRU traces on one reference string — Figure 1. The reference string 3 2 4 5 2 3 1 2 3 2 4 3 with 3 frames: FIFO causes 9 faults, the optimal algorithm 6 and LRU 7. The lower panel shows Belady's anomaly for FIFO on 1 2 3 4 1 2 5 1 2 3 4 5: 9 faults with 3 frames but 10 with 4.

Clock (second chance): 8 faults

Each frame has a reference bit, set to 1 whenever the page is referenced, including when it is loaded. On a fault the hand inspects the frame it points to: if the bit is 1, it clears the bit and advances; if the bit is 0, that page is the victim, the new page takes its frame (bit 1) and the hand advances one frame. On a hit the bit is set and the hand does not move.

On the string above, at reference 4 all three bits are 1, so the hand clears all of them, comes back to frame 0 and evicts 3. Reference 6 (page 3) clears frame 1 (page 2, referenced at step 5) and evicts 4 in frame 2. Reference 7 (page 1) clears frame 0 (page 5) and evicts 2 from frame 1, whose bit had just been cleared. Reference 8 (page 2) clears frame 2 (page 3) and evicts 5 from frame 0. References 9 and 10 hit; reference 11 (page 4) evicts 1; reference 12 hits. 8 faults: between FIFO and LRU, which is typical of an approximation.

Bit convention. Some questions load a new page with its reference bit 0. That changes the trace; follow the question's rule.

LFU: 7 faults

With the tie rule above, LFU evicts 3 at reference 4 (all counts 1, 3 loaded first), 4 at reference 6 (4 and 5 have count 1, 4 loaded earlier), 5 at reference 7 and 1 at reference 11. On this string it makes the same choices as LRU and has 7 faults. LFU keeps pages that were heavily used long ago, which can be wrong after a change of locality; MFU assumes the page with the smallest count was just brought in and is about to be used.

Algorithms and implementation

Implementing LRU

Exact LRU needs hardware help on every reference:

Counters: a logical clock is copied into the page-table entry on each reference; the victim has the smallest time stamp, found by a search.
Stack: pages are kept in a doubly linked list in order of use; a referenced page moves to the top (a few pointer changes), and the victim is always at the bottom.

Few machines provide either, so operating systems use approximations based on the reference bit that hardware sets on any access.

Approximations

Additional reference bits. At regular intervals, shift each page's reference bit into the high end of an 8-bit history byte and clear the bit. Treat the byte as an unsigned number: the page with the smallest value is the least recently used. A page with history 11000100 (196) was used more recently than one with 01110111 (119), even though the second was used in more intervals.
Second chance (clock). FIFO order with one bit of recency, as traced above. If every bit is 1, it degenerates to FIFO after one full sweep.
Enhanced second chance (NRU classes). Use the pair (reference bit, dirty bit): class (0, 0) neither used recently nor modified, the best victim; (0, 1) not used but dirty, so it must be written back first; (1, 0) used recently but clean; (1, 1) used and dirty, the worst victim. Replace a page from the lowest non-empty class.

Page buffering. Keep a pool of free frames; read the new page into a free frame first and write the victim out afterwards, so the faulting process restarts sooner. If the evicted page is referenced again before its frame is reused, it can be reclaimed without a disk read.

Text

CLOCK-REPLACE(frame, ref, hand, page):       -- frame, ref, hand are persistent in/out shared state; f >= 1, frames 0..f-1; cold-start hand = 0
    while ref[hand] = 1
        ref[hand] <- 0
        hand <- (hand + 1) mod f
    victim <- frame[hand]
    frame[hand] <- page; ref[hand] <- 1
    hand <- (hand + 1) mod f
    return victim

For $f\ge1$ , best-case fault handling inspects one frame, $\Theta(1)$ ; worst case inspects $f+1$ frames, $\Theta(f)$ . Extra workspace is $O(1)$ beyond the $O(f)$ frame/reference-bit storage. An average requires a reference-bit distribution.

Mathematical explanation: Belady's anomaly and stack algorithms

Belady's anomaly is an increase in page faults when the number of frames increases. On the reference string

1\ 2\ 3\ 4\ 1\ 2\ 5\ 1\ 2\ 3\ 4\ 5

FIFO has 9 faults with 3 frames and 10 faults with 4 frames. With 4 frames, references 5 and 6 hit on pages 1 and 2, but a hit does not change a page's FIFO position; so when page 5 arrives at reference 7, pages 1 and 2 are the oldest and are evicted just before they are needed at references 8 and 9, and each later reference then evicts the page needed next. With 3 frames, pages 1 and 2 are reloaded at references 5 and 6, which makes them young when 5 arrives, so references 8 and 9 hit. On the same string LRU has 10 faults with 3 frames and 8 with 4, and the optimal algorithm 7 and 6.

Stack algorithms. An algorithm has the inclusion property if, at every point of every reference string, the set of pages in memory with $n$ frames is a subset of the set with $n + 1$ frames. Such an algorithm cannot show Belady's anomaly: any reference that hits with $n$ frames also hits with $n + 1$ . LRU has the property (the $n$ most recently used pages are among the $n + 1$ most recently used), and so does OPT provided ties between pages that are never used again are broken by a rule that does not depend on the number of frames, such as "evict the larger page number". (A load-order tie rule, used in the traces above, can break inclusion of the sets, but OPT's fault count can never rise with more frames, because $n + 1$ frames can always imitate $n$ .) FIFO does not: on the string above, after reference 7 the 3-frame memory is {5, 1, 2} but the 4-frame memory is {5, 2, 3, 4}, which does not contain page 1.

Worked examples

Hit ratio

On the main string with LRU there are 7 faults and 5 hits in 12 references, a hit ratio of $5/12$ . With 5 or more frames, every algorithm has exactly 5 faults (one per distinct page).

Faults versus replacements

FIFO on the main string has 9 faults; three of them fill empty frames, so there are $9 - 3 = 6$ replacements.

A loop larger than memory

A program cycles through 5 pages, $1, 2, 3, 4, 5$ , three times (15 references), with 4 frames.

LRU faults on every reference: 15. When page $p$ is needed it is the one used longest ago, because the 4 pages used since are the other four, which are exactly what LRU keeps.
FIFO also faults 15 times: the oldest page loaded is the next one needed.
OPT faults 7 times: 4 cold faults, then it evicts the page whose next use is furthest away, which in a cycle is the most recently used page. Only 3 further faults are needed in the remaining 11 references.

OPT is optimal, and OPT gives 7, so 7 is the minimum. This pattern (a working set one page larger than the allocation) is the worst case for LRU, and it is the reason that the size of the working set, not the cleverness of the algorithm, decides whether a process thrashes.

Important properties and observations

OPT gives the minimum faults for a fixed number of frames and serves as the benchmark; it cannot be implemented online.
Reversal symmetry: LRU has the same number of faults on a string and on its reverse, and so does OPT; FIFO does not. (LRU is not OPT run backwards: on the main string their counts differ.)
FIFO and clock can show Belady's anomaly; LRU and OPT cannot.
Clock with every bit set behaves as FIFO.
Evicting a clean page is cheaper than evicting a dirty one, which the enhanced second-chance classes exploit.

Common misconceptions.

"More frames always mean fewer faults." Not for FIFO, as Belady's string shows.
"LRU is optimal." It is a good approximation of OPT, not optimal; on the main string it has 7 faults against OPT's 6.
"Initial faults do not count." They do count as page faults; only "replacements" exclude them.

GATE examination perspective

Traces. Draw the frames as columns, mark faults, and write the victim each time. Check the cold-start convention and whether the problem counts faults or replacements.
OPT ties. When several pages are never used again, any of them is optimal for the count; state a tie rule only if the question asks for the frame contents.
Clock details. Whether a loaded page starts with bit 1 or 0, and where the hand points after a replacement.
Belady's anomaly. Only for non-stack algorithms (FIFO, clock); the standard string is 1 2 3 4 1 2 5 1 2 3 4 5.
Bounds. Faults are at least the number of distinct pages and at most the length of the string.

Summary

A replacement algorithm picks the victim on a fault; quality is measured by faults on a reference string.
FIFO evicts the oldest page; OPT the page used farthest in the future; LRU the least recently used page.
On 3 2 4 5 2 3 1 2 3 2 4 3 with 3 frames: FIFO 9, clock 8, LRU 7, LFU 7, OPT 6 faults.
Clock gives a referenced page a second chance by clearing its bit; enhanced second chance also prefers clean pages.
LRU needs counters or a stack per reference; real systems approximate it with reference bits.
Belady's anomaly: FIFO has 9 faults with 3 frames and 10 with 4 on 1 2 3 4 1 2 5 1 2 3 4 5.
LRU satisfies set inclusion; OPT does too with a consistent capacity-independent tie order (such as fixed page-number order), not arbitrary load-order ties. Both have nonincreasing fault counts as capacity grows and never show Belady's fault-count anomaly.
Faults are at least the number of distinct pages; with enough frames every algorithm reaches that bound.

Sources

A. Silberschatz, P. B. Galvin, G. Gagne, Operating System Concepts, 10th ed., Wiley: Chapter 10 (10.4 Page Replacement).
A. S. Tanenbaum, H. Bos, Modern Operating Systems, 4th ed., Pearson, Chapter 3 (3.4.1 The Optimal Page Replacement Algorithm, 3.4.2 The Not Recently Used Page Replacement Algorithm, 3.4.3 The First-In, First-Out (FIFO) Page Replacement Algorithm, 3.4.4 The Second-Chance Page Replacement Algorithm, 3.4.5 The Clock Page Replacement Algorithm, 3.4.6 The Least Recently Used (LRU) Page Replacement Algorithm, 3.4.7 Simulating LRU in Software).