Page Replacement Policies

General caching problem: which entry should be removed from the cache to make room for another?

When should page replacement policy be invoked:

Min Policy (Belady's algorithm), Optimal Policy

Discard the page whose next access is farthest in the future.

Least Recently Used

Use (recent) past as a predictor of the future:

However, good approximations are possible.

Not Recently Used (NRU)

Approximate time stamp with 1-bit clock:

One implementation:

Clock Algorithm

To increase fairness (and improve performance) start search for candidate page where previous search ended--Clock Algorithm. This algorithm does not divide pages into classes nor does it use the modify bit in making decisions (although a such an algorithm could be constructed).

Like advancing a clock hand through the pages.

if (R == 0)
    reset R
    advance hand

FIFO Page Replacement

In the first in first out (FIFO) policy, the memory manager swaps out the oldest page, regardless of how recently it was accessed.

Inclusion (Stack) Property

Page-reference strings can be used to evaluate page replacement policies. Usually one counts the number of page faults for a given reference string, page replacement policy, and number of pages.

A fault-rate graph plots the number of page faults vs. the number of page frames.

Does an increase in the number of pages in memory decrease the number of page faults a process generates?

Consider the reference string (sequence of pages a process references: 0 1 2 3 0 1 4 0 1 2 3 4

If physical store holds 3 pages, 9 faults occur (3 for cold start faults, 6 warm faults). If we increase the physical size to 4 pages, 10 faults occur (4 cold, 6 warm).

Cold-start behavior refers to starting with an empty cache (e.g., pure demand paging).

Warm-start behavior refers to that part of the fault-rate graph after the cache has been loaded. Fill up initial frames.

The characteristic number is a single number that summarizes the page fault frequency; it is given by the area under the curve of the graph. Other analysis is given in Tanenbaum.

Anomalies can occur only in policies that lack the stack property or inclusion property. The inclusion property requires that:

FIFO does not satisfy the inclusion property, while LRU (among others) does.

Locality of Reference

Experiments show that some pages are accessed more frequently than others. In particular, programs exhibit a locality of reference:

At each instance, a few pages are in active use, while others are unreferenced. A phase change occurs when the set of pages in active use changes.

Working Set

The working set policy:

The working set is defined as follows:

Simulations show that the working set policy works well. In practice, it is difficult to implement exactly.

Page-Fault Frequency

The page-fault frequency policy approximates the working set policy.

Working Size

Rather than keep track of the actual working set, just keep track of its size. The size can be estimated by looking at the referenced bits. A process is not placed on the ready list until the number of free frames exceeds the process's working set size.

Missing Used Field

DEC VAX lacks a Used field. Simulates the use of one through a mirror table and the present bit. Reset present bit rather when it would want to reset the non-existent use bit. Expensive because uses a page fault to help keep track of correct use bit value (stored in the mirror table).

Global vs. Local Policies

So far, we have considered single process systems where there is only one page table. Multiple processes can be accommodated by giving each process a quota of frames and applying a policy individually to each process.

Local policies resolve competition for frames local to a process.

Global policies have processes competing against each other for frames.

Global Policies

Why global policies?

Problems with global policies:

For global policies, scan frame table (rather than page table) for candidate pages to swap. Usually, the frame table is not directly supported by the hardware, so the OS maintains one in software.

Sharing Pages

Can think of allowing sharing of pages between processes. Useful, but causes problems. How to approach? A central mapping table to use for keeping track of shared information?

Locking Pages in Memory

Some pages cannot safely be swapped out:

Backing Store

Have an explicit swap area on disk. Sometimes the executable itself is used, which can result in the message ``text file busy'' when recompiling.