[News] Explaining the Sophistication of the Linux Scheduler

Kernel space: Fair user scheduling for Linux

,----[ Quote ]
| The Completely Fair Scheduler (CFS) was merged for the 2.6.23 kernel. One CFS
| feature which did not get in, though, was the group scheduling facility.
| Group scheduling makes the CFS fairness algorithm operate in a hierarchical
| fashion: processes are divided into groups, and, within each group, processes
| are scheduled fairly against one another.
`----

[url]http://www.linuxworld.com/news/2007/101207-kernel.html[/url]

That's a /real/ multi-user desktop and server. Not a Solitaire/Minesweeper
foundation with some network addons, slapped in 'security' layer (cancel
allow), and added pseudo-multi-user support.


Related:

[Vista scheduler is broken]

,----[ Quote ]
| Critical optimizations such as zero-copy aside, there is no excusable reason
| why processing IP packets should so damagingly affect the system.
|
| [...]
|
| Putting aside the larger problem for the moment, there are several issues
| with this solution. It prioritizes multimedia playback over networking
| performance, which, as the resulting clamor has shown, is not everyone's
| personal policy preference. It is almost assuredly a layering violation. It
| picks a fixed and hard-coded packet limit (ten per millisecond), which won't
| scale across different hardware—think significantly faster processors or
| substantially slower networking drivers. It ignores the commonality of GigE.
| And, finally, the solution is complicated, as the convoluted description and
| resulting bugs in the implementation demonstrate.
`----

[url]http://blogbeebe.blogspot.com/2007/08/robert-love-backs-up-my-very-simple.html[/url]


CFS, Focusing on Simplification and Performance

,----[ Quote ]
| He added, "we are now a bit faster than the O(1) scheduler was under
| v2.6.22 - even on 32-bit. The main speedup comes from the avoidance of
| divisions (or shifts) in the wakeup and context-switch fastpaths." Â*
`----

[url]http://kerneltrap.org/Linux/CFS_Focusing_on_Simplification_and_Performance[/url]


Defining Scheduler Task Groups

,----[ Quote ]
| Srivatsa requested that his patch be merged into Andrew Morton's -mm tree to
| receive more testing...
`----

[url]http://kerneltrap.org/Linux/Defining_Scheduler_Task_Groups[/url]


Linux: Discussing the Really Fair Scheduler

,----[ Quote ]
| Ingo Molnar reviewed Roman Zippel's Really Fair Scheduler code, suggesting
| that much of the work was similar to that which was being done by Peter
| Zijlstra Â*
`----

[url]http://kerneltrap.org/Linux/Discussing_the_Really_Fair_Scheduler[/url]


Linux: The Really Fair Scheduler

,----[ Quote ]
| He offered a mathematical overview of how his new scheduler works, included
| some benchmarks, and reflected back to earlier discussions on the lkml...
`----

[url]http://kerneltrap.org/Linux/The_Really_Fair_Scheduler[/url]


Syllable Server Video Demonstration

,----[ Quote ]
| Turning our attention to the future, there's a demonstration video of
| Syllable Server, the server companion to Syllable Desktop that is under
| development and is being built on the Linux kernel [torrent, 91 MB AVI
| video]. Â*
`----

[url]http://www.osnews.com/story.php/18470/Syllable-Server-Video-Demonstration/[/url]


Linux: The Original Process Scheduler

,----[ Quote ]
| In a June of 1992 posting to the linux-activists mailing list, Linus Torvalds
| described the original Linux scheduler noting, "the scheduler in linux is
| pretty simple, but does a reasonably good job at giving good IO response
| while not being too unfair against cpu-bound processes." Â*
|
| [...]
|
| Â** Â*1996-12-23 Â*Modified by Dave Grothe to fix bugs in semaphores and
| Â** Â* Â* Â* Â* Â* Â* Â*make semaphores SMP safe
| Â** Â*1998-11-19 Â*Implemented schedule_timeout() and related stuff
| Â** Â* Â* Â* Â* Â* Â* Â*by Andrea Arcangeli
| Â** Â*2002-01-04 Â*New ultra-scalable O(1) scheduler by Ingo Molnar:
| Â** Â* Â* Â* Â* Â* Â* Â*hybrid priority-list and round-robin design with
| Â** Â* Â* Â* Â* Â* Â* Â*an array-switch method of distributing timeslices
| Â** Â* Â* Â* Â* Â* Â* Â*and per-CPU runqueues. Â*Cleanups and useful suggestions
| Â** Â* Â* Â* Â* Â* Â* Â*by Davide Libenzi, preemptible kernel bits by Robert Love.
| Â** Â*2003-09-03 Â*Interactivity tuning by Con Kolivas.
| Â** Â*2004-04-02 Â*Scheduler domains code by Nick Piggin
| Â** Â*2007-04-15 Â*Work begun on replacing all interactivity tuning with a
| Â** Â* Â* Â* Â* Â* Â* Â*fair scheduling design by Con Kolivas.
| Â** Â*2007-05-05 Â*Load balancing (smp-nice) and other improvements
| Â** Â* Â* Â* Â* Â* Â* Â*by Peter Williams
| Â** Â*2007-05-06 Â*Interactivity improvements to CFS by Mike Galbraith
| Â** Â*2007-07-01 Â*Group scheduling enhancements by Srivatsa Vaddagiri
`----

[url]http://kerneltrap.org/node/14191[/url]


Linux: Tuning CFS

,----[ Quote ]
| Nick Piggin used 'git bisect' to track a lmbench regression to the main CFS
| commit, leading to an interesting discussion between Nick and Ingo Molnar. Â*
`----

[url]http://kerneltrap.org/node/14055[/url]


Linux: CFS and 3D Gaming

,----[ Quote ]
| Some of the concerns expressed about the Completely Fair Scheduler were
| reports that it might not handle 3D games as well as the SD scheduler.
`----

[url]http://kerneltrap.org/node/14023[/url]


CFS scheduler to appear in Linux kernel 2.6.23

,----[ Quote ]
| And also credit where credit's due, Con Kolivas was the first one to
| prove via RSDL/SD that 'fair scheduling' is possible and that it
| results in better desktop scheduling.
`----

[url]http://www.linuxinsight.com/cfs-scheduler-to-appear-in-linux-kernel-2.6.23.html[/url]


Linux: Linus On CFS vs SD

,----[ Quote ]
| "People who think SD was 'perfect' were simply ignoring reality," Linus
| Torvalds began in a succinct explanation as to why he chose the CFS scheduler
| written by Ingo Molnar instead of the SD scheduler written by Con Kolivas. Â*
`----

[url]http://kerneltrap.org/node/14008[/url]