||This article provides insufficient context for those unfamiliar with the subject. (October 2009)|
An O(1) 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. In Linux, it has replaced the previously used O(n) scheduler. One of the major goals of operating system designers is to minimize overhead and jitter of OS services, so that application programmers who use them endure less of a performance impact. O(1) scheduler providing "constant time" scheduling services has helped in this regard.
In the realm of real-time operating systems, deterministic execution is key, and an O(1) scheduler is able to provide scheduling services with a fixed upper-bound on execution times. In versions of Linux kernel 2.6 prior to 2.6.23, the scheduler used is an O(1) scheduler by Ingo Molnár. The scheduler used thereafter is the Completely Fair Scheduler, also by Ingo Molnár, which runs in O(log N) time.
The Linux scheduler was overhauled completely with the release of kernel 2.6. This new scheduler is called the O(1) scheduler. The algorithm used by the O(1) scheduler relies on active and expired arrays of processes to achieve constant scheduling time. Each process is given a fixed time quantum, after which it is preempted and moved to the expired array. Once all the tasks from the active array have exhausted their time quantum and have been moved to the expired array, an array switch takes place. Because the arrays are accessed only via pointer, switching them is as fast as swapping two pointers. This switch makes the active array the new empty expired array, while the expired array becomes the active array.
About O(1) Algorithm
An algorithm operates on input, and the size of that input usually determines its running time. Big O notation is used to denote the growth rate of an algorithm’s execution time based on the amount of input. For example - the running time of an O(n) algorithm increases linearly as the input size n grows. The running time of an O(nˆ2) algorithm grows quadratically. If it is possible to establish a constant upper bound on the running time of an algorithm, it is considered to be O(1) (one might say it runs in “constant time”). That is, an O(1) algorithm is guaranteed to complete in a certain amount of time regardless of the size of the input.
Improvement in Linux Scheduler Performance
The Linux 18.104.22.168 scheduler does not contain any algorithms that run in worse than O(1) time. That is, every part of the scheduler is guaranteed to execute within a certain constant amount of time regardless of how many tasks are on the system. This allows the Linux kernel to efficiently handle massive numbers of tasks without increasing overhead costs as the number of tasks grows. There are two key data structures in the Linux 22.214.171.124 scheduler that allow for it to perform its duties in O(1) time, and its design revolves around them - runqueues and priority arrays.
The main issue with this algorithm is the complex heuristics used to mark a task as interactive or non-interactive. The algorithm tries to identify interactive processes by analyzing average sleep time (the amount of time the process spends waiting for input). Processes that sleep for long periods of time probably are waiting for user input, so the scheduler assumes they're interactive. The scheduler gives a priority bonus to interactive tasks (for better throughput) while penalizing non-interactive tasks by lowering their priorities. All the calculations to determine the interactivity of tasks are complex and subject to potential miscalculations, causing non-interactive behavior from an interactive process.
Then, Completely Fair Scheduler was introduced. According to Ingo Molnar, the author of the CFS, its core design can be summed up in single sentence: “CFS basically models an 'ideal, precise multitasking CPU' on real hardware.”
- Chandandeep Singh Pabla. "Completely Fair Scheduler". Retrieved 2014-09-09.
- Robert Love. "The Linux Process Scheduler". Retrieved 2014-09-09.
- dws. "An informal introduction to O(N) notation". Retrieved 2014-09-09.
- Rob Bell. "A Beginner’s Guide to Big O Notation". Retrieved 2014-09-09.
- Josh Aas. "Understanding the Linux 126.96.36.199 CPU Scheduler" (PDF). Retrieved 2014-09-09.
- Understanding the Linux 188.8.131.52 CPU Scheduler; Josh Aas, 17 February 2005
- HybridThreads (Hthreads); A HW/SW co-designed POSIX-compatible OS featuring an O(1) scheduler implemented in hardware
- Inside the Linux scheduler; Written by M. Tim Jones, an IBM developerWorks article
- David Mosberger. "A closer look at the Linux O(1) scheduler". HP Research Labs. Archived from the original on 16 March 2012.