Editing O(1) scheduler

{{Short description|Historical Linux 2.6 kernel process scheduler}}
[[File:Simplified_Structure_of_the_Linux_Kernel.svg|thumb|Location of the "O(1) scheduler" (a [[process scheduler]]) in a simplified structure of the [[Linux kernel]]]]
An '''O(1) scheduler''' (pronounced "O of 1 scheduler", "Big O of 1 scheduler", or "constant time scheduler") is a [[kernel (operating system)|kernel]] [[scheduling (computing)|scheduling]] design that can schedule [[process (computing)|processes]] within a constant amount of time, regardless of how many processes are running on the [[operating system]]. This is an improvement over  previously used [[O(n) scheduler|O(n) schedulers]], which schedule processes in an amount of time that [[Scaling (geometry)|scales]] linearly based on the amounts of inputs.

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.

The O(1) scheduler was used in Linux releases 2.6.0 through 2.6.22 (2003-2007), at which point it was superseded by the [[Completely Fair Scheduler]].

== Overview ==
The Linux scheduler was overhauled completely with the release of kernel 2.6 in 2003.<ref>{{Cite web|url=https://www.linuxjournal.com/article/6530|title=Introducing the 2.6 Kernel {{!}} Linux Journal|website=www.linuxjournal.com|access-date=2019-07-19}}</ref><ref>{{cite web|url=http://www.linuxjournal.com/magazine/completely-fair-scheduler|title=Completely Fair Scheduler|author=Chandandeep Singh Pabla|date=August 1, 2009|website=linux journal|access-date=2014-09-09}}</ref> The new scheduler was called the O(1) scheduler. The algorithm used by the O(1) scheduler relies on active and expired arrays of processes to achieve constant scheduling time. Each process is given a fixed time quantum, after which it is [[preemption (computing)|preempted]] and moved to the expired array. Once all the tasks from the active array have exhausted their time quantum and have been moved to the expired array, an array switch takes place. Because the arrays are accessed only via pointer, switching them is as fast as swapping two pointers.<ref>{{cite web
|author = Robert Love
|url = http://www.informit.com/articles/article.aspx?p=101760&seqNum=2
|title = The Linux Process Scheduler
|access-date = 2014-09-09
}}</ref> This switch makes the active array the new empty expired array, while the expired array becomes the active array.

== About O(1) notation ==
{{Main|Big O notation}}
An [[algorithm]] operates over an input, and the size of that input usually determines its running time. [[Big O notation]] is used to denote the growth rate of an algorithm's execution time based on the amount of input. For example, the running time of an O(n) algorithm increases linearly as the input size n grows.<ref>{{cite web
|author = dws
|url = http://www.perlmonks.org/?node_id=227909
|title = An informal introduction to O(N) notation
|access-date = 2014-09-09
}}</ref> The running time of an [[Big O notation#Orders of common functions|O(n{{sup|2}})]] algorithm grows [[quadratic time|quadratically]]. If it is possible to establish a constant upper bound on the running time of an algorithm, it is considered to be O(1) (one might say it runs in "constant time"). That is, an O(1) algorithm is guaranteed to complete in a certain amount of time regardless of the size of the input.<ref>{{cite web
|author = Rob Bell
|url = http://rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation/
|title = A Beginner's Guide to Big O Notation
|access-date = 2014-09-09
}}</ref>

== Improvement in Linux scheduler performance ==
The Linux 2.6.8.1 scheduler did not contain any algorithms that run in worse than O(1) time.<ref>{{cite web
|author = Josh Aas
|url = https://github.com/bdaehlie/linux-cpu-scheduler-docs/blob/master/linux_cpu_scheduler.pdf
|title = Understanding the Linux 2.6.8.1 CPU Scheduler
|website = [[GitHub]]
|access-date = 2014-09-09
}}</ref> That is, every part of the scheduler is guaranteed to execute within a certain constant amount of time regardless of how many tasks are on the system. This allows the [[Linux kernel]] to efficiently handle massive numbers of tasks without increasing overhead costs as the number of tasks grows. There are two key data structures in the Linux 2.6.8.1 scheduler that allow for it to perform its duties in O(1) time, and its design revolves around them: [[run queue|runqueues]] and priority arrays.

== Issues ==
The main issue with this algorithm is the complex heuristics used to mark a task as [[interactive computing|interactive]] or non-interactive. The algorithm tries to identify interactive processes by analyzing average sleep time (the amount of time the process spends waiting for input). Processes that sleep for long periods of time probably are waiting for user input, so the scheduler assumes they're interactive. The scheduler gives a priority bonus to interactive tasks (for better throughput) while penalizing non-interactive tasks by lowering their priorities. All the calculations to determine the interactivity of tasks are complex and subject to potential miscalculations,{{citation needed|date=July 2016}} causing non-interactive behavior from an interactive process.

== Replacement ==
In 2.6.23 (October 2007), the [[Completely Fair Scheduler]] was introduced, replacing the O(1) Scheduler. According to Ingo Molnar, the author of the CFS, its core design can be summed up in single sentence: "CFS basically models an 'ideal, precise multitasking CPU' on real hardware."<ref>{{Cite web|url=http://lkml.iu.edu/hypermail/linux/kernel/0705.1/3017.html|title=Linux-Kernel Archive: Re: fair clock use in CFS|last=<mingo@elte.hu>|first=Ingo Molnar|website=lkml.iu.edu|access-date=2018-08-30}}</ref>

==See also==
{{Portal|Linux}}
*[[Time complexity]]
*[[Brain Fuck Scheduler]] (BFS) – a process scheduler designed for the Linux kernel in August 2009 as an alternative to CFS and the O(1) scheduler

==References==
{{Reflist}}

== External links ==
* [https://web.archive.org/web/20131230235336/http://joshaas.net/linux/ Understanding the Linux 2.6.8.1 CPU Scheduler]; Josh Aas, 17 February 2005
* [http://www.ittc.ku.edu/hybridthreads HybridThreads (Hthreads)] {{Webarchive|url=https://web.archive.org/web/20080511154918/http://www.ittc.ku.edu/hybridthreads |date=2008-05-11 }}; a HW/SW co-designed POSIX-compatible OS featuring an O(1) scheduler implemented in hardware
* [https://www.ibm.com/developerworks/library/l-scheduler/index.html Inside the Linux scheduler]; by M. Tim Jones, an IBM developerWorks article
* {{cite web |author=David Mosberger |title=A closer look at the Linux O(1) scheduler |publisher=HP Research Labs |url=http://www.hpl.hp.com/research/linux/kernel/o1.php |archive-url=https://web.archive.org/web/20120316072525/http://www.hpl.hp.com/research/linux/kernel/o1.php |archive-date=16 March 2012 }}

{{Linux kernel}}

[[Category:Linux kernel process schedulers]]