Scheduler
§1Design position: why a single global run queue
Rux's scheduling core is one global run queue serving all CPUs (design divergence D-1): no per-CPU run queues, no load balancer, no stealing. An idle CPU is woken by IPI and pulls tasks on demand — the queue is inherently balanced, and the whole "imperfect balancing" bug class does not exist.
This is a deliberate trade for desktop, mobile and embedded core counts: the platform currently builds with MAX_CPUS=8 (kernel/src/config.rs), and the target workload is a graphics session plus a service mesh with tens-to-hundreds of tasks — not a multi-hundred-core server. At this scale, what per-CPU queues plus load balancing add — migration decisions, balancer heuristics, fairness bugs from imperfect balancing — is pure cost; the two known GRQ costs (contention ceiling at high core counts, cache-locality loss) are recorded in the divergence entry with an explicit revisit trigger: reopen when measurements show the hold entering a contention-bound regime.
The key difference from a per-CPU design is forensicability: scheduling order has a single source of truth, and every wake/pick/strand instrument (§8) reasons over exactly one structure. The scheduler bug families of the OpenHarmony campaign (lost wakes, phantom preempt bits, stale claims) were all located on this single structure — by design, not by luck.
Evidence that the cost is pinned
- Hold measurement (post measurement-correction): production critical section ≈60 ns; minimal-bracket measured 75–80 ns. The switch-path segments (lock wait 70–84 / acct 110–122 / deq 58–64 / pick 89–98 / ownership 68–77 ns) are likewise probe-class readings carrying instrument weight — their relative scale stands; the "lock wait" segment is the KVM tax on cross-vCPU locked instructions — the hypervisor emulates cache coherence in the management path, so cross-vCPU atomics cost several times more than on bare metal; Linux's per-rq lock pays the same tax on this test platform, so it does not mean the GRQ is slow — it is a fixed cost of this virtualized test platform. Of the work that is genuinely the GRQ's, the tree work is down to ~20–30 ns per mutation with zero allocation under the lock; the rest is D-1's own bookkeeping (class-chain walk, ownership publish, slice math, min_vruntime rebase, counter updates) — squeezing the whole section to a 10 ns class would mean changing D-1 itself, which is ruled out.
The gate metric is a different quantity: the gate band tracks the call-site IF=0 span average (spin_lock_irqsave irqsave→restore, including lock-acquisition wait and critical-section work): 2786 ns (n=6.3M, 17.6 s total; KVM q35 smp2/4G, 780 s window, host load 6.4–11.3), gate band 2786 ns. Across the same boot, scheduling volume grew ~2× while the span stayed flat → the cost is a function of execution volume, not lock-line contention. - The Amdahl verdict: this hold is NOT a concurrency bottleneck (2026-11-17, user-directed analysis): S(N) = 1/(s+(1−s)/N). With the TRUE critical section (production ≈60 ns, minimal bracket 75–80 ns) × 6.3M acquisitions per boot, the serialized fraction s = 0.024–0.032% — parallel efficiency at 8 CPUs ≈99.8%, Amdahl ceiling ≈3100–4200 cores under the most conservative reading (the call-site IF=0 span average, 2786 ns, including lock wait) s = 1.13% — 92.7% efficiency at 8, ceiling ≈89 cores. Both bounds sit far above MAX_CPUS=8, so the GRQ lock hold has a negligible effect on concurrency (empirical: 4k direct I/O scales near-linearly from numjobs 4→8). Any further hold slimming is switch-LATENCY work (the per-schedule path length), not concurrency work.
- Churn pinned by config:
cfs_min_granularity_ns = 0.7 ms(wakeup-preemption granularity takes the same value) plus a 100 Hz tick — a freshly queued task cannot lose its CPU before ~0.7 ms of service, the 10 ms tick bounds the re-queue rate, and wake storms cannot churn the queue structure. - Hold cost decomposed into segments: wake hold = runqueue accounting / dequeue-enqueue / pick / stats, each segment measured by the wakewatch and WW census instruments (§8).
- Survey record (
docs/architecture/os-kernel-survey.md): Barrelfish-style replicated-state message kernels and flat combining are both REJECTED-with-data — the motivating problem (coherence traffic at high core counts) does not exist in this regime.
§2Data structures and lock protocol
GlobalRunQueue {
lock: RawSpinlock,
dl_rq: DlRunQueue, // BTreeMap<(deadline, task_id)> EDF
rt_rq: RtRunQueue, // bitmap [AtomicU64;2] + per-prio lists
cfs_rq: CfsRunQueue, // BTreeMap<vruntime> (tasks_timeline)
nr_running: AtomicUsize,
idle_cpus: AtomicU32, // bitmap
}
Per-CPU state keeps only current / idle / stop slot pointers. pick_next_task class order: stop (highest, per-CPU) → DL → RT (skipped while this CPU is RT-bandwidth throttled) → CFS → idle; every class pick passes a PID-0 gate and a DEAD-pick gate (poisoned entries are dropped and counted).
- idle_cpus bitmap:
mark_idlefetch_or sets a bit;claim_idle_cpufinds and atomically clears in one step — two racing wakes can never target the same idle CPU; the scan start rotates pastLAST_IDLE_HINTso wakes spread across idle CPUs. - Lock protocol:
lock_irqsave= save IRQ state + disable + preempt count + spin; the nested variantlock_irqsave_nestedconsumes a NestProof minted by typed lock keys (D-11) — a reverse nesting does not compile. GRQ-vs-futex-bucket nesting is a compile-time fact: waking under the bucket lock with GRQ nested is the everyday path; the reverse is a machine-wide deadlock. - Counter discipline: every nr_running decrement goes through checked-sub (fetch_update) — unsigned wraparound is the fingerprint of the historical "unexcluded section" incident family and is no longer representable.
- Structural limits are on record: the CFS tasks_timeline
dequeue()is still a linear scan (O(n) per call), the leftmost cache is logged but not landed; pick's lift-out/re-insert pays 2 tree walks per skipped candidate (bounded ≤32, on a correctness-critical path — no speculative optimization).
§3CFS class (fair.rs)
- vruntime = delta_exec × NICE_0_LOAD / weight, implemented as the shift multiply
delta × NICE_0_LOAD × inv_weight >> 32(inv_weight = 2³²/weight); NICE_0_LOAD = 1024; the SCHED_IDLE policy is fair-class weight 3 (not a separate class). - Granularity constants:
SCHED_MIN_GRANULARITY_NS = 0.7 ms(also the wakeup-preemption granularity — a waker preempts only if it beats the incumbent by > 0.7 ms);SCHED_LATENCY_NS = 6 mslatency window; tick 100 Hz. sched_slice = min(granularity×nr_running, 6 ms) × weight / total weight, floored at the granularity. - Placement and credit: min_vruntime is a monotone floor; the wake/first-link placement base uses avg_vruntime (the 6.6 fair.c mapping); a sleeper enqueues with a credit floor of
min_vruntime − 6 ms(sleeping is never penalized to zero); lag is clamped to max(2×slice, tick) in the fair domain. - Pick walk and lift-out: the leftmost walk refuses entries this CPU cannot run — five refusal reasons (ownership / on_cpu / pick claim held elsewhere / affinity / cgroup throttle / healed reset) — each refused entry is temporarily lifted into a 32-slot stash and re-inserted in reverse after the pick. min_vruntime is updated after full re-insertion, over the complete timeline: lifting entries makes the leftmost look further right, and updating first would permanently erase the sleep credit of new tasks and wakers (order fixed after a measured regression).
- entity_tick guard: a solo CPU-bound task is no longer dequeued/re-queued/re-picked on every tick (Linux's entity_tick nr_running>1 condition).
§4RT and DL classes
- RT (rt.rs): SCHED_FIFO/RR; 100 user priorities encoded in an
[AtomicU64; 2]bitmap (bit 0 = user priority 99, inverted; lowest set bit = highest priority), one ListHead queue per priority; RR timeslice 10 ticks = 100 ms; counts checked-sub like everywhere. - DL (deadline.rs): EDF + CBS; BTreeMap keyed (deadline, task_id); default period 1 s / runtime 100 ms, bandwidth unit 1<<20. CBS was once completely defeated (every enqueue replenished) — fixed into real throttling: an exhausted task leaves the run queue (INTERRUPTIBLE) and a kernel timer re-fills it at the next deadline, replenishing exactly once per period. Safety argument: GRQ→TIMERS is one-way because the timer softirq delivers its wake_up_process calls only after releasing TIMERS (R12-3).
- stop / idle: stop-class slot (per-CPU, for hotplug/active balancing, currently always empty); idle tasks never enqueue — any wake preempts idle immediately and rescheds.
§5Wakeup path and the preemption gate (D-14)
Wakeup dispatch is a three-rung ladder (kernel/src/process/task.rs):
- An idle CPU within the wakee's affinity first (Linux's select_task_sibling + remote-enqueue shape): claim an idle CPU and send the resched IPI.
- No idle CPU, non-sync wake: pass the measured-wait preemption gate (D-14) — poke the busy CPU's need_resched only when the wakee's measured wait (sched_clock − last pick stamp) is ≥ one latency window (6 ms); a wakee that ran within the window is left to slice expiry / handoff machinery.
- Sync wake, no idle: stacking — preserve the wake_affine parity property: while holding the global queue, a sync wake never notifies another busy CPU; the waker stacks the receiver onto its own CPU.
Why not a vruntime-credit comparison as the gate: Linux preempts when the wakee's vruntime beats the incumbent's. Rux's sleeper-credit floor and place-on-wake adjustments keep a ping-pong peer permanently a few ms of vruntime behind (measured: re-queue clamps cause +~10 ms vruntime jumps) — Linux's gate would pass on EVERY wake and degrade into a per-record preempt dance. The measured-wait gate pokes only when the wakee has genuinely waited.
| D-14 effect (same test platform) | Before | After |
|---|---|---|
| 74-byte unix-stream record's wake/preempt/switch dance | ~275 µs | ~2.5 µs |
| p5b unix DGRAM send/recv | 318.6 / 318.3 µs | 23.1 / 40.9 µs (−93%/−87%) |
| p5c unix stream write set | 276.5–277.6 µs | 24.9–26.8 µs (−90%) |
| p5 IPC family overall | 10–18× | |
| p5a pipe roundtrip (handoffs bypass the wake gate, by design) | 19.673 µs | 18.306 µs (−6.9%) |
Known costs (on record): sub-6 ms ping-pong receivers wake at slice expiry rather than immediately; exec_start approximates true wait with the last pick stamp, slightly overestimating; a futex wake→run behind an incumbent is tick-quantized to ~10 ms (p2f suite run: 9.99/10.0 ms in both hog regimes — the sentinel row of the known quantization class).
IPI and polling idle
- Resched IPI sender-side alone 935–1139 ns (cctx probe); IPI + halt exit costs ~2–5 µs of KVM exit per handoff.
- Polling idle window 120 µs: wakes landing inside the pure-spin idle window skip the resched IPI (raised from 30 µs — suite run 2 measured 815/1915 wakes whose IPIs landed just past the window at a 995 ns mean; each elided IPI saves ~1 µs of handoff). Dekker SeqCst fence pairing with
resched_cpucarries a documented lost-wake safety argument. - Re-check need_resched between MARK_IDLE and WFI (R20-2): otherwise a task enqueued the instant before mark_idle sleeps a full 10 ms tick for nothing.
§6Tick, kernel preemption and NOHZ
- Tick: per-CPU timer at 100 Hz.
scheduler_tick()does: softlockup touch, schedstat, phantom-bit orphan scan, allocwatch, a 1 Hz CLAIM-SWEEP (stale-claim heal over the whole CFS timeline under the GRQ), and the per-task PREEMPT-LEAK tripwire. - Kernel preemption defaults off (opt-in via explicit schedule() calls); the
kpreempt=1/0boot param arms the irq-exit preemption hook; A/B reads flat for hog regimes — default stays off. - can_stop_tick decision tree (Linux core.c order): any DL task needs the tick; >1 RR task needs it; FIFO-only does not; >1 CFS task (GRQ counter plus running non-idle currents added back) needs it.
- NOHZ (adaptive tick): a function-for-function mirror of Linux's tick-sched.c (check_tick_dependency / tick_nohz_stop·restart_sched_tick / tick_nohz_irq_exit / the nohz_full= parameter); tick_dep bits POSIX_TIMER/PERF/SCHED/RCU etc.; the per-rq→GRQ structural mapping is on record (the 0→1 kick kept as a resched IPI from the enqueue edge). Wired on x86_64 (LAPIC one-shot); other twins pending.
nohz_full=1measured (merge record): under a hostile-load suite lmbench lat_syscall,null passes 11/12 (main tip 0/10), p1_null median 0.050 vs 0.060 µs (−17%), both census bands hold exactly. - Dependency gate: tick-dependency re-evaluation on load change is gated by NOHZ_FULL_RUNNING — ungated, the can-stop predicate's per-CPU current scan lands inside every GRQ-held enqueue (p2_ctxsw 1.242→2.149 µs, +73%, eliminated by the gate).
§7Context switch (the three x86_64 levers)
The switch path decomposes via cctx counters into FPU save / mm switch / FS·GS / asm body / FPU restore:
- Lazy FPU: save (xsaveopt) only if prev actually used FP since switch-in; the restore moves into the #NM handler (CR0.TS); the kernel binary is disassembly-verified to contain no compiler-emitted FP. fpusave 51 ns + fpurest 76 ns per switch.
- FSGSBASE: CPUID-gated; FS/GS moves become wrfsbase/rdfsbase (393 ns of the per-switch cost); without hardware, wrmsr fallback; per-task cached mirrors avoid rdmsr on the switch path.
- PCID: dual-CPUID-gated (PCID+INVPCID); every mm owns a 12-bit PCID and the CR3 write carries tag+NOFLUSH — switching back to a previous mm keeps its cached translations instead of a full flush (pre-PCID CR3 reload was 543 ns, the largest single switch cost); INVPCID type 0 precise single-page / type 3 full; ASIDs are synchronously flushed on all CPUs before returning to the pool.
- Measured (median of 3 interleaved A/B):
lat_ctx -s64 24.97→2.07 µs (−58%),-s64 84.68→1.94 µs (−59%). Same-test platform lmbench authoritative row (smp2 KVM, same guest, same binary): 2.51 vs 12.84–12.97 µs (ahead 5.14×; -s64 8: 1.92 vs 12.06–12.08, ahead 6.29×).
§8Forensic instruments and gate bands
The scheduling domain has its own instrument suite; usage lives in the debugging guide:
- wakewatch: wake-to-run latency forensics. A 1024-slot side table (Task-pointer hashed; the task layout is untouched) classifies "should have run but didn't" into four verdicts: WAKE-STRANDED (woke on time, never picked — names the victim, the latency, the picking CPU) / TIMER-LATE-FIRE / WAKE-REFUSED / in-process loss; WW5 bucket counters N250/N500/N750; strand threshold 1000 ms (raised after prints inside IF=0 contexts ate the LIFECYCLE_TIMEOUT budget).
- census: TERM-DESCHED 8±2 (the terminal-deschedule loop for DEAD tasks, print budget n<8) and WAKE-REFUSED 32±4 (the W3 wake-refusal census, budget 32). Both census counts are exactly identical on every qualifying quiet boot (8/32) and serve as the scheduling domain's shape signature in the perf gate.
- cctx segments: wake side WK_N/WK_SEL/WK_ENQ/WK_DISP/IPI_N/IPI_NS; switch side CW_FPUSAVE/CW_MM/CW_MSR/CW_ASM/CW_FPUREST; schedule side SCH_PRE/LOCKWAIT/ACCT/DEQREQ/PICK/PUB — any switch or wake regression lands in a segment.
- Gate bands (scheduling domain): GRQ average hold 2786 ns, census 8±2 / 32±4, p2_ctxsw ±20%, p5 row bands; any pick/placement change must pass a release-strong pbench boot.
§9Known costs and open items
- GRQ contention ceiling and locality loss: recorded in D-1; revisit trigger = IF=0/hold measurements entering a contention-bound regime (currently volume-coupled).
- O(n) linear dequeue over the CFS timeline and the missing leftmost cache: the next known hold-slimming target; the pick lift-out's 2× walks are bounded but real.
- The p4 fork family is currently an open regression (fork_exit 13.2 ms vs the 9.4–10.0 ms historical family), carried honestly on the gate's watch row.
- Kernel preemption defaults off: differs from Linux's optional preemptible-kernel default for throughput workloads; the ~10 ms tick quantization of futex wakes behind incumbents is the other face of the same coin — removing it depends on NOHZ wiring on all arches and kpreempt tuning.
kernel/src/sched/ (sched.rs / fair.rs / rt.rs / deadline.rs / idle.rs / wakewatch.rs). Divergences: D-1/D-11/D-14. Instruments: cctx (inside syscost), wakewatch, census. Gate bands: the scheduling-domain rows of docs/development/perf-gate-baseline.md.