Linux: Completely Fair Scheduler Merged
July 10, 2007 - 10:02am
Submitted by Jeremy on July 10, 2007 - 10:02am.
*kerneltrap.org/files/category_pictures/K-Linux_0.gif
Ingo Molnar [interview]'s Completely Fair Scheduler [story] has been merged into the Linux kernel for inclusion in the upcoming 2.6.23 release. A comment in the patch titled 'sched: cfs core code' noted, "
apply the CFS core code. This change switches over the scheduler core to CFS's modular design and makes use of kernel/sched_fair/rt/idletask.c to implement Linux's scheduling policies." Another patch included documentation which described the new scheduler, "
80% of CFS's design can be summed up in a single sentence: CFS basically models an 'ideal, precise multi-tasking CPU' on real hardware." It goes on to explain:
"CFS's task picking logic is based on this p->wait_runtime value and it is thus very simple: it always tries to run the task with the largest p->wait_runtime value. In other words, CFS tries to run the task with the 'gravest need' for more CPU time. So CFS always tries to split up CPU time between runnable tasks as close to 'ideal multitasking hardware' as possible.
"Most of the rest of CFS's design just falls out of this really simple concept, with a few add-on embellishments like nice levels, multiprocessing and various algorithm variants to recognize sleepers."
Credit was given to four developers other than Ingo Molnar: "
Con Kolivas, for pioneering the fair-scheduling approach [story]
; Peter Williams, for smpnice; Mike Galbraith, for interactivity tuning of CFS, Srivatsa Vaddagiri, for group scheduling enhancements [story]".
The CFS scheduler replaces Ingo's own O(1) scheduler which was first proposed on January 3rd, 2002 [story], and merged into the 2.5.2-pre10 kernel a few days later, on January 8th [story].
