- 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.
Meaning of O(1)
O(1) does not mean the scheduler is necessarily extremely fast. Big O notation does not make any statements about speed or execution time. As stated above, O(1) simply means that no matter how many tasks there are in the system, scheduling them takes at most some constant amount of time, however many tasks there might be. This constant amount of time (potentially) needed may be considered "slow" or "fast" when compared to other schedulers under a typical load.
See also
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
Categories:- Scheduling algorithms
- Linux kernel
Wikimedia Foundation. 2010.
