Completely Fair Scheduler

From Wikipedia, the free encyclopedia

The Completely Fair Scheduler is the name of a task scheduler which was merged into the 2.6.23 release of the Linux kernel. It handles CPU resource allocation for executing processes, and aims to maximize overall CPU utilization while maximizing interactive performance.

Con Kolivas's work with CPU scheduling, most significantly his implementation of "fair scheduling" named Rotating Staircase Deadline, inspired Ingo Molnar to develop his CFS, as a replacement for the earlier O(1) scheduler, crediting Kolivas in his announcement.^[1]

In contrast to the previous O(1) scheduler used in older Linux 2.6 kernels, the CFS scheduler implementation is not based on run queues. Instead a red-black tree implements a 'timeline' of future task execution. Additionally, the scheduler uses nanosecond granularity accounting, the atomic units by which an individual process' share of the CPU was allocated (thus making redundant the previous notion of timeslices). This precise knowledge also means that no specific heuristics are required to determine the interactivity of a process, for example.^[2]

Like the old O(1) scheduler, CFS utilizes a concept called "sleeper fairness", which considers sleeping or waiting tasks equivalent to those on the runqueue. This means that interactive tasks which spend most of their time waiting for user input or other events get a comparable share of CPU time when they need it.

[edit] OS background

This section may be confusing or unclear to readers. Please help clarify the article; suggestions may be found on the talk page. (October 2009)

From Molnar's description, CFS is an implementation of a well-studied, classic scheduling algorithm called fair queuing.^{[citation needed]}

Originally invented for packet networks, it had been previously applied to CPU scheduling under the name stride scheduling. However, it uses different terminology than normally applied to fair queuing; "service error" (the amount in which a process's obtained CPU share differs from its expected CPU share) is called "wait_runtime"; the term "queue virtual time" (QVT) was given the name "fair_clock" in Linux's adaptation.

The fair queuing CFS scheduler has a scheduling complexity of O(log N), where N is the number of tasks in the runqueue. Choosing a task can be done in constant time, but reinserting a task after it has run requires O(log N) operations, because the runqueue is implemented as a red-black tree.

CFS is the first implementation of a fair queuing process scheduler widely used in a general-purpose operating system.^{[citation needed]}

Technically, the name "Completely Fair Scheduler" is not entirely correct, since the algorithm only guarantees the "unfair" level to be less than O(n), where n is the number of processes. There are more complicated algorithms^{[clarification needed]} which can give better bound on the "unfair" level (e.g. O(logn)).

[edit] See also

• Staircase Deadline Scheduler
• Fair Share Scheduling

[edit] References