Working Set Model

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

# 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("\n" + "=" * 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("\nSuspended/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"\n--- 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()

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

# 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("\nSimulation: 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("\nSimulation: 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"\nScenario:")
    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("\n" + "=" * 60)
    print("RESULTS COMPARISON")
    print("=" * 60)
    
    print("\nWithout 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("\nWith 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("\nAnalysis:")
    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("\n  ✓ Running fewer processes with adequate memory")
        print("    is BETTER than running all processes with inadequate memory")
 
if __name__ == "__main__":
    compare_approaches()

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

# 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("\nSimulating 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("\nFinal Allocations:")
    for pid, frames in allocator.get_allocations().items():
        print(f"  PID {pid}: {frames} frames")
    
    print("\nKey insight: PFF converges to allocation proportional to WSS")
    print("without explicitly tracking the working set!")
 
if __name__ == "__main__":
    demonstrate_pff()