||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. 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.
- 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 a 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.