]> 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)
commit565486e98cfaa572cfac794bd98aa5d5ee393c47
treed73c0cf7a90431541afb2ffdef096a5241db14bc
parent0cfd0ec8540c7a882f8fbc13403f7703db4d7a34
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