Grant Novota
About Projects Peaks Blog Links Resume

Page Replacement Policies

20 Jul 2019

Page Replacement Policies

As processes execute and bring in more pages on demand into memory, eventually the system runs out of free frames so we need a page replacement policy.

Steps:

  1. Select a victim frame that is not currently being used.
  2. Save or write the victim frame to disk, update the page table (page now invalid).
  3. Load in the new desired page from disk.

If out of free frames, each page fault causes two disk operations, one to write the victim and one to read the desired page. This is big hit to performance.

To reduce the performance penalty of two disk operations, systems can employ a dirty/modify bit.

  • modify bit = 0 initially.
  • When a page in memory is written to, set the bit = 1.
  • When a victim page is needed, select a page that has not been modified (dirty bit = 0).
    • Such an unmodified page need not be written to disk because its mirror image is already on disk.
    • This saves on disk I/O - reduces to only one disk operation (read desired page).

Page Table Status Bits

Each entry in the page table can conceptually store several extra bits of metadata information along with the physical frame #f.

  • valid/invalid bits - for memory protection. Accessing an invalid page causes a page fault.
  • dirty bits - has the page been modified for page replacement?
  • R/W or read-only bits - for memory protection. Writing to a read-only page causes a fault and a trap to the OS.
  • reference bit - useful for a Clock page replacement algorithm.

FIFO Page Replacement

insert the figure here

FIFO is easy to understand and implement, but performance can be poor.

Suppose page 7, which was replaced, was a very active page that was frequently referenced, then page 7 will be referenced again very soon, causing a page fault because it’s not in memory any more. In the worst case, each page that is paged out could be one that is referenced next, leading to a high page fault rate. Ideally, we want to keep pages around that are about to be used next.

OPT Page Replacement

OPT means optimal. Using this policy, we replace the page that will not be referenced for the longest time. This guarantees the lowest page-fault rate; however, it requires future knowledge.

LRU Page Replacement

LRU means least recently used. This policy uses the past to predict the future.

  • If a page wasn’t used recently, then it is unlikely to be used again in the near future.
  • If a page was used recently, then it is likely to be used again in the near future.
  • So we select a victime that was least recently used.

Page fault rates: LRU > OPT, but LRU < FIFO

Variations of LRU are popular

LRU Implementation Options

  • Keep a history of past page accesses.
    • The entire history (lots of memory)
    • A sliding window
    • Complicated and slow
  • Timers
    • Keep an actual time stamp for each page as to when it was last used.
    • Expensive in delay (consult system clock on each page reference).
    • Large storage (at least 64 bits per absolute time stamp).
    • Search (find the page with the oldest time stamp).
  • Counters
    • Approximate time stamp in the form of a counter that is incremented with any page reference, i.e. each page’s counter must be incremented on each page reference.
    • Counter is stored with that entry in the page table. It is reset to 0 on a reference to a page.
    • It’s expensive because it must update each page’s counter (on each reference) and it must search a list.
  • Linked list
    • Whenever a page is referenced, put it on the end of the linked list, removing it from within the linked list if it’s already present in the list.
    • The front of the linked list is LRU.
    • The problem is that managing a (doubly) linked list and rearranging pointers becomes expensive.
    • Similar problems with a stack data structure.

LRU Approximation Algorithms

Add an extra HW bit called a reference bit.

  • This is set any time a page is referenced (read or write).
  • It allows the OS to see what pages have been used, though not fine-grained detail on the order of use.
  • Reference-bit based algorithms only approximate LRU, i.e. they do not seek to exactly implement LRU.
  • 3 types of reference-bit LRU approximation algorithms;
    1. Additional Reference-Bits Algorithm
    2. Second-Chance (Clock) Algorithm
    3. Enhanced Clock Algorithm with Dirty/Modify Bit

Additional Reference-Bits Algorithm

  • Record the last 8 reference bits for each page.
  • Periodically a timer interrupt shifts right the bits in the record and puts the reference bit into the MSB.
  • Example to compare times: 11000100 > 01110111
  • So LRU is the lowest valued record.

Second-Chance (Clock) Algorithm

  • In-memory pages plus reference bits conceptually form a circular queue. A hand points to a page.
  • If the page pointed to has R=0, it is replaced and the hand moves forward.
  • Otherwise, set R=0; hand moves forward and checks the next page.
  • Advantages:
    • Simple to implement (one pointer for the clock hand plus one ref bit/page)
      • Note: the circular buffer is actually just the page table with entries where the valid bit is set, so no new circular queue has to be constructed.
    • Fast to check reference bit.
    • Usually fast to find first page with a 0 reference bit.
    • Approximates LRU.
  • Disadvantages:
    • In the worst case, we have to rotate through the entire circular buffer once before finding the first victim frame.

Counting-Based Page Replacement

Keep a counter of the number of page accesses for each page since its introduction, which is an activity or popularity index.

Most Frequently Used

  • Replace page with highest count.
  • Assumes the smallest counts are most recently loaded.

Least Frequently Used

  • Replace page with lowest count.
  • What if a page was heavily used in the beginning, but not recently?
    • Age the count by shifting its value right by 1 bit periodically. this is exponential decay of the count.

These kinds of policies are not commonly used.

Top