Completely Fair Scheduler
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 also maximizing interactive performance.
Con Kolivas
's work with CPU scheduling
, most significantly his implementation of "fair scheduling
" named Rotating Staircase Deadline
, inspired Ingo Molnár
to develop his CFS, as a replacement for the earlier O(1) scheduler
, crediting Kolivas in his announcement.
In contrast to the previous O(1) scheduler
used in older Linux 2.6 kernels, the CFS scheduler implementation is not based on run queue
s. 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.
Like the old O(1) scheduler, CFS uses 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.
, using the spent processor time as a key. This allows it to pick efficiently the process that has used the least amount of time (it is stored in the leftmost node of the tree). The entry of the picked process is then removed from the tree, the spent execution time is updated and the entry is then returned to the tree where it normally takes some other location. The new leftmost node is then picked from the tree, repeating the iteration.
If the task spends a lot of its time sleeping, then its spent time value is low and it automatically gets the priority boost when it finally needs it. Hence such tasks do not get less processor time than the tasks that are constantly running.
Originally invented for packet networks, fair queuing had been previously applied to CPU scheduling under the name stride scheduling
. However, CFS 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" in Linux's implementation, and the term "queue virtual time" (QVT) was given the name "fair_clock".
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.
, 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:
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:
from Red Hat pointed out that this change is a policy, which is against the Unix philosophy of implementing "mechanism, not policy." He also gave an equivalent implementation in shell script that was supposed to achieve the same result in userspace to prove although this patch demonstrates an optimization, there is no point to implement it in the kernel. The script was tested by Markus Trippelsdorf and appeared to work better than the kernel patch.
Lennart Poettering also doubted the usefulness of the patch, as he explained to the reader,
Linus confirmed this indirectly in his other post,
Scheduling (computing)
In computer science, a scheduling is the method by which threads, processes or data flows are given access to system resources . This is usually done to load balance a system effectively or achieve a target quality of service...
which was merged into the 2.6.23 release of the Linux
Linux
Linux is a Unix-like computer operating system assembled under the model of free and open source software development and distribution. The defining component of any Linux system is the Linux kernel, an operating system kernel first released October 5, 1991 by Linus Torvalds...
kernel
Linux kernel
The Linux kernel is an operating system kernel used by the Linux family of Unix-like operating systems. It is one of the most prominent examples of free and open source software....
. It handles CPU
Central processing unit
The central processing unit is the portion of a computer system that carries out the instructions of a computer program, to perform the basic arithmetical, logical, and input/output operations of the system. The CPU plays a role somewhat analogous to the brain in the computer. The term has been in...
resource allocation for executing processes
Process (computing)
In computing, a process is an instance of a computer program that is being executed. It contains the program code and its current activity. Depending on the operating system , a process may be made up of multiple threads of execution that execute instructions concurrently.A computer program is a...
, and aims to maximize overall CPU utilization while also maximizing interactive performance.
Con Kolivas
Con Kolivas
Con Kolivas is an Australian anaesthetist who is known on the Internet for his programming work on the Linux kernel in his spare time. He has written patches for the kernel to improve its desktop performance, particularly reducing I/O impact...
's work with CPU scheduling
Scheduling (computing)
In computer science, a scheduling is the method by which threads, processes or data flows are given access to system resources . This is usually done to load balance a system effectively or achieve a target quality of service...
, most significantly his implementation of "fair scheduling
Fair-share scheduling
Fair-share scheduling is a scheduling strategy for computer operating systems in which the CPU usage is equally distributed among system users or groups, as opposed to equal distribution among processes....
" named Rotating Staircase Deadline
Con Kolivas
Con Kolivas is an Australian anaesthetist who is known on the Internet for his programming work on the Linux kernel in his spare time. He has written patches for the kernel to improve its desktop performance, particularly reducing I/O impact...
, inspired Ingo Molnár
Ingo Molnar
Ingo Molnár, currently employed by Red Hat, is a Hungarian Linux hacker. He is best known for his contributions to the operating system in terms of security and performance...
to develop his CFS, as a replacement for the earlier O(1) scheduler
O(1) scheduler
An O scheduler is a kernel scheduling design that can schedule processes within a constant amount of time, regardless of how many processes are running on the operating system. One of the major goals of operating system designers is to minimize overhead and jitter of OS services, so that...
, crediting Kolivas in his announcement.
In contrast to the previous O(1) scheduler
O(1) scheduler
An O scheduler is a kernel scheduling design that can schedule processes within a constant amount of time, regardless of how many processes are running on the operating system. One of the major goals of operating system designers is to minimize overhead and jitter of OS services, so that...
used in older Linux 2.6 kernels, the CFS scheduler implementation is not based on run queue
Run queue
In modern computers many processes run at once. Active processes are placed in an array called a run queue, or runqueue. The run queue may contain priority values for each process, which will be used by the scheduler to determine which process to run next...
s. Instead, a red-black tree
Red-black tree
A red–black tree is a type of self-balancing binary search tree, a data structure used in computer science, typically to implement associative arrays. The original structure was invented in 1972 by Rudolf Bayer and named "symmetric binary B-tree," but acquired its modern name in a paper in 1978 by...
implements a "timeline" of future task execution. Additionally, the scheduler uses nanosecond
Nanosecond
A nanosecond is one billionth of a second . One nanosecond is to one second as one second is to 31.7 years.The word nanosecond is formed by the prefix nano and the unit second. Its symbol is ns....
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.
Like the old O(1) scheduler, CFS uses 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.
Algorithm
The scheduler stores the records about the planned tasks in a red-black treeRed-black tree
A red–black tree is a type of self-balancing binary search tree, a data structure used in computer science, typically to implement associative arrays. The original structure was invented in 1972 by Rudolf Bayer and named "symmetric binary B-tree," but acquired its modern name in a paper in 1978 by...
, using the spent processor time as a key. This allows it to pick efficiently the process that has used the least amount of time (it is stored in the leftmost node of the tree). The entry of the picked process is then removed from the tree, the spent execution time is updated and the entry is then returned to the tree where it normally takes some other location. The new leftmost node is then picked from the tree, repeating the iteration.
If the task spends a lot of its time sleeping, then its spent time value is low and it automatically gets the priority boost when it finally needs it. Hence such tasks do not get less processor time than the tasks that are constantly running.
OS background
From Molnar's description, CFS is an implementation of a well-studied, classic scheduling algorithm called fair queuing.Originally invented for packet networks, fair queuing had been previously applied to CPU scheduling under the name stride scheduling
Stride scheduling
Stride scheduling mechanism has been introduced as a simple concept to achieve proportional CPU capacity reservation among concurrent processes. Stride scheduling aims to sequentially allocate a resource for the duration of standard time-slices in a fashion, that performs periodic recurrences of...
. However, CFS 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" in Linux's implementation, and the term "queue virtual time" (QVT) was given the name "fair_clock".
The fair queuing CFS scheduler has a scheduling complexity of O(log
Logarithm
The logarithm of a number is the exponent by which another fixed value, the base, has to be raised to produce that number. For example, the logarithm of 1000 to base 10 is 3, because 1000 is 10 to the power 3: More generally, if x = by, then y is the logarithm of x to base b, and is written...
N), where N is the number of tasks in the runqueue
Run queue
In modern computers many processes run at once. Active processes are placed in an array called a run queue, or runqueue. The run queue may contain priority values for each process, which will be used by the scheduler to determine which process to run next...
. 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
Red-black tree
A red–black tree is a type of self-balancing binary search tree, a data structure used in computer science, typically to implement associative arrays. The original structure was invented in 1972 by Rudolf Bayer and named "symmetric binary B-tree," but acquired its modern name in a paper in 1978 by...
.
CFS is the first implementation of a fair queuing process scheduler widely used in a general-purpose operating system.
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
Linus Torvalds
Linus Benedict Torvalds is a Finnish software engineer and hacker, best known for having initiated the development of the open source Linux kernel. He later became the chief architect of the Linux kernel, and now acts as the project's coordinator...
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:
The primary issues solved by this are for multi-core as well as multi-cpu (SMP
Symmetric multiprocessing
In computing, symmetric multiprocessing involves a multiprocessor computer hardware architecture where two or more identical processors are connected to a single shared main memory and are controlled by a single OS instance. Most common multiprocessor systems today use an SMP architecture...
) 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
Linux kernel
The Linux kernel is an operating system kernel used by the Linux family of Unix-like operating systems. It is one of the most prominent examples of free and open source software....
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
Linux
Linux is a Unix-like computer operating system assembled under the model of free and open source software development and distribution. The defining component of any Linux system is the Linux kernel, an operating system kernel first released October 5, 1991 by Linus Torvalds...
on the desktop a reality for all those who have found desktop performance to be less than desired.
As Linus
Linus Torvalds
Linus Benedict Torvalds is a Finnish software engineer and hacker, best known for having initiated the development of the open source Linux kernel. He later became the chief architect of the Linux kernel, and now acts as the project's coordinator...
put it:
Controversy
In the same LKML post, Lennart PoetteringLennart Poettering
Lennart Poettering is a computer programmer, best known for the creation of the PulseAudio cross-platform sound server, the systemd replacement for the System V init daemon, and the Avahi zeroconf implementation....
from Red Hat pointed out that this change is a policy, which is against the Unix philosophy of implementing "mechanism, not policy." He also gave an equivalent implementation in shell script that was supposed to achieve the same result in userspace to prove although this patch demonstrates an optimization, there is no point to implement it in the kernel. The script was tested by Markus Trippelsdorf and appeared to work better than the kernel patch.
Lennart Poettering also doubted the usefulness of the patch, as he explained to the reader,
Linus confirmed this indirectly in his other post,
See also
- Brain Fuck SchedulerBrain Fuck SchedulerThe Brain Fuck Scheduler is a task scheduler designed for the Linux kernel in August of 2009 as an alternative to the Completely Fair Scheduler and the O scheduler...
- Staircase Deadline SchedulerCon KolivasCon Kolivas is an Australian anaesthetist who is known on the Internet for his programming work on the Linux kernel in his spare time. He has written patches for the kernel to improve its desktop performance, particularly reducing I/O impact...
- Fair Share SchedulingFair-share schedulingFair-share scheduling is a scheduling strategy for computer operating systems in which the CPU usage is equally distributed among system users or groups, as opposed to equal distribution among processes....