Weekly Paper Notes — the Seminal Paper of the Week for the 2026-10-24 digest. Area: Operating Systems.

Author: Peter J. Denning (MIT Project MAC) Published: Communications of the ACM 11(5), May 1968, pp. 323–333. DOI: 10.1145/363095.363141. First presented at the first ACM Symposium on Operating Systems Principles, Gatlinburg, 1967.

Why the paper still matters

In the mid-1960s, paging was new and it was misbehaving. Machines like Atlas, the IBM 360/67 and the GE 645 running Multics could keep more programs in memory than would fully fit, by paging the parts not in use out to drum or disk. Add a few too many programs, though, and throughput fell off a cliff. Each program had too few pages to make progress, so it faulted, waited for the drum, and on return found its other pages had been taken by someone else. The CPU sat idle while the paging device saturated. Denning analysed this collapse, thrashing, in a companion paper at the 1968 Fall Joint Computer Conference.

The CACM paper is the constructive half. Its question is what memory a program actually needs to make progress. Denning’s answer is a definition precise enough to measure and simple enough to build into hardware.

The setup

Treat a running program as a sequence of page references, measured in the program’s own process time, meaning time it spends executing, not wall-clock time. Pick a window size τ. Then

W(t, τ) = the set of distinct pages referenced in the process-time interval (t − τ, t]
w(t, τ) = |W(t, τ)|   (the working set size)

That’s the whole model. The working set is whatever the program has touched recently, and the bet is that what it touched recently is what it’s about to touch next. Denning was writing before “locality of reference” had its name (he formalised it later), but the model assumes programs spend long stretches inside small groups of pages and shift between groups now and then.

Sliding working-set window over a page reference string, and a throughput curve that collapses past the point where working sets exceed memory Top: the working set is the set of pages in the last τ references, here {3, 4, 5}. Bottom: past the point where the working sets of the running programs exceed memory, adding programs reduces useful work. Original diagram for this post.

A few properties fall straight out of the definition, and Denning works through them. w(t, τ) never decreases as τ grows, and it can’t grow faster than τ itself. Choosing τ is a trade-off. Too small, and pages the program will want again soon fall out of the set. Too large, and the set carries dead pages that occupy memory for nothing. Denning ties a sensible τ to the time it takes to bring a page in from backing store: the window should be long compared with that transfer time, so a page isn’t dropped just before the program comes back for it.

The rule

The model turns into policy with two linked rules:

  1. A program is eligible to run only if its working set is in main memory.
  2. A page that belongs to the working set of a running program must not be evicted.

Together these make memory and CPU scheduling one decision. If the working sets of all the programs you’d like to run don’t fit, you don’t squeeze them in and let them steal from each other. You deactivate a program, swap it out entirely, and let the rest run properly. That’s load control, and it’s what prevents thrashing. The degree of multiprogramming is no longer a fixed number chosen by an operator. It changes with the programs’ actual demand.

Replacement falls out too. Any page that isn’t in some running program’s working set can be evicted, and the paper’s appendix sketches hardware support that tracks recent use per page. Compare global LRU, which pools every page in the machine and evicts the oldest, so one program’s burst can push another program’s working set out of memory. The working-set policy gives each program its own window.

Why this design has outlasted everything around it

A precise working-set implementation is expensive, because you’d need a per-page timestamp in process time on every reference. Practical systems approximate it, and most of the approximations have been around for decades. Carr and Hennessy’s WSClock (1981) combined the working-set test with a clock-hand scan and became the standard textbook compromise. Windows NT exposes per-process minimum and maximum working set sizes and trims processes toward them under memory pressure. The term is right there in Task Manager.

Linux didn’t use the term for a long time, but it now has mm/workingset.c. When a page that was evicted gets faulted back in, the kernel measures its refault distance: how many other pages were evicted in between. If that distance is smaller than the active list, the page was part of the working set and shouldn’t have gone, so it goes straight back to active. That’s Denning’s window, measured in evictions instead of process time. Pressure Stall Information, added in 2018, reports how much time tasks spend stalled on memory. It’s a direct thrashing signal, and tools like systemd-oomd and Meta’s oomd use it to kill or throttle workloads before the machine locks up. That’s load control again, fifty years later.

The idea also spread beyond OS paging. Any cache sitting in front of a slower tier has a working set: database buffer pools, CDN edges, the KV cache in front of a GPU serving LLM agents. Each of them can thrash. A buffer pool that’s smaller than the hot set of the query mix behaves like a 1967 time-sharing system with one program too many. Sizing the cache to the working set and turning away load that doesn’t fit is still the answer.

Two things about the paper itself are worth taking away. The model is defined over an observable quantity, the reference string, rather than programmer declarations of what memory they’ll need. Programmers’ guesses about their own memory needs were unreliable, and the working set looks at what the program actually does instead. And it ties two resources together. Memory and CPU look like separate scheduling problems until you notice that giving a process the CPU without its working set wastes both. Plenty of modern multi-resource schedulers rediscover that.

Denning spent the next decade on the theory, from the 1970 Computing Surveys article “Virtual Memory” to the locality principle, but the 1968 paper is where the definition first appears.

Read alongside

Part of the Weekly CS Paper Digest series. Written from the published paper and its well-documented history; the diagram is original to this post.