CS 134

Page Replacement Revisited

  • Duck speaking

    I think we're all set. LRU (least recently used) is a pretty good strategy for page replacement. Let's just use that.

  • PinkRobot speaking

    But LRU requires us to know exactly when every page was last accessed…

Why might it be considered impractical to use LRU (least recently used) as a page-replacement strategy in a real operating system?

  • Dog speaking

    So I guess we need to find a way to approximate LRU that's more practical than what we saw earlier.

Approximating LRU

Since it's too expensive to update a timestamp on every page access, we need to find a more practical way to approximate LRU. One simple option is a referenced bit—a single bit that is set whenever a page is accessed. Importantly, once the bit is set, we don't need to keep setting it unless it gets cleared. So once the bit is set, there will be no impact on performance.

If you remember the FIFO algorithm from last lesson, one of its flaws was that it could throw out one of the pages we actually need. A referenced bit can help us reduce this problem.

First-In, First-Out (FIFO) with Second-Chance

We follow the same strategy for page replacement as FIFO, but with a twist. When we need to replace a page, we can look at the referenced bit:

  • If it's not set, we know the page hasn't been accessed recently, and we can replace it (as normal for FIFO).
  • If it's set, we know the page has been accessed recently and it gets a second chance. We clear the referenced bit and move on to consider the next page.

So long as a page that got a second chance is referenced again before we cycle back to it, it will be safe from replacement.

The visualization below shows the FIFO with Second-Chance algorithm in action. The page stream is the same as before, using our 1013-step trace of page accesses from ls. We've kept the same indicators at the bottom of each frame, showing when the page was last accessed and when it will be needed next, but there are two new indicators:

  • A red arrow pointing to the frame that will be the next target for replacement (unless it gets a second chance).
  • When a page has been referenced, it shows a flag in the top right corner of the frame.
    • When the arrow moves past a flag, it's removed until the page is referenced again.

The visualization defaults to FIFO with Second-Chance, but you can switch to the FIFO, LRU, or Optimal strategies using the dropdown.

Visualization of Page Replacement

Page Frames
Paging Strategy:
Number of Frames10
Step: XX
Next Page: XX
Status: Message
Total page faults: 0
     
  • Horse speaking

    Hay! I noticed that in the dropdown, FIFO with Second-Chance is also called “Clock.”

  • PinkRobot speaking

    If you follow the arrow indicating the current target page for replacement, you'll see that it moves across all the frames left to right and then comes back to the beginning. If we arranged all the frames in a circle, the arrow would move around the circle like the hand of a clock.

Because it's so much shorter to say, from this point on we'll refer to “FIFO with Second-Chance” as the Clock algorithm.

Exploring the Algorithm

With the paging simulator set to 11 frames, scrub through the page trace and observe how the clock algorithm behaves.

Then, answer the following questions:

  1. How many page faults does FIFO with Second-Chance have with 11 frames (i.e., total faults for the entire page trace). How does that compare with Optimal, LRU, and FIFO?
  2. Scrub around with the sequence between steps 34 and 538. What do you notice?
  3. Set the step number to step 538, and slowly step through the page trace. What happens when you step forward one step from step 542 and the next few page faults afterwards? Do you notice anything suboptimal about the choices made by the FIFO with Second-Chance algorithm, and why those choices are made?
  • Cat speaking

    There's a long run where no pages are replaced, and the clock hand stays in the same place. That's because all the pages that are needed are in memory. But what's interesting is that because of that, quite quickly almost all the referenced bits get set. There are (subtle) differences in how long ago each page was accessed (as shown by the color of the lower left square) but those differences aren't captured in the totally binary referenced bit.

  • Dog speaking

    So, when we need to replace a page, we don't have a good way to distinguish between pages that were used very recently and pages that haven't been used in a while. That's why we end up replacing page 7 at step 547, even though it was used very recently and will be needed again soon.

  • Duck speaking

    I think the problem is that the clock is stopped for so long that all the pages get referenced. We need to find a way to keep the clock moving.

  • PinkRobot speaking

    Good idea!

Keeping the Clock Moving

Normally, the clock hand (which points to the next page to replace) doesn't move forward until we actually need to replace a page. But we can keep the clock moving by advancing the hand periodically, even if it doesn't have to replace a page. Perhaps we don't need to advance it for every step through the page trace, but we could advance it every few steps.

Click the button below to reveal an auto-advance control. It's currently set to zero, which means the clock won't advance automatically. You can adjust the slider to set how often the clock hand should advance.

  • 1 means advance one step through the page trace.
  • 2 means advance every other step.
  • And so on.

With auto-advance enabled and set to 4 and the number of frames set to 11, scrub through the page trace and observe how the clock algorithm behaves now.

How does the total number of page faults compare to LRU now?

  • Horse speaking

    Hay! I tried setting it to 1 and it did even better, with only 25 page faults. So we're beating LRU now!

  • PinkRobot speaking

    That is true in this case, but that was mostly luck. Remember, we're trying to approximate LRU, so we really shouldn't have an expectation that we'd do better than LRU.

  • Goat speaking

    Meh. With luck on your side, I guess worse is better.

Staying with an auto-advance of 4, do we still make a foolish choice at step 543?

  • Dog speaking

    So this is pretty cool. With just one bit we can get a pretty good approximation of LRU and reduce the amount of space we need in memory to store code.

  • Horse speaking

    Hay! Were we only thinking about code all this time? What about data?

  • PinkRobot speaking

    The nice thing about throwing away the code was that we could always reload it from disk because we have the executable file to hand. We can't throw away the program's data, though.

  • Duck speaking

    Couldn't we write the data to disk and reload it when we need it?

  • PinkRobot speaking

    Good point. We'll think about that next.

(When logged in, completion status appears here.)