Scheduling (computing): Difference between revisions

Revision as of 18:37, 15 November 2024

Latest revision as of 02:46, 28 August 2025

(20 intermediate revisions by 9 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 [[Traffic 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 mechanism 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]].

The scheduling activity is carried out by a mechanism 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 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 289 ⟶ 290:

==== 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 294 ⟶ 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 322 ⟶ 326:

| [[O(1) scheduler]]

|-

| Linux kernel after 2.6.23&ndash;6.6

| {{Yes}}

| [[Completely Fair Scheduler]]