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 them: 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 are 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." See also Time complexity Brain Fuck Scheduler (BFS) – a process scheduler designed for the Linux kernel in August 2009 as an alternative to CFS and the O(1) scheduler References External links Understanding the Linux 2.6.8.1 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 Linux kernel process schedulers