Peter J. Denning – Page 17 – Communications of the ACM

Research and Advances Sep 1 1978

Generalized working sets for segment reference strings

The working-set concept is extended for programs that reference segments of different sizes. The generalized working-set policy (GWS) keeps as its resident set those segments whose retention costs do not exceed their retrieval costs. The GWS is a model for the entire class of demand-fetching memory policies that satisfy a resident-set inclusion property. A generalized optimal policy (GOPT) is also defined; at its operating points it minimizes aggregated retention and swapping costs. Special cases of the cost structure allow GWS and GOPT to simulate any known stack algorithm, the working set, and VMIN. Efficient procedures for computing demand curves showing swapping load as a function of memory usage are developed for GWS and GOPT policies. Empirical data from an actual system are included.

Computing Applications

Research and Advances Jul 1 1977

Certification of programs for secure information flow

ertification mechanism for verifying the secure flow of information through a program. Because it exploits the properties of a lattice structure among security classes, the procedure is sufficiently simple that it can easily be included in the analysis phase of most existing compilers. Appropriate semantics are presented and proved correct. An important application is the confinement problem: The mechanism can prove that a program cannot cause supposedly nonconfidential results to depend on confidential input data.

Research and Advances Nov 1 1973

A note on sub-expression ordering in the execution of arithmetic expressions

A counterexample to the supposed optimality of an algorithm for generating schedules for trees of tasks with unequal execution times is presented. A comparison with the “critical path” heuristic is discussed.

Research and Advances Mar 1 1972

Properties of the working-set model

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.

Opinion Dec 1 1971

ACM forum

News Nov 1 1971

On ACM special interest groups and committees

This report has been written to explain the nature, purposes, and organization of the Special Interest Groups (SIGS) and Special Interest Committees (SICS) of ACM, and to summarize SIG/SIC activity during the period August 1, 1970, to August 1, 1971.

Research and Advances Sep 1 1968

Operating Systems: A statistical model for console behavior in multiuser computers

The ability of a computer system to communicate with the outside world efficiently is as important as its ability to perform computations efficiently. It is quite difficult to characterize a particular user, but rather easy to characterize the entire user community. Based on the properties of this community we have postulated a hypothetical “virtual console.” No claim is made that a virtual console behaves like any actual console, but the entire collection of virtual consoles models the collection of actual consoles. Using the model we answer questions like: How many processes are suspended waiting for console input? What is the maximum rate at which a process can execute? What bounds can be set on overall buffer requirements? Answers to these and similar questions are needed in certain aspects of operating system design.

Research and Advances May 1 1968

The working set model for program behavior

Shape the Future of Computing