Page replacement simulator

When a program touches a page that is not in memory and every frame is taken, the operating system must evict one. Enter the reference string and frame count from your exercise, pick FIFO, LRU, Optimal or Clock, and get the frame table, the fault count and the reason for each eviction.

By Semicolony staff

Page faults

Hits

References

15 / 15

Reference string

Frames after each reference

Ref	1	3	0	3	5	6	3	1	0	5	2	3	1	6	0
F1	1	1	1	1	5	5	5	1	1	1	2	2	2	6	6
F2		3	3	3	3	6	6	6	0	0	0	3	3	3	0
F3			0	0	0	0	3	3	3	5	5	5	1	1	1
	F	F	F	H	F	F	F	F	F	F	F	F	F	F	F

page loaded (F = fault)hit (H)

Step 15: Memory is full. FIFO evicts 3, loaded longest ago (step 12). 0 goes into frame 2.

So far

Page faults: 14
Hits: 1
Fault rate: 93.3%
All 15 references: 14 faults

11 is not in memory; frame 1 is free, so it is loaded there (a fault).
23 is not in memory; frame 2 is free, so it is loaded there (a fault).
30 is not in memory; frame 3 is free, so it is loaded there (a fault).
43 is already in frame 2: a hit.
5Memory is full. FIFO evicts 1, loaded longest ago (step 1). 5 goes into frame 1.
6Memory is full. FIFO evicts 3, loaded longest ago (step 2). 6 goes into frame 2.
7Memory is full. FIFO evicts 0, loaded longest ago (step 3). 3 goes into frame 3.
8Memory is full. FIFO evicts 5, loaded longest ago (step 5). 1 goes into frame 1.
9Memory is full. FIFO evicts 6, loaded longest ago (step 6). 0 goes into frame 2.
10Memory is full. FIFO evicts 3, loaded longest ago (step 7). 5 goes into frame 3.
11Memory is full. FIFO evicts 1, loaded longest ago (step 8). 2 goes into frame 1.
12Memory is full. FIFO evicts 0, loaded longest ago (step 9). 3 goes into frame 2.
13Memory is full. FIFO evicts 5, loaded longest ago (step 10). 1 goes into frame 3.
14Memory is full. FIFO evicts 2, loaded longest ago (step 11). 6 goes into frame 1.
15Memory is full. FIFO evicts 3, loaded longest ago (step 12). 0 goes into frame 2.

Faults on this string for every policy and frame count

Policy	1 frame	2 frames	3 frames	4 frames	5 frames	6 frames	7 frames
FIFO	15	14	14	9	7	6	6
LRU	15	14	13	13	8	6	6
Optimal	15	12	10	8	6	6	6
Clock	15	14	14	13	8	6	6

How to use the simulator

Paste the reference string from your exercise, separated by spaces or commas, choose the number of frames and a policy, and press "Run all". The table has one column per reference and one row per frame, as textbooks draw it: a shaded cell is where a page was loaded, F marks a fault and H a hit. "Start step by step" walks through it one reference at a time, with the reason for every eviction.

The table under the frames counts faults for every policy and frame count on your string at once, so you can check each part of a multi-part question.
If your course counts only replacements as faults, set "First loads" to "Don't count".
"Copy answer" gives the frame table as plain text, and "Copy link" an address that reopens this exact exercise.

Page replacement
Part of	Virtual memory, demand paging
Triggered by	A page fault with no free frame
Common policies	FIFO, LRU, Clock; Optimal as a yardstick
Best possible	Belady's MIN (Optimal), 1966
Known anomaly	FIFO can fault more with more frames

With demand paging, a process's pages are loaded into physical memory frames only when they are used. A reference to a page that is not in memory causes a page fault: the operating system reads the page from disk into a free frame. When no frame is free, a page replacement policy picks a victim page to evict, writing it back first if it was modified.

Disk reads are many thousands of times slower than memory accesses, so the number of faults dominates performance, and the policy that picks victims matters. Exercises reduce the problem to a reference string, the sequence of pages a program touches, and a fixed number of frames.

The four policies

FIFO evicts the page that has been in memory longest, regardless of use. It is simple, but a page loaded early and used constantly is evicted anyway.
LRU (least recently used) evicts the page whose last use is oldest, betting that the recent past predicts the near future.
Optimal, also called MIN or OPT, evicts the page whose next use is furthest away, or a page that is never used again. It needs the future, so it serves as the lower bound for the others.
Clock (second chance) keeps a reference bit per frame, set when the page is used. A hand sweeps the frames: a page with its bit set has it cleared and is skipped, and the first page with a clear bit is evicted. It approximates LRU with one bit per page.

Faults on this page's example string, 1 3 0 3 5 6 3 1 0 5 2 3 1 6 0, counting first loads:

Policy	1 frame	2 frames	3 frames	4 frames	5 frames	6 frames
FIFO	15	14	14	9	7	6
LRU	15	14	13	13	8	6
Optimal	15	12	10	8	6	6
Clock	15	14	14	13	8	6

Clock's answer depends on a convention textbooks do not agree on: whether a newly loaded page starts with its reference bit set. With three frames the example gives 14 faults if it does and 13 if it does not, so check which your course uses.

Belady's anomaly

More frames would seem to mean fewer faults, but for FIFO it is not always so. Laszlo Belady, Robert Nelson and Gerald Shedler published the effect in 1969. On the string 1 2 3 4 1 2 5 1 2 3 4 5, FIFO's faults for one to five frames are:

1 frame	2 frames	3 frames	4 frames	5 frames
12	12	9	10	5

LRU and Optimal cannot show it. They are stack algorithms: the set of pages they hold with n frames is always a subset of what they would hold with n + 1, so a hit with n frames is a hit with more. Mattson and colleagues defined the property in 1970. FIFO lacks it because the arrival order of pages depends on the number of frames. The anomaly is also rare: of 20,000 random strings of 20 references over five pages, 6 showed it for some frame count between one and five.

Locality and real systems

Programs reuse a small working set of pages for a while and then move on, which is why LRU and Clock do well in practice. Patterns that break that assumption break them: a program looping over one page more than fits makes LRU evict exactly the page it is about to need. Looping over four pages with three frames for 24 references:

FIFO	LRU	Optimal	Clock
24 faults	24 faults	10 faults	24 faults

Real kernels use Clock-like approximations rather than exact LRU, since recording the order of every memory access is too expensive. Linux keeps active and inactive page lists and uses the hardware's accessed bits, much as Clock does; databases face the same problem with their buffer pools and use similar policies.

History

Laszlo Belady studied replacement algorithms for IBM's virtual-storage research in "A study of replacement algorithms for a virtual-storage computer" in the IBM Systems Journal in 1966, which describes the optimal algorithm now called MIN. The anomaly paper with Nelson and Shedler appeared in Communications of the ACM in 1969, and Mattson, Gecsei, Slutz and Traiger's 1970 paper on storage hierarchies introduced stack algorithms, which let one pass over a trace give the fault count for every memory size. Fernando Corbató described a Clock-style algorithm for Multics in 1968.

Page replacement questions and answers

How do you count page faults?

Go through the reference string one page at a time. If the page is already in a frame it is a hit; otherwise it is a page fault, and the page is loaded into a free frame or replaces the victim the policy picks. Most textbooks count the first loads into empty frames as faults too. With three frames, this page’s example string 1 3 0 3 5 6 3 1 0 5 2 3 1 6 0 gives 14 faults with FIFO, 13 with LRU and 10 with Optimal.

What is Belady’s anomaly?

Giving FIFO more frames can cause more page faults. On the string 1 2 3 4 1 2 5 1 2 3 4 5, FIFO has 9 faults with three frames and 10 with four. LRU and Optimal are stack algorithms, whose frames for n pages are always a subset of their frames for n + 1, so they cannot show the anomaly. On random strings it is rare: 6 of 20,000 random 20-reference strings over five pages showed it here.

Why is the optimal page replacement algorithm not used in practice?

Optimal (Belady’s MIN) evicts the page whose next use is furthest in the future, which requires knowing the future references. An operating system cannot know them, so Optimal is used as a yardstick: no policy can have fewer faults on the same string and frame count.

What is the difference between LRU and Clock?

LRU evicts the page whose last use is oldest, which needs the order of every access, too expensive to keep exactly in hardware. Clock (second chance) approximates it with one reference bit per page: the hand clears set bits and evicts the first page whose bit is already clear. On the example with three frames, Clock had 14 faults against LRU’s 13.

Does the first page loaded count as a page fault?

In most operating systems textbooks, yes: the frames start empty, so the first reference to each page is a fault (a compulsory or cold miss). Some exercises count only replacements. This page counts both by default and lets you switch.

Which page replacement algorithm is best?

Optimal has the fewest faults but cannot be implemented. Among the real policies it depends on the access pattern: LRU does well when recently used pages are used again, but a loop over one page more than fits defeats it. Looping over four pages with three frames, FIFO faulted 24 times, LRU faulted 24 times, Optimal faulted 10 times, Clock faulted 24 times in 24 references.