CS 134

A Queue-Based Approach to Page Replacement

  • Duck speaking

    So, besides the clock algorithm and its variations, what other page-replacement algorithms are there?

  • PinkRobot speaking

    Let's look at the approach used on macOS and BSD (which is similar to what's used in Linux). It's based on the virtual memory design (and kernel design) that came out of CMU called Mach.

  • Goat speaking

    Meh. Bet it was in the 1960s.

  • Rabbit speaking

    The Mach operating system was developed at Carnegie Mellon University in the 1980s. It was a research project that was influential in the design of many operating systems that followed. The head of the project, Avie Tevanian, later went on to work at NeXT and then Apple, where he was the chief software architect for the Mac OS X operating system. But the idea of queues for paging predates Mach—it was used in the VAX/VMS operating system in the 1970s.

  • Goat speaking

    Meh. I knew it.

Active, Inactive, and Free Queues

Mach's approach was to move pages between three queues:

  • Active: Pages that are actively being used.
  • Inactive: Pages where we're unsure whether they're being used or not.
  • Free: Frames that we think are free and can use for new pages. If a page in the free queue is accessed, it can be reactivated.

How pages can move between these queues is shown in the following diagram:

Active 08 P06 11 P14 12 P28 13 P23 05 P22 06 P08 16 P47 17 P46 Inactive 02 P18 03 P19 04 P20 10 P04 14 P02 19 P44 21 P31 23 P09 09 P21 18 P30 07 P05 22 P29 01 P53 15 P07 20 P51 Free Page back in Need new frame, fill with new contents Not referenced, add to free list Referenced, return to active list Unconditional move to inactive list and clear referenced bit
Page Replacement with Queues
  • Horse speaking

    Whoa! So while a page is on the active list, we actually aren't even checking to see if it's being used!

  • PinkRobot speaking

    That's right. After a while of being active, once it hits the front of the active queue, it's moved to the inactive queue. Once it reaches the head of the inactive queue, we look to see if it's been used. If it hasn't, we move it to the free queue. If it has, we move it to the tail of the active queue.

  • Cat speaking

    I notice that diagram shows how pages move between the queues, but not when they move. How do we decide when to move a page?

In the original design, the system would try to keep

  • About 2/3 of the pages in the active queue,
  • About 1/3 of the pages in the inactive queue, and
  • 5% of frames in the free queue,

and would perform page movement between the queues to maintain these ratios. In our simulator, we also require that the free queue always has at least two pages. We've also added an option to “bump” pages from the active queue to the inactive queue every k steps (much like the auto-advancing clock), but you can set that option to zero to disable it.

Visualization of Page Replacement

Page Frames
Paging Strategy:
Number of Frames10
Auto Advance10
Step: XX
Next Page: XX
Status: Message
Total page faults: 0
Disk Writes: 0
Disk Write Stalls: 0
     

You Experiment…

Explore queues-based page replacement with the simulator above.

  1. With the default settings (14 frames, bump from active to inactive every 4 steps), scrub though the trace of ls and see how the pages move between the queues. Something interesting happens in the time period 1280–1500. What is it?
  2. With bump-every-4, the number of disk writes is rather high. Sticking with 14 frames, try cranking the bump setting to the maximum (13) and also try setting it to zero (so that pages only move between the queues to fill the space that opens up when a free page is allocated). What do you observe? Are the two results surprising/contradictory?
  3. How does the Mach queue-based approach compare to the two versions of the clock algorithm?
  • Dog speaking

    I like it! We're managing to keep the number of disk writes down, and we're not stalling at all because pages spend long enough on the free list that they get written out before they're needed again.

  • Cat speaking

    I do like that it performs well, but I have an uneasy feeling. There are all these parameters and settings we can tune. Are they good in general, or just for the ls trace? Is there one good setting or does it depend on the program?

  • Dog speaking

    Or the phase of the moon?

  • PinkRobot speaking

    Good question!

(When logged in, completion status appears here.)