Association for Computing Machinery
Special Interest Group Operating Systems
Hall of Fame Award 2005


Peter J. Denning

The ACM Special Interest Group on Operating Systems (SIGOPS) awarded one of its first Hall of Fame Awards to Peter Denning for a classic paper he wrote in 1967.

The performance of a computing system depends as much on the storage system speed as it does on the processor speed. Until the early 1960s, programmers had to manually perform the burdensome task of moving data between fast main memory and slow disk. Computer researchers were trying to completely automate these data transfers because the resulting system would double or triple programmer productivity. Unfortunately, the early implementations of virtual storage were finicky and were prone to thrashing, a sudden collapse of throughput when too many jobs were activated at once. Many millions of dollars of investment and sales were at risk because of the volatility of these systems.

In 1967 Peter Denning proposed a method of dynamically measuring the amount of memory a running computation needed. This measure was called the working set. By guaranteeing that every computation's working set was loaded in main memory, the operating system would never thrash and in fact would automatically adjust system throughput to be near its optimum. The working set model became the ideal for designing the memory manager parts of operating systems. Virtual storage became as standard part of operating systems.

The principle of the working set has spread to many fields. Anything that uses a "cache" to hold data close to the processing site is based on it. Denning's work put the words working set, locality, and thrashing into the standard lexicon of operating systems and computer science.

Denning is currently the chair of the computer science department at the Naval Postgraduate School in Monterey, California, and also the Director of the Cebrowski Institute on Information Superiority and Innovation. He is currently working with John Hiles of the CS department on a paper that proposes to use the working set principle to create a new generation of "post autistic software". Much current software creates costly problems for users because it is unaware of the context the user brings. Denning and Hiles believe that thrashing was the first instance of software autism and that the working set principle can cure modern software autism by helping software learn enough about its users' contexts to avoid costly breakdowns.

The ACM SIGOPS began a research conference, Symposium on Operating System Principles, in 1967. The conference has been held every other year since then. Denning's paper, "The working set model for program behavior," was presented in the 1967 inaugural conference.

The SIGOPS Hall of Fame was established in 2005 to recognize the most influential papers that appeared in previous symposia at least ten years ago. Three other seminal papers besides Denning's were selected as the initial members of the Hall of Fame in 2005.