The Working Set Model for Program Behavior.¶
Denning, P. J. (1968). The Working Set Model for Program Behavior. Communications of the ACM, 11(5), 323-333.
Cited by¶
8 citations across 8 artifacts.
Each citation links to the sentence it supports in the citing article.
Primes¶
- Caching
- Caching is the technique of maintaining a fast, local, usually-smaller copy of information whose original is slow to produce or fetch, so that repeated or nearby accesses are served from the copy rather than from the source — exploiting locality of reference (the empirical observation that accesses exhibit temporal and spatial clustering) to reduce average latency, bandwidth consumption, computational cost, or coordination overhead
This sourceIntroduces the working-set model: a running program references only a small, slowly-drifting subset of its address space at any instant, so the working set rather than the whole address space is the unit of locality reasoning and management.
Supported in partVerified against the work's full text
Denning supports the temporal-locality premise (recent page references predict near-future ones) but says nothing about caches or spatial locality.
“We expect intuitively that the im- mediate past page reference behavior of a program con- stitutes a good prediction of its immediate future page reference behavior:”
- Caching is the technique of maintaining a fast, local, usually-smaller copy of information whose original is slow to produce or fetch, so that repeated or nearby accesses are served from the copy rather than from the source — exploiting locality of reference (the empirical observation that accesses exhibit temporal and spatial clustering) to reduce average latency, bandwidth consumption, computational cost, or coordination overhead
- Locality Of Reference
- The concept emerged in computer architecture from the observation, formalized by Denning (1968) in the working-set model, that a running program touches only a small, slowly-drifting subset of its address space at any instant rather than ranging freely over all of memory.
This sourceIntroduces the working-set model: a running program references only a small, slowly-drifting subset of its address space at any instant, so the working set rather than the whole address space is the unit of reasoning and management.
Supported in partVerified against the work's full text
Denning defines the working set from recent page references and says the immediate past predicts the immediate future, matching the slowly-changing in-use set; he does not say it is a small share of the address space.
“We expect intuitively that the im- mediate past page reference behavior of a program con- stitutes a good prediction of its immediate future page reference behavior”
- The concept emerged in computer architecture from the observation, formalized by Denning (1968) in the working-set model, that a running program touches only a small, slowly-drifting subset of its address space at any instant rather than ranging freely over all of memory.
- Mixed Layer
- The "active surface over passive interior" framework maps so cleanly onto multi-tier storage that LRU eviction is recognizable as the cache analogue of detrainment, and cache-tier sizing borrows the logic of mixed-layer depth.
This sourceWorking-set theory of caching and the thrashing failure mode when the working set exceeds available fast storage.
- The "active surface over passive interior" framework maps so cleanly onto multi-tier storage that LRU eviction is recognizable as the cache analogue of detrainment, and cache-tier sizing borrows the logic of mixed-layer depth.
Domain-specific¶
- Virtual memory
- Working Set
- Working set size
- When the access pattern causes continual replacement and reload, the system can enter thrashing and its performance can collapse even though the computation is otherwise correct.
SupportedVerified against the work's full text
Denning names thrashing: overcommitted working sets keep displacing one another's pages, stalling programs in page-wait and seriously degrading service.
“when too many working sets occupy main memory, each is displac- ing another's pages in an attempt to have its own pages present. This phenomenon, known as "thrashing,"”
- When the access pattern causes continual replacement and reload, the system can enter thrashing and its performance can collapse even though the computation is otherwise correct.
Mechanisms¶
- Local Inventory or Edge Cache
- The discipline that keeps it honest is to size to the measured working set, watch the hit rate as the real scorecard,
This sourceDefines the working set from recently referenced pages and uses observed demand to guide memory allocation and removal.
- The discipline that keeps it honest is to size to the measured working set, watch the hit rate as the real scorecard,
- Virtual Memory System
- Its characteristic failure is thrashing.
This sourceIdentifies thrashing as a characteristic performance-collapse failure of multiprogrammed virtual memory.
- Its characteristic failure is thrashing.
Verification¶
Does it exist? Confirmed. This work's DOI resolves to a registered record, which fixes its identity. That is all it fixes.
Does it back the claim? Read against the text for 3 of 8 citations: 1 supported, 2 supported in part. Each verdict is shown under its citation below, with what in the work backs the sentence.
Support is checked per citation rather than per work — the same source can be cited soundly in one article and wrongly in another. Per-citation recording began recently, so a citation with no recorded check is a gap in the record rather than evidence it went unchecked.
See how references were verified.
Links previously used in the corpus¶
Before the registry existed this work was also linked 1 other way.
Registry ID ref:76f04dfd5855 · see in the full table