Operating Systems Lecture Notes

19 March 2012 • Managing Virtual Storage

---

Outline

• Paging In
• Landing Pages
• Page-Replacement Policies
• Working Sets

Pages Come In, Pages Go Out

• A process accesses a non-resident virtual address, throwing a page fault.
• Now the fun begins:
  1. How many pages should be brought in?
  2. Where should these pages go?
  3. For how long should these pages stay?
• Answer these questions to maintain the virtual-storage promise.

Paging In

• The page containing the non-resident virtual address should be read in.
• Reading a page is expensive (10⁶ nsecs).
  • One-page read sequences are inefficient disk management.
• Amortization suggests reading in many pages, not one.
  • Distribute overhead among many pages.
  • Better disk management.

Spatial Locality

• Is reading extra pages meaningful?
  What extra pages should be read in?
• Accessing address a makes it likely that addresses within a ± δ will be accessed too.
  • This property is known as spatial locality.
  • δ is an important parameter (knob).
• The extra pages read should be clustered around the required page.

Rational

• Loops are common control structures; sequences are common data structures.

  

Locality Illustrated

Landing Pages

• Which page frames should receive incoming pages?
• One answer: It doesn’t matter — primary store has constant-time access.
• A closer look shows that:
  • Treating the cache nicely is important.
  • Careless page placement can frustrate power management.

Storage Power Management

• Primary store can be divided into banks.
• Unaccessed banks can be switched to stand-by mode, reducing power use.
• Dealing pages into page frames without regard to banks can
  • Wake-up banks in stand-by mode.
  • Prevent banks from returning to stand-by mode.

Page-Frame Assignment

• Cluster incoming pages into as few banks as possible.
• Favor active banks over banks in stand-by mode.

  

Cache Management

• Caches are orders-of-magnitude smaller than primary store (10 vs 1000 Mbytes).
• Running primary store through a cache causes cache conflicts (collisions).

  

• Artful page-frame allocations can help avoid cache conflicts.

Cache-Friendly Allocation

• Cache-friendly page-frame allocation techniques include:
  • Page coloring: replicate virtual-address characteristics in primary store.
  • Bin hopping: allocate consecutively read pages to non-conflicting frames.
• Bin hopping tends to work better than does page coloring, and requires less onerous assumptions.

Paging Economics

• Economics requires a maximum of in-use page frames at all times (high utilization).
  • But performance may require some slack.
• Economics and the virtual-memory promise conspire to aim for a constant, non-zero paging rate.
  • But paging is expensive.

Page-Frame Pre-emption

• High page-frame utilization implies few or no free page frames.
• A non-zero paging rate implies two-way page traffic.
  • Some page frames are going to contain modified pages.
• The page-replacement policy determines the pages ejected to make room new pages.

Replacement Characteristics

• Who suffers when a page is ejected?
  • The faulting process: local replacement.
  • Any resident process: global replacement.
• Global replacement is simpler and more flexible than is local replacement.

Page-Replacement Policies

• A page-replacement policy determines the pages replaced in an occupied page-frame set.
  • An obvious policy: eject unmodifed pages before modified pages.
  • “Obvious” doesn’t mean “good,” and it may not apply.
• Good page replacement policies minimize overall paging rates.

Optimal Replacement

• The best page to replace is the one least in demand.
  • The page accessed furthest in the future, or not at all.
• This is a provably optimal page-replacement policy.
  • It’s also unimplementable, requiring future knowledge.
• But it sets a goal, and shows the way.

The Past as Prologue

• The optimal policy ejects the page unaccessed the longest.
• What’s a good guess for the page unaccessed the longest?
• Work locality backwards: A page not accessed recently is unlikely to be accessed soon.
• This is the least-recently used (LRU) page-replacement policy.

Implementing LRU

• LRU has a straightforward implementation:
  • Maintain a queue of pages ordered by last-access time.
  • One queue end has the least-recently used page.
• This implementation is impractical: too much equipment and too much effort.
• But, again, LRU sets a new goal, and points the way further.

Estimating LRU

• A queue provides a cheap and quick approximation to LRU.
• New pages are added at the queue tail.
• The queue head has the oldest page.
  • Pure residence time, nothing about accesses.
• When needed, replace the oldest page.
• This is the FIFO replacement policy.

FIFO Analysis

• FIFO’s oldest = longest unaccessed assumption is poor.
  • The FIFO policy is about as bad as you can get.
• Bring back access metrics, but cheaply: the access bit.
  • The hardware sets the access bit, the OS can clear it.
• Access bits allow various improvements to FIFO.

Second-Chance FIFO

• A new page has its access bit set.
• If the head page has its access bit set, clear the bit and requeue it.
• If the head page access bit is clear, replace the page.
  • It made one trip through the queue without access.
• Second-chance access is a fair approximation to LRU.

Clock Replacement

• The clock replacement policy is a variant of the FIFO policy.
• Pages form a ring, and a clock hand sweeps from page to page.
• The clock hand
  • cleared an access bit if set, and
  • replaces a page with a cleared access bit.
• Clock replacement is a popular policy, and has many variants.

Clock Analysis

• Clock replacement seems identical to FIFO.
• It is, but clock replacement is more flexible (has more knobs) than FIFO.
  • Clock replacement can have more than one hand sweeping the ring.
    • Extra hands can represent priorities.
  • The lag between hands adjusts the second-chance time.

Local-Global Hybrids

• Local policies contain miscreants, but don’t exploit low-hanging fruit.
• Global policies are the opposite.
• Is there a local-global cross-bread policy?
  • Fallow pages are put to best use.
  • Misbehaving processes are contained.
• Also, how are pages allocated under a local policy?

Working Sets

• A process P accesses some set of pages ws during a time interval τ.
• ws is P’s working set.
  • τ is a parameter.
• Recalculate working sets periodically.
  • Another parameter.

Hybrid Policy

• A process may allocate pages beyond their working set between recalculations.
• A process’s page fault is satisfied by
  • The set of all pages outside of any working set, or by
  • pages from the process’s working set.

Summary

• A page fault raises many questions.
  • The number of pages to read, their landing place, and how to open up space.
• VS managers differ in the policies used to guide the answers.
  • Guided by more encompassing policies.
• Page-ejection policies form a sequence of ever-less accurate approximations to an ideal policy.

References

• Large and Fast: Exploiting Memory Hierarchy, Chapter 7, in Computer Organization & Design, 2nd edition, by David Patterson and John Hennessy, Morgan Kaufmann, 1998.
• CLOCK-Pro: An Effective Improvement of the CLOCK Replacement by Song Jiang, Feng Chen, and Xiaodong Zhang, USENIX Technical Conference, 2005.

---

This page last modified on 2011 October 9.