Working Sets Past and Present

Peter Denning

Paper outlines argument that it will be unlikely to find a cheaper nonlookahead memory policy than working sets.

Working set: collection of recently referenced segments (or pages). Solution to Saltzer’s problem—allows for adaptive control that would allocated memory and schedule the CPU in order to maxmize performance.

Theta—control parameter – used to trade pagaing load vs. resident set size. For working sets, larger theta -> larger mean resident set size -> longer mean interfault times

Early working set—sample usage bits every theta units of virtual time. swap in entire working set whenever you swap in the program. working set policy – program’s resident set is always its working set. working set at time t = # of distinct segments among r(t-theta+1) ... r(t).

Derives formula for determining size of working set based upon interreference distribution. Working sets are tools for measuring memory demand, but not models of program behavior.

VMIN is optimal variable-space memory policy and uses lookahead by theta. VMIN generates segment faults exactly when WS does for the same theta.

Generalized Working Set comprises each segment whose “retention cost” accumulated since prior reference is not more than theta.

People who used to do manual overlays used to draw up phase diagrams... turns out programs had locality of reference even when programmers didn’t plan for it simply by

doing “good programming.”

program reorganization—figure out how to arrange segments to minimize paging.