]> Projects (at) Tadryanom (dot) Me - AdrOS.git/commit
feat: O(1) sorted sleep queue for process_wake_check
authorTulio A M Mendes <[email protected]>
Fri, 13 Feb 2026 21:00:07 +0000 (18:00 -0300)
committerTulio A M Mendes <[email protected]>
Fri, 13 Feb 2026 21:00:07 +0000 (18:00 -0300)
commitb5267984a4558d779a1414760b61a92684506c80
tree925bc5395c27b25e8332d291f77bdeba65ce7d39
parent5ea305805773fa12bc1905149822a176bcb651ad
feat: O(1) sorted sleep queue for process_wake_check

Replace O(N) scan of all processes with a sorted doubly-linked sleep
queue. process_wake_check now pops expired entries from the queue head
in O(1) time. The O(N) scan is retained only for alarm delivery.

Key design decisions:
- sleep_prev/sleep_next/in_sleep_queue fields added to struct process
- process_sleep() inserts into sorted queue under sched_lock
- schedule() handles deferred insertion for ksem_wait_timeout/futex
  (SLEEPING set under external lock, inserted under sched_lock in
  schedule — no preemption window)
- All wake paths (signal, kill, reap, sched_enqueue_ready) call
  sleep_queue_remove to prevent double-insert corruption
- Defensive sleep_queue_remove before insert in process_sleep

20/20 smoke tests pass, cppcheck clean.
include/process.h
src/kernel/scheduler.c