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. The scheduler used thereafter is the Completely Fair Scheduler, which runs in O(log N) time.

[edit] Meaning of O(1)

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.

[edit] See also

[edit] External links