Related Directory Categories
Sources
Help build the largest human-edited directory on the web.
Submit a site - Become an editor
Wikipedia. Licensed under the GNU Free Documentation License.
Are you an expert in this subject? Join the discussion and share your knowledge at Wikipedia.org.
O(1) scheduler
From Wikipedia, the free encyclopedia
 |
The introduction to this article provides insufficient context for those unfamiliar with the subject. Please help improve the article with a good introductory style. |
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 (OS). One of the major goals of OS designers is to minimize the overhead and jitter of OS services so that application programmers feel less of a performance impact when using OS services. A 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 a O(1) scheduler is able to provide scheduling services with a fixed upper-bound on execution times.
Ingo Molnár's scheduler used in versions of the Linux kernel 2.6 prior to 2.6.23 is an O(1) scheduler.
O(1) does not mean the scheduler is super 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 the same amount of time, however much time that may be.
- Understanding the Linux 2.6.8.1 CPU Scheduler; Josh Aas, 17th 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