Working Set Publications

Peter J. Denning

The Working Set Model for Program Behavior. 1968. This classic paper, which received the ACM Best Paper Award for Systems, laid out the concept of locality of reference and the working set model as a means of estimating the current locality sets. It also described a scheduling mechanism that would avoid thrashing by protecting the working sets of loaded programs.

Thrashing: Its Causes and Prevention. 1968. This classic paper explained the then-mysterious phenomenon of thrashing, the operating system state in which throughput drops to a low value because the virtual memory is spending all its time swapping pages. The solution was to use working set memory management, which keeps each process's working set safe from being stolen by other processes. The paper contains a clever analysis showing that the large "traverse time" (gap between main and secondary memory) is the primary source of sensitivity to thrashing. The paper ends with the amazing statement, "Even the best-designed systems can be dragged by thrashing into dawdling languor."

Virtual Memory. 1970. This classic paper laid out a coherent scientific and engineering framework for the architecture and performance of virtual memory. It settled the controversies about the viability of virtual memory. It was widely used as a reading in operating systems courses well into the 1980s, when the material was finally integrated into operating systems textbooks.

Properties of the Working Set Model. 1972. This paper, co-authored with Stuart Schwartz, further developed the mathematical theory of working sets and showed how to apply it to taking dynamic working set and locality measurements.

Dynamic Storage Partitioning (with J Spirn). 1973. A variable storage partition policy varies the memory allocated to a task dynamically. If the fault-rate curve or the efficiency curve is concave up, almost any variation of storage will increase processing efficiency relative to a fixed partition.

Generalized Working Sets for Segment Reference Strings. 1978. This paper, co-authored with Donald Slutz, continued the development of the mathematical theory of working sets and locality, here showing how to apply the concept to segment reference strings as well as page reference strings, and showing that the generalized working set models the entire class of "stack algorithm" replacement policies.

Working Sets Past and Present. 1980. This paper gave a complete historical summary of the extensive research stimulated by the working set model over the previous decade, in which over 200 researchers participated. By this time the theory had been strongly validated by many experiments and was an accepted basis for the architecture of virtual memory systems. Among the new conclusions articulated here are: none of the plethora of simple stochastic models of locality fit data; locality has a phase transition structure that can be modeled with a semi-Markov model; working set memory management is near optimal among all policies without perfect lookahead.

Virtual Memory. 1996. From ACM Computing Surveys, December 1996. An overview of virtual memory that shows its timelessness and utility in the age of the Internet.

Before Memory was Virtual. 1997. From the book In the Beginning: Recollections of Software Pioneers, edited by Robert Glass, IEEE Press, 1997. A belated eyewitness account of the invention of virtual memory, one of the engineering triumphs of the computer age.

The Locality Principle. 2006. This chapter for a book in honor of Erol Gelenbe gives a historical account of the discovery and development of the locality principle. Locality is one of the great principles of computing. It was discovered in 1966 and is behind the success of many modern systems from CPU and memory caches, to web caches, to Google, and downloading into mobile devices.