nodes/state.py¶
Part of You’re the OS.
1"""Pure-Python game-state model.
2
3Mirrors the upstream process state machine and its process/page accounting.
4No rendering, no SimVX imports, just the simulation: the render layer reads
5this through the public accessors below, once per frame.
6"""
7
8from __future__ import annotations
9
10import math
11import random
12from collections import deque
13from dataclasses import dataclass, field
14from enum import Enum, auto
15
16# ---------------------------------------------------------------- constants
17
18ONE_SECOND = 1000 # ms
19
20LAST_ALIVE_STARVATION_LEVEL = 5
21DEAD_STARVATION_LEVEL = 6
22
23# Stage layout: a fixed Normal-difficulty config.
24NUM_CPUS = 4
25NUM_PROCESS_SLOT_ROWS = 6
26NUM_PROCESS_SLOT_COLS = 7
27MAX_PROCESSES = NUM_PROCESS_SLOT_ROWS * NUM_PROCESS_SLOT_COLS # 42
28
29NUM_RAM_ROWS = 8
30NUM_DISK_ROWS = 3
31PAGES_PER_ROW = 16
32MAX_PAGES_PER_PROCESS = 4
33
34NUM_PROCESSES_AT_STARTUP = 14
35MAX_RAGEQUITS = 10 # max processes terminated by user before game over
36
37# Probabilities (per-second tick: same as upstream).
38NEW_PROCESS_PROBABILITY = 5 # 5%
39IO_PROBABILITY = 1 # 1%
40GRACEFUL_TERMINATION_PROBABILITY = 1 # 1%
41NEW_PAGE_PROBABILITY_DENOMINATOR = 20
42
43# Tunables
44PROCESS_HAPPINESS_MS = 5000 # time on CPU before starvation level resets to 0
45TIME_BETWEEN_STARVATION_LEVELS_MS = 5000
46
47SWAP_DELAY_MS = 100
48PARALLEL_SWAPS = 1
49
50IO_MIN_WAITING_TIME_MS = 1000
51IO_MAX_WAITING_TIME_MS = 5000
52
53
54# ------------------------------------------------------------------- enums
55
56
57class ProcessState(Enum):
58 IDLE = auto()
59 RUNNING = auto()
60 BLOCKED_ON_CPU_IO_REQUESTED = auto()
61 BLOCKED_ON_CPU_IO_AVAILABLE = auto()
62 BLOCKED_ON_CPU_PAGE_FAULT = auto()
63 BLOCKED_OFF_CPU_IO_REQUESTED = auto()
64 BLOCKED_OFF_CPU_IO_AVAILABLE = auto()
65 ENDED = auto()
66
67
68class StateEvent(Enum):
69 ASSIGN_TO_CPU = auto()
70 TERMINATE_FROM_STARVATION = auto()
71 REMOVE_FROM_CPU = auto()
72 REQUEST_IO = auto()
73 PAGE_FAULT = auto()
74 TERMINATE_GRACEFULLY = auto()
75 IO_AVAILABLE = auto()
76 IO_DELIVERED = auto()
77 PAGE_AVAILABLE = auto()
78
79
80_STATE_TRANSITIONS: dict[ProcessState, dict[StateEvent, ProcessState]] = {
81 ProcessState.IDLE: {
82 StateEvent.ASSIGN_TO_CPU: ProcessState.RUNNING,
83 StateEvent.TERMINATE_FROM_STARVATION: ProcessState.ENDED,
84 },
85 ProcessState.RUNNING: {
86 StateEvent.REMOVE_FROM_CPU: ProcessState.IDLE,
87 StateEvent.REQUEST_IO: ProcessState.BLOCKED_ON_CPU_IO_REQUESTED,
88 StateEvent.PAGE_FAULT: ProcessState.BLOCKED_ON_CPU_PAGE_FAULT,
89 StateEvent.TERMINATE_GRACEFULLY: ProcessState.ENDED,
90 },
91 ProcessState.BLOCKED_ON_CPU_IO_REQUESTED: {
92 StateEvent.IO_AVAILABLE: ProcessState.BLOCKED_ON_CPU_IO_AVAILABLE,
93 StateEvent.REMOVE_FROM_CPU: ProcessState.BLOCKED_OFF_CPU_IO_REQUESTED,
94 },
95 ProcessState.BLOCKED_ON_CPU_IO_AVAILABLE: {
96 StateEvent.IO_DELIVERED: ProcessState.RUNNING,
97 StateEvent.REMOVE_FROM_CPU: ProcessState.BLOCKED_OFF_CPU_IO_AVAILABLE,
98 StateEvent.TERMINATE_FROM_STARVATION: ProcessState.ENDED,
99 },
100 ProcessState.BLOCKED_ON_CPU_PAGE_FAULT: {
101 StateEvent.PAGE_AVAILABLE: ProcessState.RUNNING,
102 StateEvent.REMOVE_FROM_CPU: ProcessState.IDLE,
103 StateEvent.TERMINATE_FROM_STARVATION: ProcessState.ENDED,
104 },
105 ProcessState.BLOCKED_OFF_CPU_IO_REQUESTED: {
106 StateEvent.IO_AVAILABLE: ProcessState.BLOCKED_OFF_CPU_IO_AVAILABLE,
107 StateEvent.ASSIGN_TO_CPU: ProcessState.BLOCKED_ON_CPU_IO_REQUESTED,
108 },
109 ProcessState.BLOCKED_OFF_CPU_IO_AVAILABLE: {
110 StateEvent.IO_DELIVERED: ProcessState.IDLE,
111 StateEvent.ASSIGN_TO_CPU: ProcessState.BLOCKED_ON_CPU_IO_AVAILABLE,
112 StateEvent.TERMINATE_FROM_STARVATION: ProcessState.ENDED,
113 },
114}
115
116
117# ------------------------------------------------------------------- model
118
119
120@dataclass
121class Page:
122 pid: int
123 idx: int
124 on_disk: bool = False
125 in_use: bool = False
126 waiting_to_swap: bool = False
127 swap_started_at_ms: int | None = None
128 swap_progress: float = 0.0 # 0..1
129 # Slot indices into stage's flat ram_slots/disk_slots arrays.
130 swap_from_slot: int | None = None # index in current side
131 swap_to_slot: int | None = None # index in opposite side
132 swap_from_side: str | None = None # "ram" or "disk"
133
134 @property
135 def in_ram(self) -> bool:
136 return not self.on_disk
137
138 @property
139 def swap_in_progress(self) -> bool:
140 return self.swap_started_at_ms is not None
141
142 @property
143 def swap_requested(self) -> bool:
144 return self.waiting_to_swap or self.swap_in_progress
145
146 @property
147 def display_blink(self) -> bool:
148 return self.in_use and self.on_disk and not self.swap_in_progress
149
150
151@dataclass
152class IoEventWaiter:
153 waiting_since_ms: int
154 process: Process
155
156
157@dataclass
158class Process:
159 pid: int
160 state: ProcessState = ProcessState.IDLE
161 cpu_idx: int | None = None # None == not on cpu
162 starvation_level: int = 1
163 last_state_change_ms: int = 0
164 last_starvation_change_ms: int = 0
165 last_periodic_update_ms: int = 0
166 on_io_cooldown: bool = False
167 pages: list[Page] = field(default_factory=list)
168 # rendering target (the slot or cpu the process should glide toward)
169 target_x: float = 0.0
170 target_y: float = 0.0
171 pos_x: float = 0.0
172 pos_y: float = 0.0
173 slot_idx: int | None = None # idle slot index (0..41)
174 ragequit_slot_idx: int | None = None
175 blink_state: bool = False # for page-fault pulsing colour
176 # True until the render layer has parked the process at a start position.
177 # The model never assigns screen coordinates; it only says "this one is new".
178 needs_placement: bool = True
179
180 @property
181 def has_cpu(self) -> bool:
182 return self.cpu_idx is not None
183
184 @property
185 def is_waiting_for_io(self) -> bool:
186 return self.state in {
187 ProcessState.BLOCKED_ON_CPU_IO_REQUESTED,
188 ProcessState.BLOCKED_ON_CPU_IO_AVAILABLE,
189 ProcessState.BLOCKED_OFF_CPU_IO_REQUESTED,
190 ProcessState.BLOCKED_OFF_CPU_IO_AVAILABLE,
191 }
192
193 @property
194 def is_progressing_to_happiness(self) -> bool:
195 return self.state == ProcessState.RUNNING and self.starvation_level > 0
196
197 @property
198 def has_ended_gracefully(self) -> bool:
199 return self.state == ProcessState.ENDED and self.starvation_level == 0
200
201 def apply(self, event: StateEvent, current_time_ms: int) -> None:
202 transitions = _STATE_TRANSITIONS.get(self.state)
203 if not transitions or event not in transitions:
204 return
205 new_state = transitions[event]
206 if new_state != self.state:
207 self.state = new_state
208 self.last_state_change_ms = current_time_ms
209
210 def time_to_termination_ms(self, current_time_ms: int) -> float:
211 if self.starvation_level >= DEAD_STARVATION_LEVEL:
212 return 0
213 if self.state in {
214 ProcessState.RUNNING,
215 ProcessState.BLOCKED_ON_CPU_IO_REQUESTED,
216 ProcessState.BLOCKED_OFF_CPU_IO_REQUESTED,
217 } or (self.state == ProcessState.ENDED and self.starvation_level == 0):
218 return math.inf
219 remaining_levels = DEAD_STARVATION_LEVEL - self.starvation_level
220 elapsed = max(0, current_time_ms - self.last_starvation_change_ms)
221 rem_current = TIME_BETWEEN_STARVATION_LEVELS_MS - elapsed
222 return max(0, (remaining_levels - 1) * TIME_BETWEEN_STARVATION_LEVELS_MS + rem_current)
223
224 def current_state_duration_ms(self, current_time_ms: int) -> int:
225 return max(0, current_time_ms - self.last_state_change_ms)
226
227
228# ------------------------------------------------------------------ stage
229
230
231@dataclass
232class GameStats:
233 score: int = 0 # gracefully terminated count
234 ragequits: int = 0 # user-terminated count
235 uptime_ms: int = 0
236
237
238class GameState:
239 """Top-level simulation state."""
240
241 def __init__(self, *, seed: int | None = None) -> None:
242 self.rng = random.Random(seed)
243 self.now_ms: int = 0
244 self.processes: dict[int, Process] = {}
245 self._dead_processes: dict[int, Process] = {}
246 self.cpu_process: list[int | None] = [None] * NUM_CPUS # cpu_idx -> pid
247 self.idle_slots: list[int | None] = [None] * MAX_PROCESSES
248 self.ragequit_slots: list[int | None] = [None] * MAX_RAGEQUITS
249 # ram_slots/disk_slots: index -> (pid, page_idx) | None
250 self.ram_slots: list[tuple[int, int] | None] = [None] * (NUM_RAM_ROWS * PAGES_PER_ROW)
251 self.disk_slots: list[tuple[int, int] | None] = [None] * (NUM_DISK_ROWS * PAGES_PER_ROW)
252 self.swap_in_queue: deque[tuple[int, int]] = deque() # (pid, idx)
253 self.swap_out_queue: deque[tuple[int, int]] = deque()
254 self.io_waiters: deque[IoEventWaiter] = deque()
255 self.io_event_count: int = 0
256 self.last_io_check_ms: int = 0
257 self.next_pid: int = 1
258 self.last_new_process_check_ms: int = 0
259 self.last_process_creation_ms: int = 0
260 self.stats = GameStats()
261 self.game_over: bool = False
262 self.game_over_at_ms: int | None = None
263 self._page_lookup: dict[tuple[int, int], Page] = {}
264
265 # ----- read-only views for the render layer -----
266 def get_page(self, pid: int, idx: int) -> Page | None:
267 return self._page_lookup.get((pid, idx))
268
269 def pages(self) -> list[Page]:
270 """Every allocated page, whether it currently sits in RAM or on disk."""
271 return list(self._page_lookup.values())
272
273 def dead_processes(self) -> list[Process]:
274 """Starved processes, kept around so the ragequit row can show them."""
275 return list(self._dead_processes.values())
276
277 def all_processes(self) -> list[Process]:
278 """Live processes first, then the starved ones still on screen."""
279 return list(self.processes.values()) + list(self._dead_processes.values())
280
281 # ----- process manager -----
282
283 def _empty_idle_slot(self) -> int | None:
284 for i, occ in enumerate(self.idle_slots):
285 if occ is None:
286 return i
287 return None
288
289 def _empty_ragequit_slot(self) -> int | None:
290 for i, occ in enumerate(self.ragequit_slots):
291 if occ is None:
292 return i
293 return None
294
295 def alive_count(self) -> int:
296 return sum(1 for p in self.processes.values() if p.state != ProcessState.ENDED)
297
298 def create_process(self) -> Process | None:
299 if self.alive_count() >= MAX_PROCESSES:
300 return None
301 slot_idx = self._empty_idle_slot()
302 if slot_idx is None:
303 return None
304 pid = self.next_pid
305 self.next_pid += 1
306 p = Process(
307 pid=pid,
308 last_state_change_ms=self.now_ms,
309 last_starvation_change_ms=self.now_ms,
310 last_periodic_update_ms=self.now_ms,
311 )
312 self.processes[pid] = p
313 self.idle_slots[slot_idx] = pid
314 p.slot_idx = slot_idx
315 return p
316
317 # ----- CPU dispatch -----
318 def select_free_cpu(self) -> int | None:
319 for i, occ in enumerate(self.cpu_process):
320 if occ is None:
321 return i
322 return None
323
324 def assign_to_cpu(self, p: Process) -> None:
325 if p.has_cpu:
326 return
327 if p.state == ProcessState.ENDED:
328 return
329 cpu_idx = self.select_free_cpu()
330 if cpu_idx is None:
331 return
332 # If the process already has a slot, vacate it.
333 if p.slot_idx is not None:
334 self.idle_slots[p.slot_idx] = None
335 p.slot_idx = None
336 self.cpu_process[cpu_idx] = p.pid
337 p.cpu_idx = cpu_idx
338 p.apply(StateEvent.ASSIGN_TO_CPU, self.now_ms)
339 # Allocate pages on first use.
340 if not p.pages:
341 num_pages = round(math.sqrt(self.rng.randint(1, 20)))
342 num_pages = max(1, min(num_pages, MAX_PAGES_PER_PROCESS))
343 for i in range(num_pages):
344 self._allocate_new_page(p, i)
345 for page in p.pages:
346 page.in_use = True
347
348 def yield_cpu(self, p: Process) -> None:
349 if not p.has_cpu:
350 return
351 cpu_idx = p.cpu_idx
352 self.cpu_process[cpu_idx] = None
353 p.cpu_idx = None
354 p.apply(StateEvent.REMOVE_FROM_CPU, self.now_ms)
355
356 if not p.is_waiting_for_io:
357 p.on_io_cooldown = False
358 for page in p.pages:
359 page.in_use = False
360
361 if p.state == ProcessState.ENDED:
362 # Free its pages and remove the process from the list.
363 for page in list(p.pages):
364 self._free_page(page)
365 self._delete_process(p)
366 else:
367 # Find a free idle slot
368 slot_idx = self._empty_idle_slot()
369 if slot_idx is not None:
370 self.idle_slots[slot_idx] = p.pid
371 p.slot_idx = slot_idx
372
373 def toggle_process(self, p: Process) -> None:
374 if p.starvation_level >= DEAD_STARVATION_LEVEL:
375 return
376 if p.has_cpu:
377 self.yield_cpu(p)
378 else:
379 self.assign_to_cpu(p)
380
381 # ----- termination -----
382 def _delete_process(self, p: Process) -> None:
383 # Remove from idle and ragequit slots if any.
384 if p.slot_idx is not None and self.idle_slots[p.slot_idx] == p.pid:
385 self.idle_slots[p.slot_idx] = None
386 p.slot_idx = None
387 # Don't remove from ragequit_slots, those persist visually until
388 # game over.
389 # Also remove from cpu if still attached
390 if p.cpu_idx is not None and self.cpu_process[p.cpu_idx] == p.pid:
391 self.cpu_process[p.cpu_idx] = None
392 p.cpu_idx = None
393 # Drop from process registry: it's "done".
394 self.processes.pop(p.pid, None)
395
396 def _terminate_gracefully(self, p: Process) -> None:
397 p.apply(StateEvent.TERMINATE_GRACEFULLY, self.now_ms)
398 p.starvation_level = 0
399 self.stats.score += 1
400 # Animation: it'll glide off-screen; freeing happens when it leaves.
401 # For simplicity we delete it immediately and let the Node fade.
402 # But upstream keeps it briefly to show halo emoji, so we keep the
403 # process alive but ENDED. yield_cpu will eventually delete it.
404 # Special-case: if it's on-cpu, it'll be yielded -> deleted next frame.
405
406 def _terminate_starved(self, p: Process) -> None:
407 # Only count if a ragequit slot is free.
408 slot = self._empty_ragequit_slot()
409 if slot is None:
410 # No room: skip; will retry next tick.
411 return
412 self.ragequit_slots[slot] = p.pid
413 p.ragequit_slot_idx = slot
414 self.stats.ragequits += 1
415 # Move pages free; clear cpu.
416 if p.cpu_idx is not None:
417 self.cpu_process[p.cpu_idx] = None
418 p.cpu_idx = None
419 if p.slot_idx is not None:
420 self.idle_slots[p.slot_idx] = None
421 p.slot_idx = None
422 for page in list(p.pages):
423 self._free_page(page)
424 p.apply(StateEvent.TERMINATE_FROM_STARVATION, self.now_ms)
425 p.starvation_level = DEAD_STARVATION_LEVEL
426 # Process is removed from active lookup but we keep its data for
427 # rendering in ragequit slot via a ghost map.
428 self._dead_processes[p.pid] = p
429 self.processes.pop(p.pid, None)
430
431 # ----- pages -----
432 def _allocate_new_page(self, p: Process, idx: int) -> Page:
433 page = Page(pid=p.pid, idx=idx)
434 # Try ram first
435 for slot_i, occ in enumerate(self.ram_slots):
436 if occ is None:
437 self.ram_slots[slot_i] = (p.pid, idx)
438 page.on_disk = False
439 p.pages.append(page)
440 self._page_lookup[(p.pid, idx)] = page
441 return page
442 for slot_i, occ in enumerate(self.disk_slots):
443 if occ is None:
444 self.disk_slots[slot_i] = (p.pid, idx)
445 page.on_disk = True
446 p.pages.append(page)
447 self._page_lookup[(p.pid, idx)] = page
448 return page
449 # No room anywhere: just track but don't place
450 p.pages.append(page)
451 self._page_lookup[(p.pid, idx)] = page
452 return page
453
454 def _free_page(self, page: Page) -> None:
455 # Remove from slots and lookup.
456 key = (page.pid, page.idx)
457 self._page_lookup.pop(key, None)
458 for arr in (self.ram_slots, self.disk_slots):
459 for i, occ in enumerate(arr):
460 if occ == key:
461 arr[i] = None
462 # Remove from owner's page list
463 owner = self.processes.get(page.pid) or self._dead_processes.get(page.pid)
464 if owner and page in owner.pages:
465 owner.pages.remove(page)
466
467 def page_slot_index(self, page: Page) -> tuple[str, int] | None:
468 key = (page.pid, page.idx)
469 for arr_name, arr in (("ram", self.ram_slots), ("disk", self.disk_slots)):
470 for i, occ in enumerate(arr):
471 if occ == key:
472 return arr_name, i
473 return None
474
475 def request_page_swap(self, page: Page) -> None:
476 if page.swap_requested:
477 return
478 # Determine target side
479 if page.on_disk:
480 self.swap_in_queue.append((page.pid, page.idx))
481 else:
482 self.swap_out_queue.append((page.pid, page.idx))
483 # Mark current slot as the source
484 page.waiting_to_swap = True
485 loc = self.page_slot_index(page)
486 if loc:
487 page.swap_from_side, page.swap_from_slot = loc
488
489 def cancel_page_swap(self, page: Page) -> None:
490 if not page.swap_requested:
491 return
492 if page.swap_in_progress and page.swap_to_slot is not None:
493 # Vacate the destination slot we already reserved.
494 arr = self.disk_slots if page.swap_from_side == "ram" else self.ram_slots
495 arr[page.swap_to_slot] = None
496 page.waiting_to_swap = False
497 page.swap_started_at_ms = None
498 page.swap_progress = 0.0
499 page.swap_to_slot = None
500
501 # ----- IO -----
502 def request_io(self, p: Process) -> None:
503 self.io_waiters.append(IoEventWaiter(self.now_ms, p))
504 p.apply(StateEvent.REQUEST_IO, self.now_ms)
505 p.on_io_cooldown = True
506
507 def deliver_io_events(self) -> int:
508 if self.io_event_count == 0:
509 return 0
510 delivered = 0
511 while self.io_event_count > 0 and self.io_waiters:
512 self.io_event_count -= 1
513 waiter = self.io_waiters.popleft()
514 p = waiter.process
515 if p.state != ProcessState.ENDED and p.pid in self.processes:
516 p.apply(StateEvent.IO_DELIVERED, self.now_ms)
517 delivered += 1
518 return delivered
519
520 def _on_io_arrived(self, p: Process) -> None:
521 if p.state != ProcessState.ENDED:
522 p.last_starvation_change_ms = self.now_ms
523 p.apply(StateEvent.IO_AVAILABLE, self.now_ms)
524
525 # ----------------------------------------------------------------- tick
526
527
528def tick(state: GameState, dt_ms: int) -> None:
529 """Advance the simulation by ``dt_ms`` milliseconds."""
530 if state.game_over:
531 if state.game_over_at_ms is None:
532 state.game_over_at_ms = state.now_ms
533 state.now_ms += dt_ms
534 return
535 state.now_ms += dt_ms
536 state.stats.uptime_ms = state.now_ms
537
538 _handle_process_creation(state)
539 _handle_swap_queues(state)
540 _handle_processes(state)
541 _handle_io_queue(state)
542 _check_game_over(state)
543
544
545def _handle_process_creation(state: GameState) -> None:
546 # Startup burst: rapidly fill until num_processes_at_startup.
547 if state.next_pid <= NUM_PROCESSES_AT_STARTUP and state.now_ms - state.last_new_process_check_ms >= 50:
548 state.last_new_process_check_ms = state.now_ms
549 state.last_process_creation_ms = state.now_ms
550 state.create_process()
551 elif state.now_ms - state.last_new_process_check_ms >= ONE_SECOND:
552 state.last_new_process_check_ms = state.now_ms
553 if state.alive_count() < MAX_PROCESSES:
554 max_wait_ms = int(100 / NEW_PROCESS_PROBABILITY * ONE_SECOND)
555 if (
556 state.rng.randint(1, 100) <= NEW_PROCESS_PROBABILITY
557 or state.now_ms - state.last_process_creation_ms >= max_wait_ms
558 ):
559 if state.create_process() is not None:
560 state.last_process_creation_ms = state.now_ms
561
562
563def _handle_swap_queues(state: GameState) -> None:
564 # Update progress of in-flight swaps
565 completed_keys: list[tuple[int, int]] = []
566 for key, page in list(state._page_lookup.items()):
567 if page.swap_in_progress:
568 elapsed = state.now_ms - (page.swap_started_at_ms or state.now_ms)
569 page.swap_progress = min(1.0, elapsed / SWAP_DELAY_MS)
570 if page.swap_progress >= 1.0:
571 completed_keys.append(key)
572
573 for key in completed_keys:
574 page = state._page_lookup.get(key)
575 if not page:
576 continue
577 # Apply: vacate source slot; flip on_disk.
578 from_arr = state.ram_slots if page.swap_from_side == "ram" else state.disk_slots
579 if page.swap_from_slot is not None and from_arr[page.swap_from_slot] == key:
580 from_arr[page.swap_from_slot] = None
581 page.on_disk = not page.on_disk
582 page.swap_started_at_ms = None
583 page.swap_progress = 0.0
584 page.swap_from_slot = None
585 page.swap_to_slot = None
586 page.swap_from_side = None
587
588 # Start new in-swaps (disk -> ram)
589 in_progress_in = sum(1 for p in state._page_lookup.values() if p.swap_in_progress and p.on_disk)
590 while state.swap_in_queue and in_progress_in < PARALLEL_SWAPS:
591 empty_ram = next((i for i, occ in enumerate(state.ram_slots) if occ is None), None)
592 if empty_ram is None:
593 break
594 pid_idx = state.swap_in_queue.popleft()
595 page = state._page_lookup.get(pid_idx)
596 if not page or not page.waiting_to_swap or not page.on_disk:
597 continue
598 state.ram_slots[empty_ram] = pid_idx
599 page.swap_to_slot = empty_ram
600 page.waiting_to_swap = False
601 page.swap_started_at_ms = state.now_ms
602 page.swap_progress = 0.0
603 in_progress_in += 1
604
605 # Start new out-swaps (ram -> disk) only when no in-swaps in progress
606 if in_progress_in == 0:
607 in_progress_out = sum(1 for p in state._page_lookup.values() if p.swap_in_progress and p.in_ram)
608 while state.swap_out_queue and in_progress_out < PARALLEL_SWAPS:
609 empty_disk = next((i for i, occ in enumerate(state.disk_slots) if occ is None), None)
610 if empty_disk is None:
611 break
612 pid_idx = state.swap_out_queue.popleft()
613 page = state._page_lookup.get(pid_idx)
614 if not page or not page.waiting_to_swap or not page.in_ram:
615 continue
616 state.disk_slots[empty_disk] = pid_idx
617 page.swap_to_slot = empty_disk
618 page.waiting_to_swap = False
619 page.swap_started_at_ms = state.now_ms
620 page.swap_progress = 0.0
621 in_progress_out += 1
622
623
624def _handle_processes(state: GameState) -> None:
625 # Update each process; also drives state.dead_processes glide-off cleanup.
626 to_terminate_grace: list[Process] = []
627 for p in list(state.processes.values()):
628 # Page-fault check
629 page_fault = any(page.in_use and (page.on_disk or page.swap_in_progress) for page in p.pages)
630 if p.state == ProcessState.RUNNING and page_fault:
631 p.apply(StateEvent.PAGE_FAULT, state.now_ms)
632 elif p.state == ProcessState.BLOCKED_ON_CPU_PAGE_FAULT and not page_fault:
633 p.apply(StateEvent.PAGE_AVAILABLE, state.now_ms)
634
635 # Periodic 1-second tick
636 if state.now_ms >= p.last_periodic_update_ms + ONE_SECOND:
637 p.last_periodic_update_ms = state.now_ms
638 _update_starvation_level(state, p)
639 _maybe_request_io(state, p)
640 _maybe_new_page(state, p)
641 if p.state == ProcessState.RUNNING and state.now_ms - p.last_state_change_ms >= ONE_SECOND:
642 if state.rng.randint(1, 100) <= GRACEFUL_TERMINATION_PROBABILITY:
643 to_terminate_grace.append(p)
644
645 # Blink animation for page-fault
646 if p.state == ProcessState.BLOCKED_ON_CPU_PAGE_FAULT:
647 p.blink_state = int(state.now_ms / 200) % 2 == 1
648 else:
649 p.blink_state = False
650
651 for p in to_terminate_grace:
652 if p.pid in state.processes:
653 state._terminate_gracefully(p)
654 # Yield cpu after graceful termination; deletion of process happens in yield_cpu.
655 if p.has_cpu:
656 state.yield_cpu(p)
657
658
659def _update_starvation_level(state: GameState, p: Process) -> None:
660 if p.state == ProcessState.RUNNING:
661 if state.now_ms - p.last_state_change_ms >= PROCESS_HAPPINESS_MS:
662 p.last_starvation_change_ms = state.now_ms
663 p.starvation_level = 0
664 return
665 if p.state == ProcessState.ENDED:
666 return
667 elapsed = state.now_ms - p.last_starvation_change_ms
668 if elapsed < TIME_BETWEEN_STARVATION_LEVELS_MS:
669 return
670 if p.state in {ProcessState.BLOCKED_ON_CPU_IO_REQUESTED, ProcessState.BLOCKED_OFF_CPU_IO_REQUESTED}:
671 return
672 p.last_starvation_change_ms = state.now_ms
673 if p.starvation_level < LAST_ALIVE_STARVATION_LEVEL:
674 p.starvation_level += 1
675 else:
676 state._terminate_starved(p)
677
678
679def _maybe_request_io(state: GameState, p: Process) -> None:
680 if p.state != ProcessState.RUNNING:
681 return
682 if p.on_io_cooldown:
683 return
684 if state.rng.randint(1, 100) <= IO_PROBABILITY:
685 state.request_io(p)
686
687
688def _maybe_new_page(state: GameState, p: Process) -> None:
689 if p.state != ProcessState.RUNNING:
690 return
691 if len(p.pages) >= MAX_PAGES_PER_PROCESS:
692 return
693 if state.rng.randint(1, NEW_PAGE_PROBABILITY_DENOMINATOR) == 1:
694 new_page = state._allocate_new_page(p, len(p.pages))
695 new_page.in_use = True
696
697
698def _handle_io_queue(state: GameState) -> None:
699 if not state.io_waiters:
700 return
701 # Force events for waiters that have hit max wait time
702 waiter_index = state.io_event_count
703 if waiter_index < len(state.io_waiters):
704 oldest = state.io_waiters[waiter_index]
705 if state.now_ms - oldest.waiting_since_ms >= IO_MAX_WAITING_TIME_MS:
706 state._on_io_arrived(oldest.process)
707 state.io_event_count += 1
708 state.last_io_check_ms = state.now_ms
709
710 # Probabilistic events when min_waiting_time has elapsed
711 if state.now_ms < state.last_io_check_ms + IO_MIN_WAITING_TIME_MS:
712 return
713 waiter_index = state.io_event_count
714 if waiter_index >= len(state.io_waiters):
715 return
716 oldest = state.io_waiters[waiter_index]
717 if state.now_ms < oldest.waiting_since_ms + IO_MIN_WAITING_TIME_MS:
718 return
719 state.last_io_check_ms = state.now_ms
720 if state.rng.randint(1, 3) != 1:
721 return
722 new_count = state.rng.randint(state.io_event_count + 1, len(state.io_waiters))
723 for i in range(state.io_event_count, new_count):
724 state._on_io_arrived(state.io_waiters[i].process)
725 state.io_event_count = new_count
726
727
728def _check_game_over(state: GameState) -> None:
729 if state.stats.ragequits >= MAX_RAGEQUITS and not state.game_over:
730 state.game_over = True
731 state.game_over_at_ms = state.now_ms
732
733
734__all__ = [
735 "GameState",
736 "Process",
737 "Page",
738 "ProcessState",
739 "StateEvent",
740 "tick",
741 # constants
742 "NUM_CPUS",
743 "NUM_PROCESS_SLOT_ROWS",
744 "NUM_PROCESS_SLOT_COLS",
745 "MAX_PROCESSES",
746 "NUM_RAM_ROWS",
747 "NUM_DISK_ROWS",
748 "PAGES_PER_ROW",
749 "MAX_RAGEQUITS",
750 "PROCESS_HAPPINESS_MS",
751 "TIME_BETWEEN_STARVATION_LEVELS_MS",
752 "LAST_ALIVE_STARVATION_LEVEL",
753 "DEAD_STARVATION_LEVEL",
754]