Home → Magazine Archive → March 1972 (Vol. 15, No. 3) → Properties of the working-set model → Abstract

Properties of the working-set model

By Peter J. Denning, Stuart C. Schwartz

Communications of the ACM, Vol. 15 No. 3, Pages 191-198

A program's working set W(t, T) at time t is the set of distinct pages among the T most recently referenced pages. Relations between the average working-set size, the missing-page rate, and the interreference-interval distribution may be derived both from time-average definitions and from ensemble-average (statistical) definitions. An efficient algorithm for estimating these quantities is given. The relation to LRU (lease recently used) paging is characterized. The independent-reference model, in which page references are statistically independent, is used to assess the effects of interpage dependencies on working-set size observations. Under general assumptions, working-set size is shown to be normally distributed.

The full text of this article is premium content


No entries found