The Completely Fair Scheduler (CFS) is the name of a process 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 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.
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.
Read more about Completely Fair Scheduler: Algorithm, OS Background, Fairer Algorithms
Famous quotes containing the words completely and/or fair:
“In compensation for considerable disgust, despondency, and boredom—such as living in solitude without friends, books, duties, or passions necessarily entails—we are given those quarter-hours of deepest communion with ourselves and nature. Those who completely barricade themselves from boredom, barricade themselves from themselves as well: they will never get to drink the most refreshingly potent draught from the their own innermost fountain.”
—Friedrich Nietzsche (1844–1900)
“Most books belong to the house and street only, and in the fields their leaves feel very thin. They are bare and obvious, and have no halo nor haze about them. Nature lies far and fair behind them all. But this, as it proceeds from, so it addresses, what is deepest and most abiding in man. It belongs to the noontide of the day, the midsummer of the year, and after the snows have melted, and the waters evaporated in the spring, still its truth speaks freshly to our experience.”
—Henry David Thoreau (1817–1862)