Allocation Based on WSS — Working Set Model | OneNoughtOne

0/107

Operating SystemsWorking Set Model

Working Set Model

LevelIntermediate

Duration75 mins

TopicWorking Set Model

5 / 5

Allocation Based on WSS

Closing the Loop: From Measurement to Action

We've built all the pieces: we understand locality, we've defined the working set, we've tuned the window parameter, and we've implemented tracking. Now comes the payoff— using this information to allocate memory intelligently . The working set model doesn't just describe behavior; it prescribes action. Its fundamental policy is elegantly simple: give each process enough frames to hold its working set, and prevent thrashing by controlling admission when memory is overcommitted . This page shows how to implement this policy in practice.

What You Will Learn

By the end of this page, you will understand how to translate working set sizes into allocation decisions, how the working set policy prevents thrashing, how load control and admission decisions integrate with WSS tracking, and how modern systems approximate working set allocation. You'll have a complete picture of working set-based memory management.

The Working Set Allocation Policy

Peter Denning's working set policy provides a principled answer to the frame allocation problem: The Working Set Policy (Formal Statement): Allocate to each active process a number of frames equal to its current working set size. A process may run only if its working set can be satisfied. If total working set demand exceeds available memory, suspend processes until demand is met. Mathematically: For each active process i: allocated_frames(i) = WSS(i, Δ) Constraint: Σ WSS(i) \leq Total Physical Frames If constraint violated: suspend process(es) until satisfied Policy Implications:

Key Policy Properties

•Dynamic allocation: Frames allocated change as WSS changes—no static partitioning
•Demand-driven: Allocation based on actual behavior, not worst-case assumptions
•Self-limiting: Multiprogramming level bounded by available memory
•Thrashing-free (ideally): Processes have their working sets, so page faults minimal
•Admission control: New processes admitted only if memory available

The Allocation-Fault Feedback Loop: The working set policy creates a stable feedback system: Normal operation: Each process has WSS frames, page faults are rare Process WSS grows: More references to new pages, more frames allocated System becomes overcommitted: Σ WSS > memory Process suspension: One or more processes suspended to restore balance Memory pressure reduces: Remaining processes have their working sets Suspension reconsidered: When memory available, suspended processes resume This feedback prevents the runaway positive feedback that causes thrashing (where more faults \to more paging \to slower progress \to longer in system \to even more faults).

The Fundamental Insight

The working set policy transforms memory management from a reactive crisis (responding to thrashing after it happens) to a proactive strategy (preventing thrashing by controlling admission). By knowing memory requirements BEFORE they cause problems, we can make intelligent decisions instead of scrambling.

Implementing WSS-Based Allocation

Translating the working set policy into an implementation requires several components working together. Component 1: WSS Tracking (Per-Process) For each process, continuously track working set size using one of the techniques from the previous page (reference bit aging, active/inactive lists, etc.). Component 2: Global Memory Accounting Maintain a global view of: Total available physical frames Sum of all active process WSS values List of suspended processes waiting for memory Component 3: Allocation Decision Logic When allocating frames, follow this logic: Process requests page not in memory (page fault) If process has free frames (allocated < WSS): allocate a free frame If process is at WSS limit: page replacement within its allocation If global memory is available and process needs more: expand allocation

wss_allocator.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
# Complete WSS-Based Memory Allocator Implementation
 
from enum import Enum
from dataclasses import dataclass, field
from typing import Dict, Set, List, Optional
from collections import deque
 
class ProcessState(Enum):
    RUNNING = "running"
    SUSPENDED = "suspended"
    WAITING = "waiting"
 
@dataclass
class ProcessMemory:
    """Per-process memory state."""
    pid: int
    wss: int = 0                    # Current working set size
    allocated_frames: int = 0        # Currently allocated frames
    resident_pages: Set[int] = field(default_factory=set)
    access_history: deque = field(default_factory=lambda: deque(maxlen=1000))
    state: ProcessState = ProcessState.RUNNING
    priority: int = 0
    
class WSSAllocator:
    """
    Working Set-Based Frame Allocator
    
    Implements Denning's working set policy:
    - Allocate frames equal to WSS for each process
    - Suspend processes when memory overcommitted
    - Resume when memory becomes available
    """
    
    def __init__(self, total_frames: int, delta: int = 100):
        self.total_frames = total_frames
        self.delta = delta  # Working set window
        
        # System state
        self.processes: Dict[int, ProcessMemory] = {}
        self.free_frames: int = total_frames
        self.suspended_queue: deque = deque()
        
        # Frame to process mapping
        self.frame_owner: Dict[int, int] = {}  # frame -> pid
        
        # Statistics
        self.suspensions = 0
        self.resumptions = 0
        self.page_faults = 0
        
    def add_process(self, pid: int, priority: int = 0) -> bool:
        """
        Add a new process to the system.
        Returns True if process can be admitted immediately.
        """
        proc = ProcessMemory(pid=pid, priority=priority)
        self.processes[pid] = proc
        
        # Initial WSS estimate (minimal)
        proc.wss = 1
        
        if self._can_allocate(proc.wss):
            proc.state = ProcessState.RUNNING
            self._allocate_frames(pid, proc.wss)
            return True
        else:
            proc.state = ProcessState.WAITING
            self.suspended_queue.append(pid)
            return False
    
    def access_page(self, pid: int, page: int) -> bool:
        """
        Process accesses a page. Returns True if page fault occurred.
        """
        if pid not in self.processes:
            return True
            
        proc = self.processes[pid]
        
        if proc.state != ProcessState.RUNNING:
            # Can't access pages while suspended
            return True
            
        # Record access in history
        proc.access_history.append(page)
        
        # Update WSS estimate
        self._update_wss(proc)
        
        if page in proc.resident_pages:
            # Page hit - no fault
            return False
        
        # Page fault
        self.page_faults += 1
        
        # Handle the fault
        self._handle_page_fault(proc, page)
        return True
    
    def _update_wss(self, proc: ProcessMemory):
        """
        Update process's WSS estimate from recent access history.
        """
        # WSS = number of distinct pages in last delta accesses
        recent = list(proc.access_history)[-self.delta:]
        proc.wss = len(set(recent)) if recent else 1
    
    def _handle_page_fault(self, proc: ProcessMemory, page: int):
        """
        Handle a page fault for a process.
        """
        # Check if process can grow its allocation
        if proc.allocated_frames < proc.wss and self._can_allocate(1):
            # Allocate additional frame
            self._allocate_frames(proc.pid, 1)
            proc.resident_pages.add(page)
        elif proc.allocated_frames > 0:
            # Replace within current allocation
            victim = self._select_victim_page(proc)
            if victim is not None:
                proc.resident_pages.remove(victim)
                proc.resident_pages.add(page)
        
        # Check if system is overcommitted after WSS update
        self._check_overcommitment()
    
    def _can_allocate(self, frames_needed: int) -> bool:
        """Check if frames can be allocated."""
        return self.free_frames >= frames_needed
    
    def _allocate_frames(self, pid: int, count: int):
        """Allocate frames to a process."""
        proc = self.processes[pid]
        
        for _ in range(min(count, self.free_frames)):
            self.free_frames -= 1
            proc.allocated_frames += 1
    
    def _deallocate_frames(self, pid: int, count: int):
        """Deallocate frames from a process."""
        proc = self.processes[pid]
        
        deallocated = min(count, proc.allocated_frames)
        self.free_frames += deallocated
        proc.allocated_frames -= deallocated
    
    def _select_victim_page(self, proc: ProcessMemory) -> Optional[int]:
        """
        Select a page to evict from process's resident set.
        Uses LRU approximation based on access history.
        """
        if not proc.resident_pages:
            return None
            
        # Find page with oldest recent access
        recent_accesses = list(proc.access_history)
        
        # Find resident page that appears earliest (or not at all) in history
        oldest_page = None
        oldest_position = -1
        
        for page in proc.resident_pages:
            try:
                position = len(recent_accesses) - 1 - recent_accesses[::-1].index(page)
            except ValueError:
                # Page not in recent history - perfect eviction candidate
                return page
            
            if oldest_page is None or position < oldest_position:
                oldest_page = page
                oldest_position = position
        
        return oldest_page
    
    def _check_overcommitment(self):
        """
        Check if system is overcommitted and suspend processes if needed.
        """
        total_wss = sum(
            p.wss for p in self.processes.values() 
            if p.state == ProcessState.RUNNING
        )
        
        while total_wss > self.total_frames:
            # System is overcommitted - suspend a process
            victim = self._select_suspension_victim()
            if victim is None:
                break  # No more processes to suspend
            
            self._suspend_process(victim)
            total_wss = sum(
                p.wss for p in self.processes.values() 
                if p.state == ProcessState.RUNNING
            )
    
    def _select_suspension_victim(self) -> Optional[int]:
        """
        Select a process to suspend when memory is overcommitted.
        
        Strategies:
        - Lowest priority
        - Largest WSS (frees most memory)
        - Most recently arrived (fairness)
        - Combination
        """
        running = [
            p for p in self.processes.values() 
            if p.state == ProcessState.RUNNING
        ]
        
        if not running:
            return None
        
        # Select process with largest WSS to free most memory
        victim = max(running, key=lambda p: p.wss)
        return victim.pid
    
    def _suspend_process(self, pid: int):
        """Suspend a process and free its frames."""
        proc = self.processes[pid]
        
        # Free all allocated frames
        self._deallocate_frames(pid, proc.allocated_frames)
        
        # Update state
        proc.state = ProcessState.SUSPENDED
        proc.resident_pages.clear()
        self.suspended_queue.append(pid)
        self.suspensions += 1
        
        print(f"Suspended process {pid} (WSS={proc.wss})")
        
        # Try to resume waiting processes
        self._try_resume_suspended()
    
    def _try_resume_suspended(self):
        """Try to resume suspended/waiting processes."""
        resumed = []
        
        while self.suspended_queue:
            pid = self.suspended_queue[0]
            proc = self.processes[pid]
            
            if self._can_allocate(proc.wss):
                self.suspended_queue.popleft()
                self._allocate_frames(pid, proc.wss)
                proc.state = ProcessState.RUNNING
                self.resumptions += 1
                resumed.append(pid)
                print(f"Resumed process {pid}")
            else:
                break  # Can't resume any more
        
        return resumed
    
    def get_multiprogramming_level(self) -> int:
        """Get number of running processes."""
        return sum(
            1 for p in self.processes.values() 
            if p.state == ProcessState.RUNNING
        )
    
    def get_memory_utilization(self) -> float:
        """Get fraction of memory in use."""
        return (self.total_frames - self.free_frames) / self.total_frames
    
    def get_total_wss(self) -> int:
        """Get sum of WSS for running processes."""
        return sum(
            p.wss for p in self.processes.values() 
            if p.state == ProcessState.RUNNING
        )
    
    def status_report(self):
        """Print detailed status."""
        print("
" + "=" * 60)
        print("Working Set Allocator Status")
        print("=" * 60)
        print(f"Total frames: {self.total_frames}")
        print(f"Free frames: {self.free_frames}")
        print(f"Memory utilization: {self.get_memory_utilization():.1%}")
        print(f"Multiprogramming level: {self.get_multiprogramming_level()}")
        print(f"Total WSS demand: {self.get_total_wss()}")
        print(f"Total suspensions: {self.suspensions}")
        print(f"Total resumptions: {self.resumptions}")
        print(f"Total page faults: {self.page_faults}")
        print()
        
        print("Running Processes:")
        for p in self.processes.values():
            if p.state == ProcessState.RUNNING:
                print(f"  PID {p.pid}: WSS={p.wss}, allocated={p.allocated_frames}, "
                      f"resident={len(p.resident_pages)}")
        
        print("
Suspended/Waiting Processes:")
        for p in self.processes.values():
            if p.state != ProcessState.RUNNING:
                print(f"  PID {p.pid}: WSS={p.wss}, state={p.state.value}")
        print()
 
 
# Demonstration
def demonstrate_wss_allocation():
    """Demonstrate WSS-based allocation in action."""
    print("WSS-Based Allocation Demonstration")
    print("=" * 60)
    
    import random
    
    # Create allocator with 100 frames
    allocator = WSSAllocator(total_frames=100, delta=50)
    
    # Add some processes
    for pid in range(1, 6):
        admitted = allocator.add_process(pid)
        print(f"Added process {pid}: {'admitted' if admitted else 'queued'}")
    
    allocator.status_report()
    
    # Simulate execution with varying access patterns
    print("Simulating execution...")
    
    for round in range(3):
        print(f"
--- Round {round + 1} ---")
        
        for p in allocator.processes.values():
            if p.state != ProcessState.RUNNING:
                continue
            
            # Simulate accesses (each process has different WSS)
            hot_pages = list(range(p.pid * 10, p.pid * 10 + 15 + p.pid * 5))
            
            for _ in range(100):
                page = random.choice(hot_pages)
                allocator.access_page(p.pid, page)
        
        allocator.status_report()
 
if __name__ == "__main__":
    demonstrate_wss_allocation()

Thrashing Prevention Through WSS

The working set model's primary purpose is preventing thrashing. Let's examine exactly how WSS-based allocation achieves this. Why Thrashing Occurs (Root Cause): Thrashing happens when: Total memory demand (Σ WSS) exceeds available memory System doesn't recognize this overcommitment Each process steals pages from others All processes fault continuously CPU spends all time on paging, not computation How WSS-Based Allocation Prevents Thrashing: WSS measurement: System knows each process's memory requirement Overcommitment detection: When Σ WSS > memory, system recognizes problem Proactive suspension: BEFORE thrashing begins, suspend processes Working sets satisfied: Remaining processes have their pages resident Stable operation: Running processes make progress efficiently

Thrashing Prevention: With vs Without WSS
Aspect	Without WSS Management	With WSS Management
Detection	Reactive (notice high fault rate)	Proactive (detect before thrashing)
Response	Kill processes randomly	Suspend systematically
Recovery time	Long (cascading effects)	Immediate (prevention not recovery)
Data loss risk	High (OOM killer)	Low (suspend/resume)
Throughput during	Near zero	Remains high for running processes
Multiprogramming	Uncontrolled	Dynamically managed

The Thrashing Cliff

Without WSS management, systems often exhibit a 'cliff' behavior: performance is acceptable until some threshold, then collapses catastrophically. With WSS management, performance degrades gracefully—fewer processes run when memory is tight, but those that run perform well. The cliff is replaced by a gradual slope.

thrashing_prevention.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
# Demonstration of thrashing prevention via WSS
 
import random
import time
 
class ThrashingDemonstrator:
    """
    Compare system behavior with and without WSS-based allocation.
    """
    
    def __init__(self, total_memory, num_processes, wss_per_process):
        self.total_memory = total_memory
        self.num_processes = num_processes
        self.wss_per_process = wss_per_process
        
    def simulate_without_wss(self, simulation_cycles):
        """
        Simulate naive allocation without WSS tracking.
        All processes share memory pool equally, no suspension.
        """
        print("
Simulation: WITHOUT WSS-Based Allocation")
        print("-" * 50)
        
        frames_per_process = self.total_memory // self.num_processes
        print(f"Each process gets: {frames_per_process} frames")
        print(f"Each process needs (WSS): {self.wss_per_process} frames")
        
        if frames_per_process < self.wss_per_process:
            print("⚠️  ALLOCATION < WSS: Thrashing expected!")
        
        # Simulate
        total_faults = 0
        total_useful_work = 0
        
        for cycle in range(simulation_cycles):
            cycle_faults = 0
            cycle_work = 0
            
            for p in range(self.num_processes):
                process_pages = set()
                pages_needed = []
                
                # Generate access pattern based on WSS
                for _ in range(50):  # 50 accesses per cycle
                    page = random.randint(0, self.wss_per_process - 1)
                    pages_needed.append(page)
                
                # Simulate with limited frames (LRU-ish)
                resident = []
                for page in pages_needed:
                    if page in resident:
                        cycle_work += 1
                    else:
                        cycle_faults += 1
                        if len(resident) >= frames_per_process:
                            resident.pop(0)  # Evict oldest
                        resident.append(page)
            
            total_faults += cycle_faults
            total_useful_work += cycle_work
        
        fault_rate = total_faults / (total_faults + total_useful_work)
        throughput = total_useful_work / simulation_cycles
        
        return {
            'total_faults': total_faults,
            'total_work': total_useful_work,
            'fault_rate': fault_rate,
            'throughput': throughput,
            'processes_running': self.num_processes
        }
    
    def simulate_with_wss(self, simulation_cycles):
        """
        Simulate with WSS-based allocation.
        Suspend processes when overcommitted.
        """
        print("
Simulation: WITH WSS-Based Allocation")
        print("-" * 50)
        
        # How many processes can we actually run?
        max_running = self.total_memory // self.wss_per_process
        actual_running = min(max_running, self.num_processes)
        suspended = self.num_processes - actual_running
        
        print(f"Can run {actual_running} processes with full WSS")
        if suspended > 0:
            print(f"Suspended {suspended} processes to prevent thrashing")
        
        # Each running process gets its full WSS
        frames_per_process = self.wss_per_process
        
        # Simulate
        total_faults = 0
        total_useful_work = 0
        
        for cycle in range(simulation_cycles):
            cycle_faults = 0
            cycle_work = 0
            
            for p in range(actual_running):
                process_pages = set()
                pages_needed = []
                
                # Generate access pattern
                for _ in range(50):
                    page = random.randint(0, self.wss_per_process - 1)
                    pages_needed.append(page)
                
                # Simulate with adequate frames
                resident = []
                for page in pages_needed:
                    if page in resident:
                        cycle_work += 1
                    else:
                        cycle_faults += 1
                        if len(resident) >= frames_per_process:
                            resident.pop(0)
                        resident.append(page)
            
            total_faults += cycle_faults
            total_useful_work += cycle_work
        
        fault_rate = total_faults / (total_faults + total_useful_work)
        throughput = total_useful_work / simulation_cycles
        
        return {
            'total_faults': total_faults,
            'total_work': total_useful_work,
            'fault_rate': fault_rate,
            'throughput': throughput,
            'processes_running': actual_running,
            'processes_suspended': suspended
        }
 
 
def compare_approaches():
    """
    Compare thrashing behavior with and without WSS management.
    """
    print("=" * 60)
    print("THRASHING PREVENTION COMPARISON")
    print("=" * 60)
    
    # Scenario: 100 frames total, 10 processes each needing 20 frames
    # Total demand: 200 frames, only 100 available -> overcommitted
    
    demo = ThrashingDemonstrator(
        total_memory=100,
        num_processes=10,
        wss_per_process=20
    )
    
    print(f"
Scenario:")
    print(f"  Total memory: 100 frames")
    print(f"  Number of processes: 10")
    print(f"  WSS per process: 20 frames")
    print(f"  Total demand: 200 frames (2x overcommitted)")
    
    without_wss = demo.simulate_without_wss(100)
    with_wss = demo.simulate_with_wss(100)
    
    print("
" + "=" * 60)
    print("RESULTS COMPARISON")
    print("=" * 60)
    
    print("
Without WSS Management:")
    print(f"  Processes running: {without_wss['processes_running']}")
    print(f"  Page fault rate: {without_wss['fault_rate']:.1%}")
    print(f"  Throughput: {without_wss['throughput']:.0f} ops/cycle")
    
    print("
With WSS Management:")
    print(f"  Processes running: {with_wss['processes_running']}")
    print(f"  Processes suspended: {with_wss.get('processes_suspended', 0)}")
    print(f"  Page fault rate: {with_wss['fault_rate']:.1%}")
    print(f"  Throughput: {with_wss['throughput']:.0f} ops/cycle")
    
    print("
Analysis:")
    throughput_ratio = with_wss['throughput'] / without_wss['throughput']
    print(f"  WSS management provides {throughput_ratio:.1f}x throughput")
    print(f"  Fault rate reduced from {without_wss['fault_rate']:.1%} to {with_wss['fault_rate']:.1%}")
    
    if with_wss['throughput'] > without_wss['throughput']:
        print("
  ✓ Running fewer processes with adequate memory")
        print("    is BETTER than running all processes with inadequate memory")
 
if __name__ == "__main__":
    compare_approaches()

Load Control and Admission Decisions

The working set model naturally integrates with load control—managing how many processes can run concurrently based on available resources. Load Control Mechanisms: 1. Admission Control: When a new process is created or wants to run: Estimate its WSS (from history, process type, or initial value) Check if Σ WSS + new_WSS \leq available memory If yes: admit; if no: queue until memory available 2. Degree of Multiprogramming: The number of running processes is dynamically bounded: Maximum MPL = available_memory / average_WSS Actual MPL varies as process WSS values change System self-adjusts to maintain stability 3. Suspension Priority: When suspension is needed, choose victim by: Lowest priority Largest WSS (frees most memory) Most recently admitted (fairness) Least work completed (minimize wasted progress)

When to Increase MPL

•Process completes and frees frames
•Running process's WSS decreases
•Additional physical memory available
•Suspended process no longer needed
•Low page fault rate indicates headroom

When to Decrease MPL

•Total WSS exceeds available memory
•Running process's WSS increases
•Page fault rate exceeds threshold
•CPU utilization drops due to paging
•Memory pressure from kernel/buffers

The Balance Set Manager

Windows uses a 'Balance Set Manager' that periodically evaluates system memory state and adjusts process working sets. When memory is plentiful, processes are allowed to grow their working sets. When memory is tight, working sets are trimmed and processes may be suspended. This provides the load control functionality without exact WSS tracking.

Medium-Term Scheduling Integration: Load control connects to the medium-term scheduler (swapper): Swap-out decision: When memory is tight, select process(es) to swap out entirely (all pages removed from memory) WSS guides selection: Processes with largest WSS are good swap-out candidates (free most memory) Swap-in decision: When memory becomes available, select process(es) to bring back WSS predicts cost: Swapping in a process with large WSS requires loading many pages The working set model provides the information needed for intelligent medium-term scheduling: which processes to suspend and what the cost of resuming them will be.

Modern Approximations to Working Set Policy

Pure working set allocation as described by Denning is rarely implemented exactly. Modern systems use approximations that capture the essential benefits with lower overhead. Linux's Approximate Approach: Linux doesn't track explicit working sets but achieves similar effects: Active/Inactive Lists: Approximate recency tracking kswapd: Background daemon reclaims memory proactively Watermarks: Trigger reclaim before memory exhaustion OOM Killer: Last resort when memory truly exhausted Cgroups: Allow explicit memory limits per process group The Result: Linux behaves somewhat like a working set system without explicit WSS tracking.

Linux Memory Management vs Pure Working Set
Aspect	Linux Approach	Pure Working Set
Recency tracking	Active/Inactive lists	Explicit window Δ
Allocation basis	Demand + limits	WSS per process
Overcommit handling	OOM killer	Process suspension
Thrashing response	Reactive (detect)	Proactive (prevent)
Memory limits	Optional (cgroups)	Implicit (WSS-based)

Page Fault Frequency (PFF) as Alternative: Many systems use PFF as a simpler alternative to working set tracking: Monitor: Page fault rate for each process If fault rate too high: Allocate more frames If fault rate very low: Reclaim some frames Converges to: Allocation approximating WSS PFF is reactive rather than proactive but achieves similar steady-state behavior with lower implementation complexity. Container-Era Considerations: Modern containerized environments add new dimensions: Memory limits per container: Explicit bounds (like mini-working-sets) Memory QoS: Guaranteed minimum, burstable maximum Pressure propagation: Containers can signal memory pressure Kill policies: Which container to terminate when limits hit These mechanisms approximate working set principles at the container level rather than process level.

pff_alternative.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
# Page Fault Frequency (PFF) as WSS Alternative
 
from dataclasses import dataclass
from typing import Dict
 
@dataclass
class ProcessPFF:
    """Per-process PFF tracking state."""
    pid: int
    allocated_frames: int = 10  # Starting allocation
    page_faults: int = 0
    time_elapsed: int = 0
    fault_rate: float = 0.0
 
class PFFAllocator:
    """
    Page Fault Frequency Based Allocator
    
    Adjusts allocation based on observed fault rate rather than
    explicit WSS tracking. Simpler but reactive rather than proactive.
    """
    
    def __init__(self, total_frames: int):
        self.total_frames = total_frames
        self.free_frames = total_frames
        self.processes: Dict[int, ProcessPFF] = {}
        
        # Tuning parameters
        self.upper_threshold = 0.05   # Above this: need more frames
        self.lower_threshold = 0.01   # Below this: can give up frames
        self.adjustment_interval = 100  # Evaluate every N time units
        
    def add_process(self, pid: int, initial_frames: int = 10):
        """Add a new process with initial frame allocation."""
        if self._can_allocate(initial_frames):
            self.processes[pid] = ProcessPFF(
                pid=pid,
                allocated_frames=initial_frames
            )
            self.free_frames -= initial_frames
            return True
        return False
    
    def _can_allocate(self, frames: int) -> bool:
        return self.free_frames >= frames
    
    def record_page_fault(self, pid: int):
        """Record a page fault for a process."""
        if pid in self.processes:
            self.processes[pid].page_faults += 1
    
    def time_tick(self, pid: int):
        """Record time passing for a process."""
        if pid not in self.processes:
            return
            
        proc = self.processes[pid]
        proc.time_elapsed += 1
        
        # Evaluate allocation periodically
        if proc.time_elapsed % self.adjustment_interval == 0:
            self._evaluate_allocation(proc)
    
    def _evaluate_allocation(self, proc: ProcessPFF):
        """
        Evaluate and adjust allocation based on fault rate.
        
        This is the core PFF logic:
        - High fault rate -> allocate more frames
        - Low fault rate -> reclaim frames
        """
        interval = self.adjustment_interval
        faults_in_interval = proc.page_faults  # Simplified: total faults
        
        # Compute fault rate (faults per time unit)
        proc.fault_rate = proc.page_faults / proc.time_elapsed if proc.time_elapsed > 0 else 0
        
        print(f"PID {proc.pid}: fault_rate={proc.fault_rate:.4f}, allocated={proc.allocated_frames}")
        
        if proc.fault_rate > self.upper_threshold:
            # Fault rate too high: process needs more memory
            frames_to_add = min(5, self.free_frames)  # Add up to 5 frames
            if frames_to_add > 0:
                proc.allocated_frames += frames_to_add
                self.free_frames -= frames_to_add
                print(f"  → Increased allocation by {frames_to_add}")
                
        elif proc.fault_rate < self.lower_threshold:
            # Fault rate very low: process has excess allocation
            frames_to_reclaim = min(2, proc.allocated_frames - 5)  # Keep minimum 5
            if frames_to_reclaim > 0:
                proc.allocated_frames -= frames_to_reclaim
                self.free_frames += frames_to_reclaim
                print(f"  → Reclaimed {frames_to_reclaim} frames")
        
        # Reset fault counter for next interval
        proc.page_faults = 0
    
    def get_allocations(self) -> Dict[int, int]:
        """Get current frame allocations."""
        return {pid: p.allocated_frames for pid, p in self.processes.items()}
 
 
def demonstrate_pff():
    """Demonstrate PFF-based allocation."""
    print("Page Fault Frequency (PFF) Allocation")
    print("=" * 60)
    
    allocator = PFFAllocator(total_frames=200)
    
    # Add processes
    allocator.add_process(1, initial_frames=20)
    allocator.add_process(2, initial_frames=20)
    allocator.add_process(3, initial_frames=20)
    
    # Simulate varying fault rates
    print("
Simulating execution...")
    
    import random
    
    for t in range(500):
        for pid in [1, 2, 3]:
            allocator.time_tick(pid)
            
            # Different fault rates for different processes
            if pid == 1:
                fault_prob = 0.08  # High fault rate - needs more memory
            elif pid == 2:
                fault_prob = 0.005  # Low fault rate - has excess
            else:
                fault_prob = 0.02  # Normal
            
            if random.random() < fault_prob:
                allocator.record_page_fault(pid)
    
    print("
Final Allocations:")
    for pid, frames in allocator.get_allocations().items():
        print(f"  PID {pid}: {frames} frames")
    
    print("
Key insight: PFF converges to allocation proportional to WSS")
    print("without explicitly tracking the working set!")
 
if __name__ == "__main__":
    demonstrate_pff()

WSS vs PFF: Complementary Approaches

Working set and PFF approaches are not mutually exclusive. Working set is proactive (predicts needs from behavior), while PFF is reactive (adjusts based on faults). A combined approach might use WSS for admission control and PFF for fine-tuning within-process allocation. Many systems implicitly use both principles.

Putting It All Together

Let's consolidate everything we've learned about the working set model into a coherent view of how it enables intelligent memory management. The Complete Working Set Memory Management System: Layer 1: Observation Track page references for each process Maintain working set estimates (via reference bit aging, active/inactive lists, or sampling) Monitor WSS trends over time Layer 2: Analysis Compute total system WSS demand Compare against available memory Identify overcommitment risk Detect phase transitions in processes Layer 3: Decision Admission control for new processes Suspension decisions when overcommitted Resumption decisions when memory available Per-process allocation adjustments Layer 4: Action Allocate/deallocate frames Trigger page-in for newly allocated frames Initiate swap-out for suspended processes Update page tables and TLBs

Design Decisions Summary:

Design Choice	Options	Trade-off
Window size Δ	Fixed vs Adaptive	Simplicity vs Optimality
WSS tracking	Exact vs Sampled	Accuracy vs Overhead
Suspension victim	Largest WSS vs Lowest Priority	Memory vs Fairness
Allocation granularity	Per-page vs Per-quantum	Precision vs Overhead
Overcommit tolerance	None vs Limited	Safety vs Utilization

Best Practices for Implementation: Use efficient data structures: Active/inactive lists with O(1) operations Batch updates: Update WSS estimates periodically, not on every access Smooth adjustments: Avoid oscillation by damping allocation changes Monitor metrics: Track page fault rates, CPU utilization, suspension frequency Provide visibility: Allow administrators to see WSS and allocation status

Key Implementation Insights

•Approximate is good enough: Don't over-engineer WSS tracking; approximate values serve allocation decisions well
•Proactive beats reactive: Detecting overcommitment before thrashing is far better than recovering after
•Suspension isn't failure: Temporarily suspending a process protects all other processes' performance
•Combine techniques: Use WSS for load control, PFF for fine-tuning, and whatever else helps
•Monitor continuously: Memory requirements change; tracking must be ongoing, not one-time

Summary: The Working Set Model Complete

We've now completed our deep dive into the working set model—from its theoretical foundation in the principle of locality to its practical implementation in modern operating systems.

Module Summary: Key Concepts

•Locality Principle: Programs access memory predictably; temporal and spatial locality enable prediction
•Working Set Definition: W(t, Δ) = pages accessed in interval [t-Δ, t]; formalizes 'memory in active use'
•Window Parameter Δ: Controls trade-off between memory consumption and page fault rate
•WSS Tracking: Reference bit aging, active/inactive lists, hardware counters, and sampling provide practical approximations
•WSS-Based Allocation: Allocate frames equal to WSS; suspend when overcommitted; prevents thrashing proactively

Module Complete

You have mastered the working set model for memory management. You understand why it works (locality), how it's defined (W(t, Δ)), how to tune it (window selection), how to measure it (WSS tracking), and how to use it (WSS-based allocation). This knowledge enables you to reason about memory management in any operating system and design effective allocation policies.

Connecting to Broader Context: The working set model is part of a broader family of memory management techniques: Next topic: Thrashing Solutions explores additional techniques beyond working set management Related: Page Fault Frequency (PFF) provides a reactive alternative to proactive WSS Integration: Working set concepts apply to caching, database buffer pools, and distributed systems The principles you've learned here—understanding demand, tracking usage, preventing overcommitment, and making proactive decisions—apply far beyond operating system memory management. They're fundamental to any resource allocation problem where demand varies and resources are limited.

Operating SystemsWorking Set Model

Working Set Model

LevelIntermediate

Duration75 mins

TopicWorking Set Model

5 / 5

Allocation Based on WSS

Closing the Loop: From Measurement to Action

We've built all the pieces: we understand locality, we've defined the working set, we've tuned the window parameter, and we've implemented tracking. Now comes the payoff— using this information to allocate memory intelligently . The working set model doesn't just describe behavior; it prescribes action. Its fundamental policy is elegantly simple: give each process enough frames to hold its working set, and prevent thrashing by controlling admission when memory is overcommitted . This page shows how to implement this policy in practice.

What You Will Learn

By the end of this page, you will understand how to translate working set sizes into allocation decisions, how the working set policy prevents thrashing, how load control and admission decisions integrate with WSS tracking, and how modern systems approximate working set allocation. You'll have a complete picture of working set-based memory management.

The Working Set Allocation Policy

Peter Denning's working set policy provides a principled answer to the frame allocation problem: The Working Set Policy (Formal Statement): Allocate to each active process a number of frames equal to its current working set size. A process may run only if its working set can be satisfied. If total working set demand exceeds available memory, suspend processes until demand is met. Mathematically: For each active process i: allocated_frames(i) = WSS(i, Δ) Constraint: Σ WSS(i) \leq Total Physical Frames If constraint violated: suspend process(es) until satisfied Policy Implications:

Key Policy Properties

•Dynamic allocation: Frames allocated change as WSS changes—no static partitioning
•Demand-driven: Allocation based on actual behavior, not worst-case assumptions
•Self-limiting: Multiprogramming level bounded by available memory
•Thrashing-free (ideally): Processes have their working sets, so page faults minimal
•Admission control: New processes admitted only if memory available

The Allocation-Fault Feedback Loop: The working set policy creates a stable feedback system: Normal operation: Each process has WSS frames, page faults are rare Process WSS grows: More references to new pages, more frames allocated System becomes overcommitted: Σ WSS > memory Process suspension: One or more processes suspended to restore balance Memory pressure reduces: Remaining processes have their working sets Suspension reconsidered: When memory available, suspended processes resume This feedback prevents the runaway positive feedback that causes thrashing (where more faults \to more paging \to slower progress \to longer in system \to even more faults).

The Fundamental Insight

The working set policy transforms memory management from a reactive crisis (responding to thrashing after it happens) to a proactive strategy (preventing thrashing by controlling admission). By knowing memory requirements BEFORE they cause problems, we can make intelligent decisions instead of scrambling.

Implementing WSS-Based Allocation

Translating the working set policy into an implementation requires several components working together. Component 1: WSS Tracking (Per-Process) For each process, continuously track working set size using one of the techniques from the previous page (reference bit aging, active/inactive lists, etc.). Component 2: Global Memory Accounting Maintain a global view of: Total available physical frames Sum of all active process WSS values List of suspended processes waiting for memory Component 3: Allocation Decision Logic When allocating frames, follow this logic: Process requests page not in memory (page fault) If process has free frames (allocated < WSS): allocate a free frame If process is at WSS limit: page replacement within its allocation If global memory is available and process needs more: expand allocation

wss_allocator.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
# Complete WSS-Based Memory Allocator Implementation
 
from enum import Enum
from dataclasses import dataclass, field
from typing import Dict, Set, List, Optional
from collections import deque
 
class ProcessState(Enum):
    RUNNING = "running"
    SUSPENDED = "suspended"
    WAITING = "waiting"
 
@dataclass
class ProcessMemory:
    """Per-process memory state."""
    pid: int
    wss: int = 0                    # Current working set size
    allocated_frames: int = 0        # Currently allocated frames
    resident_pages: Set[int] = field(default_factory=set)
    access_history: deque = field(default_factory=lambda: deque(maxlen=1000))
    state: ProcessState = ProcessState.RUNNING
    priority: int = 0
    
class WSSAllocator:
    """
    Working Set-Based Frame Allocator
    
    Implements Denning's working set policy:
    - Allocate frames equal to WSS for each process
    - Suspend processes when memory overcommitted
    - Resume when memory becomes available
    """
    
    def __init__(self, total_frames: int, delta: int = 100):
        self.total_frames = total_frames
        self.delta = delta  # Working set window
        
        # System state
        self.processes: Dict[int, ProcessMemory] = {}
        self.free_frames: int = total_frames
        self.suspended_queue: deque = deque()
        
        # Frame to process mapping
        self.frame_owner: Dict[int, int] = {}  # frame -> pid
        
        # Statistics
        self.suspensions = 0
        self.resumptions = 0
        self.page_faults = 0
        
    def add_process(self, pid: int, priority: int = 0) -> bool:
        """
        Add a new process to the system.
        Returns True if process can be admitted immediately.
        """
        proc = ProcessMemory(pid=pid, priority=priority)
        self.processes[pid] = proc
        
        # Initial WSS estimate (minimal)
        proc.wss = 1
        
        if self._can_allocate(proc.wss):
            proc.state = ProcessState.RUNNING
            self._allocate_frames(pid, proc.wss)
            return True
        else:
            proc.state = ProcessState.WAITING
            self.suspended_queue.append(pid)
            return False
    
    def access_page(self, pid: int, page: int) -> bool:
        """
        Process accesses a page. Returns True if page fault occurred.
        """
        if pid not in self.processes:
            return True
            
        proc = self.processes[pid]
        
        if proc.state != ProcessState.RUNNING:
            # Can't access pages while suspended
            return True
            
        # Record access in history
        proc.access_history.append(page)
        
        # Update WSS estimate
        self._update_wss(proc)
        
        if page in proc.resident_pages:
            # Page hit - no fault
            return False
        
        # Page fault
        self.page_faults += 1
        
        # Handle the fault
        self._handle_page_fault(proc, page)
        return True
    
    def _update_wss(self, proc: ProcessMemory):
        """
        Update process's WSS estimate from recent access history.
        """
        # WSS = number of distinct pages in last delta accesses
        recent = list(proc.access_history)[-self.delta:]
        proc.wss = len(set(recent)) if recent else 1
    
    def _handle_page_fault(self, proc: ProcessMemory, page: int):
        """
        Handle a page fault for a process.
        """
        # Check if process can grow its allocation
        if proc.allocated_frames < proc.wss and self._can_allocate(1):
            # Allocate additional frame
            self._allocate_frames(proc.pid, 1)
            proc.resident_pages.add(page)
        elif proc.allocated_frames > 0:
            # Replace within current allocation
            victim = self._select_victim_page(proc)
            if victim is not None:
                proc.resident_pages.remove(victim)
                proc.resident_pages.add(page)
        
        # Check if system is overcommitted after WSS update
        self._check_overcommitment()
    
    def _can_allocate(self, frames_needed: int) -> bool:
        """Check if frames can be allocated."""
        return self.free_frames >= frames_needed
    
    def _allocate_frames(self, pid: int, count: int):
        """Allocate frames to a process."""
        proc = self.processes[pid]
        
        for _ in range(min(count, self.free_frames)):
            self.free_frames -= 1
            proc.allocated_frames += 1
    
    def _deallocate_frames(self, pid: int, count: int):
        """Deallocate frames from a process."""
        proc = self.processes[pid]
        
        deallocated = min(count, proc.allocated_frames)
        self.free_frames += deallocated
        proc.allocated_frames -= deallocated
    
    def _select_victim_page(self, proc: ProcessMemory) -> Optional[int]:
        """
        Select a page to evict from process's resident set.
        Uses LRU approximation based on access history.
        """
        if not proc.resident_pages:
            return None
            
        # Find page with oldest recent access
        recent_accesses = list(proc.access_history)
        
        # Find resident page that appears earliest (or not at all) in history
        oldest_page = None
        oldest_position = -1
        
        for page in proc.resident_pages:
            try:
                position = len(recent_accesses) - 1 - recent_accesses[::-1].index(page)
            except ValueError:
                # Page not in recent history - perfect eviction candidate
                return page
            
            if oldest_page is None or position < oldest_position:
                oldest_page = page
                oldest_position = position
        
        return oldest_page
    
    def _check_overcommitment(self):
        """
        Check if system is overcommitted and suspend processes if needed.
        """
        total_wss = sum(
            p.wss for p in self.processes.values() 
            if p.state == ProcessState.RUNNING
        )
        
        while total_wss > self.total_frames:
            # System is overcommitted - suspend a process
            victim = self._select_suspension_victim()
            if victim is None:
                break  # No more processes to suspend
            
            self._suspend_process(victim)
            total_wss = sum(
                p.wss for p in self.processes.values() 
                if p.state == ProcessState.RUNNING
            )
    
    def _select_suspension_victim(self) -> Optional[int]:
        """
        Select a process to suspend when memory is overcommitted.
        
        Strategies:
        - Lowest priority
        - Largest WSS (frees most memory)
        - Most recently arrived (fairness)
        - Combination
        """
        running = [
            p for p in self.processes.values() 
            if p.state == ProcessState.RUNNING
        ]
        
        if not running:
            return None
        
        # Select process with largest WSS to free most memory
        victim = max(running, key=lambda p: p.wss)
        return victim.pid
    
    def _suspend_process(self, pid: int):
        """Suspend a process and free its frames."""
        proc = self.processes[pid]
        
        # Free all allocated frames
        self._deallocate_frames(pid, proc.allocated_frames)
        
        # Update state
        proc.state = ProcessState.SUSPENDED
        proc.resident_pages.clear()
        self.suspended_queue.append(pid)
        self.suspensions += 1
        
        print(f"Suspended process {pid} (WSS={proc.wss})")
        
        # Try to resume waiting processes
        self._try_resume_suspended()
    
    def _try_resume_suspended(self):
        """Try to resume suspended/waiting processes."""
        resumed = []
        
        while self.suspended_queue:
            pid = self.suspended_queue[0]
            proc = self.processes[pid]
            
            if self._can_allocate(proc.wss):
                self.suspended_queue.popleft()
                self._allocate_frames(pid, proc.wss)
                proc.state = ProcessState.RUNNING
                self.resumptions += 1
                resumed.append(pid)
                print(f"Resumed process {pid}")
            else:
                break  # Can't resume any more
        
        return resumed
    
    def get_multiprogramming_level(self) -> int:
        """Get number of running processes."""
        return sum(
            1 for p in self.processes.values() 
            if p.state == ProcessState.RUNNING
        )
    
    def get_memory_utilization(self) -> float:
        """Get fraction of memory in use."""
        return (self.total_frames - self.free_frames) / self.total_frames
    
    def get_total_wss(self) -> int:
        """Get sum of WSS for running processes."""
        return sum(
            p.wss for p in self.processes.values() 
            if p.state == ProcessState.RUNNING
        )
    
    def status_report(self):
        """Print detailed status."""
        print("
" + "=" * 60)
        print("Working Set Allocator Status")
        print("=" * 60)
        print(f"Total frames: {self.total_frames}")
        print(f"Free frames: {self.free_frames}")
        print(f"Memory utilization: {self.get_memory_utilization():.1%}")
        print(f"Multiprogramming level: {self.get_multiprogramming_level()}")
        print(f"Total WSS demand: {self.get_total_wss()}")
        print(f"Total suspensions: {self.suspensions}")
        print(f"Total resumptions: {self.resumptions}")
        print(f"Total page faults: {self.page_faults}")
        print()
        
        print("Running Processes:")
        for p in self.processes.values():
            if p.state == ProcessState.RUNNING:
                print(f"  PID {p.pid}: WSS={p.wss}, allocated={p.allocated_frames}, "
                      f"resident={len(p.resident_pages)}")
        
        print("
Suspended/Waiting Processes:")
        for p in self.processes.values():
            if p.state != ProcessState.RUNNING:
                print(f"  PID {p.pid}: WSS={p.wss}, state={p.state.value}")
        print()
 
 
# Demonstration
def demonstrate_wss_allocation():
    """Demonstrate WSS-based allocation in action."""
    print("WSS-Based Allocation Demonstration")
    print("=" * 60)
    
    import random
    
    # Create allocator with 100 frames
    allocator = WSSAllocator(total_frames=100, delta=50)
    
    # Add some processes
    for pid in range(1, 6):
        admitted = allocator.add_process(pid)
        print(f"Added process {pid}: {'admitted' if admitted else 'queued'}")
    
    allocator.status_report()
    
    # Simulate execution with varying access patterns
    print("Simulating execution...")
    
    for round in range(3):
        print(f"
--- Round {round + 1} ---")
        
        for p in allocator.processes.values():
            if p.state != ProcessState.RUNNING:
                continue
            
            # Simulate accesses (each process has different WSS)
            hot_pages = list(range(p.pid * 10, p.pid * 10 + 15 + p.pid * 5))
            
            for _ in range(100):
                page = random.choice(hot_pages)
                allocator.access_page(p.pid, page)
        
        allocator.status_report()
 
if __name__ == "__main__":
    demonstrate_wss_allocation()

Thrashing Prevention Through WSS

The working set model's primary purpose is preventing thrashing. Let's examine exactly how WSS-based allocation achieves this. Why Thrashing Occurs (Root Cause): Thrashing happens when: Total memory demand (Σ WSS) exceeds available memory System doesn't recognize this overcommitment Each process steals pages from others All processes fault continuously CPU spends all time on paging, not computation How WSS-Based Allocation Prevents Thrashing: WSS measurement: System knows each process's memory requirement Overcommitment detection: When Σ WSS > memory, system recognizes problem Proactive suspension: BEFORE thrashing begins, suspend processes Working sets satisfied: Remaining processes have their pages resident Stable operation: Running processes make progress efficiently

Thrashing Prevention: With vs Without WSS
Aspect	Without WSS Management	With WSS Management
Detection	Reactive (notice high fault rate)	Proactive (detect before thrashing)
Response	Kill processes randomly	Suspend systematically
Recovery time	Long (cascading effects)	Immediate (prevention not recovery)
Data loss risk	High (OOM killer)	Low (suspend/resume)
Throughput during	Near zero	Remains high for running processes
Multiprogramming	Uncontrolled	Dynamically managed

The Thrashing Cliff

Without WSS management, systems often exhibit a 'cliff' behavior: performance is acceptable until some threshold, then collapses catastrophically. With WSS management, performance degrades gracefully—fewer processes run when memory is tight, but those that run perform well. The cliff is replaced by a gradual slope.

thrashing_prevention.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
# Demonstration of thrashing prevention via WSS
 
import random
import time
 
class ThrashingDemonstrator:
    """
    Compare system behavior with and without WSS-based allocation.
    """
    
    def __init__(self, total_memory, num_processes, wss_per_process):
        self.total_memory = total_memory
        self.num_processes = num_processes
        self.wss_per_process = wss_per_process
        
    def simulate_without_wss(self, simulation_cycles):
        """
        Simulate naive allocation without WSS tracking.
        All processes share memory pool equally, no suspension.
        """
        print("
Simulation: WITHOUT WSS-Based Allocation")
        print("-" * 50)
        
        frames_per_process = self.total_memory // self.num_processes
        print(f"Each process gets: {frames_per_process} frames")
        print(f"Each process needs (WSS): {self.wss_per_process} frames")
        
        if frames_per_process < self.wss_per_process:
            print("⚠️  ALLOCATION < WSS: Thrashing expected!")
        
        # Simulate
        total_faults = 0
        total_useful_work = 0
        
        for cycle in range(simulation_cycles):
            cycle_faults = 0
            cycle_work = 0
            
            for p in range(self.num_processes):
                process_pages = set()
                pages_needed = []
                
                # Generate access pattern based on WSS
                for _ in range(50):  # 50 accesses per cycle
                    page = random.randint(0, self.wss_per_process - 1)
                    pages_needed.append(page)
                
                # Simulate with limited frames (LRU-ish)
                resident = []
                for page in pages_needed:
                    if page in resident:
                        cycle_work += 1
                    else:
                        cycle_faults += 1
                        if len(resident) >= frames_per_process:
                            resident.pop(0)  # Evict oldest
                        resident.append(page)
            
            total_faults += cycle_faults
            total_useful_work += cycle_work
        
        fault_rate = total_faults / (total_faults + total_useful_work)
        throughput = total_useful_work / simulation_cycles
        
        return {
            'total_faults': total_faults,
            'total_work': total_useful_work,
            'fault_rate': fault_rate,
            'throughput': throughput,
            'processes_running': self.num_processes
        }
    
    def simulate_with_wss(self, simulation_cycles):
        """
        Simulate with WSS-based allocation.
        Suspend processes when overcommitted.
        """
        print("
Simulation: WITH WSS-Based Allocation")
        print("-" * 50)
        
        # How many processes can we actually run?
        max_running = self.total_memory // self.wss_per_process
        actual_running = min(max_running, self.num_processes)
        suspended = self.num_processes - actual_running
        
        print(f"Can run {actual_running} processes with full WSS")
        if suspended > 0:
            print(f"Suspended {suspended} processes to prevent thrashing")
        
        # Each running process gets its full WSS
        frames_per_process = self.wss_per_process
        
        # Simulate
        total_faults = 0
        total_useful_work = 0
        
        for cycle in range(simulation_cycles):
            cycle_faults = 0
            cycle_work = 0
            
            for p in range(actual_running):
                process_pages = set()
                pages_needed = []
                
                # Generate access pattern
                for _ in range(50):
                    page = random.randint(0, self.wss_per_process - 1)
                    pages_needed.append(page)
                
                # Simulate with adequate frames
                resident = []
                for page in pages_needed:
                    if page in resident:
                        cycle_work += 1
                    else:
                        cycle_faults += 1
                        if len(resident) >= frames_per_process:
                            resident.pop(0)
                        resident.append(page)
            
            total_faults += cycle_faults
            total_useful_work += cycle_work
        
        fault_rate = total_faults / (total_faults + total_useful_work)
        throughput = total_useful_work / simulation_cycles
        
        return {
            'total_faults': total_faults,
            'total_work': total_useful_work,
            'fault_rate': fault_rate,
            'throughput': throughput,
            'processes_running': actual_running,
            'processes_suspended': suspended
        }
 
 
def compare_approaches():
    """
    Compare thrashing behavior with and without WSS management.
    """
    print("=" * 60)
    print("THRASHING PREVENTION COMPARISON")
    print("=" * 60)
    
    # Scenario: 100 frames total, 10 processes each needing 20 frames
    # Total demand: 200 frames, only 100 available -> overcommitted
    
    demo = ThrashingDemonstrator(
        total_memory=100,
        num_processes=10,
        wss_per_process=20
    )
    
    print(f"
Scenario:")
    print(f"  Total memory: 100 frames")
    print(f"  Number of processes: 10")
    print(f"  WSS per process: 20 frames")
    print(f"  Total demand: 200 frames (2x overcommitted)")
    
    without_wss = demo.simulate_without_wss(100)
    with_wss = demo.simulate_with_wss(100)
    
    print("
" + "=" * 60)
    print("RESULTS COMPARISON")
    print("=" * 60)
    
    print("
Without WSS Management:")
    print(f"  Processes running: {without_wss['processes_running']}")
    print(f"  Page fault rate: {without_wss['fault_rate']:.1%}")
    print(f"  Throughput: {without_wss['throughput']:.0f} ops/cycle")
    
    print("
With WSS Management:")
    print(f"  Processes running: {with_wss['processes_running']}")
    print(f"  Processes suspended: {with_wss.get('processes_suspended', 0)}")
    print(f"  Page fault rate: {with_wss['fault_rate']:.1%}")
    print(f"  Throughput: {with_wss['throughput']:.0f} ops/cycle")
    
    print("
Analysis:")
    throughput_ratio = with_wss['throughput'] / without_wss['throughput']
    print(f"  WSS management provides {throughput_ratio:.1f}x throughput")
    print(f"  Fault rate reduced from {without_wss['fault_rate']:.1%} to {with_wss['fault_rate']:.1%}")
    
    if with_wss['throughput'] > without_wss['throughput']:
        print("
  ✓ Running fewer processes with adequate memory")
        print("    is BETTER than running all processes with inadequate memory")
 
if __name__ == "__main__":
    compare_approaches()

Load Control and Admission Decisions

The working set model naturally integrates with load control—managing how many processes can run concurrently based on available resources. Load Control Mechanisms: 1. Admission Control: When a new process is created or wants to run: Estimate its WSS (from history, process type, or initial value) Check if Σ WSS + new_WSS \leq available memory If yes: admit; if no: queue until memory available 2. Degree of Multiprogramming: The number of running processes is dynamically bounded: Maximum MPL = available_memory / average_WSS Actual MPL varies as process WSS values change System self-adjusts to maintain stability 3. Suspension Priority: When suspension is needed, choose victim by: Lowest priority Largest WSS (frees most memory) Most recently admitted (fairness) Least work completed (minimize wasted progress)

When to Increase MPL

•Process completes and frees frames
•Running process's WSS decreases
•Additional physical memory available
•Suspended process no longer needed
•Low page fault rate indicates headroom

When to Decrease MPL

•Total WSS exceeds available memory
•Running process's WSS increases
•Page fault rate exceeds threshold
•CPU utilization drops due to paging
•Memory pressure from kernel/buffers

The Balance Set Manager

Windows uses a 'Balance Set Manager' that periodically evaluates system memory state and adjusts process working sets. When memory is plentiful, processes are allowed to grow their working sets. When memory is tight, working sets are trimmed and processes may be suspended. This provides the load control functionality without exact WSS tracking.

Medium-Term Scheduling Integration: Load control connects to the medium-term scheduler (swapper): Swap-out decision: When memory is tight, select process(es) to swap out entirely (all pages removed from memory) WSS guides selection: Processes with largest WSS are good swap-out candidates (free most memory) Swap-in decision: When memory becomes available, select process(es) to bring back WSS predicts cost: Swapping in a process with large WSS requires loading many pages The working set model provides the information needed for intelligent medium-term scheduling: which processes to suspend and what the cost of resuming them will be.

Modern Approximations to Working Set Policy

Pure working set allocation as described by Denning is rarely implemented exactly. Modern systems use approximations that capture the essential benefits with lower overhead. Linux's Approximate Approach: Linux doesn't track explicit working sets but achieves similar effects: Active/Inactive Lists: Approximate recency tracking kswapd: Background daemon reclaims memory proactively Watermarks: Trigger reclaim before memory exhaustion OOM Killer: Last resort when memory truly exhausted Cgroups: Allow explicit memory limits per process group The Result: Linux behaves somewhat like a working set system without explicit WSS tracking.

Linux Memory Management vs Pure Working Set
Aspect	Linux Approach	Pure Working Set
Recency tracking	Active/Inactive lists	Explicit window Δ
Allocation basis	Demand + limits	WSS per process
Overcommit handling	OOM killer	Process suspension
Thrashing response	Reactive (detect)	Proactive (prevent)
Memory limits	Optional (cgroups)	Implicit (WSS-based)

Page Fault Frequency (PFF) as Alternative: Many systems use PFF as a simpler alternative to working set tracking: Monitor: Page fault rate for each process If fault rate too high: Allocate more frames If fault rate very low: Reclaim some frames Converges to: Allocation approximating WSS PFF is reactive rather than proactive but achieves similar steady-state behavior with lower implementation complexity. Container-Era Considerations: Modern containerized environments add new dimensions: Memory limits per container: Explicit bounds (like mini-working-sets) Memory QoS: Guaranteed minimum, burstable maximum Pressure propagation: Containers can signal memory pressure Kill policies: Which container to terminate when limits hit These mechanisms approximate working set principles at the container level rather than process level.

pff_alternative.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
# Page Fault Frequency (PFF) as WSS Alternative
 
from dataclasses import dataclass
from typing import Dict
 
@dataclass
class ProcessPFF:
    """Per-process PFF tracking state."""
    pid: int
    allocated_frames: int = 10  # Starting allocation
    page_faults: int = 0
    time_elapsed: int = 0
    fault_rate: float = 0.0
 
class PFFAllocator:
    """
    Page Fault Frequency Based Allocator
    
    Adjusts allocation based on observed fault rate rather than
    explicit WSS tracking. Simpler but reactive rather than proactive.
    """
    
    def __init__(self, total_frames: int):
        self.total_frames = total_frames
        self.free_frames = total_frames
        self.processes: Dict[int, ProcessPFF] = {}
        
        # Tuning parameters
        self.upper_threshold = 0.05   # Above this: need more frames
        self.lower_threshold = 0.01   # Below this: can give up frames
        self.adjustment_interval = 100  # Evaluate every N time units
        
    def add_process(self, pid: int, initial_frames: int = 10):
        """Add a new process with initial frame allocation."""
        if self._can_allocate(initial_frames):
            self.processes[pid] = ProcessPFF(
                pid=pid,
                allocated_frames=initial_frames
            )
            self.free_frames -= initial_frames
            return True
        return False
    
    def _can_allocate(self, frames: int) -> bool:
        return self.free_frames >= frames
    
    def record_page_fault(self, pid: int):
        """Record a page fault for a process."""
        if pid in self.processes:
            self.processes[pid].page_faults += 1
    
    def time_tick(self, pid: int):
        """Record time passing for a process."""
        if pid not in self.processes:
            return
            
        proc = self.processes[pid]
        proc.time_elapsed += 1
        
        # Evaluate allocation periodically
        if proc.time_elapsed % self.adjustment_interval == 0:
            self._evaluate_allocation(proc)
    
    def _evaluate_allocation(self, proc: ProcessPFF):
        """
        Evaluate and adjust allocation based on fault rate.
        
        This is the core PFF logic:
        - High fault rate -> allocate more frames
        - Low fault rate -> reclaim frames
        """
        interval = self.adjustment_interval
        faults_in_interval = proc.page_faults  # Simplified: total faults
        
        # Compute fault rate (faults per time unit)
        proc.fault_rate = proc.page_faults / proc.time_elapsed if proc.time_elapsed > 0 else 0
        
        print(f"PID {proc.pid}: fault_rate={proc.fault_rate:.4f}, allocated={proc.allocated_frames}")
        
        if proc.fault_rate > self.upper_threshold:
            # Fault rate too high: process needs more memory
            frames_to_add = min(5, self.free_frames)  # Add up to 5 frames
            if frames_to_add > 0:
                proc.allocated_frames += frames_to_add
                self.free_frames -= frames_to_add
                print(f"  → Increased allocation by {frames_to_add}")
                
        elif proc.fault_rate < self.lower_threshold:
            # Fault rate very low: process has excess allocation
            frames_to_reclaim = min(2, proc.allocated_frames - 5)  # Keep minimum 5
            if frames_to_reclaim > 0:
                proc.allocated_frames -= frames_to_reclaim
                self.free_frames += frames_to_reclaim
                print(f"  → Reclaimed {frames_to_reclaim} frames")
        
        # Reset fault counter for next interval
        proc.page_faults = 0
    
    def get_allocations(self) -> Dict[int, int]:
        """Get current frame allocations."""
        return {pid: p.allocated_frames for pid, p in self.processes.items()}
 
 
def demonstrate_pff():
    """Demonstrate PFF-based allocation."""
    print("Page Fault Frequency (PFF) Allocation")
    print("=" * 60)
    
    allocator = PFFAllocator(total_frames=200)
    
    # Add processes
    allocator.add_process(1, initial_frames=20)
    allocator.add_process(2, initial_frames=20)
    allocator.add_process(3, initial_frames=20)
    
    # Simulate varying fault rates
    print("
Simulating execution...")
    
    import random
    
    for t in range(500):
        for pid in [1, 2, 3]:
            allocator.time_tick(pid)
            
            # Different fault rates for different processes
            if pid == 1:
                fault_prob = 0.08  # High fault rate - needs more memory
            elif pid == 2:
                fault_prob = 0.005  # Low fault rate - has excess
            else:
                fault_prob = 0.02  # Normal
            
            if random.random() < fault_prob:
                allocator.record_page_fault(pid)
    
    print("
Final Allocations:")
    for pid, frames in allocator.get_allocations().items():
        print(f"  PID {pid}: {frames} frames")
    
    print("
Key insight: PFF converges to allocation proportional to WSS")
    print("without explicitly tracking the working set!")
 
if __name__ == "__main__":
    demonstrate_pff()

WSS vs PFF: Complementary Approaches

Working set and PFF approaches are not mutually exclusive. Working set is proactive (predicts needs from behavior), while PFF is reactive (adjusts based on faults). A combined approach might use WSS for admission control and PFF for fine-tuning within-process allocation. Many systems implicitly use both principles.

Putting It All Together

Let's consolidate everything we've learned about the working set model into a coherent view of how it enables intelligent memory management. The Complete Working Set Memory Management System: Layer 1: Observation Track page references for each process Maintain working set estimates (via reference bit aging, active/inactive lists, or sampling) Monitor WSS trends over time Layer 2: Analysis Compute total system WSS demand Compare against available memory Identify overcommitment risk Detect phase transitions in processes Layer 3: Decision Admission control for new processes Suspension decisions when overcommitted Resumption decisions when memory available Per-process allocation adjustments Layer 4: Action Allocate/deallocate frames Trigger page-in for newly allocated frames Initiate swap-out for suspended processes Update page tables and TLBs

Design Decisions Summary:

Design Choice	Options	Trade-off
Window size Δ	Fixed vs Adaptive	Simplicity vs Optimality
WSS tracking	Exact vs Sampled	Accuracy vs Overhead
Suspension victim	Largest WSS vs Lowest Priority	Memory vs Fairness
Allocation granularity	Per-page vs Per-quantum	Precision vs Overhead
Overcommit tolerance	None vs Limited	Safety vs Utilization

Best Practices for Implementation: Use efficient data structures: Active/inactive lists with O(1) operations Batch updates: Update WSS estimates periodically, not on every access Smooth adjustments: Avoid oscillation by damping allocation changes Monitor metrics: Track page fault rates, CPU utilization, suspension frequency Provide visibility: Allow administrators to see WSS and allocation status

Key Implementation Insights

•Approximate is good enough: Don't over-engineer WSS tracking; approximate values serve allocation decisions well
•Proactive beats reactive: Detecting overcommitment before thrashing is far better than recovering after
•Suspension isn't failure: Temporarily suspending a process protects all other processes' performance
•Combine techniques: Use WSS for load control, PFF for fine-tuning, and whatever else helps
•Monitor continuously: Memory requirements change; tracking must be ongoing, not one-time

Summary: The Working Set Model Complete

We've now completed our deep dive into the working set model—from its theoretical foundation in the principle of locality to its practical implementation in modern operating systems.

Module Summary: Key Concepts

•Locality Principle: Programs access memory predictably; temporal and spatial locality enable prediction
•Working Set Definition: W(t, Δ) = pages accessed in interval [t-Δ, t]; formalizes 'memory in active use'
•Window Parameter Δ: Controls trade-off between memory consumption and page fault rate
•WSS Tracking: Reference bit aging, active/inactive lists, hardware counters, and sampling provide practical approximations
•WSS-Based Allocation: Allocate frames equal to WSS; suspend when overcommitted; prevents thrashing proactively

Module Complete

You have mastered the working set model for memory management. You understand why it works (locality), how it's defined (W(t, Δ)), how to tune it (window selection), how to measure it (WSS tracking), and how to use it (WSS-based allocation). This knowledge enables you to reason about memory management in any operating system and design effective allocation policies.

Connecting to Broader Context: The working set model is part of a broader family of memory management techniques: Next topic: Thrashing Solutions explores additional techniques beyond working set management Related: Page Fault Frequency (PFF) provides a reactive alternative to proactive WSS Integration: Working set concepts apply to caching, database buffer pools, and distributed systems The principles you've learned here—understanding demand, tracking usage, preventing overcommitment, and making proactive decisions—apply far beyond operating system memory management. They're fundamental to any resource allocation problem where demand varies and resources are limited.

Allocation Based on WSS

Closing the Loop: From Measurement to Action

The Working Set Allocation Policy

Implementing WSS-Based Allocation

Thrashing Prevention Through WSS

Load Control and Admission Decisions

Modern Approximations to Working Set Policy

Putting It All Together

Summary: The Working Set Model Complete

There’s more to understand.

Allocation Based on WSS

Closing the Loop: From Measurement to Action

The Working Set Allocation Policy

Implementing WSS-Based Allocation

Thrashing Prevention Through WSS

Load Control and Admission Decisions

Modern Approximations to Working Set Policy

Putting It All Together

Summary: The Working Set Model Complete

There’s more to understand.