scheduler bug-fix commits studied since 2020
Paper
kSTEP: Characterization and Deterministic Testing of Linux CPU Scheduler Bugs
Tingjia Cao, Shawn (Wanxiang) Zhong, Caeden Whitaker, Ke Han, Andrea C. Arpaci-Dusseau, and Remzi H. Arpaci-Dusseau.
Bug study
Scheduler bugs matter, but they are hard to see.
The study separates functionality bugs from policy bugs: failures where Linux keeps running, but scheduler behavior quietly drifts from intended goals such as balance, fairness, locality, and energy efficiency.
Fatal failures
Crashes, oopses, hard lockups, or hangs are visible, but they are only part of the story.
No warnings
Most bugs leave no useful panic, warning, or default trace of the triggering event sequence.
Semantic root causes
Wrong state updates and logic faults dominate, demanding scheduler-specific understanding.
Hidden for years
Many fixes land only after long exposure in mainline, with some bugs surviving over a decade.
Attribute-sensitive
Task, cgroup, and system-level scheduler attributes form a large input space for testing.
Beyond userspace
Kernel events and special hardware topologies are often required to trigger real bugs.
Platform
Controlled execution without inventing fake scheduler states.
kSTEP runs driver programs in kernel space and dispatches normal scheduler-invoking events into an isolated environment. The scheduler remains unmodified; tests guide it into target states through realistic code paths.
Precise timing
Explicit ticks advance logical time and place events inside narrow transient windows.
Rich control
Drivers can orchestrate tasks, cgroups, kernel activities, CPU frequency, and topology.
Deterministic traces
Mocked clocks, isolated CPUs, and reset state make the same input produce the same trace.
High fidelity
kSTEP avoids direct scheduler-state mutation, preserving behavior reachable on real systems.
Evaluation
Short drivers expose bugs that benchmarks struggle to reproduce.
Case-study reproducers use compact event sequences to trigger scheduler failures, then compare buggy and fixed kernels with deterministic traces.
Sync wakeup locality
A wakee selects a remote CPU despite the waker CPU becoming idle, causing an initial slowdown.
Cgroup vruntime overflow
A transient hierarchy state can inflate vruntime and starve a task almost indefinitely.
Load-balancing waste
Topology-sensitive bugs make CPUs rebalance redundantly or stay idle with runnable work.
Utilization misaccounting
Bad accounting after sleep can delay CPU frequency ramp-up for latency-sensitive tasks.
Study results
Figures from the scheduler bug study.
These figures summarize the paper's characterization results: where scheduler bugs come from, how visible they are, and how fixes are validated. Together they show why scheduler bugs need controlled, deterministic tests rather than benchmark-only validation.
Root causes and consequences
Semantic state and logic faults dominate, while many consequences remain hard to observe externally.
Bug observability
Most scheduler bugs do not leave clear warnings or logs, especially policy misalignments.
Functionality vs. policy
The study separates strict correctness failures from policy compromises such as fairness and balance.
Discovery and validation
Current practice often relies on review or workload symptoms instead of concise regression tests.
Reproduced bugs
Buggy-vs-fixed traces from kSTEP drivers.
Each reproducer plot links to the rendered trace. The card links point to the driver source and the raw buggy and fixed kSTEP outputs used to generate the figure.
sync_wakeup.c
Sync wakeup locality
vruntime_overflow.c
Cgroup vruntime overflow
freeze.c
Delayed-dequeue freezer
extra_balance.c
Extra load balancing
util_avg.c
RT util_avg drop
long_balance.c
Long balance scan
lag_vruntime.c
Lag vruntime reweight
even_idle_cpu.c
Even idle CPU
local_group_imbalance.c
Local group imbalance
util_avg_jump.c
Util avg jump
rt_runtime_toggle.c
RT runtime toggle
uclamp_inversion.c
uclamp inversion
h_nr_runnable.c
h_nr_runnable accounting
Resources
Build on deterministic scheduler execution.
kSTEP can support reproducible debugging, regression tests, policy evaluation, anomaly detection, fuzzing, and agent-driven scheduler test generation.