Linux kernel: The battle of the CPU schedulers

Since some time already, different patches are being written for the Linux kernel, which improve the CPU scheduler. The CPU scheduler, is that part of the kernel, that’s responsible for assigning CPU time to the different task running on your system. If you sometimes experience problems with sound stuttering or your mouse becoming jerky while running other CPU intensive tasks, then this is definitely a problem caused by the task scheduler.

Con Kolivas has been maintaining an alternative scheduler for some time. His Staircase scheduler was designed with interactivity in mind, especially for desktop systems, where people want their system to be quickly responsive under all kinds of workloads. This scheduler has been optimized a lot through the years, and as such is very stable. Still there are some rare cases where “starvation” is possible.

At the start of March, Con Kolivas published a new scheduler, which was called RSDL (Rotating Staircase DeadLine scheduler) at first, and has been renamed to SD (Staircase Deadline) afterwards. Based on the experience Con Kolivas gathered with his Staircase scheduler, SD is a more general purpose scheduler, trying to give absolute fairness to the different running tasks, without favouring any process (for example lots of other schedulers favour X). This way, no starvation issues should be possible with this scheduler. A lot of discussion followed after his announcement, and it became quickly clear that a lot of people were not happy with the current scheduler in Linux. Important kernel developers like Mike Galbraith, Nick Piggin, Ingo Molnar, Willy Tarreau and Andrew Morton joined the discussion and also posted other scheduler patches, sometimes not without some trolling and flaming as sometimes happen on such mailing lists. Con Kolivas’ scheduler was added to Andrew Morton’s mm kernel tree to get some more testing. The development of RDSL/SD went up and down sometimes, because of Con Kolivas’ health problems.

Ingo Molnar, which was rather critical of some of the ideas in the new scheduler at first, also recently began the development of CFS (Completely Fair Scheduler, which actually is based on the same basic concept of fairness. Con Kolivas announced that he would stop development of the RD scheduler, because of his health problems, and because his ideas would now continue to be used in the CFS scheduler. But things came out differently, and Con Kolivas continued development in the end. The result is that the SD scheduler is now at its 46’th version (v. 0.46), and it seems most problems have been fixed. Based on all the testing done on the kernel mailing list, it seems SD 0.46 is more mature than CFS 6. Even Willy Tarreau, maintainer of the 2.4 Linux kernel tree, said that thanks to SD, he did make Linux 2.6 the default kernel on his laptop, as he found the scheduler in mainline 2.6 too bad compared to 2.4. It’s unclear however which of these schedulers will be integrated in linux finally, and when this will happen.

Personally I think SD 0.46 should be integrated now in Linux 2.6.22 pre-releases. There has been a lot of testing and bug fixing, and it seems there are no serious bugs open anymore now. I also hope that Mandriva 2008 will come out with one of these new schedulers. The tmb kernel in Mandriva Cooker, already uses the SD scheduler now. People interested in this discussion, can subscribe to the ck mailing list where a lot of the discussion is happening. Sites like LWN.net and Kerneltrap also often post about the progress of this subject.