Scheduling (computing): Difference between revisions

Revision as of 22:28, 7 February 2024

Latest revision as of 02:46, 28 August 2025

(32 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 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 258 ⟶ 259:

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

Line 273 ⟶ 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 287 ⟶ 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 293 ⟶ 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 321 ⟶ 326:

| [[O(1) scheduler]]

|-

| Linux kernel after 2.6.23&ndash;6.6

| {{Yes}}

| [[Completely Fair Scheduler]]

Line 366 ⟶ 371:

* [[Activity selection problem]]

* [[Aging (scheduling)]]

* [[Atropos scheduler]]

* [[Automated planning and scheduling]]

* [[Cyclic executive]]

Line 378 ⟶ 382:

* [[Queuing theory]]

* [[Rate-monotonic scheduling]]

* [[Resource-Task Network]]

* [[Scheduling (production processes)]]

* [[Stochastic scheduling]]