Scheduling (computing): Difference between revisions

Revision as of 18:12, 30 January 2024

Latest revision as of 02:46, 28 August 2025

(34 intermediate revisions by 15 users not shown)

Line 1:

{{Short description|Method by which work is assigned}}

{{About|scheduling of computing resources|networks|Network scheduler|other uses|Scheduling (disambiguation)}}

In [[computing]], '''scheduling''' is the action of assigning ''resources'' to perform ''tasks''. The ''resources'' may be [[central processing unit|processors]], [[telecommunications link|network links]] or [[expansion card]]s. The ''tasks'' may be [[thread (computer science)|threads]], [[process (computing)|processes]] or data [[flow (computer networking)|flows]].

In [[computing]], '''scheduling''' is the action of assigning ''[[System resource|resources'']] to perform ''[[task (computing)|tasks'']]. The ''resources'' may be [[central processing unit|processors]], [[telecommunications link|network links]] or [[expansion card]]s. The ''tasks'' may be [[thread (computer science)|threads]], [[process (computing)|processes]] or data [[Traffic flow (computer networking)|flows]].

The scheduling activity is carried out by a process called '''scheduler'''. Schedulers are often designed so as to keep all computer resources busy (as in [[load balancing (computing)|load balancing]]), allow multiple users to share system resources effectively, or to achieve a target [[quality of service|quality-of-service]].

The scheduling activity is carried out by a processmechanism called a '''scheduler'''. Schedulers are often designed so as to keep all computer resources busy (as in [[load balancing (computing)|load balancing]]), allow multiple users to share system resources effectively, or to achieve a target [[quality of service|quality-of-service]].

Scheduling is fundamental to computation itself, and an intrinsic part of the [[execution model]] of a computer system; the concept of scheduling makes it possible to have [[computer multitasking]] with a single [[central processing unit]] (CPU).

Line 72 ⟶ 73:

=={{Anchor|SCHEDULER}}Types of operating system schedulers==

{{See also|Network scheduler|I/O scheduling|jobJob scheduler}}

The scheduler is an operating system module that selects the next jobs to be admitted into the system and the next process to run. Operating systems may feature up to three distinct scheduler types: a ''long-term scheduler'' (also known as an admission scheduler or high-level scheduler), a ''mid-term or medium-term scheduler'', and a ''short-term scheduler''. The names suggest the relative frequency with which their functions are performed.

Line 82 ⟶ 83:

===={{Anchor|LONG-TERM}}Long-term scheduling====

The ''long-term scheduler'', or ''admission scheduler'', decides which jobs or processes are to be admitted to the [[ready queue]] (in main memory); that is, when an attempt is made to execute a program, its admission to the set of currently executing processes is either authorized or delayed by the long-term scheduler. Thus, this scheduler dictates what processes are to run on a system, the degree of concurrency to be supported at any one time{{snd}} whether many or few processes are to be executed concurrently, and how the split between I/O-intensive and CPU-intensive processes is to be handled. The long-term scheduler is responsible for controlling the degree of multiprogramming.

In general, most processes can be described as either [[I/O-bound]] or [[CPU-bound]]. An I/O-bound process is one that spends more of its time doing I/O than it spends doing computations. A CPU-bound process, in contrast, generates I/O requests infrequently, using more of its time doing computations. It is important that a long-term scheduler selects a good process mix of I/O-bound and CPU-bound processes. If all processes are I/O-bound, the ready queue will almost always be empty, and the short-term scheduler will have little to do. On the other hand, if all processes are CPU-bound, the I/O waiting queue will almost always be empty, devices will go unused, and again the system will be unbalanced. The system with the best performance will thus have a combination of CPU-bound and I/O-bound processes. In modern operating systems, this is used to make sure that real-time processes get enough CPU time to finish their tasks.<ref name="Galvin">{{cite book

Line 111 ⟶ 112:

===={{Anchor|SHORT-TERM}}Short-term scheduling====

The ''short-term scheduler'' (also known as the ''CPU scheduler'') decides which of the ready, in-memory processes is to be executed (allocated a CPU) after a clock [[interrupt]], an I/O interrupt, an operating [[system call]] or another form of [[Signal programming(IPC)|signal]]. Thus the short-term scheduler makes scheduling decisions much more frequently than the long-term or mid-term schedulers{{snd}} A scheduling decision will at a minimum have to be made after every time slice, and these are very short. This scheduler can be [[Preemption (computing)|preemptive]], implying that it is capable of forcibly removing processes from a CPU when it decides to allocate that CPU to another process, or non-preemptive (also known as ''voluntary'' or ''co-operative''), in which case the scheduler is unable to ''force'' processes off the CPU.

A preemptive scheduler relies upon a [[programmable interval timer]] which invokes an [[interrupt handler]] that runs in [[kernel mode]] and implements the scheduling function.

Line 226 ⟶ 227:

===OS/360 and successors===

IBM [[OS/360 and successors|OS/360]] was available with three different schedulers. The differences were such that the variants were often considered three different operating systems:

* The ''Single Sequential Scheduler'' option, also known as the ''Primary Control Program (PCP)'' provided sequential execution of a single stream of jobs.

Line 255 ⟶ 256:

Threads are primarily of interest for applications that currently consist of several asynchronous processes. These applications might impose a lighter load on the system if converted to a multithreaded structure.

AIX 5 implements the following scheduling policies: FIFO, round robin, and a fair round robin. The FIFO policy has three different implementations: FIFO, FIFO2, and FIFO3. The round robin policy is named SCHED_RR in AIX, and the fair round robin is called SCHED_OTHER.<ref>[http://www.ibm.com/developerworks/aix/library/au-aix5_cpu/index.html#N100F6] {{webarchive|url=https://web.archive.org/web/20110811094049/http://www.ibm.com/developerworks/aix/library/au-aix5_cpu/index.html |date=2011-08-11 }}</ref>

===Linux===

{{See also|Linux kernel#Scheduling}}

[[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 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&ndash;99 are reserved for real-time tasks and 100&ndash;140 are considered [[nice (Unix)|nice]] task levels. For real-time tasks, the time quantum for switching processes was approximately 200&nbsp;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.

Line 268 ⟶ 274:

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.

====Since 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

Line 282 ⟶ 288:

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>

===FreeBSD===

Line 288 ⟶ 298:

===NetBSD===

[[NetBSD]] uses a multilevel feedback queue with priorities ranging from 0–223. 0–63 are reserved for time-shared threads (default, SCHED_OTHER policy), 64–95 for user threads which entered [[kernel space]], 96-12896–128 for kernel threads, 128–191 for user real-time threads (SCHED_FIFO and SCHED_RR policies), and 192–223 for [[Interrupt|software interrupts]].

===Solaris===

Line 316 ⟶ 326:

| [[O(1) scheduler]]

|-

| Linux kernel after 2.6.23&ndash;6.6

| {{Yes}}

| [[Completely Fair Scheduler]]

Line 361 ⟶ 371:

* [[Activity selection problem]]

* [[Aging (scheduling)]]

* [[Atropos scheduler]]

* [[Automated planning and scheduling]]

* [[Cyclic executive]]

Line 373 ⟶ 382:

* [[Queuing theory]]

* [[Rate-monotonic scheduling]]

* [[Resource-Task Network]]

* [[Scheduling (production processes)]]

* [[Stochastic scheduling]]