Department of Computer Science Course: CS 3725

Working set replacement

A replacement scheme which accounts for this variation in memory requirements dynamically may perform much better than a fixed memory allocation scheme. One such algorithm is the working set replacement algorithm. This algorithm uses a moving window in time. Pages which are not referred to in this time are removed from the working set.

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.)

Example:

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. Figure  shows the sliding window; the working set is the set of pages contained in this window.

  
Figure: Working set replacement - sliding window of 4

The following table shows the working set after each time period:

1 a 8 acgf

2 ab 9 acgf

3 ab 10 acgf

4 abc 11 acgf

5 abcg 12 agfd

6 acg 13 afdb

7 acgf 14 fdbg

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:

1. 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.
2. 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.

Figure  shows the behaviour of the working set replacement algorithm relative to LRU.

  
Figure: Behaviour of the WS and LRU replacement algorithms