CSE Roadmap

Core tier · about 5 hours · 7 parts

Part 4 of 7 · 3 min read

The working set

In plain words: If a process needs about 20 pages now, the system should give it 20 frames. How can the system know? The working set model answers with the recent past. Take a window of the last Δ memory references (Δ is the Greek letter delta, a number chosen by the designer, such as 10,000). The set of distinct pages in the window is the working set of the process, and its size is the WSS.

A small example with Δ = 4 (made up to show the idea). The reference string has 18 references:

1 2 1 3 1 2 4 5 4 5 4 5 7 8 7 8 7 8

After reference number Last 4 references Working set WSS
4 1 2 1 3 1, 2, 3 3
6 1 3 1 2 1, 2, 3 3
8 1 2 4 5 1, 2, 4, 5 4
10 4 5 4 5 4, 5 2
14 4 5 7 8 4, 5, 7, 8 4
18 7 8 7 8 7, 8 2

The working set changes as the program moves from one phase to the next: first pages 1 to 3, then 4 and 5, then 7 and 8. At the moments of change (numbers 8 and 14) the window holds pages of both phases, and the set is larger.

The system uses it like this. Let D be the sum of the working set sizes of all running processes. If D is more than the number of frames, the frames cannot hold all the working sets, and thrashing will follow. The system then suspends a process, which means that it takes all its frames away (its pages go to disk) and does not run it until memory is free. If D is below the number of frames, another process may start. With four processes of WSS 12, 20, 9 and 14 (D = 55) and 50 frames, one process must be suspended. Suspending any one of them brings D to at most 46.

The choice of Δ matters. If Δ is too small, the window does not cover the locality, and the working set is too small. If Δ is too large, the window reaches across several phases, and the working set is too large. The exact working set costs too much to track, and real systems approximate it with reference bits that are cleared and read from time to time, as in the clock algorithm of page 8.

Working set

The working set of a process at a time t, for a window of Δ references, is the set of distinct pages that the process touched in its last Δ references, and the size of that set estimates how many frames the process needs now.

Example: in the string 1 2 1 3 1 2 4 5 with Δ = 4, the working set after the eighth reference is {1, 2, 4, 5}.

Check yourself: 1. What are the working set and the WSS after reference 10 in the table? 2. What should the system do if D is larger than the number of frames? 3. What goes wrong if Δ is much too large?