kSTEP (OSDI ’26) runs the unmodified Linux CPU scheduler deterministically, one tick at a time, on CPUs it isolates. A Linux kernel boots below when the page loads, with kSTEP holding its scheduler clock. Nothing happens in it except what you ask for: create tasks, change their nice value or affinity, pause or kill them, pick the machine's topology, and advance the scheduler one tick at a time.
One column per tick, newest on the right. Hover for values; wheel to pan back through the run, ctrl (or ⌘) wheel to zoom.
| task | cgroup | state | affinity | cpu | cpu time | policy |
|---|
One box per CPU: its runqueue in the header, then each class with something queued. Real-time first, since it outranks fair; the fair queue picks the eligible entity with the earliest deadline, a task or a cgroup whose own queue is indented under it.
The sched domains the kernel built, a box per span down to the CPUs; a level that adds nothing is dropped by the kernel and absent here. One bar per box: running, the time fair tasks were on the CPU, over the box's capacity, 1024 being one CPU at full speed, in the colour of the balancer's verdict: green has spare room, orange is fully busy, red is overloaded. Hover it for the two other averages the balancer reads, contention and load, and hover a level's name for its flags and thresholds. Each box says in how many ticks it is next weighed against its siblings.
What moved, and why, per command: a balance is a CPU running the balancer at a level and pulling from the busiest group's busiest CPU; a move on a create or wake is the wakeup placement, which picks an idle CPU near where the task last ran or near its waker. The destination is always the CPU that did the pulling.
The machine: its sockets, their clusters of cores, and each core's threads and capacity. A cluster is a shared cache, and its cores need not be alike. Each thread is one CPU, numbered cpu 1 upwards across the tree; cpu 0 runs the driver and is kept out of the scheduler's reach. Capacity is the hardware and is applied at boot; frequency, on each CPU's card under Load balancer, changes while it runs. Changing the machine restarts the VM and resets tasks, cgroups and the charts.
Each row is a real Linux CPU scheduler bug with a kSTEP driver that triggers it; the plot compares the trace of the buggy and the fixed kernel. ./reproduce.py <bug> in the kSTEP repo builds both kernels and reruns the driver.
| Bug, driver, and fix | Buggy vs fixed |
|---|
A driver program (kernel code, one per bug) declares a sequence of scheduler-invoking events: task creation, wakeups, sleeps, cgroup changes, ticks. The kSTEP module dispatches them on CPUs isolated from the rest of the system, with the scheduler clock and the tick under its control, so the unmodified scheduler runs the same code path it would in production and produces the same trace on every run. The plot in each row compares that output for the buggy and the fixed kernel.
kSTEP: Characterization and Deterministic Testing of Linux CPU Scheduler Bugs. Tingjia Cao, Shawn (Wanxiang) Zhong, Caeden Whitaker, Ke Han, Andrea C. Arpaci-Dusseau, Remzi H. Arpaci-Dusseau. OSDI '26.
We present an in-depth study of CPU scheduler bugs, covering both functional violations and misalignments between implementation and policy. Our study shows that these bugs are hard to observe and even harder to trigger. To close this gap, we introduce kSTEP. kSTEP gives testers fine-grained control over scheduler-invoking events and runs them deterministically on isolated CPUs. kSTEP produces noise-free, repeatable traces that expose subtle behavior. We then build a coverage-guided fuzzer on top of kSTEP for automated CPU scheduler testing. We demonstrate kSTEP's effectiveness by reproducing seven real-world scheduler bugs and uncovering four new ones.