CS 134

Page Replacement

If we redraw our view of Neovim's pages, this time showing not when a page was loaded but when it was last needed, we get a different picture:

Page at 0x00000000 Loaded at 0.289ms Page at 0x00005000 Loaded at 1.665ms Page at 0x00013000 Loaded at 84.863ms Page at 0x0002e000 Loaded at 0.376ms Page at 0x00039000 Loaded at 86.083ms Page at 0x00044000 Loaded at 1.517ms Page at 0x00045000 Loaded at 2.286ms Page at 0x00051000 Loaded at 85.460ms Page at 0x00055000 Loaded at 2.377ms Page at 0x00061000 Loaded at 85.546ms Page at 0x00065000 Loaded at 2.472ms Page at 0x00071000 Loaded at 85.657ms Page at 0x00075000 Loaded at 2.814ms Page at 0x0007d000 Loaded at 3.117ms Page at 0x00090000 Loaded at 5.720ms Page at 0x00091000 Loaded at 99.161ms Page at 0x000a1000 Loaded at 432.544ms Page at 0x000b3000 Loaded at 154.056ms Page at 0x000b6000 Loaded at 154.043ms Page at 0x000bc000 Loaded at 140.207ms Page at 0x000cb000 Loaded at 92.784ms Page at 0x000d2000 Loaded at 4.409ms Page at 0x000e1000 Loaded at 4.419ms Page at 0x000e9000 Loaded at 3.901ms Page at 0x000fd000 Loaded at 5.367ms Page at 0x00108000 Loaded at 4.847ms Page at 0x00114000 Loaded at 133.838ms Page at 0x00121000 Loaded at 3.984ms Page at 0x00129000 Loaded at 4.114ms Page at 0x00132000 Loaded at 132.835ms Page at 0x00144000 Loaded at 163.709ms Page at 0x00156000 Loaded at 4.066ms Page at 0x0016e000 Loaded at 3.635ms Page at 0x00173000 Loaded at 130.469ms Page at 0x00175000 Loaded at 153.801ms Page at 0x00188000 Loaded at 149.589ms Page at 0x00197000 Loaded at 5.243ms Page at 0x001ae000 Loaded at 273.827ms Page at 0x001ba000 Loaded at 3.973ms Page at 0x001ca000 Loaded at 4.001ms Page at 0x001dd000 Loaded at 4.456ms Page at 0x001ee000 Loaded at 5.264ms Page at 0x001fc000 Loaded at 91.788ms Page at 0x00203000 Loaded at 3.918ms Page at 0x00207000 Loaded at 4.470ms Page at 0x0021b000 Loaded at 4.154ms Page at 0x00229000 Loaded at 3.809ms Page at 0x00240000 Loaded at 91.190ms Page at 0x00242000 Loaded at 4.165ms Page at 0x0024a000 Loaded at 115.805ms Page at 0x00257000 Loaded at 450.215ms Page at 0x0026b000 Loaded at 4.355ms Page at 0x0027a000 Loaded at 91.749ms Page at 0x00283000 Loaded at 3.174ms Page at 0x00285000 Loaded at 3.856ms Page at 0x00291000 Loaded at 91.922ms Page at 0x002a3000 Loaded at 4.988ms Page at 0x002aa000 Loaded at 5.000ms Page at 0x002c8000 Loaded at 4.963ms Page at 0x002d7000 Loaded at 4.561ms Page at 0x002e2000 Loaded at 194.097ms Page at 0x002fb000 Loaded at 92.340ms Page at 0x00302000 Loaded at 4.943ms Page at 0x00307000 Loaded at 4.930ms Page at 0x0031b000 Loaded at 4.953ms Page at 0x00328000 Loaded at 5.378ms Page at 0x0033b000 Loaded at 5395.712ms Page at 0x00340000 Loaded at 18961.107ms Page at 0x00350000 Loaded at 3.951ms Page at 0x00351000 Loaded at 90.764ms Page at 0x0035c000 Loaded at 5.355ms Page at 0x00362000 Loaded at 449.686ms Page at 0x00373000 Loaded at 4.836ms Page at 0x00378000 Loaded at 4.370ms Page at 0x00390000 Loaded at 4.011ms Page at 0x00398000 Loaded at 4.091ms Page at 0x003a4000 Loaded at 91.974ms Page at 0x003a8000 Loaded at 90859.549ms Page at 0x003a9000 Loaded at 3.154ms Page at 0x003ba000 Loaded at 4.044ms Page at 0x003d0000 Loaded at 120.361ms Page at 0x003d2000 Loaded at 4.606ms Page at 0x003d9000 Loaded at 3.933ms Page at 0x003ea000 Loaded at 4.330ms Page at 0x00400000 Loaded at 6.989ms Page at 0x00407000 Loaded at 6.401ms Page at 0x0041f000 Loaded at 4.649ms Page at 0x0042e000 Loaded at 4.100ms Page at 0x0047c000 Loaded at 2.275ms Page at 0x0047d000 Loaded at 2.293ms Page at 0x0047e000 Loaded at 2.300ms Page at 0x0047f000 Loaded at 2.308ms Page at 0x00480000 Loaded at 2.315ms Page at 0x00481000 Loaded at 2.322ms Page at 0x00482000 Loaded at 2.330ms Page at 0x00483000 Loaded at 2.337ms Page at 0x00484000 Loaded at 2.344ms Page at 0x00485000 Loaded at 2.351ms Page at 0x00486000 Loaded at 2.359ms Page at 0x00487000 Loaded at 2.366ms Page at 0x00488000 Loaded at 2.385ms Page at 0x00489000 Loaded at 2.392ms Page at 0x0048a000 Loaded at 2.400ms Page at 0x0048b000 Loaded at 2.411ms Page at 0x0048c000 Loaded at 2.418ms Page at 0x0048d000 Loaded at 0.302ms Page at 0x0048e000 Loaded at 2.427ms Page at 0x0048f000 Loaded at 2.434ms Page at 0x00490000 Loaded at 2.441ms Page at 0x00491000 Loaded at 2.447ms Page at 0x00492000 Loaded at 2.454ms Page at 0x00493000 Loaded at 2.461ms Page at 0x00494000 Loaded at 2.479ms Page at 0x00495000 Loaded at 2.486ms Page at 0x00496000 Loaded at 2.492ms Page at 0x00497000 Loaded at 2.499ms Page at 0x00498000 Loaded at 2.506ms Page at 0x00499000 Loaded at 2.513ms Page at 0x0049a000 Loaded at 2.520ms Page at 0x0049d000 Loaded at 2.530ms Page at 0x0049e000 Loaded at 2.536ms Page at 0x0049f000 Loaded at 2.543ms Page at 0x004a0000 Loaded at 77.250ms 0x0 0x4a0000 0.29ms 90859.55ms
Neovim Pages Loaded
Page at 0x00000000 Loaded at 81.127ms Page at 0x00005000 Loaded at 1.665ms Page at 0x00013000 Loaded at 84.863ms Page at 0x0002e000 Loaded at 81.224ms Page at 0x00039000 Loaded at 86.083ms Page at 0x00044000 Loaded at 82.579ms Page at 0x00045000 Loaded at 2.286ms Page at 0x00051000 Loaded at 85.460ms Page at 0x00055000 Loaded at 2.377ms Page at 0x00061000 Loaded at 85.546ms Page at 0x00065000 Loaded at 2.472ms Page at 0x00071000 Loaded at 85.657ms Page at 0x00075000 Loaded at 2.814ms Page at 0x0007d000 Loaded at 86.667ms Page at 0x00090000 Loaded at 99.109ms Page at 0x00091000 Loaded at 99.161ms Page at 0x000a1000 Loaded at 432.544ms Page at 0x000b3000 Loaded at 154.056ms Page at 0x000b6000 Loaded at 154.043ms Page at 0x000bc000 Loaded at 140.207ms Page at 0x000cb000 Loaded at 92.784ms Page at 0x000d2000 Loaded at 91.673ms Page at 0x000e1000 Loaded at 4.419ms Page at 0x000e9000 Loaded at 90.678ms Page at 0x000fd000 Loaded at 92.820ms Page at 0x00108000 Loaded at 92.162ms Page at 0x00114000 Loaded at 133.838ms Page at 0x00121000 Loaded at 90.813ms Page at 0x00129000 Loaded at 4.114ms Page at 0x00132000 Loaded at 132.835ms Page at 0x00144000 Loaded at 163.709ms Page at 0x00156000 Loaded at 90.898ms Page at 0x0016e000 Loaded at 87.208ms Page at 0x00173000 Loaded at 130.469ms Page at 0x00175000 Loaded at 153.801ms Page at 0x00188000 Loaded at 149.589ms Page at 0x00197000 Loaded at 92.640ms Page at 0x001ae000 Loaded at 273.827ms Page at 0x001ba000 Loaded at 90.799ms Page at 0x001ca000 Loaded at 90.829ms Page at 0x001dd000 Loaded at 91.762ms Page at 0x001ee000 Loaded at 92.676ms Page at 0x001fc000 Loaded at 91.788ms Page at 0x00203000 Loaded at 90.696ms Page at 0x00207000 Loaded at 4.470ms Page at 0x0021b000 Loaded at 91.160ms Page at 0x00229000 Loaded at 90.449ms Page at 0x00240000 Loaded at 91.190ms Page at 0x00242000 Loaded at 91.174ms Page at 0x0024a000 Loaded at 115.805ms Page at 0x00257000 Loaded at 450.215ms Page at 0x0026b000 Loaded at 91.579ms Page at 0x0027a000 Loaded at 91.749ms Page at 0x00283000 Loaded at 86.737ms Page at 0x00285000 Loaded at 3.856ms Page at 0x00291000 Loaded at 91.922ms Page at 0x002a3000 Loaded at 92.302ms Page at 0x002aa000 Loaded at 5.000ms Page at 0x002c8000 Loaded at 92.277ms Page at 0x002d7000 Loaded at 91.880ms Page at 0x002e2000 Loaded at 194.097ms Page at 0x002fb000 Loaded at 92.340ms Page at 0x00302000 Loaded at 4.943ms Page at 0x00307000 Loaded at 92.250ms Page at 0x0031b000 Loaded at 92.266ms Page at 0x00328000 Loaded at 92.831ms Page at 0x0033b000 Loaded at 5395.712ms Page at 0x00340000 Loaded at 18961.107ms Page at 0x00350000 Loaded at 90.743ms Page at 0x00351000 Loaded at 90.764ms Page at 0x0035c000 Loaded at 5.355ms Page at 0x00362000 Loaded at 449.686ms Page at 0x00373000 Loaded at 4.836ms Page at 0x00378000 Loaded at 91.624ms Page at 0x00390000 Loaded at 90.838ms Page at 0x00398000 Loaded at 90.923ms Page at 0x003a4000 Loaded at 91.974ms Page at 0x003a8000 Loaded at 90859.549ms Page at 0x003a9000 Loaded at 86.702ms Page at 0x003ba000 Loaded at 90.872ms Page at 0x003d0000 Loaded at 120.361ms Page at 0x003d2000 Loaded at 4.606ms Page at 0x003d9000 Loaded at 90.719ms Page at 0x003ea000 Loaded at 91.555ms Page at 0x00400000 Loaded at 125.687ms Page at 0x00407000 Loaded at 122.633ms Page at 0x0041f000 Loaded at 91.964ms Page at 0x0042e000 Loaded at 90.932ms Page at 0x0047c000 Loaded at 90859.340ms Page at 0x0047d000 Loaded at 24489.653ms Page at 0x0047e000 Loaded at 86676.750ms Page at 0x0047f000 Loaded at 426.141ms Page at 0x00480000 Loaded at 86683.994ms Page at 0x00481000 Loaded at 6426.691ms Page at 0x00482000 Loaded at 25850.127ms Page at 0x00483000 Loaded at 25848.958ms Page at 0x00484000 Loaded at 25850.331ms Page at 0x00485000 Loaded at 87798.338ms Page at 0x00486000 Loaded at 90838.691ms Page at 0x00487000 Loaded at 36248.307ms Page at 0x00488000 Loaded at 25851.502ms Page at 0x00489000 Loaded at 25850.521ms Page at 0x0048a000 Loaded at 25851.718ms Page at 0x0048b000 Loaded at 25850.742ms Page at 0x0048c000 Loaded at 2.418ms Page at 0x0048d000 Loaded at 90843.798ms Page at 0x0048e000 Loaded at 90844.326ms Page at 0x0048f000 Loaded at 90859.532ms Page at 0x00490000 Loaded at 90846.632ms Page at 0x00491000 Loaded at 454.936ms Page at 0x00492000 Loaded at 90796.751ms Page at 0x00493000 Loaded at 90797.839ms Page at 0x00494000 Loaded at 90797.139ms Page at 0x00495000 Loaded at 90797.446ms Page at 0x00496000 Loaded at 86684.874ms Page at 0x00497000 Loaded at 86684.466ms Page at 0x00498000 Loaded at 453.085ms Page at 0x00499000 Loaded at 452.225ms Page at 0x0049a000 Loaded at 90858.124ms Page at 0x0049d000 Loaded at 90823.557ms Page at 0x0049e000 Loaded at 90852.889ms Page at 0x0049f000 Loaded at 90857.026ms Page at 0x004a0000 Loaded at 90853.088ms 0x0 0x4a0000 0.29ms 90859.55ms
Neovim Pages Needed
  • Dog speaking

    Wow! A ton of these pages were used when Neovim loaded but weren't needed afterwards.

  • PinkRobot speaking

    That's right.

  • Horse speaking

    Hay! This isn't the same picture I saw on the last page. What's going on here?

  • PinkRobot speaking

    To get the information needed to draw this diagram, I switched to using the CS 134 server, which is a 64-bit machine. In this case, there are 1185 pages (4.6 MB) of code loaded for Neovim, of which we only actually needed 123 pages (492 KB), so, again, 90% of Neovim's pages were never used.

  • BlueRobot speaking

    Also, of those 123 pages, 93 of them (75%) weren't touched after Neovim had been running for 20 seconds.

Page Traces

To further explore the idea of page replacement, we could look at a page trace—the sequence of pages that were needed over time. Unfortunately, the page trace for Neovim is too large for us to explore here (~43,305 page accesses!), so we'll look at a page trace from the ls program (only 1013 page accesses).

Here's a complete page trace of all the instruction-fetch accesses from the ls code itself (ignoring library calls).

2, 0, 20, 1, 14, 2, 0, 5, 1, 13, 4, 0, 5, 1, 6, 2, 12, 0, 1, 13, 5, 6, 0, 19, 7, 14, 15, 0, 19, 20, 12, 13, 7, 8, 0, 19, 14, 15, 7, 0, 19, 20, 12, 13, 7, 8, 0, 19, 14, 15, 7, 0, 19, 20, 12, 13, 7, 8, 0, 19, 14, 15, 7, 0, 19, 20, 12, 13, 7, 8, 0, 19, 14, 15, 7, 0, 19, 20, 12, 13, 7, 8, 0, 19, 14, 15, 7, 0, 19, 20, 12, 13, 7, 8, 0, 19, 14, 15, 7, 0, 19, 20, 12, 13, 7, 8, 0, 19, 14, 15, 7, 0, 19, 20, 12, 13, 7, 8, 0, 19, 14, 15, 7, 0, 19, 20, 12, 13, 7, 8, 0, 19, 14, 15, 7, 0, 19, 20, 12, 13, 7, 8, 0, 19, 14, 15, 7, 0, 19, 20, 12, 13, 7, 8, 0, 19, 14, 15, 7, 0, 19, 20, 12, 13, 7, 8, 0, 19, 14, 15, 7, 0, 19, 20, 12, 13, 7, 8, 0, 19, 14, 15, 7, 0, 19, 20, 12, 13, 7, 8, 0, 19, 14, 15, 7, 0, 19, 20, 12, 13, 7, 8, 0, 19, 14, 15, 7, 0, 19, 20, 12, 13, 7, 8, 0, 19, 14, 15, 7, 0, 19, 20, 12, 13, 7, 8, 0, 19, 14, 15, 7, 0, 19, 20, 12, 13, 7, 8, 0, 19, 14, 15, 7, 0, 19, 20, 12, 13, 7, 8, 0, 19, 14, 15, 7, 0, 19, 20, 12, 13, 7, 8, 0, 19, 14, 15, 7, 0, 19, 20, 12, 13, 7, 8, 0, 19, 14, 15, 7, 0, 19, 20, 12, 13, 7, 8, 0, 19, 14, 15, 7, 0, 19, 20, 12, 13, 7, 8, 0, 19, 14, 15, 7, 0, 19, 20, 12, 13, 7, 8, 0, 19, 14, 15, 7, 0, 19, 20, 12, 13, 7, 8, 0, 19, 14, 15, 7, 0, 19, 20, 12, 13, 7, 8, 0, 19, 14, 15, 7, 0, 19, 20, 12, 13, 7, 8, 0, 19, 14, 15, 7, 0, 19, 20, 12, 13, 7, 8, 0, 19, 14, 15, 7, 0, 19, 20, 12, 13, 7, 8, 0, 19, 14, 15, 7, 0, 19, 20, 12, 13, 7, 8, 0, 19, 14, 15, 7, 0, 19, 20, 12, 13, 7, 8, 0, 19, 14, 15, 7, 0, 19, 20, 12, 13, 7, 8, 0, 19, 14, 15, 7, 0, 19, 20, 12, 13, 7, 8, 0, 19, 14, 15, 7, 0, 19, 20, 12, 13, 7, 8, 0, 19, 14, 15, 7, 0, 19, 20, 12, 13, 7, 8, 0, 19, 14, 15, 7, 0, 19, 20, 12, 13, 7, 8, 0, 19, 14, 15, 7, 0, 19, 20, 12, 13, 7, 8, 0, 19, 14, 15, 7, 0, 19, 20, 12, 13, 7, 8, 0, 19, 14, 15, 7, 0, 19, 20, 12, 13, 7, 8, 0, 19, 14, 15, 7, 0, 19, 20, 12, 13, 7, 8, 0, 19, 14, 15, 7, 0, 19, 20, 12, 13, 7, 8, 0, 19, 14, 15, 7, 0, 19, 20, 12, 13, 7, 8, 0, 19, 14, 15, 7, 0, 19, 20, 12, 13, 7, 8, 0, 10, 16, 7, 4, 6, 0, 10, 13, 12, 11, 0, 9, 20, 10, 16, 0, 7, 8, 10, 20, 12, 4, 0, 9, 20, 10, 16, 0, 7, 8, 10, 20, 12, 4, 0, 9, 20, 10, 16, 0, 7, 8, 10, 20, 12, 0, 9, 10, 16, 7, 8, 20, 12, 4, 0, 9, 20, 10, 16, 0, 7, 8, 10, 20, 12, 4, 0, 9, 20, 10, 16, 0, 7, 8, 10, 20, 12, 0, 9, 10, 16, 7, 8, 20, 12, 4, 0, 9, 20, 10, 16, 0, 7, 8, 10, 20, 12, 4, 0, 9, 20, 10, 16, 0, 7, 8, 10, 20, 12, 0, 9, 10, 16, 7, 8, 20, 12, 4, 0, 9, 20, 10, 16, 0, 7, 8, 10, 20, 12, 4, 0, 9, 20, 10, 16, 0, 7, 8, 10, 20, 12, 0, 9, 10, 16, 7, 8, 20, 12, 4, 0, 9, 20, 10, 16, 0, 7, 8, 10, 20, 12, 4, 0, 9, 20, 10, 16, 0, 7, 8, 10, 20, 12, 0, 9, 10, 16, 7, 8, 20, 12, 4, 0, 9, 20, 10, 16, 0, 7, 8, 10, 20, 12, 4, 0, 9, 20, 10, 16, 0, 7, 8, 10, 20, 12, 0, 9, 10, 16, 7, 8, 20, 12, 4, 0, 9, 20, 10, 16, 0, 7, 8, 10, 20, 12, 4, 0, 9, 20, 10, 16, 0, 7, 8, 10, 20, 12, 0, 9, 10, 16, 7, 8, 20, 12, 4, 0, 9, 20, 10, 16, 0, 7, 8, 10, 20, 12, 4, 0, 9, 20, 10, 16, 0, 7, 8, 10, 20, 12, 0, 9, 10, 16, 7, 8, 20, 12, 4, 0, 9, 20, 10, 16, 0, 7, 8, 10, 20, 12, 4, 0, 9, 20, 10, 16, 0, 7, 8, 10, 20, 12, 0, 9, 10, 16, 7, 8, 20, 12, 4, 0, 9, 20, 10, 16, 0, 7, 8, 10, 20, 12, 4, 0, 9, 20, 10, 16, 0, 7, 8, 10, 20, 12, 0, 9, 10, 16, 7, 8, 20, 12, 4, 0, 9, 20, 10, 16, 0, 7, 8, 10, 20, 12, 4, 0, 9, 20, 10, 16, 0, 7, 8, 10, 20, 12, 0, 9, 10, 16, 7, 8, 20, 12, 4, 0, 9, 20, 10, 16, 0, 7, 8, 10, 20, 12, 4, 0, 9, 20, 10, 16, 0, 7, 8, 10, 20, 12, 0, 9, 10, 16, 7, 8, 20, 12, 4, 0, 9, 20, 10, 16, 0, 7, 8, 10, 20, 12, 4, 0, 9, 20, 10, 16, 0, 7, 8, 10, 20, 12, 0, 9, 10, 16, 7, 8, 20, 12, 4, 0, 9, 20, 10, 16, 0, 7, 8, 10, 20, 12, 0, 9, 10, 16, 7, 8, 20, 12, 4, 0, 9, 20, 10, 16, 0, 7, 8, 10, 20, 12, 0, 1, 7, 2, 20

We can visualize this page trace in a couple of ways. First, we could look at how often each page was accessed:

Page Access Frequency Histogram
Page Access Frequency
  • Dog speaking

    Yeah, I can totally see that pages 3, 17, and 18 are never accessed.

  • Hedgehog speaking

    And 1, 2, 5, 6, and 11 are pretty unloved, too.

  • Pig speaking

    And page 0 gets MORE access than any other page!

The graph makes it clear that some pages are accessed a lot, while others are accessed very infrequently or not at all. But a timeline view can also be helpful:

Page Access Timeline
Page Access Timeline
  • Horse speaking

    Whoa! You can totally see there's, like, a phase change halfway through this trace.

  • Duck speaking

    You know, I think ls might be able to live in about 10 pages of memory.

  • PinkRobot speaking

    But then we'd need a strategy for deciding which pages to keep in memory and which to evict.

Page-Replacement Strategies

Let's look at a few different strategies for deciding which page to replace when a new page is needed and there's not enough unused memory to load it.

First-In, First-Out (FIFO)

First-In, First-Out (FIFO) is the simplest page-replacement strategy. When a page needs to be replaced, the page that has been in memory the longest is chosen.

Below is a page-replacement simulator that runs our trace from ls using our chosen page-replacement strategy.

The diagram shows all the frames of physical memory in the system.

  • Initially, all frames are empty, and colored gray.
  • When a page is loaded into a frame, it changes color, shifting from
    • light blue when it is first loaded, to
    • purple when it has been in a frame a long time.

You can move forward through the trace by clicking the Step Forward button to see the next page access, or you can use the Step to Next Fault button to skip ahead to the next page fault. (And then try to determine which page will be replaced yourself!). You can also adjust the long horizontal slider to jump to any specific point in the trace.

Visualization of Page Replacement

Page Frames
Step: XX
Next Page: XX
Status: Message
Total page faults: 0
  

FIFO Investigation

Over the entire trace, how many page faults occur when using the FIFO page-replacement strategy with 10 frames?

Do you notice anything interesting about when the page faults occur?

  • Cat speaking

    There are some long runs where no page faults occur. That's interesting.

  • PinkRobot speaking

    So we can say that much of the time, the pages in memory are sufficient to handle the page accesses. So even though there are 21 possible pages, we don't do too badly with just 10 frames of memory to hold them.

  • Duck speaking

    I wonder what would happen if we changed the number of frames.

  • PinkRobot speaking

    Let's find out.

Click the button below to enable more controls, including the ability to change the number of frames (and the page-replacement strategy, although right now we're only using FIFO).


Clicking this button also enables something else: A glimpse of the future! In the bottom-right corner of each frame, you'll see an indication of when its contents will be needed next. The square's color ranges between

  • light green when it will be needed soon; and
  • brown when it will be needed later.

Do you notice anything about how the number of page faults changes as you increase or decrease the number of available frames?

Also, does the added glimpse of the future help you judge how well FIFO is doing at replacing pages?

  • Horse speaking

    Whoa! Dropping below 8 frames really makes the number of page faults skyrocket.

When a program has too few frames and the number of page faults increases dramatically, we say that the program is thrashing. The system is spending so much time swapping pages in and out of memory that it's not getting any real work done.

  • Duck speaking

    That glimpse into the future is really helpful. It shows that just because a page has been in memory a long time doesn't mean it's no longer needed. I think we should try for a better strategy.

Optimal Page Replacement

Click the button below to enable the optimal page-replacement strategy. This strategy replaces the page that won't be needed for the longest time.


The button also adds a second indicator to the frames. In the bottom-left corner of each frame, you'll see a small square whose color ranges between

  • light green was last accessed recently; and
  • brown was last accessed a long time ago.

Now go back to the simulator, use the dropdown to select the optimal strategy, and see how Optimal compares to FIFO.

How many page faults does the optimal strategy have with 10 frames?

  • Dog speaking

    Optimal is so much better than FIFO! It's like magic!

  • Hedgehog speaking

    With 8 frames, it manages 117 page faults, which is way better than FIFO's 416.

  • Cat speaking

    Yes, but it's a bit too magical. In real life we can't see into the future.

  • Alien speaking

    Speak for yourself!

  • Horse speaking

    Hay! I noticed something. Scrubbing back and forward with the step slider, I noticed that the color for the “past” square and the color for the “future” square are often the same. Not always, but a lot. I think we could use that.

Least Recently Used (LRU)

Based on the idea that the future might often resemble the past, we can use the Least Recently Used (LRU) strategy. This strategy replaces the page that hasn't been accessed for the longest time.

Click the button below to enable the LRU page-replacement strategy (along with two others, Least Frequently Used and Random).


This time, set the number of frames to 11 and contrast LRU with FIFO and Optimal.

You can also look at the least frequently used (LFU) strategy, which (inspired by the histogram from earlier) replaces the page that has been accessed the fewest times overall. LFU “sounds a bit like” LRU, but it's a different strategy, and it's important to understand just how different it is.

In the paging simulator, set the number of frames to 11 (at least at first), and experiment with the LRU, LFU, and Random strategies.

What do you observe about how well each strategy performs?

If LFU is not the same as LRU, why does it behave so differently?

  • Duck speaking

    I think I like LRU the best. It's close enough to Optimal, but without the future-seeing magic.

  • Hedgehog speaking

    OMG, LFU is terrible! It's like it's trying to be bad. It's too weighted down by the past. When we hit the phase change in the middle, it does everything wrong—not replacing the pages that are no longer needed because they were accessed a lot in the past and throwing out the new pages that are just starting to be accessed.

  • Dog speaking

    I guess just because two terms sound a bit alike doesn't mean they're similar. LRU and LFU are very different.

  • Goat speaking

    And Random, well, that's just dumb. It's worse than FIFO! Meh.

  • PinkRobot speaking

    Actually, let's not judge Random too harshly yet…

Pathological Cases

So far, we've looked at a real page stream from the ls command. But what if we had a pathological case, a page stream that was designed to make a particular strategy look bad?

Can you think of a page stream that would make LRU replacement perform really poorly? (Hint: Choose a stream where the number of pages that we want to access is one more than the number of frames and come up with a simple pattern that will make LRU replace a page every time.)

  • Duck speaking

    I see it. If we have 11 pages and 10 frames, and we access them in order, LRU will replace a page every time because the page we need next will always be the one we just evicted.

  • Horse speaking

    Whoa! That's terrible! LRU is so bad in that case.

  • Hedgehog speaking

    Can we see it in the simulator?

  • PinkRobot speaking

    We can!

Click the button below to enable an option that provides a sequential page stream that will make LRU perform poorly. Then go back to the simulator and see how LRU does.


  • Horse speaking

    Whoa! LRU is basically acting exactly the same as FIFO, and both are terrible.

  • Rabbit speaking

    FWIW, posix_madvise has an option POSIX_MADV_SEQUENTIAL that tells the system that we're going to access pages in order.

  • Duck speaking

    That's kinda weird. “Our regular algorithm actually can't handle this pathological case, so, uh, please tell us in advance if you're going to do it.”

  • Goat speaking

    Meh. Classic worse is better.

  • Cat speaking

    Hmm… what really intrigues me is how Random performs…

Go back to the simulator and change the stream to the pathological case. How does Random perform compared to the other strategies.

  • Goat speaking

    Meh. Are we done? I need to page out of here.

  • PinkRobot speaking

    There's more to learn, but we've reached a good stopping point for now.

(When logged in, completion status appears here.)