Self-checkedTier 1 14 min reados.page-replacement

Page replacement algorithms

Choosing the victim when memory is full: FIFO, optimal, LRU and the approximations of LRU (reference bits, second chance and the clock, the enhanced version with the modify bit), counting algorithms, Belady's anomaly, stack algorithms, and counting page faults for a reference string.

Why it exists

When a page fault occurs and every frame is in use, the operating system must evict a page. Evicting a page that is needed again soon causes another fault soon. The best choice is the page that will not be used for the longest time; that cannot be known, so practical algorithms guess from the past. The algorithms differ in cost and in how many faults they cause, and GATE asks you, almost every year, to count the page faults for a given algorithm, reference string and number of frames, and to reason about Belady's anomaly.

Prerequisites

Virtual memory and demand paging

You need the page fault and its handling from virtual memory and demand paging.

Precise definitions

Reference string. The sequence of page numbers a process references. Consecutive references to the same page cause at most one fault, so strings are usually given with repeats removed. A page fault is counted every time the referenced page is not in a frame, including the first loads into empty frames (unless the question says to count only replacements).

Replacement is local or global. With local replacement a process chooses a victim among its own frames; with global replacement from any process's frames. The algorithms below choose among the candidate frames.

FIFO. Evict the page that has been in memory longest (the oldest by time of loading). Simple (a queue), but it can evict a page that is still heavily used. It is not a stack algorithm and suffers Belady's anomaly.

Optimal (OPT, MIN). Evict the page that will not be used for the longest time in the future. It has the lowest possible fault rate of all algorithms and is never worse with more frames, but needs knowledge of the future, so it cannot be implemented; it is the yardstick. (A page never used again is the best victim; ties are broken arbitrarily, usually by FIFO.)

LRU (least recently used). Evict the page that has not been used for the longest time in the past; the idea is that the past predicts the future. Implementations: a counter or timestamp in each entry (set on every reference; the victim has the smallest); a stack of page numbers (on a reference the page moves to the top; the victim is at the bottom). Exact LRU needs hardware support on every memory reference, which is expensive, so real systems use approximations.

Stack algorithms. An algorithm for which the set of pages in memory with $n$ frames is always a subset of the set with $n + 1$ frames for the same reference string. LRU and OPT are stack algorithms and so never suffer Belady's anomaly: more frames never gives more faults. FIFO is not.

Belady's anomaly. For FIFO, the number of faults can increase when the number of frames increases. The standard example is the 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.

LRU approximations (using a reference bit). The hardware sets a reference bit in the page-table entry whenever the page is referenced.

Additional-reference-bits: the OS periodically shifts each page's reference bit into the high end of a byte; the page with the smallest value was used least recently.
Second chance (clock): a FIFO queue, but when a page is selected its reference bit is checked: if 0, evict it; if 1, clear the bit (its "second chance") and move on to the next page. Implemented as a circular list with a hand (the clock algorithm). If all bits are 1 it clears them all and degenerates to FIFO.
Enhanced second chance (using the reference bit $r$ and the modify bit $m$ ): pages fall into classes $(r, m)$ : $(0, 0)$ not recently used, not modified: best victim; $(0, 1)$ not recently used but modified (must be written back); $(1, 0)$ recently used, clean; $(1, 1)$ recently used and modified: worst. Evict from the lowest non-empty class.

Counting-based algorithms. LFU evicts the page with the smallest reference count; MFU evicts the page with the largest count (reasoning that a page with a small count was just brought in). Neither is common.

Page buffering. Keep a pool of free frames so that a faulting process need not wait for a victim to be written; and keep a list of modified pages to write out in batches.

How it works

All the animations use the reference string 1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 1 2 3 6 (20 references, 7 distinct pages) and 3 frames. In the string at the top, green means a hit and amber a fault; the frames show the resident pages and the page just brought in; the evicted page is named.

FIFO evicts in the order the pages were loaded, ignoring how often they are used: 16 faults.

FIFO page replacement: start

Algorithm simulated, not typed

FIFO (evict the page that has been in memory longest), 3 frames.

reference string (green: hit, amber: page fault)

page faults

hits

hit ratio

Step 0

3 frames, all empty. The reference string has 20 references. For each reference the algorithm either finds the page in a frame (a hit) or takes a page fault and, when every frame is full, chooses a victim by its rule: FIFO (evict the page that has been in memory longest).

0 / 20

computed by script: the algorithm is executed on the reference string, one reference per step. python3 scripts/gen-os-vm-traces.py

LRU keeps the recently used pages: 15 faults here (the string has little re-use within three frames).

LRU page replacement: start

Algorithm simulated, not typed

LRU (evict the least recently used page), 3 frames.

reference string (green: hit, amber: page fault)

page faults

hits

hit ratio

Step 0

0 / 20

computed by script: the algorithm is executed on the reference string, one reference per step. python3 scripts/gen-os-vm-traces.py

OPT looks ahead at the string and evicts the page used farthest in the future: 11 faults, the minimum possible with 3 frames.

Optimal page replacement: start

Algorithm simulated, not typed

OPT (evict the page whose next use is farthest away), 3 frames.

reference string (green: hit, amber: page fault)

page faults

hits

hit ratio

Step 0

3 frames, all empty. The reference string has 20 references. For each reference the algorithm either finds the page in a frame (a hit) or takes a page fault and, when every frame is full, chooses a victim by its rule: OPT (evict the page whose next use is farthest away).

0 / 20

computed by script: the algorithm is executed on the reference string, one reference per step. python3 scripts/gen-os-vm-traces.py

Clock (second chance). Each frame shows its reference bit and the hand. A hit sets the bit; on a fault the hand skips (and clears) pages with bit 1 and evicts the first with bit 0: 16 faults here.

Clock (second chance) page replacement: start

Algorithm simulated, not typed

Clock / second chance (a FIFO that spares pages with reference bit 1), 3 frames.

reference string (green: hit, amber: page fault)

▲ ref 0

ref 0

page faults

hits

hit ratio

Step 0

3 frames, all empty. The reference string has 20 references. For each reference the algorithm either finds the page in a frame (a hit) or takes a page fault and, when every frame is full, chooses a victim by its rule: Clock / second chance (a FIFO that spares pages with reference bit 1).

0 / 20

computed by script: the algorithm is executed on the reference string, one reference per step. python3 scripts/gen-os-vm-traces.py

Belady's anomaly. The same FIFO algorithm on the string 1 2 3 4 1 2 5 1 2 3 4 5: 9 faults with 3 frames, but 10 faults with 4 frames.

FIFO with 3 frames: start

Algorithm simulated, not typed

FIFO (evict the page that has been in memory longest), 3 frames.

reference string (green: hit, amber: page fault)

page faults

hits

hit ratio

Step 0

3 frames, all empty. The reference string has 12 references. For each reference the algorithm either finds the page in a frame (a hit) or takes a page fault and, when every frame is full, chooses a victim by its rule: FIFO (evict the page that has been in memory longest).

0 / 12

computed by script: the algorithm is executed on the reference string, one reference per step. python3 scripts/gen-os-vm-traces.py

FIFO with 4 frames: more frames, more faults: start

Algorithm simulated, not typed

FIFO (evict the page that has been in memory longest), 4 frames.

reference string (green: hit, amber: page fault)

page faults

hits

hit ratio

Step 0

4 frames, all empty. The reference string has 12 references. For each reference the algorithm either finds the page in a frame (a hit) or takes a page fault and, when every frame is full, chooses a victim by its rule: FIFO (evict the page that has been in memory longest).

0 / 12

computed by script: the algorithm is executed on the reference string, one reference per step. python3 scripts/gen-os-vm-traces.py

Worked examples

EX 1The four algorithms, by program

Easy

A C program counts the faults of FIFO, LRU, OPT and the clock for 3 and 4 frames, and the Belady string.

#include <stdio.h>
 
#define MAXF 8
 
static int refs_main[20] = {1, 2, 3, 4, 2, 1, 5, 6, 2, 1, 2, 3, 7, 6, 3, 2, 1, 2, 3, 6};
static int refs_belady[12] = {1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5};
 
static int next_use(const int *refs, int n, int from, int page) {
    for (int i = from; i < n; i++) if (refs[i] == page) return i;
    return n + 1;                                   /* never used again */
}
 
/* algo: 0 FIFO, 1 LRU, 2 OPT, 3 clock (second chance) */
static int run(const int *refs, int n, int frames, int algo) {
    int page[MAXF], loaded[MAXF], used[MAXF], bit[MAXF], faults = 0, hand = 0;
    for (int i = 0; i < frames; i++) { page[i] = -1; bit[i] = 0; }
    for (int t = 0; t < n; t++) {
        int slot = -1;
        for (int i = 0; i < frames; i++) if (page[i] == refs[t]) slot = i;
        if (slot >= 0) { used[slot] = t; bit[slot] = 1; continue; }
        faults++;
        for (int i = 0; i < frames; i++) if (page[i] < 0) { slot = i; break; }
        if (slot < 0) {
            if (algo == 0) { slot = 0; for (int i = 1; i < frames; i++) if (loaded[i] < loaded[slot]) slot = i; }
            else if (algo == 1) { slot = 0; for (int i = 1; i < frames; i++) if (used[i] < used[slot]) slot = i; }
            else if (algo == 2) { slot = 0; for (int i = 1; i < frames; i++) if (next_use(refs, n, t + 1, page[i]) > next_use(refs, n, t + 1, page[slot])) slot = i; }
            else {
                while (bit[hand]) { bit[hand] = 0; hand = (hand + 1) % frames; }
                slot = hand;
            }
        }
        page[slot] = refs[t]; loaded[slot] = t; used[slot] = t; bit[slot] = 1;
        if (algo == 3) hand = (slot + 1) % frames;
    }
    return faults;
}
 
int main(void) {
    const char *name[4] = {"FIFO", "LRU", "OPT", "clock"};
    for (int f = 3; f <= 4; f++) {
        printf("%d frames, 20 references:", f);
        for (int a = 0; a < 4; a++) printf("  %s %d", name[a], run(refs_main, 20, f, a));
        printf("\n");
    }
    printf("Belady string (12 references), FIFO: 3 frames %d faults, 4 frames %d faults\n", run(refs_belady, 12, 3, 0), run(refs_belady, 12, 4, 0));
    printf("Belady string, LRU: 3 frames %d, 4 frames %d; OPT: 3 frames %d, 4 frames %d\n", run(refs_belady, 12, 3, 1), run(refs_belady, 12, 4, 1), run(refs_belady, 12, 3, 2), run(refs_belady, 12, 4, 2));
    return 0;
}

3 frames, 20 references:  FIFO 16  LRU 15  OPT 11  clock 16
4 frames, 20 references:  FIFO 14  LRU 10  OPT 8  clock 14
Belady string (12 references), FIFO: 3 frames 9 faults, 4 frames 10 faults
Belady string, LRU: 3 frames 10, 4 frames 8; OPT: 3 frames 7, 4 frames 6

Reading it. OPT always has the fewest faults (11 and 8); LRU is next here, FIFO and the clock after. Going from 3 to 4 frames reduces the faults of every algorithm on the main string, but on the Belady string FIFO goes from 9 to 10 while LRU goes from 10 to 8 and OPT from 7 to 6: the anomaly is a property of FIFO, not of the string. With 7 frames (one per distinct page) every algorithm has only the 7 first-use faults.

EX 2LRU by hand on the first references

Easy

Frames empty; references 1, 2, 3, 4, 2, 1. Reference 1, 2, 3: three faults (the frames fill). Reference 4: fault; the pages' last uses are 1 at time 1, 2 at time 2, 3 at time 3, so LRU evicts page 1 (frames 4, 2, 3). Reference 2: hit (page 2 becomes the most recent). Reference 1: fault; last uses are 4 at time 4, 2 at time 5, 3 at time 3, so page 3 is evicted (frames 4, 2, 1). Compare FIFO on the same references: at the fault for page 4 it also evicts page 1 (the oldest), giving frames 4, 2, 3; page 2 is a hit; but at the fault for page 1 FIFO evicts the oldest loaded page, page 2, although page 2 has just been used. LRU evicted page 3 and kept the recently used page 2: this is the difference between the two.

EX 3The clock algorithm in action

Medium

Three frames filled by 1, 2, 3 (all reference bits 1, hand at frame 0). Reference 4 faults and all pages have bit 1: the hand clears bit after bit as it sweeps (page 1, then page 2, then page 3 each get a second chance), returns to page 1, which now has bit 0 and is evicted; page 4 enters with bit 1 and the hand moves on. If all bits are 1 at every fault, the clock behaves like FIFO. Reference 2 is a hit: its bit becomes 1 again. The animation shows each bit and the hand: the clock does what LRU would do for a page that was recently referenced, at a small fraction of LRU's cost, because the hardware only sets one bit.

EX 4Counting faults and the hit ratio

Medium

For the main string with 3 frames: FIFO has 16 faults, so $20 - 16 = 4$ hits and a hit ratio of $4/20 = 0.2$ ; LRU: 15 faults, 5 hits, ratio 0.25; OPT: 11 faults, 9 hits, ratio 0.45. With the fault rate $p = 16/20 = 0.8$ (FIFO) and the effective access time formula of the previous page, such a rate would be disastrous: it shows why a process needs enough frames for its working set (thrashing). If a question gives a string of references and asks for the number of replacements instead of faults, subtract the faults that only filled empty frames (3 here): FIFO 13.

EX 5True or false?

GATE level

"Increasing the number of frames always reduces the number of page faults." False for FIFO (Belady); true for LRU and OPT. "LRU is a stack algorithm." True. "OPT can be implemented in a real system." No, it needs the future; it is used to measure other algorithms. "The number of page faults is at least the number of distinct pages in the reference string." True: each distinct page must be loaded at least once. "With a frame for every distinct page, all algorithms have the same number of faults." True: only first-use faults (7 here). In the enhanced second chance algorithm, which page is evicted first? The one in the lowest class: $(r, m) = (0, 0)$ , then $(0, 1)$ , then $(1, 0)$ , then $(1, 1)$ .

Cheat box

Faults counted from the first load: every reference to a page not in a frame, including fills of empty frames.
FIFO: oldest loaded. LRU: least recently used. OPT: used farthest in the future (minimum faults, not implementable).
Belady's anomaly: FIFO can fault more with more frames. LRU and OPT are stack algorithms: never.
Second chance / clock: FIFO that spares pages with reference bit 1 (clearing it). Enhanced: classes $(r, m)$ , $(0, 0)$ best.
LFU evicts the smallest count; MFU the largest.
Faults $\ge$ number of distinct pages; with a frame per distinct page, faults $=$ distinct pages.
The standard Belady string 1 2 3 4 1 2 5 1 2 3 4 5: FIFO 9 (3 frames), 10 (4 frames).

Traps and GATE patterns

Connections

Builds on

Virtual memory and demand paging

Unlocks

Cache replacement and write policiesanalogous to Virtual memory and demand paginguses Thrashing and the working setPrerequisite of Thrashing and the working setuses

Across subjects

Cache replacement and write policiesanalogous-to

Within this subject

Virtual memory and demand paginguses Thrashing and the working setuses TLB and effective access timeuses

Replacement is the step inside the fault handling of virtual memory; too few frames for the working set leads to thrashing. The same problem appears in the CPU cache, with the same names (LRU, FIFO, random) in cache replacement. A replaced page's TLB entry must be invalidated (TLB).

PYQs

17 previous year questions from your book. I re-solved each one myself (13 by running or simulating, 4 by reasoning only); the book's key is shown next to my answer. All PYQs

GATE 2025 · MSQQ5 · page 340 of the book

Consider a demand paging system with three frames, and the
following page reference string:1 2 3 4 5 4 1 6 4 5 1 3 2
          The contents of the frames are shown initially and after each
reference.

          The *-marked references cause page replacements.
          Which one or more of the following could be the page
replacement policy/policies in use?

(a)Least Recently Used page replacement policy
(b)Least Frequently Used page replacement policy
(c)Most Frequently Used page replacement policy
(d)Optimal page replacement policy OPERATING SYSTEMS

GATE 2025 · NATQ8 · page 341 of the book

In
optimal
page
replacement
algorithm,
information about all future page references is
available to the operating system (OS). A
modification of the optimal page replacement
algorithm is as follows: The OS correctly predicts
only up to next 4 page references (including the
current page) at the time of allocating a frame to a
page. A process accesses the pages in the following
order of page numbers: 1, 3, 2, 4, 2, 3, 1, 2, 4, 3, 1,
4. If the system has three memory frames that are
initially empty, the number of page faults that will
occur during execution of the process is ________
. (Answer in integer)

GATE 2023 · MCQQ12 · page 342 of the book

Consider the following two-dimensional array D in
the C programming language, which is stored in
row-major order:

int D[128][128];

Demand paging is used for allocating memory and
each physical page frame holds 512 elements of the
array D. The Least Recently Used (LRU) page-
replacement policy is used by the operating system.
A total of 30 physical page frames are allocated to
a process that executes the following code snippet:

for (int i = 0; i < 128; i++)

for (int j = 0; j < 128; j++)

D[j][i] *= 10;

The number of page faults generated during the
execution of this code snippet is

(a)2048
(b)512
(c)4096
(d)1032

GATE 2022 · NAT · 2 marksQ15 · page 342 of the book

Consider a demand paging system with four-page
frames (initially empty) and an LRU page
replacement policy. For the following page reference
string 7, 2,7,3, 2,5,3, 4,6,7,7,1,5,6,1 the page fault
rate, defined as the ratio of number of page faults to
the number of memory accesses (rounded off to one
decimal place) is_________.

year not read yetQ22 · page 343 of the book

Recall that Belady's anomaly is that the page-fault
rate may increase as the number of allocated frames
increases. Now, consider the following statements:

S1: Random page replacement algorithm (where a
page chosen at random is replaced) suffers from
Belady's anomaly

S2: LRU page replacement algorithm suffers from
Belady's anomaly

Which of the following is CORRECT?

(a)S1 is true, S2 is true.
(b)S1 is true, S2 is false.
(c)S1 is false, S2 is true.
(d)S1 is false, S2 is false.

GATE 2016 · MCQQ23 · page 343 of the book

In which one of the following page replacement
algorithms is it possible for the page fault rate to
increase even when the number of allocated frames
increases?

(a)LRU (Least Recently Used)
(b)OPT (Optimal Page Replacement)
(c)MRU (Most Recently Used)
(d)FIFO (First In First Out) OPERATING SYSTEMS

year not read yetQ24 · page 344 of the book

Consider a computer system with ten physical
page frames. The system is provided with an
access sequence (a1, a2,........., a20, a1, a2, ...... a20),
where each ai is a distinct virtual page number.
The difference in the number of page faults
between the last-in-first-out page replacement
policy and the optimal page replacement policy is
__.

GATE 2015 · MCQQ26 · page 344 of the book

Consider a main memory with five page frames and
the following sequence of page references: 3, 8, 2,
3, 9, 1, 6, 3, 8, 9, 3, 6, 2, 1, 3. Which one of the
following is true with respect to page replacement
policies First-In-First Out (FIFO) and Least
Recently Used (LRU)?

(a)Both incur the same number of page faults
(b)FIFO incurs 2 more page faults than LRU
(c)LRU incurs 2 more page faults than FIFO
(d)FIFO incurs 1 more page faults than LRU

GATE 2014 · NATQ32 · page 345 of the book

A system uses 3 page frames for storing process
pages in main memory. It uses the Least Recently
Used (LRU) page replacement policy. Assume that
all the page frames are initially empty. What is the
total number of page faults that will occur while
processing the page reference string given below?
          4, 7, 6, 1, 7, 6, 1, 2, 7, 2

GATE 2014 · MCQQ33 · page 345 of the book

A computer has twenty physical page frames which
contain pages numbered 101 through 120. Now a
program accesses the pages numbered 1, 2, ..., 100
in that order, and repeats the access sequence thrice.
Which one of the following page replacement
policies experiences the same number of page
faults as the optimal page replacement policy for
this program?

(a)Least-recently-used
(b)First-in-first-out
(c)Last-in-first-out
(d)Most-recently-used

GATE 2014 · NATQ34 · page 345 of the book

Assume that there are 3 page frames which are
initially empty. If the page reference string is
1,
2,
3,
4,
2,
1,
5,
3,
2,
4,
6
the number of page faults using the optimal
replacement policy is ______

GATE 2012 · MCQ · 2 marksQ37 · page 345 of the book

Consider the virtual page reference string 1, 2, 3, 2, 4,
1, 3, 2, 4, 1 On a demand paged virtual memory
system running on a computer system that has a main
memory size of 3 pages frames which are initially
empty. Let LRU, FIFO and OPTIMAL denote the
number of page faults under the corresponding page
replacements policy. Then

(a)OPTIMAL < LRU < FIFO
(b)OPTIMAL < FIFO < LRU
(c)OPTIMAL = LRU
(d)OPTIMAL = FIFO OPERATING SYSTEMS

GATE 2010 · MCQ · 1 markQ39 · page 346 of the book

A system uses FIFO policy for page replacement. It
has 4 page frames with no pages loaded to begin
with. The system first accesses 100 distinct pages
in some order and then accesses the same 100 pages
but now in the reverse order.

How many page faults will occur?

(a)196
(b)192
(c)197
(d)195

GATE 2009 · MCQ · 1 markQ40 · page 346 of the book

In which one of the following page replacement
policies, Belady's anomaly may occur?

(a)FIFO
(b)Optimal
(c)LRU
(d)MRU

GATE 2007 · MCQ · 2 marksQ44 · page 347 of the book

A virtual memory system uses First In First Out
(FIFO) page replacement policy and allocates a
fixed number of frames to a process. Consider the
following statements:

P: Increasing the number of page frames allocated
to a process sometimes increases the page fault rate.

Q: Some programs do not exhibit locality of reference.

Which one of the following is TRUE?

(a)Both P and Q are true, and Q is the reason for P.
(b)Both P and Q are true, but Q is not the reason for P.
(c)P is false, but Q is true.
(d)Both P and Q are false.

GATE 2007 · MCQ · 2 marksQ45 · page 347 of the book

A process has been allocated 3 page frames.
Assume that none of the pages of the process are
available in memory initially.

The process makes the following sequence of page
references (reference string):

1, 2, 1, 3, 7, 4, 5, 6, 3, 1

If optimal page replacement policy is used, how
many page faults occur for the above reference string?

(a)7
(b)8
(c)9
(d)10

GATE 2007 · MCQ · 2 marksQ46 · page 347 of the book

A process has been allocated 3 page frames.
Assume that none of the pages of the process are
available in memory initially.

The process makes the following sequence of page
references (reference string):

1, 2, 1, 3, 7, 4, 5, 6, 3, 1

Least Recently Used (LRU) page replacement policy is
a practical approximation to optimal page replacement.

For the above reference string, how many more
page faults occur with LRU than with the optimal
page replacement policy?

(a)0
(b)1
(c)2
(d)3

Self-check

Question 1

Reference string 1 2 3 1 4 2 1 5 with 3 frames. FIFO and LRU fault counts?

Show answer

FIFO: faults at 1, 2, 3, 4 (evicts 1), 1 (evicts 2, the oldest; reference 2 was a hit), 5 (evicts 3): 6 faults. LRU: faults at 1, 2, 3, 4 (evicts 2, the least recently used since 1 was just used), 2 (evicts 3), 5 (evicts 4); the hits are the second 1 and the third 1: 6 faults as well.

Question 2

What is the minimum number of faults for any algorithm on a string with 6 distinct pages, whatever the number of frames?

Show answer

6: each distinct page must be loaded at least once.

Question 3

Why can the clock algorithm degenerate into FIFO?

Show answer

If every page has reference bit 1, the hand clears them all and returns to the page where it started, which is the oldest: it evicts that one, exactly as FIFO would.

Question 4

An algorithm has the property that the pages in memory with $n$ frames are a subset of those with $n + 1$ frames. Can it suffer Belady's anomaly?

Show answer

No: it is a stack algorithm, and for those more frames never mean more faults.

Revision card

One-screen revision

Count every reference not in a frame as a fault. FIFO oldest loaded; LRU least recently used; OPT farthest next use.
Belady: FIFO only (9 vs 10 on 1 2 3 4 1 2 5 1 2 3 4 5). Stack algorithms (LRU, OPT) never.
Clock: reference bit 1 earns a second chance; enhanced uses $(r, m)$ , $(0, 0)$ is the best victim.
Faults $\ge$ distinct pages.

References

·Silberschatz, Galvin, Gagne, Operating System Concepts, Chapter 10 Virtual Memory (page replacement: FIFO, optimal, LRU, LRU-approximation, counting-based, page-buffering)
·Tanenbaum and Bos, Modern Operating Systems, Chapter 3 Memory Management (page replacement algorithms)
·Stallings, Operating Systems: Internals and Design Principles, Chapter 8 Virtual Memory (replacement policy)

Verification

The five replacement traces are produced by a simulator (scripts/gen-os-vm-traces.py). scripts/enum-checks/os_vm.py compares its fault counts with second implementations (a queue for FIFO, an ordered dictionary for LRU, a look-ahead for OPT, a circular queue for the clock) on 1500 random reference strings; confirms by EXHAUSTIVE search over every eviction choice that OPT gives the minimum number of faults of any policy (300 small strings); checks the stack (inclusion) property of LRU and that LRU and OPT never fault more with more frames while FIFO sometimes does; and checks the page examples. tests/os-vm-traces.test.ts re-simulates every step in TypeScript and the C program on this page (npm run verify:c) is a third implementation that prints the same counts. Conventions that change answers: a page loaded on a fault counts as referenced (clock bit 1); the clock hand moves to the frame after the one just filled; free frames are used before any replacement; an empty frame counts as a fault when first filled. Textbook chapter titles are from memory. SECOND PASS (2026-11-02, done by the assistant, not a human check): every Self-check question was solved before the printed answer was read and all agreed; the definitions, worked examples, cheat box and traps were read claim by claim and the numbers re-derived by hand. No defect found. Status raised to self-checked; verified needs a textbook or human check.

last verified: never

My notes (saved in this browser)

TLB and effective access time

Thrashing and the working set