Fairer Algorithms
Technically, the name "Completely Fair Scheduler" is not entirely correct, since the algorithm only guarantees the "unfair" level to be less than, where is the number of processes. There are more complicated algorithms which can give better bounds over the "unfair" levels (e.g. ).
The Linux kernel received a patch for CFS in November 2010 for the 2.6.38 kernel that has made the scheduler fairer for use on desktops and workstations. Developed by Mike Galbraith using ideas suggested by Linus Torvalds the patch is expected to significantly boost multi-tasking performance on most systems in that class. The explanation of the basic algorithm implementation was included by Mike Galbraith in a LKML post by him about the patch:
|
Each task's signal struct contains an inherited pointer to a refcounted autogroup struct containing a task group pointer, the default for all tasks pointing to the init_task_group. When a task calls __proc_set_tty, the process wide reference to the default group is dropped, a new task group is created, and the process is moved into the new task group. Children thereafter inherit this task group, and increase its refcount. On exit, a reference to the current task group is dropped when the last reference to each signal struct is dropped. The task group is destroyed when the last signal struct referencing it is freed. At runqueue selection time, IFF a task has no cgroup assignment, its current autogroup is used. The feature is enabled from boot by default if CONFIG_SCHED_AUTOGROUP is selected, but can be disabled via the boot option noautogroup, and can be also be turned on/off on the fly. |
The primary issues solved by this are for multi-core as well as multi-cpu (SMP) systems experiencing increased interactive response times while performing other tasks that use many threads in those tasks. A simple explanation is that one will be able to still watch a video, read email and perform other typical desktop activities without glitches or choppiness while compiling the Linux kernel or a similar process such as encoding video. However there are objections on this statement.
This patch implements the tty task group creation only for fair class tasks and, as such, leaves the way open for enhancement. Even at this basic implementation this patch can make Linux on the desktop a reality for all those who have found desktop performance to be less than desired. As Linus put it:
| So I think this is firmly one of those "real improvement" patches. Good job. Group scheduling goes from "useful for some specific server loads" to "that's a killer feature". |
Read more about this topic: Completely Fair Scheduler
Famous quotes containing the word fairer:
“Apart from letters, it is the vulgar custom of the moment to deride the thinkers of the Victorian and Edwardian eras; yet there has not been, in all history, another age ... when so much sheer mental energy was directed toward creating a fairer social order.”
—Ellen Glasgow (1873–1945)