Page Replacement: FIFO, LRU and the Optimal Policy

Memory has a few frames, each holding one page, and the program asks for pages in the order of the reference string. A page already in a frame is a hit. Any other is a fault, and when every frame is full a page has to go: FIFO throws out the one loaded longest ago, LRU the one used longest ago, OPT the one needed furthest in the future.

Worked example — Page Replacement: FIFO, LRU and the Optimal Policy

References	12
FIFO faults with 3 frames: references − hits	9
LRU faults with 3 frames: references − hits	10
OPT faults with 3 frames: references − hits	7

These are the values the calculator shows when the page opens. Change any input above to recompute them.

Loading interactive simulation...

Lesson

The theory — Page Replacement: FIFO, LRU and the Optimal Policy

Memory is divided into frames of equal size, and a program's data into pages of the same size, so any page fits any frame. The reference string is the sequence of pages a program touches. A reference to a page not in memory is a page fault: the page is loaded, and if no frame is free a replacement policy chooses which page to evict. With F frames, a policy shows Bélády's anomaly on a string if it faults more with F + 1 frames than with F.

What each symbol means

F: the number of frames
n: the number of pages in a loop (worked problem)
r: how many times the loop runs

Assumes: Demand paging: a page is loaded only when it is asked for, and memory starts empty, so the first reference to every page faults under every policy. When several pages are never needed again, OPT here evicts the lowest-numbered. Each reference is one page; reads and writes are not told apart, and an evicted page costs nothing to throw out. Exact LRU needs the time of every memory access, which is too costly to record, so real kernels approximate it with a referenced bit per page; the clock algorithm is the best known of these.

One more frame, one more fault 🖖

Press FIFO, 3 frames, then FIFO, 4 frames. The string is 1 2 3 4 1 2 5 1 2 3 4 5, and the bigger memory faults more: 10 times against 9. Step both to step 7, where page 5 arrives. With three frames, pages 1 and 2 had already been thrown out and loaded again, so they are the newest, and FIFO evicts 4. With four frames, 1 and 2 never left, so page 1 is the oldest load in memory, and FIFO evicts it one step before the program asks for it. Bélády, Nelson and Shedler described the effect in 1969. It is rare: we ran FIFO over every reference string shorter than twelve, with any number of pages, and none does it. Of the 4,213,597 strings of exactly twelve (two strings counted once when they differ only in what the pages are called), eight do, every one of them beginning 1 2 3 4 1 2 5 1 and every one costing a single extra fault going from three frames to four. This one is the only one of the eight with five pages.

LRU and OPT never fault more with more memory 🖖

Press LRU, 4 frames: 8 faults on the same string, against 10 with three. With F frames, LRU holds the F pages used most recently; with F + 1 it holds those and one more. So at every step the smaller memory's pages are all in the larger one, and a reference that hits in three frames hits in four. FIFO holds the pages loaded most recently, and a different number of frames gives a different history of loads: after step 7, three frames hold 1, 2 and 5, while four hold 2, 3, 4 and 5. OPT has the same nesting as LRU. Policies with it are called stack algorithms, and the table under the results, which counts the faults for every number of frames, never goes up for them. For FIFO it can go up, and the cell where it does is marked.

A loop one page too big for memory defeats LRU completely 🖖

Press Loop, LRU: five pages read in order, three times over, with four frames. Every one of the 15 references faults, because the page used longest ago is always the one the loop wants next. FIFO does exactly the same. Press Loop, OPT and the count drops to 7. OPT throws out the page needed furthest ahead, at steps 5 and 9 the page it has just read, and it can only know which page that is because it reads the string to the end before choosing. No operating system can do that. What OPT gives is the yardstick: the fewest faults any policy could have had on this string. Give the loop a fifth frame and all three fault 5 times, once per page.

Problem solved in full

When LRU faults on every reference 5 steps
Press Loop, OPT and say where its 7 faults fall. Then take a program that sums an array filling 100 pages, 1,000 times over, with 99 frames. How many faults does LRU make, how many does OPT make, and how many with a 100th frame?

Open this problem in the tool
1. On the page, the first five references fault: four fill the empty frames and the fifth evicts. After that the faults fall at steps 9 and 13, four references apart: 5 + 2 = 7.
  
  $5 + 2 = 7 faults: steps 1 - 5, 9, 13$
2. Why every four. With n − 1 frames and a loop of n pages, exactly one page of the loop is out of memory. At a fault, the page needed furthest ahead is the one read just before, which comes round again in n − 1 references (on the last pass some pages are not needed again, and OPT may evict one of those instead). Evicting it leaves the next n − 2 references in memory, so the next fault is n − 1 references later.
  
  $n - 1 frames : one fault every n - 1 references$
3. LRU with 99 frames: when page p faults, the frames hold every other page, and the one used longest ago is p + 1, the next page the loop asks for. Every one of the 100 × 1,000 = 100,000 references faults, as on the page, where all 15 did. FIFO evicts the same pages.
  
  $LRU : 100 \times 1000 = 100000$
4. OPT: the first 99 references fill the frames. From the 100th on, a fault every 99 references, at references 100, 199, 298, …: 1 + ⌊(100,000 − 100) / 99⌋ = 1 + 1,009 = 1,010 of them. In all 99 + 1,010 = 1,109, which is n + ⌊n(r − 1)/(n − 1)⌋ with n = 100 and r = 1,000.
  
  $OPT : 99 + (1 + ⌊ \frac{100 000 - 100}{99} ⌋) = 99 + 1010 = 1109 = n + ⌊ \frac{n ( r - 1 )}{n - 1} ⌋$
5. With a 100th frame the whole array fits: 100 faults under any of the three policies, one per page, and none after the first pass.
  
  $F = 100 : 100 faults$
Answer

LRU 100,000, OPT 1,109, and 100 with one frame more. LRU is at its worst on a loop one page bigger than memory, and the one frame that closes the gap is worth a thousandfold.

$LRU 100000, OPT 1109, 100 with one frame more$

Learning path

What a data structure makes cheap

References (1)

The first insight's date and attribution: the anomaly, and its formal treatment for FIFO: L. A. Belady, R. A. Nelson and G. S. Shedler, "An anomaly in space-time characteristics of certain programs running in a paging machine," Communications of the ACM 12(6), 349–353, June 1969.

By the 42Math team · Reviewed against published sources. Corrections welcome.