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

# Demonstration of how window size affects working set behavior
 
class WorkingSetTracker:
    """
    Track working set over time with configurable window.
    
    Key insight: Same access trace produces different working sets
    depending on the window parameter Δ.
    """
    
    def __init__(self, delta):
        self.delta = delta
        self.access_history = []  # All page accesses: [(time, page), ...]
        self.current_time = 0
        
    def access_page(self, page):
        """Record a page access."""
        self.access_history.append((self.current_time, page))
        self.current_time += 1
        
    def get_working_set(self, at_time=None):
        """
        Compute W(t, Δ) - the working set at specified time.
        
        W(t, Δ) = {p : page p accessed in interval [t-Δ, t]}
        """
        if at_time is None:
            at_time = self.current_time - 1
            
        window_start = at_time - self.delta
        
        # Collect all distinct pages accessed in window
        working_set = set()
        for access_time, page in self.access_history:
            if window_start <= access_time <= at_time:
                working_set.add(page)
                
        return working_set
    
    def get_wss(self, at_time=None):
        """Get Working Set Size = |W(t, Δ)|"""
        return len(self.get_working_set(at_time))
 
 
def demonstrate_window_effects():
    """
    Show how the same access pattern produces different working sets
    with different window sizes.
    """
    # Simulate a process with two phases:
    # Phase 1 (time 0-49): Access pages 0-4 in a loop
    # Phase 2 (time 50-99): Access pages 5-9 in a loop
    
    access_trace = []
    
    # Phase 1: pages 0-4
    for _ in range(10):  # 10 cycles through pages 0-4
        for p in range(5):
            access_trace.append(p)  # 50 accesses total
    
    # Phase 2: pages 5-9
    for _ in range(10):  # 10 cycles through pages 5-9  
        for p in range(5, 10):
            access_trace.append(p)  # 50 accesses total
    
    # Test different window sizes
    print("Working Set Analysis with Different Window Sizes")
    print("=" * 60)
    print()
    print("Trace: Phase 1 (t=0-49): pages 0-4, Phase 2 (t=50-99): pages 5-9")
    print()
    
    for delta in [10, 25, 50, 75, 100]:
        tracker = WorkingSetTracker(delta=delta)
        
        for page in access_trace:
            tracker.access_page(page)
        
        # Measure working set at different times
        print(f"Window Δ = {delta}:")
        
        # At time 25 (middle of phase 1)
        ws_25 = tracker.get_working_set(at_time=25)
        print(f"  t=25 (Phase 1): W(25,{delta}) = {sorted(ws_25)}, WSS = {len(ws_25)}")
        
        # At time 75 (middle of phase 2)
        ws_75 = tracker.get_working_set(at_time=75)
        print(f"  t=75 (Phase 2): W(75,{delta}) = {sorted(ws_75)}, WSS = {len(ws_75)}")
        
        # At time 60 (just after phase transition)
        ws_60 = tracker.get_working_set(at_time=60)
        print(f"  t=60 (Transition): W(60,{delta}) = {sorted(ws_60)}, WSS = {len(ws_60)}")
        print()
    
    print("Observations:")
    print("- Small Δ (10): Only sees current phase, quick adaptation")
    print("- Medium Δ (50): Exactly captures one phase")
    print("- Large Δ (75+): Working set includes pages from BOTH phases")
    print("- At transitions: Larger Δ means more 'carry-over' from old phase")
 
# Example output:
# Window Δ = 10:
#   t=25: W(25,10) = [0, 1, 2, 3, 4], WSS = 5
#   t=75: W(75,10) = [5, 6, 7, 8, 9], WSS = 5
#   t=60: W(60,10) = [5, 6, 7, 8, 9], WSS = 5  ← Quick adaptation
#
# Window Δ = 75:
#   t=25: W(25,75) = [0, 1, 2, 3, 4], WSS = 5
#   t=75: W(75,75) = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9], WSS = 10
#   t=60: W(60,75) = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9], WSS = 10  ← Old pages linger

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

# Demonstrating mathematical properties of working sets
 
class WorkingSetMathProperties:
    """
    Verify and demonstrate mathematical properties of working sets.
    """
    
    def __init__(self, access_trace):
        """Initialize with a trace of page accesses."""
        self.trace = access_trace
        self.total_pages = len(set(access_trace))
        
    def compute_working_set(self, t, delta):
        """
        Compute W(t, Δ).
        
        Returns set of pages accessed in [t-Δ, t].
        """
        window_start = max(0, t - delta)
        return set(self.trace[window_start:t+1])
    
    def verify_monotonicity(self, t):
        """
        Verify Property 1: W(t, Δ₁) ⊆ W(t, Δ₂) when Δ₁ ≤ Δ₂
        """
        print(f"
Property 1: Monotonicity at t={t}")
        print("-" * 50)
        
        prev_ws = set()
        for delta in range(1, min(t+2, 20)):
            ws = self.compute_working_set(t, delta)
            
            # Verify subset property
            if not prev_ws.issubset(ws):
                print(f"  VIOLATION at Δ={delta}")
                return False
            
            print(f"  Δ={delta:2d}: |W| = {len(ws):2d}, W = {sorted(ws)}")
            prev_ws = ws
        
        print("  ✓ Monotonicity verified: larger Δ ⊇ smaller Δ")
        return True
    
    def verify_bounded_size(self, t):
        """
        Verify Property 2: 1 ≤ |W(t, Δ)| ≤ min(P, Δ)
        """
        print(f"
Property 2: Bounded Size (P={self.total_pages})")
        print("-" * 50)
        
        for delta in [5, 10, 20, 50, 100]:
            ws = self.compute_working_set(t, delta)
            wss = len(ws)
            
            upper_bound = min(self.total_pages, delta)
            lower_bound = 1
            
            valid = lower_bound <= wss <= upper_bound
            status = "✓" if valid else "✗"
            
            print(f"  Δ={delta:3d}: |W| = {wss:2d}, bound = [{lower_bound}, {upper_bound}] {status}")
        
        return True
    
    def demonstrate_transition_behavior(self):
        """
        Demonstrate Property 3: Working set during phase transitions
        contains pages from both old and new phases.
        """
        print("
Property 3: Transition Behavior")
        print("-" * 50)
        
        # Create trace with distinct phases
        # Phase 1 (t=0-99): pages 0-9
        # Phase 2 (t=100-199): pages 10-19
        phase1 = [i % 10 for i in range(100)]
        phase2 = [10 + (i % 10) for i in range(100)]
        trace = phase1 + phase2
        
        analyzer = WorkingSetMathProperties(trace)
        
        # Examine working set at transition points
        for t in [90, 100, 110, 120, 150]:
            ws = analyzer.compute_working_set(t, delta=30)
            
            old_pages = set(range(10)).intersection(ws)
            new_pages = set(range(10, 20)).intersection(ws)
            
            print(f"  t={t:3d}: old_phase={sorted(old_pages)}, new_phase={sorted(new_pages)}")
        
        print("  During transition, working set includes BOTH phases")
        print("  Old pages gradually age out as time advances")
        
    def analyze_miss_curve(self):
        """
        Demonstrate Property 5: Diminishing returns of additional memory.
        """
        print("
Property 5: Convexity of Miss Rate Function")
        print("-" * 50)
        
        test_point = len(self.trace) - 1
        prev_wss = 0
        prev_marginal = float('inf')
        
        print("  Memory | WSS | Marginal Benefit")
        print("  " + "-" * 35)
        
        for delta in [10, 20, 50, 100, 200, 500]:
            ws = self.compute_working_set(test_point, delta)
            wss = len(ws)
            
            # Marginal benefit = pages gained per unit of additional window
            if delta > 10:
                marginal = (wss - prev_wss) / (delta - 10)
            else:
                marginal = wss / delta
                
            print(f"  Δ={delta:3d}  | {wss:3d} | {marginal:.4f} pages/ref")
            
            prev_wss = wss
            prev_marginal = marginal
 
 
# Example usage with sample trace
def demonstrate_properties():
    # Create varied access trace
    trace = []
    
    # Looping phase
    for _ in range(50):
        trace.extend([0, 1, 2, 3, 4])
    
    # Scattered phase
    import random
    random.seed(42)
    for _ in range(100):
        trace.append(random.randint(0, 20))
    
    analyzer = WorkingSetMathProperties(trace)
    
    # Verify properties
    analyzer.verify_monotonicity(t=200)
    analyzer.verify_bounded_size(t=200)
    analyzer.demonstrate_transition_behavior()
    analyzer.analyze_miss_curve()

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

# Practical working set tracking implementations
 
from collections import defaultdict
import time
 
class ExactWorkingSetTracker:
    """
    Exact working set tracking (expensive, for analysis only).
    
    Maintains complete history of page references and computes
    W(t, Δ) precisely on demand.
    """
    
    def __init__(self, delta):
        self.delta = delta
        self.reference_history = []  # [(time, page), ...]
        self.reference_count = 0
        
    def record_reference(self, page):
        """Record a page reference. O(1) per reference."""
        self.reference_history.append((self.reference_count, page))
        self.reference_count += 1
        
    def get_working_set(self):
        """Compute exact W(t, Δ). O(Δ) per query."""
        current = self.reference_count - 1
        window_start = max(0, current - self.delta)
        
        working_set = set()
        for ref_time, page in self.reference_history[-self.delta:]:
            working_set.add(page)
            
        return working_set
 
 
class TimerBasedWorkingSetTracker:
    """
    Timer-based working set approximation (practical).
    
    Uses periodic timer interrupts to sample reference bits.
    This is similar to how real OS kernels track working sets.
    """
    
    def __init__(self, num_pages, window_intervals=10):
        self.num_pages = num_pages
        self.window_intervals = window_intervals  # Δ in timer intervals
        
        # Reference bit for each page (set by hardware on access)
        self.reference_bit = [False] * num_pages
        
        # Age bits: bitmap showing which intervals page was accessed
        # Bit 0 = current interval, bit N = N intervals ago
        self.age_bits = [0] * num_pages
        
        self.current_interval = 0
        
    def access_page(self, page):
        """
        Simulate a page access (in real OS, hardware sets this).
        """
        self.reference_bit[page] = True
        
    def timer_interrupt(self):
        """
        Called on timer interrupt to update working set tracking.
        
        This is O(num_pages) but done only periodically (e.g., 100Hz),
        so amortized overhead is low.
        """
        for page in range(self.num_pages):
            # Shift age bits right (age all references by one interval)
            self.age_bits[page] = self.age_bits[page] >> 1
            
            # Add current reference bit as most significant
            if self.reference_bit[page]:
                self.age_bits[page] |= (1 << (self.window_intervals - 1))
                
            # Clear reference bit for next interval
            self.reference_bit[page] = False
            
        self.current_interval += 1
        
    def get_working_set(self):
        """
        Return approximate working set.
        
        A page is in working set if ANY bit is set in age_bits,
        meaning it was accessed in one of the last window_intervals.
        """
        working_set = set()
        for page in range(self.num_pages):
            if self.age_bits[page] > 0:
                working_set.add(page)
        return working_set
    
    def get_working_set_size(self):
        """Return WSS = |W(t, Δ)|"""
        return len(self.get_working_set())
    
    def is_in_working_set(self, page):
        """Check if specific page is in working set. O(1)."""
        return self.age_bits[page] > 0
 
 
class ReferenceCountTracker:
    """
    Counter-based working set tracking.
    
    Each page has a counter that's incremented on access
    and decremented on timer interrupts. Pages with counter > 0
    are in the working set.
    """
    
    def __init__(self, num_pages, max_count=10):
        self.num_pages = num_pages
        self.max_count = max_count  # Maximum counter value (= window intervals)
        
        # Counter per page: higher = more recently/frequently used
        self.counters = [0] * num_pages
        self.reference_bit = [False] * num_pages
        
    def access_page(self, page):
        """Record page access."""
        self.reference_bit[page] = True
        
    def timer_interrupt(self):
        """
        Update counters on timer interrupt.
        
        Referenced pages: boost counter (capped at max)
        Unreferenced pages: decrement counter toward zero
        """
        for page in range(self.num_pages):
            if self.reference_bit[page]:
                # Page was accessed: boost counter
                self.counters[page] = min(self.counters[page] + 1, self.max_count)
            else:
                # Page not accessed: decay counter
                self.counters[page] = max(self.counters[page] - 1, 0)
                
            self.reference_bit[page] = False
            
    def get_working_set(self):
        """Pages with counter > 0 are in working set."""
        return {p for p in range(self.num_pages) if self.counters[p] > 0}
    
    def get_page_age(self, page):
        """
        Get relative age of page.
        Higher counter = more recently used = younger.
        """
        return self.max_count - self.counters[page]
 
 
# Demonstration
def compare_tracking_methods():
    print("Comparing Working Set Tracking Methods")
    print("=" * 60)
    
    num_pages = 20
    
    # Create access pattern: phases with locality
    accesses = []
    for _ in range(100):
        accesses.extend([0, 1, 2, 3, 4])  # Hot set 1
    for _ in range(50):
        accesses.extend([10, 11, 12, 13, 14])  # Hot set 2
    for _ in range(100):
        accesses.extend([0, 1, 2, 3, 4])  # Back to hot set 1
    
    # Test timer-based tracker
    timer_tracker = TimerBasedWorkingSetTracker(num_pages, window_intervals=8)
    
    for i, page in enumerate(accesses):
        timer_tracker.access_page(page)
        if i % 50 == 49:  # "Timer interrupt" every 50 accesses
            timer_tracker.timer_interrupt()
            ws = timer_tracker.get_working_set()
            print(f"After {i+1} accesses: WS = {sorted(ws)}, WSS = {len(ws)}")

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

# Simulating and visualizing WSS dynamics over time
 
import random
 
class WSSSimulator:
    """
    Simulate realistic WSS dynamics for a multi-phase process.
    """
    
    def __init__(self, delta):
        self.delta = delta
        self.history = []  # Page access trace
        self.time = 0
        
    def simulate_phase(self, duration, hot_pages, access_dist='uniform'):
        """
        Simulate a phase with given characteristics.
        
        Args:
            duration: Number of references in this phase
            hot_pages: List of pages that are "hot" in this phase
            access_dist: 'uniform' or 'skewed' access pattern
        """
        for _ in range(duration):
            if access_dist == 'uniform':
                page = random.choice(hot_pages)
            elif access_dist == 'skewed':
                # 80% to first half, 20% to second half (80-20 rule)
                if random.random() < 0.8:
                    page = random.choice(hot_pages[:len(hot_pages)//2])
                else:
                    page = random.choice(hot_pages[len(hot_pages)//2:])
            else:
                page = random.choice(hot_pages)
                
            self.history.append(page)
            self.time += 1
            
    def compute_wss_over_time(self):
        """
        Compute WSS at each point in time.
        Returns list of (time, wss) tuples.
        """
        wss_trace = []
        for t in range(len(self.history)):
            window_start = max(0, t - self.delta)
            ws = set(self.history[window_start:t+1])
            wss_trace.append((t, len(ws)))
        return wss_trace
    
    def compute_wss_statistics(self):
        """
        Compute statistics about WSS behavior.
        """
        wss_trace = self.compute_wss_over_time()
        wss_values = [wss for _, wss in wss_trace]
        
        return {
            'min_wss': min(wss_values),
            'max_wss': max(wss_values),
            'avg_wss': sum(wss_values) / len(wss_values),
            'wss_variance': sum((w - sum(wss_values)/len(wss_values))**2 for w in wss_values) / len(wss_values),
        }
 
 
def simulate_multi_phase_process():
    """
    Simulate a realistic multi-phase process and analyze WSS dynamics.
    """
    print("Simulating Multi-Phase Process WSS Dynamics")
    print("=" * 60)
    
    sim = WSSSimulator(delta=100)
    
    # Phase 1: Initialization (growing WSS)
    print("Phase 1: Initialization (pages 0-9, building up)")
    for i in range(10):
        sim.simulate_phase(50, list(range(i+1)))  # Gradually add pages
    
    # Phase 2: Stable computation (steady WSS)
    print("Phase 2: Steady-state computation (pages 0-9)")
    sim.simulate_phase(500, list(range(10)))
    
    # Phase 3: Transition to new task (WSS spike)
    print("Phase 3: Task transition (pages 0-9 + 20-29)")
    sim.simulate_phase(100, list(range(10)) + list(range(20, 30)))
    
    # Phase 4: New steady state (different WSS)
    print("Phase 4: New steady-state (pages 20-24)")
    sim.simulate_phase(400, list(range(20, 25)))
    
    # Phase 5: Cleanup (declining WSS)  
    print("Phase 5: Cleanup (pages 20-22)")
    sim.simulate_phase(200, list(range(20, 23)))
    
    # Analyze WSS dynamics
    wss_trace = sim.compute_wss_over_time()
    stats = sim.compute_wss_statistics()
    
    print()
    print("WSS Statistics:")
    print(f"  Minimum WSS: {stats['min_wss']}")
    print(f"  Maximum WSS: {stats['max_wss']}")  
    print(f"  Average WSS: {stats['avg_wss']:.1f}")
    print(f"  WSS Variance: {stats['wss_variance']:.1f}")
    print()
    
    # Sample key points
    print("WSS at Key Points:")
    key_points = [100, 500, 700, 1000, 1400]
    for t in key_points:
        if t < len(wss_trace):
            _, wss = wss_trace[t]
            print(f"  t={t:4d}: WSS={wss:2d}")
    
    # Phase identification heuristic
    print()
    print("Detected Phases (WSS changes > 20%):")
    prev_wss = wss_trace[0][1]
    for t, wss in wss_trace[::100]:  # Sample every 100 references
        if abs(wss - prev_wss) / max(prev_wss, 1) > 0.2:
            change = "↑" if wss > prev_wss else "↓"
            print(f"  t={t}: WSS {prev_wss} → {wss} ({change})")
        prev_wss = wss
 
# Example output visualization concept:
# 
# WSS │     ****                               
#     │    *    *                              
#  15 ├   *      *                             
#     │  *        *        ******              
#  10 ├ *          ********      ****          
#     │*                              ****     
#   5 ├                                    *** 
#     │                                        
#   0 └────────────────────────────────────────
#       0    500    1000   1500   2000  Time
#       └─Init─┴─Steady──┴─Trans─┴─New─┴Cleanup

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

# Working set-based frame allocation and admission control
 
class WorkingSetAllocator:
    """
    Frame allocator using working set policy.
    
    Implements Denning's key insight: allocate to each process
    its working set size, and control multiprogramming to ensure
    all active processes' working sets can be satisfied.
    """
    
    def __init__(self, total_frames, delta):
        self.total_frames = total_frames
        self.delta = delta
        
        # Per-process state
        self.processes = {}  # pid -> ProcessState
        self.active_processes = set()
        self.suspended_processes = set()
        
    def add_process(self, pid, initial_wss=1):
        """Add a new process to the system."""
        self.processes[pid] = {
            'wss': initial_wss,
            'allocated_frames': 0,
            'history': [],
        }
        self.try_activate_process(pid)
        
    def update_working_set(self, pid, new_wss):
        """
        Update process's working set size.
        
        Called when WSS tracking detects a change.
        May trigger reallocation or process suspension.
        """
        if pid not in self.processes:
            return
            
        old_wss = self.processes[pid]['wss']
        self.processes[pid]['wss'] = new_wss
        
        # Check if system is overcommitted
        self._rebalance_allocation()
        
    def _total_active_wss(self):
        """Sum of working set sizes for all active processes."""
        return sum(
            self.processes[pid]['wss']
            for pid in self.active_processes
        )
        
    def _rebalance_allocation(self):
        """
        Rebalance frame allocation to maintain working set policy.
        
        Key principle: Active processes MUST have their working sets
        fully resident. If this is impossible, suspend processes.
        """
        total_demand = self._total_active_wss()
        
        while total_demand > self.total_frames and self.active_processes:
            # Overcommitted: must suspend a process
            # Choose victim (here: largest WSS, but policies vary)
            victim = max(
                self.active_processes,
                key=lambda p: self.processes[p]['wss']
            )
            self._suspend_process(victim)
            total_demand = self._total_active_wss()
            
        # Allocate frames to remaining active processes
        for pid in self.active_processes:
            self.processes[pid]['allocated_frames'] = self.processes[pid]['wss']
            
        # Try to resume suspended processes if space available
        self._try_resume_suspended()
        
    def _suspend_process(self, pid):
        """Suspend a process (swap out its pages)."""
        if pid in self.active_processes:
            self.active_processes.remove(pid)
            self.suspended_processes.add(pid)
            self.processes[pid]['allocated_frames'] = 0
            print(f"Suspending process {pid} (WSS={self.processes[pid]['wss']})")
            
    def _try_resume_suspended(self):
        """Try to resume suspended processes if memory available."""
        available = self.total_frames - self._total_active_wss()
        
        for pid in list(self.suspended_processes):
            wss = self.processes[pid]['wss']
            if wss <= available:
                self.suspended_processes.remove(pid)
                self.active_processes.add(pid)
                self.processes[pid]['allocated_frames'] = wss
                available -= wss
                print(f"Resuming process {pid} (WSS={wss})")
                
    def try_activate_process(self, pid):
        """Try to activate a new process."""
        wss = self.processes[pid]['wss']
        available = self.total_frames - self._total_active_wss()
        
        if wss <= available:
            self.active_processes.add(pid)
            self.processes[pid]['allocated_frames'] = wss
            print(f"Activated process {pid} (WSS={wss})")
        else:
            self.suspended_processes.add(pid)
            print(f"Process {pid} suspended on creation (insufficient memory)")
            
    def get_multiprogramming_level(self):
        """Current number of active processes."""
        return len(self.active_processes)
        
    def get_memory_utilization(self):
        """Fraction of frames currently allocated."""
        allocated = sum(
            self.processes[pid]['allocated_frames']
            for pid in self.active_processes
        )
        return allocated / self.total_frames
        
    def status_report(self):
        """Print current allocation status."""
        print("
" + "=" * 50)
        print("Working Set Allocator Status")
        print("=" * 50)
        print(f"Total frames: {self.total_frames}")
        print(f"Active processes: {len(self.active_processes)}")
        print(f"Suspended processes: {len(self.suspended_processes)}")
        print(f"Total active WSS: {self._total_active_wss()}")
        print(f"Memory utilization: {self.get_memory_utilization():.1%}")
        print()
        print("Active Processes:")
        for pid in self.active_processes:
            p = self.processes[pid]
            print(f"  PID {pid}: WSS={p['wss']}, allocated={p['allocated_frames']}")
        print("Suspended Processes:")
        for pid in self.suspended_processes:
            p = self.processes[pid]
            print(f"  PID {pid}: WSS={p['wss']} (waiting)")
        print()
 
 
# Demonstration
def demonstrate_ws_allocation():
    print("Working Set Allocation Demonstration")
    print("=" * 60)
    
    allocator = WorkingSetAllocator(total_frames=100, delta=1000)
    
    # Add processes with various working set sizes
    allocator.add_process(1, initial_wss=20)
    allocator.add_process(2, initial_wss=30)
    allocator.add_process(3, initial_wss=25)
    allocator.add_process(4, initial_wss=40)  # This might not fit
    
    allocator.status_report()
    
    # Process 1 enters a new phase with larger WSS
    print("
Process 1 enters memory-intensive phase...")
    allocator.update_working_set(1, 50)  # WSS grows from 20 to 50
    
    allocator.status_report()
    
    # Process 2 completes task, WSS shrinks
    print("
Process 2 completes task, WSS shrinks...")
    allocator.update_working_set(2, 10)
    
    allocator.status_report()