Completely Fair Scheduler
   HOME

TheInfoList



OR:

The Completely Fair Scheduler (CFS) is a
process scheduler In computing, scheduling is the action of assigning ''resources'' to perform ''tasks''. The ''resources'' may be processors, network links or expansion cards. The ''tasks'' may be threads, processes or data flows. The scheduling activity is ca ...
that was merged into the 2.6.23 (October 2007) release of the
Linux Linux ( or ) is a family of open-source Unix-like operating systems based on the Linux kernel, an operating system kernel first released on September 17, 1991, by Linus Torvalds. Linux is typically packaged as a Linux distribution, w ...
kernel Kernel may refer to: Computing * Kernel (operating system), the central component of most operating systems * Kernel (image processing), a matrix used for image convolution * Compute kernel, in GPGPU programming * Kernel method, in machine learn ...
and is the default scheduler of the tasks of the SCHED_NORMAL class (i.e., tasks that have no real-time execution constraints). It handles CPU resource allocation for executing processes, and aims to maximize overall CPU utilization while also maximizing interactive performance. In contrast to the previous
O(1) scheduler An O(1) scheduler (pronounced "O of 1 scheduler", "Big O of 1 scheduler", or "constant time 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 ...
used in older Linux 2.6 kernels, which maintained and switched run queues of active and expired tasks, the CFS scheduler implementation is based on per-CPU run queues, whose nodes are time-ordered schedulable entities that are kept sorted by red–black trees. The CFS does away with the old notion of per-priorities fixed time-slices and instead it aims at giving a fair share of CPU time to tasks (or, better, schedulable entities).


Algorithm

A task (i.e., a synonym for thread) is the minimal entity that Linux can schedule. However, it can also manage groups of threads, whole multi-threaded processes, and even all the processes of a given user. This design leads to the concept of schedulable entities, where tasks are grouped and managed by the scheduler as a whole. For this design to work, each task_struct task descriptor embeds a field of type sched_entity that represents the set of entities the task belongs to. Each per-CPU run-queue of type cfs_rq sorts sched_entity structures in a time-ordered fashion into a red-black tree (or 'rbtree' in Linux lingo), where the leftmost node is occupied by the entity that has received the least slice of execution time (which is saved in the vruntime field of the entity). The nodes are indexed by processor "''execution time''" in nanoseconds. A "''maximum execution time''" is also calculated for each process to represent the time the process would have expected to run on an "ideal processor". This is the time the process has been waiting to run, divided by the total number of processes. When the scheduler is invoked to run a new process: # The leftmost node of the scheduling tree is chosen (as it will have the lowest spent ''execution time''), and sent for execution. # If the process simply completes execution, it is removed from the system and scheduling tree. # If the process reaches its ''maximum execution time'' or is otherwise stopped (voluntarily or via interrupt) it is reinserted into the scheduling tree based on its newly spent ''execution time''. # The new leftmost node will then be selected from the tree, repeating the iteration. If the process 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. The complexity of the algorithm that inserts nodes into the cfs_rq runqueue of the CFS scheduler is O(
log Log most often refers to: * Trunk (botany), the stem and main wooden axis of a tree, called logs when cut ** Logging, cutting down trees for logs ** Firewood, logs used for fuel ** Lumber or timber, converted from wood logs * Logarithm, in mathe ...
N), where N is the total number of entities. Choosing the next entity to run is made in constant time because the leftmost node is always cached.


History

Con Kolivas's work with scheduling, most significantly his implementation of " fair scheduling" named
Rotating Staircase Deadline Con Kolivas is an Australian anaesthetist.Anaesthesia Information Page
by Kolivas, Jan 2001
He ...
, inspired
Ingo Molnár Ingo Molnár, employed by Red Hat as of May 2013, is a Hungarian Linux hacker. He is known for his contributions to the operating system in terms of security and performance. Life and career Molnár studied at Eötvös Loránd University. Wo ...
to develop his CFS, as a replacement for the earlier
O(1) scheduler An O(1) scheduler (pronounced "O of 1 scheduler", "Big O of 1 scheduler", or "constant time 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 ...
, crediting Kolivas in his announcement. CFS is an implementation of a well-studied, classic scheduling algorithm called
weighted fair queuing Weighted fair queueing (WFQ) is a network scheduling algorithm. WFQ is both a packet-based implementation of the generalized processor sharing (GPS) policy, and a natural extension of fair queuing (FQ). Whereas FQ shares the link's capacity in ...
. Originally invented for
packet network In telecommunications, packet switching is a method of grouping data into '' packets'' that are transmitted over a digital network. Packets are made of a header and a payload. Data in the header is used by networking hardware to direct the pack ...
s, fair queuing had been previously applied to CPU scheduling under the name
stride scheduling The stride scheduling is a type of scheduling mechanism that 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 ...
. CFS is the first implementation of a fair queuing
process scheduler In computing, scheduling is the action of assigning ''resources'' to perform ''tasks''. The ''resources'' may be processors, network links or expansion cards. The ''tasks'' may be threads, processes or data flows. The scheduling activity is ca ...
widely used in a general-purpose operating system. 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 Benedict Torvalds ( , ; born 28 December 1969) is a Finnish software engineer who is the creator and, historically, the lead developer of the Linux kernel, used by Linux distributions and other operating systems such as Android. He also ...
, the patch implements a feature called autogrouping that significantly boosts interactive desktop performance. The algorithm puts parent processes in the same task group as child processes. (Task groups are tied to sessions created via th
setsid()
system call.) This solved the problem of slow interactive response times on multi-core and multi-CPU ( SMP) systems when they were performing other tasks that use many CPU-intensive threads in those tasks. A simple explanation is that, with this patch applied, one is able to still watch a video, read email and perform other typical desktop activities without glitches or choppiness while, say, compiling the Linux kernel or encoding video. In 2016, the Linux scheduler was patched for better multicore performance, based on the suggestions outlined in the paper, "The Linux Scheduler: A Decade of Wasted Cores".


See also

*
Brain Fuck Scheduler The Brain Fuck Scheduler (BFS) is a process scheduler designed for the Linux kernel in August 2009 as an alternative to the Completely Fair Scheduler (CFS) and the O(1) scheduler. BFS was created by an experienced kernel programmer Con Koliv ...
*
SCHED_DEADLINE SCHED_DEADLINE is a CPU scheduler available in the Linux kernel since version 3.14,
Linux Weekly News, Deadline scheduling for Lin ...


References


External links

* * * * * * * * {{Linux kernel Linux kernel process schedulers Free software