Open main menu
Home
Random
Recent changes
Special pages
Community portal
Preferences
About Wikipedia
Disclaimers
Incubator escapee wiki
Search
User menu
Talk
Dark mode
Contributions
Create account
Log in
Editing
Scheduling (computing)
(section)
Warning:
You are not logged in. Your IP address will be publicly visible if you make any edits. If you
log in
or
create an account
, your edits will be attributed to your username, along with other benefits.
Anti-spam check. Do
not
fill this in!
===Linux=== {{See also|Linux kernel#Scheduling}} ==== Linux 1.2 ==== Linux 1.2 used a [[round-robin scheduling]] policy.<ref name=":0">{{Cite web |last=Jones |first=M. |date=2018-09-18 |orig-date=first published on 2009-12-14 |title=Inside the Linux 2.6 Completely Fair Scheduler |url=https://developer.ibm.com/tutorials/l-completely-fair-scheduler/ |access-date=2024-02-07 |website=developer.ibm.com}}</ref> ==== Linux 2.2 ==== Linux 2.2 added scheduling classes and support for [[symmetric multiprocessing]] (SMP).<ref name=":0" />[[File:Simplified Structure of the Linux Kernel.svg|thumb|upright=1.5|A highly simplified structure of the Linux kernel, which includes process schedulers, I/O schedulers, and [[Linux kernel packet scheduler|packet schedulers]] ]] ====Linux 2.4==== In [[Linux]] 2.4,<ref name=":0" /> an [[O(n) scheduler]] with a [[multilevel feedback queue]] with priority levels ranging from 0 to 140 was used; 0–99 are reserved for real-time tasks and 100–140 are considered [[nice (Unix)|nice]] task levels. For real-time tasks, the time quantum for switching processes was approximately 200 ms, and for nice tasks approximately 10 ms.{{citation needed|date=December 2011}} The scheduler ran through the [[run queue]] of all ready processes, letting the highest priority processes go first and run through their time slices, after which they will be placed in an expired queue. When the active queue is empty the expired queue will become the active queue and vice versa. However, some enterprise [[Linux distributions]] such as [[SUSE Linux Enterprise Server]] replaced this scheduler with a backport of the [[O(1) scheduler]] (which was maintained by [[Alan Cox (computer programmer)|Alan Cox]] in his Linux 2.4-ac Kernel series) to the Linux 2.4 kernel used by the distribution. ====Linux 2.6.0 to Linux 2.6.22==== In versions 2.6.0 to 2.6.22, the kernel used an [[O(1) scheduler]] developed by [[Ingo Molnar]] and many other kernel developers during the Linux 2.5 development. For many kernel in time frame, [[Con Kolivas]] developed patch sets which improved interactivity with this scheduler or even replaced it with his own schedulers. ====Linux 2.6.23 to Linux 6.5==== Con Kolivas' work, most significantly his implementation of [[fair-share scheduling|fair scheduling]] named [[Rotating Staircase Deadline]] (RSDL), inspired Ingo Molnár to develop the [[Completely Fair Scheduler]] (CFS) as a replacement for the earlier [[O(1) scheduler]], crediting Kolivas in his announcement.<ref>{{cite mailing list | last=Molnár | first=Ingo | author-link=Ingo Molnár | title=[patch] Modular Scheduler Core and Completely Fair Scheduler [CFS] | url=https://lwn.net/Articles/230501/ | mailing-list=linux-kernel | date=2007-04-13}}</ref> CFS is the first implementation of a fair queuing [[process scheduler]] widely used in a general-purpose operating system.<ref name="dwrr">{{cite web|url=http://happyli.org/tongli/papers/dwrr.pdf|title=Efficient and Scalable Multiprocessor Fair Scheduling Using Distributed Weighted Round-Robin|author1=Tong Li|author2=Dan Baumberger|author3=Scott Hahn|website=Happyli.org|access-date=2016-12-09}}</ref> The CFS uses a well-studied, classic scheduling algorithm called [[fair queuing]] originally invented for [[packet network]]s. Fair queuing had been previously applied to CPU scheduling under the name [[stride scheduling]]. The fair queuing CFS scheduler has a scheduling complexity of <math>O(\log N)</math>, where {{mvar|N}} is the number of tasks in the [[run queue|runqueue]]. Choosing a task can be done in constant time, but reinserting a task after it has run requires <math>O(\log N)</math> operations, because the [[run queue]] is implemented as a [[red–black tree]]. The [[Brain Fuck Scheduler]], also created by Con Kolivas, is an alternative to the CFS. ==== Linux 6.6 ==== In 2023, Peter Zijlstra proposed replacing CFS with an [[earliest eligible virtual deadline first scheduling]] (EEVDF) process scheduler.<ref>{{Cite web |title=EEVDF Scheduler May Be Ready For Landing With Linux 6.6 |url=https://www.phoronix.com/news/Linux-6.6-EEVDF-Likely |access-date=2023-08-31 |website=[[Phoronix]] |language=en}}</ref><ref>{{Cite web |title=EEVDF Scheduler Merged For Linux 6.6, Intel Hybrid Cluster Scheduling Re-Introduced |url=https://www.phoronix.com/news/Linux-6.6-EEVDF-Merged |access-date=2024-02-07 |website=www.phoronix.com |language=en}}</ref> The aim was to remove the need for CFS ''latency nice'' patches.<ref>{{Cite web |title=An EEVDF CPU scheduler for Linux [LWN.net] |url=https://lwn.net/Articles/925371/ |access-date=2023-08-31 |website=[[LWN.net]]}}</ref> ==== Linux 6.12 ==== Linux 6.12 added support for [[User space and kernel space|userspace]] scheduler extensions, also known as sched_ext.<ref>{{Cite web |title=Sched_ext Merged For Linux 6.12 - Scheduling Policies As BPF Programs |url=https://www.phoronix.com/news/Linux-6.12-Lands-sched-ext |access-date=2025-02-10 |website=www.phoronix.com |language=en}}</ref> These schedulers can be installed and replace the default scheduler.<ref>{{Cite web |title=Pluggable CPU schedulers - openSUSE Wiki |url=https://en.opensuse.org/Pluggable_CPU_schedulers |access-date=2025-02-10 |website=en.opensuse.org}}</ref>
Edit summary
(Briefly describe your changes)
By publishing changes, you agree to the
Terms of Use
, and you irrevocably agree to release your contribution under the
CC BY-SA 4.0 License
and the
GFDL
. You agree that a hyperlink or URL is sufficient attribution under the Creative Commons license.
Cancel
Editing help
(opens in new window)