O(1) scheduler

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. 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. In Linux, it has replaced the previously used O(n) scheduler. An O(1) scheduler provides "constant time" scheduling services, thus reducing the amount of jitter normally incurred by the invocation of the scheduler. 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.

See also

• Scheduling
• Big O notation
• Completely Fair Scheduler
• Linux kernel
• Ingo Molnár

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 a O(1) scheduler implemented in hardware
• Inside the Linux scheduler; Written by M. Tim Jones, an IBM developerWorks article
• A closer look at the Linux O(1) scheduler; HP Research Labs