Fact-checked by Grok 2 weeks ago

Working set

In computer science, particularly in the field of operating systems and virtual memory management, the working set refers to the dynamic subset of a process's virtual address space consisting of the pages that have been most recently referenced within a specified time window, ensuring efficient execution by minimizing page faults and thrashing.^[1] This model captures the principle of locality of reference, where programs tend to access a clustered subset of their memory pages during execution phases, allowing systems to allocate just enough main memory to support active processes without excessive swapping.^[2] Introduced by Peter J. Denning in 1968, the working set model formalized earlier observations on program behavior to address resource allocation challenges in multiprogrammed systems, unifying process scheduling with memory management by estimating each process's minimum memory demand as the size of its working set relative to available frames.^[1] Denning defined the working set W(t, \tau) for a process at time t over a backward window \tau (typically measured in process time) as the distinct pages referenced in that interval, with its size w(t, \tau) growing monotonically as \tau increases to reflect varying locality phases.^[1] Implementations often approximate this through hardware reference bits or software sampling of page tables at fixed intervals, enabling policies like the working set clock algorithm to evict least-recently-used pages and maintain system throughput within 5–10% of optimal performance.^[2] The concept has proven enduring, influencing modern virtual memory techniques in operating systems such as UNIX and Windows, where it helps balance multiprogramming levels against memory constraints to avoid system-wide degradation from overcommitment.^[2] By preventing scenarios where too many processes compete for limited memory—leading to thrashing—the working set ensures that active computations proceed smoothly while inactive ones are suspended, adapting dynamically to workload variations.^[1]

Core Concepts

Definition

In virtual memory management, the working set of a process is defined as the set of distinct pages in its virtual address space that are actively referenced within a defined time window, known as the working set window.^[3] This model captures the locality of reference principle, where programs tend to reuse a limited subset of their pages over short periods.^[3] The size of the working set window, often denoted as Δ, determines the scope of recent activity considered and is typically measured in either process execution time units (such as seconds of CPU time) or the number of page references.^[3] For a window of length Δ, the working set W(t, \Delta) at time t consists of all unique pages referenced during the interval (t - \Delta, t).^[3] The size of this set, w(t, \Delta), represents the number of such distinct pages and increases monotonically with Δ.^[3] A key distinction exists between the virtual working set, which includes all logical pages referenced in the window irrespective of their physical location, and the resident working set, which comprises only those pages currently residing in physical memory.^[3] For instance, if a process references pages A, B, and C multiple times within the window without referencing others, its virtual working set is {A, B, C}, while the resident working set would be the subset of these pages that are actually in main memory.^[3]

Key Components

The working set model fundamentally relies on the principle of locality of reference, which underpins its ability to predict and manage active memory usage effectively. Spatial locality manifests as the tendency for programs to access pages adjacent or nearby to those recently referenced, often due to sequential processing of code or data structures.^[3] Temporal locality, conversely, describes the likelihood that a page recently accessed will be referenced again soon, allowing a finite set of pages to cover most future accesses within a defined time window.^[3] These dual aspects of locality are prerequisites for the model's efficacy, as they justify focusing memory allocation on a compact, dynamic subset of pages rather than the entire address space. Central to identifying the working set is the page reference string, which records the sequence of page accesses performed by a process over time. This string serves as the primary data structure for determining set membership, where the working set at time t with window size T—denoted W(t, T)—comprises the unique pages referenced in the preceding T units of process virtual time.^[3] As briefly noted in the model's definition, W(t, T) represents the minimal resident set needed for efficient execution during that interval, derived directly from analyzing segments of the reference string. Tracking references to compute the working set without storing the complete historical reference string requires efficient approximation methods, as exhaustive logging would be resource-intensive. In the original formulation, a hardware-assisted approach uses per-page timers initialized to T upon each reference, which decrement continuously; pages with expired timers fall outside the current working set and may be replaced.^[3] Software approximations, such as periodic sampling of page table reference bits over fixed intervals, further simplify this by estimating W(t, T) through bit counts without real-time hardware.^[3] A widely adopted variant is the WSClock algorithm, which employs a clock hand sweeping through page frames, leveraging reference and modified bits to approximate the working set window while integrating second-chance eviction for unreferenced pages.^[4] Page faults are instrumental in delineating working set boundaries, as each fault occurs when a process attempts to access a non-resident page, revealing gaps in the current resident set.^[3] By observing fault patterns—such as clusters indicating locality shifts—the model identifies when the working set expands or contracts, prompting adjustments to page residency to encompass newly active pages while retaining those under temporal locality.^[3] This fault-driven feedback ensures the working set remains aligned with ongoing reference behavior, minimizing disruptions from absent pages.

Historical Development

Origins

The roots of the working set concept emerged from the memory management challenges of the 1950s and early 1960s, as computing systems transitioned from single-program batch processing to multiprogramming environments. Limited main memory capacity—often just kilobytes—and high costs forced programmers to manually partition large programs into overlays, loading only the active segments needed for specific computational phases into memory while swapping others to slower storage like drums or tapes. This approach highlighted the need for automated mechanisms to track and prioritize the "active" portions of programs to maximize CPU utilization and minimize I/O delays in multiprogrammed systems.^[5]^[6] A pivotal early implementation appeared in the Atlas computer, operational at the University of Manchester in 1962, which introduced virtual memory to address these issues through paging and automatic overlay management. The system's "one-level store" treated core memory and a magnetic drum as a unified address space, using fixed-size pages and a replacement policy based on usage bits to retain recently accessed pages in fast core while evicting inactive ones to the drum. This informal notion of maintaining an "active memory" set of pages provided the illusion of a much larger main store, reducing the programming burden of manual overlays and enabling efficient multiprogramming.^[7]^[5] In 1966, László Bélády's analysis of page replacement algorithms for virtual-storage systems further underscored the importance of tracking active page usage, demonstrating through simulations that algorithms favoring recently or frequently used pages outperformed others in minimizing faults. Bélády's work introduced the observation of "program locality," where executing programs tend to reference a relatively small, clustered subset of their total address space over time, necessitating demand paging models to dynamically allocate memory based on this behavior rather than fixed partitions.^[8]^[9] These ideas gained prominence in the Multics project, initiated in 1964 and implemented in the mid-1960s by MIT, Bell Labs, and General Electric, which pioneered demand-paged virtual memory in a multi-user timesharing environment. Multics aimed to support secure, hierarchical file systems and process isolation by paging in segments on demand, but encountered thrashing—excessive paging overhead—when multiprogramming degrees exceeded available memory, revealing the need for principled limits on active memory per process.^[10]^[11] Such pre-1968 developments in addressing multiprogramming bottlenecks through automated active memory tracking culminated in more rigorous formalizations of program behavior models.

Peter Denning's Contribution

Peter J. Denning introduced the working set model in his seminal 1968 paper, "The Working Set Model for Program Behavior," published in Communications of the ACM. In this work, Denning formalized the concept of the working set as the set of pages a program actively references within a recent time window, providing a principled approach to predict and manage memory demands in multiprogrammed systems.^[12] He addressed key inefficiencies in early multiprogramming environments, where excessive page faults—known as thrashing—occurred due to multiple processes competing for limited memory, leading to degraded system performance. By defining the working set as a dynamic measure of locality of reference, Denning proposed a mechanism to allocate memory sufficient to cover each process's immediate needs, thereby preventing thrashing and improving overall throughput.^[12] Building on this foundation, Denning refined the working set principles in his 1970 survey paper, "Virtual Memory," published in Computing Surveys. This article expanded the model's application to virtual memory management, emphasizing how working sets could guide page replacement and processor scheduling decisions to maintain system stability. Denning argued that virtual memory systems should enforce a strong correlation between processor allocation and memory resources, using working set estimates to dynamically adjust multiprogramming levels and avoid overload. These refinements positioned the working set as a core policy for integrating memory and CPU management, influencing subsequent theoretical frameworks for resource allocation. Denning's contributions had a profound impact on operating systems design, with the working set model adopted in theoretical analyses and practical guidelines for memory management over subsequent decades. The 1968 paper alone garnered over 1,500 citations, underscoring its influence on research into program behavior and system performance.^[13] His work inspired load control mechanisms in multiprogrammed systems and remains a benchmark for thrashing-resistant policies. Denning's leadership roles in the ACM, including as president from 1980 to 1982, further amplified the dissemination of these ideas through educational and professional channels, contributing to his recognition with the ACM Distinguished Service Award in 1989.^[14]^[15]

Theoretical Rationale

Purpose and Benefits

The working set model serves as a foundational approach to virtual memory management in multiprogrammed operating systems, primarily aimed at preventing thrashing by ensuring that each active process receives sufficient physical memory frames to accommodate its working set—the collection of pages it actively references within a recent time window.^[3] This allocation strategy addresses the core challenge of resource contention in systems where multiple processes compete for limited main memory, allowing the operating system to dynamically adjust frame assignments based on observed program behavior rather than static predictions.^[16] By maintaining the integrity of each process's working set in physical memory, the model significantly reduces page faults, which occur when required pages must be fetched from secondary storage, thereby minimizing the overhead of paging operations and alleviating system congestion.^[3] In multiprogrammed environments, this leads to improved overall throughput, as the system can sustain a higher degree of multiprogramming (denoted as M, the number of concurrently active processes) without performance degradation; specifically, frame allocation is tuned to the aggregate size of all working sets, enabling more processes to execute efficiently while keeping CPU utilization high by reducing idle time spent on memory swaps.^[16] Thrashing emerges when the combined size of system-wide working sets exceeds the available physical memory, resulting in excessive swapping that consumes more resources than useful computation and collapses system performance.^[16] The working set policy counters this by integrating memory management with process scheduling, suspending or swapping out processes whose working sets cannot be fully supported, thus protecting resident processes from interference and achieving near-optimal throughput even under heavy loads.^[3] This benefit is particularly pronounced in systems exhibiting locality of reference, where programs tend to reuse a limited subset of pages over short intervals, allowing the model to sustain balanced resource distribution and enhance overall CPU efficiency.^[16]

Mathematical Formulation

The working set model employs a discrete formulation based on sequences of memory references, where the working set at a given point is defined as the collection of distinct pages accessed within a recent window of references. Formally, for a reference string r_1, r_2, \dots, r_k, \dots, the working set W(k, \Delta) is the set of pages p that appear at least once in the subsequence of the last \Delta references preceding and including the k-th reference, i.e., in r_{k - \Delta + 1}, \dots, r_k (with adjustments if k < \Delta). The size of the working set, denoted \omega(k, \Delta) = |W(k, \Delta)|, represents the minimum number of page frames required to avoid faults for references within that window. Key parameters include k, the index of the current reference in the sequence; \Delta, the fixed window size (often interpreted as the number of recent references, analogous to a time interval \tau in continuous models); and p, the identifier of an individual page. These parameters capture locality by focusing on recent access patterns, with \Delta typically tuned empirically to balance fault rates and memory usage—larger \Delta includes more pages but may over-allocate frames. In dynamic systems, exact computation of W(k, \Delta) requires storing the full reference history, which is impractical; approximations use hardware support like a reference bit in each page table entry, set to 1 on access and periodically scanned and cleared (e.g., every \Delta / n references, where n is the number of bits or frames) to estimate the set without full string retention. For illustration, consider the reference string 1, 2, 3, 2, 1, 3 with [\Delta = 4](/page/Delta_4). At the end (k = 6), the last four references are 3, 2, 1, 3, yielding W(6, 4) = \{1, 2, 3\} and \omega(6, 4) = 3.

Implementation in Operating Systems

General Approaches

The working set algorithm for page replacement operates by identifying the set of pages actively referenced by a process within a recent time window, defined by a parameter τ (the working set window size), and evicting pages that fall outside this set to make room for new pages upon a fault.^[1] This approach ensures that memory frames hold the locality-relevant pages, minimizing page faults while adapting to changes in program behavior.^[17] The algorithm replaces only those pages not in the current working set W(t, τ), where t is the current time and W(t, τ) denotes the distinct pages referenced in the preceding τ units of process virtual time, thereby approximating optimal replacement under the principle of locality.^[1] Estimation of the working set can be exact or approximate, as precise tracking of all historical references is often impractical due to computational demands. Exact estimation requires maintaining a full history of page references over the window τ, using hardware timers to record interreference intervals and compute the set directly, but this demands significant resources and is rarely feasible in real systems.^[1] Approximate techniques, in contrast, employ sampling or counters to infer the working set efficiently; for instance, software scans page table use bits at fixed intervals (e.g., every z = τ/K clock ticks) to estimate the set over K intervals, or hardware counters increment on references and age out older entries to approximate recent usage.^[1] Aging mechanisms, such as periodically shifting counter values (e.g., right-shifting by one bit) to decay the weight of distant references, further enable low-overhead approximations that mimic the temporal locality captured in the mathematical formulation of working set size.^[17] Frame allocation in the working set model dynamically adjusts the number of physical frames assigned to a process based on the estimated size of its working set ω(t, τ), ensuring sufficient memory to contain W(t, τ) without overallocation. This adjustment maintains an optimal multiprogramming level by admitting or suspending processes such that the aggregate working set sizes fit within total memory, preventing thrashing while maximizing throughput; for example, if the sum of working sets exceeds available frames, the system reduces the degree of multiprogramming by suspending low-priority processes.^[1] The allocation policy treats working set size as a demand metric, periodically recomputing and reallocating frames to reflect evolving locality, which supports balanced resource sharing across processes.^[17] Implementing the working set model faces challenges, including the overhead of tracking page references and the variability of program locality. Reference tracking incurs costs from hardware counters or software sampling, which can consume CPU cycles and memory, though approximations mitigate this by design; for instance, early hardware proposals added modest per-page costs but simplified software logic.^[17] Variable locality, arising from phase changes in program execution (e.g., shifts between computation modules), complicates accurate estimation, as abrupt working set transitions can lead to temporary overshoot in faults until the window adapts, necessitating robust policies to detect and respond to such shifts.^[1]

Specific Examples

In Windows operating systems, working set management is handled through kernel functions such as MmAdjustWorkingSetSize, which allows the memory manager to dynamically adjust the size of a process's working set based on system conditions. This mechanism includes trimming the working set during low-memory situations to free physical pages for other processes, a process initiated by the memory manager when overall system memory pressure increases.^[18] Per-process limits are enforced via user-mode APIs like SetProcessWorkingSetSize, which sets minimum and maximum working set sizes to control paging behavior and prevent excessive memory consumption by individual applications.^[19] These features were part of the foundational memory management architecture starting with Windows NT 3.1 (1993), with kernel functions such as MmAdjustWorkingSetSize available from Windows NT 3.51 (1995).^[20] In Unix-like systems such as Linux, working sets are approximated using least recently used (LRU) lists maintained by the kernel's memory management subsystem, which tracks page access patterns to identify and reclaim inactive pages.^[21] Page reclamation is primarily managed by the kswapd daemon, a kernel thread that proactively frees memory by scanning LRU lists and evicting pages when the system approaches low memory thresholds, ensuring that working sets remain efficient without exact tracking. This approach was enhanced in the Linux 2.6 kernel series, released starting in 2003, with improvements to per-node kswapd instances for better scalability in multi-processor systems. macOS employs a working set model integrated with compressed memory, where inactive pages within a process's working set are compressed in real-time to reduce physical memory footprint without immediate swapping to disk, thereby maintaining performance under memory constraints. This feature, which builds on earlier virtual memory techniques, was introduced in OS X 10.9 Mavericks (2013) and advanced in subsequent versions such as El Capitan (2015) and later, enabling more aggressive compression of working set data and supporting unified memory architectures in Apple Silicon starting in 2020.^[22] In modern cloud environments during the 2020s, such as Amazon Web Services (AWS), working set tuning for containerized applications is achieved through container runtime limits, where tools like cgroups enforce memory reservations and hard limits to approximate and control per-container working sets, preventing overcommitment in shared host environments.^[23] For instance, in Amazon ECS, administrators can specify memoryReservation to softly limit a container's working set while allowing bursts up to a hard memory cap, optimizing resource allocation across containerized workloads.^[24]

Variants

Several variants of the working set model have been developed to address specific challenges in memory management, such as adapting to varying access patterns or prioritizing certain pages. The variable-interval sampled working set (VSWS) policy extends the standard model by dynamically adjusting the sampling interval for evaluating the working set, rather than using a fixed window size. This adaptation allows the policy to respond more effectively to changes in program locality by shortening intervals during periods of high activity and lengthening them otherwise, reducing overhead while maintaining accuracy in identifying active pages. Proposed in 1982, VSWS operates as a local, variable-size allocation strategy that approximates the working set through periodic sampling based on elapsed virtual time.^[25] In contrast to the core formulation, which computes working sets per process over a uniform window, implementations distinguish between local and global working sets to optimize allocation scope. A local working set focuses on the pages actively used by an individual process, enabling per-process frame allocation that isolates memory demands and prevents one process from interfering with others. Global working sets, however, aggregate page references across all processes to manage system-wide resources, which can lead to more efficient overall utilization but risks unfairness if high-demand processes dominate. This distinction is crucial in multiprogrammed environments, where local approaches approximate the baseline model's per-process locality while global ones facilitate load balancing.^[26] The weighted working set variant modifies the standard model by assigning weights to pages based on factors like access frequency or priority, rather than treating all referenced pages equally. Each page in the set carries a weight representing estimated future accesses, allowing the system to retain higher-weighted pages longer during replacement decisions and better handling skewed access patterns in multi-application scenarios. This approach enhances thrashing prevention in shared memory systems by prioritizing pages with greater predicted utility.^[27] Variants of the working set model are particularly valuable in real-time systems, where they ensure bounded response times by detecting locality shifts in real time and adjusting allocations to avoid excessive paging. For instance, the model's ability to dynamically size memory per task supports predictable performance in resource-constrained environments like embedded RTOS, preventing thrashing that could violate timing guarantees.^[28]

Comparisons to Other Algorithms

The working set model contrasts with the First-In-First-Out (FIFO) page replacement algorithm, which evicts the page that has resided in memory the longest, irrespective of recent usage. FIFO ignores locality of reference and is susceptible to Belady's anomaly, where allocating more memory frames paradoxically increases page faults for certain reference strings. This can lead to inefficient resource use and thrashing in multiprogrammed environments, as FIFO fails to adapt to dynamic program behavior. In simulations, the working set policy demonstrated substantially lower page traffic than FIFO across sequential, repetitive, and looped reference patterns by retaining pages based on recent activity within a defined window.^[1]^[17] Relative to the Least Recently Used (LRU) algorithm, which evicts the page that has gone the longest without being referenced, the working set employs a fixed reference window to capture the locality set, offering a more targeted approximation of needed pages. LRU approximates working set size within 10% accuracy but incurs higher implementation overhead and swapping errors up to 40% in multiprogramming scenarios, where it may exacerbate thrashing by not accounting for phase changes in locality. The working set, by contrast, better handles variable locality and achieves a lower space-time product, with real-system implementations like CP-67 showing significant paging reductions over LRU.^[1]^[17] The Optimal (MIN) replacement strategy, which evicts the page whose next reference is farthest in the future, represents the theoretical ideal for minimizing page faults but is unrealizable in practice due to its reliance on complete future knowledge. The working set approximates this optimum using only historical reference data, avoiding lookahead while attaining throughput within 5% of MIN in analytic simulations and reducing thrashing by adaptively limiting multiprogramming levels. This positions the working set as a practical, near-optimal alternative for dynamic memory management.^[1]^[17]

References

[1]
The working set model for program behavior
The working set is intended to model the behavior of programs in the general purpose computer system, or computer utility. For this reason we assume that the.
[2]
[PDF] WORKING SET - the denning institute
The working set is a dynamic subset of a process's address space that must be loaded in main memory to ensure acceptable processing efficiency. In the early.
[3]
[PDF] THE WORKING SET MODEL FOR PROGRAM BEHAVIOR
We discuss a method of implementing memory management based on this model, and indicate how working set notions can be used to blend process scheduling and ...
[4]
WSCLOCK—a simple and effective algorithm for virtual memory ...
A new virtual memory management algorithm WSCLOCK has been synthesized from the local working set ... P.J. DENNING, "The Working Set Model for Program Behavior", ...
[5]
Milestones:Atlas Computer and the Invention of Virtual Memory ...
The Atlas computer invented virtual memory, allowing different memory speeds to act as one large fast memory, addressing the issue of fast and slow memory.Missing: emergence | Show results with:emergence
[6]
Revisiting the History of Virtual Machines and Containers
One of the fundamental goals of adding multiprogramming to hardware and operating systems in the late 1950s was to improve performance through more efficient ...
[7]
The Atlas Milestone - Communications of the ACM
Sep 1, 2022 · Originally called one-level storage, the Atlas virtual memory system gave each user the illusion of having a very large main memory by ...
[8]
A study of replacement algorithms for a virtual-storage computer
Page(s): 78 - 101. Date of Publication: 31 December 1966. ISSN Information ... L. A. Belady. All Authors. Sign In or Purchase. 1096. Cites in. Papers. 25. Cites ...
[9]
The locality principle | Communications of the ACM
Belady, L.A. A study of replacement algorithms for virtual storage computers. IBM Systems J. 5, 2 (1966), 78--101. Digital Library · Google Scholar. [2].
[10]
[PDF] multics: the first seven years - MIT
Jan 17, 1972 · Abstract. In 1964 planning began on the development of a prototype of a computer utility. The aspirations for this system, named Multics ...
[11]
Multics Virtual Memory - Tutorial and Reflections
This is a summary of the Multics virtual memory design, taken from memory and reflecting Multics from the start of my association in 1969 until 1980 when I ...
[12]
The working set model for program behavior - ACM Digital Library
The working set model for program behavior. SOSP '67: Proceedings of the first ACM symposium on Operating System Principles.
[13]
https://scholar.google.com/citations?view_op=view_citation&hl=en&user=-W3wvGkAAAAJ&citation_for_view=-W3wvGkAAAAJ:9yKSN-GCB0IC
[14]
Peter J. Denning -- Working Set Publications
(In Computing Surveys) The working set model for program behavior was invented in 1965. It has stood the test of time in virtual memory management for over ...
[15]
https://awards.acm.org/distinguished-service/award-recipients
[16]
[PDF] Working Sets Past and Present - Purdue e-Pubs
~V first concept of the working set was a set of recently referenced pages that estimated a program's memory demand in the immediate future. I regarded the ...
[17]
Working Set - Win32 apps | Microsoft Learn
Jun 4, 2021 · The working set is the set of pages in a process's virtual address space that are currently resident in physical memory, excluding nonpageable ...
[18]
SetProcessWorkingSetSize - Win32 apps - Microsoft Learn
Dec 8, 2022 · Sets the minimum and maximum working set sizes for the specified process. (SetProcessWorkingSetSize)Missing: MmWorkingSetSize | Show results with:MmWorkingSetSize
[19]
Chapter 10 Page Frame Reclamation - The Linux Kernel Archives
This chapter will focus exclusively on how Linux implements its page replacement policy and how different types of pages are invalidated.
[20]
Reserving Amazon ECS Linux container instance memory
The Amazon ECS container agent provides a configuration variable called ECS_RESERVED_MEMORY, which you can use to remove a specified number of MiB of memory ...
[21]
Amazon ECS task definition parameters for Fargate
You can set a memoryReservation of 128 MiB, and a memory hard limit of 300 MiB. This configuration allows the container to only reserve 128 MiB of memory from ...
[22]
VSWS: The Variable-Interval Sampled Working Set Policy
VSWS: The Variable-Interval Sampled Working Set Policy. Domenico Ferrari and Yiu-Yo Yih. EECS Department, University of California, Berkeley. Technical Report ...Missing: Denning | Show results with:Denning<|separator|>
[23]
Operating Systems: Virtual Memory
3 Global versus Local Allocation. One big question is whether frame allocation ( page replacement ) occurs on a local or global level. With local replacement ...
[24]
[PDF] Runtime Memory Management in Many-core Systems - eScholarship
Each application maintains a weighted working set of its current memory phase. The weight of each page in WWS, which is the estimated number of accesses to ...<|separator|>
[25]
[PDF] 113 Working Set Analytics - the denning institute
Working set is about detecting those patterns in real time and using them to make memory management decisions. Les Belady's famous study of paging algorithms ...