Working Set Page Replacement

The working set of a process is the set of pages expected to be used by that process during some time interval.
While the "working set model" isn't a page replacement algorithm in the strict sense (it's actually a kind of mid-term scheduler), several page replacement algorithms attempt to approximate the working set model, attempting to keep all pages in the working set in RAM.

For a window size T (measured in memory references), the working set at time t is the set of pages which were referenced in the interval (t -T + 1, t). A page may be replaced when it no longer belongs to the working set (this is not necessarily when a page fault occurs.)

Given a program with 7 virtual pages {a,b,...,g} and the reference sequence
a b a c g a f c g a f d b g
with a window of 4 references.


A variant of the basic working set replacement, which replaces pages only when there is a page fault, could do the following on a page fault:
- If all pages belong to the working set (i.e., have been accessed in the window W time units prior to the page fault) then increase the working set by 1 page.
- If one or more pages do not belong to the working set (i.i., have not been referenced in the window W time units prior to the page fault) then decrease the working set by discarding the last recently used page. If there is more than one page not in the working set, discard the 2 pages which have been least recently used.