O(1) scheduler
Historical Linux 2.6 kernel process scheduler
- 2 min read
- 4 chapters
Related on Lably
Through Big O notation, Process (computing) and Operating system
In the realm of real-time operating systems, deterministic execution is key, and an O(1) scheduler was able to provide scheduling services with a fixed upper-bound on execution times.
The O(1) scheduler was used in Linux releases 2.6.0 through 2.6.22 (2003-2007), at which point it was superseded by the Completely Fair Scheduler.
Overview
The Linux scheduler was overhauled completely with the release of kernel 2.6 in 2003. The new scheduler was 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.
Sign in to keep reading
3 more chapters are free with a Lably account.
Improvement in Linux scheduler performance
The Linux 2.6.8.1 scheduler did 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 2.6.8.1 scheduler that allow for it to perform its duties in O(1) time, and its design revolves around runqueues and priority arrays.
Issues
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 were complex and subject to potential miscalculations, causing non-interactive behavior from an interactive process.
Replacement
In 2.6.23 (October 2007), the Completely Fair Scheduler was introduced, replacing the O(1) Scheduler. 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."