General caching problem: which entry should be removed from the cache to make room for another?
When should page replacement policy be invoked:
Discard the page whose next access is farthest in the future.
Use (recent) past as a predictor of the future:
However, good approximations are possible.
Approximate time stamp with 1-bit clock:
One implementation:
Four classes (pick a page from the lowest numbered class). Approach shown in Tanenbaum.
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)
replace
else
reset R
advance hand
In the first in first out (FIFO) policy, the memory manager swaps out the oldest page, regardless of how recently it was accessed.
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.
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.
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.
The page-fault frequency policy approximates the working set policy.
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.
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).
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.
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.
Some pages cannot safely be swapped out:
Have an explicit swap area on disk. Sometimes the executable itself is used, which can result in the message ``text file busy'' when recompiling.