I have been testing the new kernel on a machine that does two incompatible jobs: compile software and remain pleasant enough to use while compiling software. Under load, the 2.6 test kernel feels less sticky than my usual 2.4 setup. The O(1) scheduler is a large part of that.

The name describes a property, not a performance promise. Choosing the next runnable task takes constant time rather than getting more expensive as the run queue grows. The scheduler keeps arrays of queues indexed by priority, plus a bitmap showing which priorities contain runnable tasks. Finding work becomes a matter of locating the first set bit and taking a task from that queue.

There are actually two priority arrays per processor: active and expired. A normal task runs for its time slice and then moves to the expired array. When active becomes empty, the kernel swaps the arrays. No grand tour through every process is required.

That design also avoids one global run queue becoming a lock everybody fights over on an SMP machine. Each processor has its own run queue, and load balancing periodically moves work when the queues become uneven. Per-processor data makes the common path cheaper, although balancing is still real work and certainly not magic.

Interactive behaviour comes from dynamic priorities. A task that sleeps often, as an editor or terminal usually does while waiting for me, receives favourable treatment when it wakes. A compiler chewing CPU continuously tends to use its slice and wait in the expired array. The scheduler is estimating interactivity from sleep behaviour; applications do not announce that they are important because a human is glaring at them.

There is a caveat. Heuristics can be fooled, and “feels faster” is not a benchmark. A database server and a desktop have very different ideas of fairness. I am watching throughput as well as latency and checking for tasks that receive odd priority treatment.

Still, the mechanism is refreshingly concrete. Constant-time selection, per-CPU queues, and explicit expired work explain the observed behaviour without fairy dust. The desktop remains responsive during a build, the build still finishes, and neither needs a special incantation. That is a scheduler improvement I can actually notice.