O(1) scheduler
Encyclopedia
An O 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 system
s, 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.
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.
Scheduling (computing)
In computer science, a scheduling is the method by which threads, processes or data flows are given access to system resources . This is usually done to load balance a system effectively or achieve a target quality of service...
design that can schedule processes
Process (computing)
In computing, a process is an instance of a computer program that is being executed. It contains the program code and its current activity. Depending on the operating system , a process may be made up of multiple threads of execution that execute instructions concurrently.A computer program is a...
within a constant amount of time, regardless of how many processes are running on the operating system
Operating system
An operating system is a set of programs that manage computer hardware resources and provide common services for application software. The operating system is the most important type of system software in a computer system...
. One of the major goals of operating system designers is to minimize overhead
Computational overhead
In computer science, overhead is generally considered any combination of excess or indirect computation time, memory, bandwidth, or other resources that are required to attain a particular goal...
and jitter
Jitter
Jitter is the undesired deviation from true periodicity of an assumed periodic signal in electronics and telecommunications, often in relation to a reference clock source. Jitter may be observed in characteristics such as the frequency of successive pulses, the signal amplitude, or phase of...
of OS services, so that application programmers who use them endure less of a performance impact. In Linux
Linux
Linux is a Unix-like computer operating system assembled under the model of free and open source software development and distribution. The defining component of any Linux system is the Linux kernel, an operating system kernel first released October 5, 1991 by Linus Torvalds...
, it has replaced the previously used O(n) scheduler
O(n) scheduler
The O scheduler is the scheduler used in the Linux kernel between versions 2.4 and 2.6. Since version 2.6, it has been replaced by the O scheduler and later by the Completely Fair Scheduler .- Algorithm :...
. 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 system
Real-time operating system
A real-time operating system is an operating system intended to serve real-time application requests.A key characteristic of a RTOS is the level of its consistency concerning the amount of time it takes to accept and complete an application's task; the variability is jitter...
s, 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
Linux kernel
The Linux kernel is an operating system kernel used by the Linux family of Unix-like operating systems. It is one of the most prominent examples of free and open source software....
2.6 prior to 2.6.23, the scheduler used is an O(1) scheduler by Ingo Molnár
Ingo Molnar
Ingo Molnár, currently employed by Red Hat, is a Hungarian Linux hacker. He is best known for his contributions to the operating system in terms of security and performance...
. The scheduler used thereafter is the Completely Fair Scheduler
Completely Fair Scheduler
The Completely Fair Scheduler is the name of a task scheduler which was merged into the 2.6.23 release of the Linux kernel. It handles CPU resource allocation for executing processes, and aims to maximize overall CPU utilization while also maximizing interactive performance.Con Kolivas's work with...
, 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 notationBig O notation
In mathematics, big O notation is used to describe the limiting behavior of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions. It is a member of a larger family of notations that is called Landau notation, Bachmann-Landau notation, or...
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
- SchedulingScheduling (computing)In computer science, a scheduling is the method by which threads, processes or data flows are given access to system resources . This is usually done to load balance a system effectively or achieve a target quality of service...
- Big O notationBig O notationIn mathematics, big O notation is used to describe the limiting behavior of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions. It is a member of a larger family of notations that is called Landau notation, Bachmann-Landau notation, or...
- Completely Fair SchedulerCompletely Fair SchedulerThe Completely Fair Scheduler is the name of a task scheduler which was merged into the 2.6.23 release of the Linux kernel. It handles CPU resource allocation for executing processes, and aims to maximize overall CPU utilization while also maximizing interactive performance.Con Kolivas's work with...
- Linux kernelLinux kernelThe Linux kernel is an operating system kernel used by the Linux family of Unix-like operating systems. It is one of the most prominent examples of free and open source software....
- Ingo MolnárIngo MolnarIngo Molnár, currently employed by Red Hat, is a Hungarian Linux hacker. He is best known for his contributions to the operating system in terms of security and performance...
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