Scheduling (computing): Difference between revisions

Revision as of 08:12, 24 April 2025

Latest revision as of 02:46, 28 August 2025

(12 intermediate revisions by 5 users not shown)

Line 78:

==={{Anchor|PROCESS}}Process scheduler===

The process scheduler is a part of the operating system that decides which process runs at a certain point in time. It usually has the ability to pause a running process, move it to the back of the running queue and start a new process; such a scheduler is known as a ''[[Preemption (computing)|preemptive]] scheduler'', otherwise it is a ''[[Nonpreemptive multitasking|cooperative]] scheduler''.<ref>{{cite web|access-date=2023-06-19|author=Paul Krzyzanowski|date=2014-02-19|title=Process Scheduling: Who gets to run next?|url=https://www.cs.rutgers.edu/~pxk/416/notes/07-scheduling.html|website=cs.rutgers.edu}}</ref>

We distinguish between ''long-term scheduling'', ''medium-term scheduling'', and ''short-term scheduling'' based on how often decisions must be made.<ref>{{cite book |author=Raphael Finkel |author-link=Raphael Finkel |url=https://www.yumpu.com/en/document/read/32199214/an-operating-systems-vade-mecum |title=An Operating Systems Vade Mecum |publisher=Prentice Hall |date=1988 |chapter=Chapter 2: Time Management |page=27}}</ref>

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

Line 94:

}}</ref>

Long-term scheduling is also important in large-scale systems such as [[batch processing]] systems, [[computer clusterscluster]]s, supercomputers[[supercomputer]]s, and [[render farmsfarm]]s. For example, in [[concurrent computing|concurrent systems]], [[coscheduling]] of interacting processes is often required to prevent them from blocking due to waiting on each other. In these cases, special-purpose [[job scheduler]] software is typically used to assist these functions, in addition to any underlying admission scheduling support in the operating system.

Some operating systems only allow new tasks to be added if it is sure all real-time deadlines can still be met.

Line 107:

===={{Anchor|MEDIUM-TERM}}Medium-term scheduling====

The ''medium-term scheduler'' temporarily removes processes from main memory and places them in secondary memory (such as a [[hard disk drive]]) or vice versa, which is commonly referred to as ''swapping out'' or ''swapping in'' (also incorrectly as ''[[paging]] out'' or ''paging in''). The medium-term scheduler may decide to swap out a process that has not been active for some time, a process that has a low priority, a process that is [[page faultingfault]]ing frequently, or a process that is taking up a large amount of memory in order to free up main memory for other processes, swapping the process back in later when more memory is available, or when the process has been unblocked and is no longer waiting for a resource.

In many systems today (those that support mapping virtual address space to secondary storage other than the swap file), the medium-term scheduler may actually perform the role of the long-term scheduler, by treating binaries as ''swapped-out processes'' upon their execution. In this way, when a segment of the binary is required it can be swapped in on demand, or ''lazy loaded'', also called [[demand paging]].

===={{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 (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.

===={{Anchor|DISPATCH-LATENCY}}Dispatcher====

Another component that is involved in the CPU-scheduling function is the dispatcher, which is the module that gives control of the CPU to the process selected by the short-term scheduler. It receives control in kernel mode as the result of an interrupt or system call. The functions of a dispatcher involve the following:

* [[Context switchesswitch]]es, in which the dispatcher saves the [[State (computer science)|state]] (also known as [[Context (computing)|context]]) of the [[Process (computing)|process]] or [[Thread (computing)|thread]] that was previously running; the dispatcher then loads the initial or previously saved state of the new process.

* Switching to user mode.

* Jumping to the proper ___location in the user program to restart that program indicated by its new state.

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