News Archive (1999-2012) | 2013-current at LinuxGizmos | Current Tech News Portal |    About   

Linux 2.6.23’s “Completely Fair Scheduler” dissected

Jan 15, 2008 — by LinuxDevices Staff — from the LinuxDevices Archive — 2 views

IBM's DeveloperWorks has published a deeply technical overview of the new CFS (“completely fair scheduler”) available in 2.6.23 and later Linux kernels. Based on fair scheduling theory proven by Con Kolivas, CFS may suit some multi-user embedded systems, and devices with desktop or server-like functionality, the article suggests.

The CFS is arguably one of the greatest open source success stories yet. Written by Ingo Molnar, it is based on scheduling theory that was proven not by a hard-core kernel hacker, but by Con Kolivas, an Australian anaesthetist for whom computing and especially benchmark testing is a hobby. Access to the source code and Linux's open development process on the LKML (Linux kernel mailing list) enabled Kolivas to influence Linux in a big way, despite having no formal background in computer science.

The DeveloperWorks article begins with a nod to Linux's modular Pluggable CPU scheduler framework, which lets users choose at boot time which scheduler policy their kernel should use — a feature useful for benchmarking specific applications with various scheduler policies. Linux 2.6.23 has five scheduler policy options, the article suggests, including three that use CFS, and two that use the “real-time” scheduler. Additionally, the arrival of “scheduling classes” brings extensibility, while group scheduling fairness improves resistance to denial of service attacks by apportioning CPU more equally among users, rather than simply among tasks.

The article next compares CFS to Con Kolivas's RSDL (rotating staircase deadline scheduler), before dissecting the “time-ordered red-black tree” runqueue that CFS keeps for each CPU. Next comes a look at CFS's scheduling logic, including a list of user-tunable runtime parameters. Finally, the article concludes with a glance towards scheduler changes expected with the forthcoming 2.6.24 kernel release.

The full story can be found here.

This article was originally published on and has been donated to the open source community by QuinStreet Inc. Please visit for up-to-date news and articles about Linux and open source.

Comments are closed.