In
computing
Computing is any goal-oriented activity requiring, benefiting from, or creating computing machinery. It includes the study and experimentation of algorithmic processes, and development of both hardware and software. Computing has scientific, e ...
, scheduling is the action of assigning ''resources'' to perform ''tasks''. The ''resources'' may be
processors
A central processing unit (CPU), also called a central processor, main processor or just processor, is the electronic circuitry that executes instructions comprising a computer program. The CPU performs basic arithmetic, logic, controlling, and ...
,
network links or
expansion card
In computing, an expansion card (also called an expansion board, adapter card, peripheral card or accessory card) is a printed circuit board that can be inserted into an electrical connector, or expansion slot (also referred to as a bus slo ...
s. The ''tasks'' may be
threads,
processes or data
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), allow multiple users to share system resources effectively, or to achieve a target
quality-of-service
Quality of service (QoS) is the description or measurement of the overall performance of a service, such as a telephony or computer network, or a cloud computing service, particularly the performance seen by the users of the network. To quantitat ...
.
Scheduling is fundamental to computation itself, and an intrinsic part of the
execution model
A programming language consists of a grammar/syntax plus an execution model. The execution model specifies the behavior of elements of the language. By applying the execution model, one can derive the behavior of a program that was written in term ...
of a computer system; the concept of scheduling makes it possible to have
computer multitasking
In computing, multitasking is the concurrent execution of multiple tasks (also known as processes) over a certain period of time. New tasks can interrupt already started ones before they finish, instead of waiting for them to end. As a result ...
with a single
central processing unit
A central processing unit (CPU), also called a central processor, main processor or just processor, is the electronic circuitry that executes instructions comprising a computer program. The CPU performs basic arithmetic, logic, controlling, an ...
(CPU).
Goals
A scheduler may aim at one or more goals, for example:
* maximizing ''
throughput
Network throughput (or just throughput, when in context) refers to the rate of message delivery over a communication channel, such as Ethernet or packet radio, in a communication network. The data that these messages contain may be delivered ov ...
'' (the total amount of work completed per time unit);
* minimizing ''
wait time'' (time from work becoming ready until the first point it begins execution);
* minimizing ''
latency'' or ''
response time
Response time may refer to:
*The time lag between an electronic input and the output signal which depends upon the value of passive components used.
* Responsiveness, how quickly an interactive system responds to user input
* Response time (biolog ...
'' (time from work becoming ready until it is finished in case of batch activity,
[
][
][
] or until the system responds and hands the first output to the user in case of interactive activity);
* maximizing ''fairness'' (equal CPU time to each process, or more generally appropriate times according to the priority and workload of each process).
In practice, these goals often conflict (e.g. throughput versus latency), thus a scheduler will implement a suitable compromise. Preference is measured by any one of the concerns mentioned above, depending upon the user's needs and objectives.
In
real-time
Real-time or real time describes various operations in computing or other processes that must guarantee response times within a specified time (deadline), usually a relatively short time. A real-time process is generally one that happens in defined ...
environments, such as
embedded system
An embedded system is a computer system—a combination of a computer processor, computer memory, and input/output peripheral devices—that has a dedicated function within a larger mechanical or electronic system. It is ''embedded'' as ...
s for
automatic control
Automation describes a wide range of technologies that reduce human intervention in processes, namely by predetermining decision criteria, subprocess relationships, and related actions, as well as embodying those predeterminations in machines ...
in industry (for example
robotics
Robotics is an interdisciplinary branch of computer science and engineering. Robotics involves design, construction, operation, and use of robots. The goal of robotics is to design machines that can help and assist humans. Robotics integrat ...
), the scheduler also must ensure that processes can meet
deadlines; this is crucial for keeping the system stable. Scheduled tasks can also be distributed to remote devices across a network and
managed through an administrative back end.
Types of operating system schedulers
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.
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 ''
preemptive scheduler'', otherwise it is a ''
cooperative
A cooperative (also known as co-operative, co-op, or coop) is "an autonomous association of persons united voluntarily to meet their common economic, social and cultural needs and aspirations through a jointly owned and democratically-control ...
scheduler''.
We distinguish between "long-term scheduling", "medium-term scheduling", and "short-term scheduling" based on how often decisions must be made.
Long-term scheduling
The ''long-term scheduler'', or ''admission scheduler'', decides which jobs or processes are to be admitted to the
ready queue In a multitasking computer system, processes may occupy a variety of states. These distinct states may not be recognized as such by the operating system kernel. However, they are a useful abstraction for the understanding of processes.
Primary ...
(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, and the degree of concurrency to be supported at any one time 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
In computer science, I/O bound refers to a condition in which the time it takes to complete a computation is determined principally by the period spent waiting for input/output operations to be completed. This is the opposite of a task being CPU bo ...
or
CPU-bound
{{Unreferenced, date=April 2007
In computer science, a computer is CPU-bound (or compute-bound) when the time for it to complete a task is determined principally by the speed of the central processor: processor utilization is high, perhaps at 100% ...
. 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.
Long-term scheduling is also important in large-scale systems such as
batch processing
Computerized batch processing is a method of running software programs called jobs in batches automatically. While users are required to submit the jobs, no other interaction by the user is required to process the batch. Batches may automatically ...
systems,
computer cluster
A computer cluster is a set of computers that work together so that they can be viewed as a single system. Unlike grid computers, computer clusters have each node set to perform the same task, controlled and scheduled by software.
The comp ...
s,
supercomputer
A supercomputer is a computer with a high level of performance as compared to a general-purpose computer. The performance of a supercomputer is commonly measured in floating-point operations per second ( FLOPS) instead of million instructions ...
s, and
render farm
A render farm is a high-performance computer system, e.g. a computer cluster, built to render computer-generated imagery (CGI), typically for film and television visual effects.
Origin of the term
The term ''render farm'' was born during the ...
s. For example, in
concurrent systems
In computer science, concurrency is the ability of different parts or units of a program, algorithm, or problem to be executed out-of-order or in partial order, without affecting the outcome. This allows for parallel execution of the concurr ...
,
coscheduling
Coscheduling is the principle for concurrent systems of scheduling related processes to run on different processors at the same time (in parallel). There are various specific implementations to realize this.
If an application consists of a colle ...
of interacting processes is often required to prevent them from blocking due to waiting on each other. In these cases, special-purpose
job scheduler
A job scheduler is a computer application for controlling unattended background program execution of jobs. This is commonly called batch scheduling, as execution of non-interactive jobs is often called batch processing, though traditional ''job'' ...
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.
The specific heuristic algorithm used by an operating system to accept or reject new tasks is the ''admission control mechanism''.
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
A hard disk drive (HDD), hard disk, hard drive, or fixed disk is an electro-mechanical data storage device that stores and retrieves digital data using magnetic storage with one or more rigid rapidly rotating platters coated with magnet ...
) or vice versa, which is commonly referred to as "swapping out" or "swapping in" (also incorrectly as "
paging
In computer operating systems, memory paging is a memory management scheme by which a computer stores and retrieves data from secondary storage for use in main memory. In this scheme, the operating system retrieves data from secondary storage ...
out" or "paging in"). The medium-term scheduler may decide to swap out a process which has not been active for some time, or a process which has a low priority, or a process which is
page fault
In computing, a page fault (sometimes called PF or hard fault) is an exception that the memory management unit (MMU) raises when a process accesses a memory page without proper preparations. Accessing the page requires a mapping to be added to t ...
ing frequently, or a process which 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.
tallings, 396 tallings, 370
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",
tallings, 394also called
demand paging
In computer operating systems, demand paging (as opposed to anticipatory paging) is a method of virtual memory management. In a system that uses demand paging, the operating system copies a disk page into physical memory only if an attempt is mad ...
.
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
In digital computers, an interrupt (sometimes referred to as a trap) is a request for the processor to ''interrupt'' currently executing code (when permitted), so that the event can be processed in a timely manner. If the request is accepted, ...
, an I/O interrupt, an operating
system call
In computing, a system call (commonly abbreviated to syscall) is the programmatic way in which a computer program requests a service from the operating system on which it is executed. This may include hardware-related services (for example, acc ...
or another form of
signal
In signal processing, a signal is a function that conveys information about a phenomenon. Any quantity that can vary over space or time can be used as a signal to share messages between observers. The ''IEEE Transactions on Signal Processing'' ...
. Thus the short-term scheduler makes scheduling decisions much more frequently than the long-term or mid-term schedulersa scheduling decision will at a minimum have to be made after every time slice, and these are very short. This scheduler can be
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
In computing and in embedded systems, a programmable interval timer (PIT) is a counter that generates an output signal when it reaches a programmed count. The output signal may trigger an interrupt.
Common features
PITs may be one-shot or periodic ...
which invokes an
interrupt handler
In computer systems programming, an interrupt handler, also known as an interrupt service routine or ISR, is a special block of code associated with a specific interrupt condition. Interrupt handlers are initiated by hardware interrupts, softwar ...
that runs in
kernel mode
In computer science, hierarchical protection domains, often called protection rings, are mechanisms to protect data and functionality from faults (by improving fault tolerance) and malicious behavior (by providing computer security).
Computer ...
and implements the scheduling function.
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 switch
In computing, a context switch is the process of storing the state of a process or thread, so that it can be restored and resume execution at a later point, and then restoring a different, previously saved, state. This allows multiple processes ...
es, in which the dispatcher saves the
state
State may refer to:
Arts, entertainment, and media Literature
* ''State Magazine'', a monthly magazine published by the U.S. Department of State
* ''The State'' (newspaper), a daily newspaper in Columbia, South Carolina, United States
* ''Our S ...
(also known as
context
Context may refer to:
* Context (language use), the relevant constraints of the communicative situation that influence language use, language variation, and discourse summary
Computing
* Context (computing), the virtual environment required to su ...
) of the
process
A process is a series or set of activities that interact to produce a result; it may occur once-only or be recurrent or periodic.
Things called a process include:
Business and management
*Business process, activities that produce a specific se ...
or
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.
The dispatcher should be as fast as possible, since it is invoked during every process switch. During the context switches, the processor is virtually idle for a fraction of time, thus unnecessary context switches should be avoided. The time it takes for the dispatcher to stop one process and start another is known as the ''dispatch latency''.
Scheduling disciplines
A scheduling discipline (also called scheduling policy or scheduling algorithm) is an algorithm used for distributing resources among parties which simultaneously and asynchronously request them. Scheduling disciplines are used in
routers (to handle packet traffic) as well as in
operating system
An operating system (OS) is system software that manages computer hardware, software resources, and provides common services for computer programs.
Time-sharing operating systems schedule tasks for efficient use of the system and may also in ...
s (to share
CPU time
CPU time (or process time) is the amount of time for which a central processing unit (CPU) was used for processing instructions of a computer program or operating system, as opposed to elapsed time, which includes for example, waiting for input ...
among both
threads and
processes), disk drives (
I/O scheduling
Input/output (I/O) scheduling is the method that computer operating systems use to decide in which order I/O operations will be submitted to storage volumes. I/O scheduling is sometimes called disk scheduling.
Purpose
I/O scheduling usually ...
), printers (
print spooler
In computing, spooling is a specialized form of multi-programming for the purpose of copying data between different devices. In contemporary systems, it is usually used for mediating between a computer application and a slow peripheral, such as ...
), most embedded systems, etc.
The main purposes of scheduling algorithms are to minimize
resource starvation
In computer science, resource starvation is a problem encountered in concurrent computing where a process is perpetually denied necessary resources to process its work. Starvation may be caused by errors in a scheduling or mutual exclusion algori ...
and to ensure fairness amongst the parties utilizing the resources. Scheduling deals with the problem of deciding which of the outstanding requests is to be allocated resources. There are many different scheduling algorithms. In this section, we introduce several of them.
In
packet-switched
In telecommunications, packet switching is a method of grouping data into '' packets'' that are transmitted over a digital network. Packets are made of a header and a payload. Data in the header is used by networking hardware to direct the pac ...
computer networks
A computer network is a set of computers sharing resources located on or provided by network nodes. The computers use common communication protocols over digital interconnections to communicate with each other. These interconnections are ma ...
and other
statistical multiplexing
Statistical multiplexing is a type of communication link sharing, very similar to dynamic bandwidth allocation (DBA). In statistical multiplexing, a communication channel is divided into an arbitrary number of variable bitrate digital channels or ...
, the notion of a scheduling algorithm is used as an alternative to
first-come first-served
Queueing theory is the mathematical study of waiting lines, or queues. A queueing model is constructed so that queue lengths and waiting time can be predicted. Queueing theory is generally considered a branch of operations research because the ...
queuing of data packets.
The simplest best-effort scheduling algorithms are
round-robin,
fair queuing (a
max-min fair
In communication networks, multiplexing and the division of scarce resources, max-min fairness is said to be achieved by an allocation if and only if the allocation is feasible and an attempt to increase the allocation of any participant necessar ...
scheduling algorithm),
proportional-fair scheduling
Proportional-fair scheduling is a compromise-based scheduling algorithm. It is based upon maintaining a balance between two competing interests: Trying to maximize total throughput of the network (wired or not) while at the same time allowing all ...
and
maximum throughput
Network throughput (or just throughput, when in context) refers to the rate of message delivery over a communication channel, such as Ethernet or packet radio, in a communication network. The data that these messages contain may be delivered ove ...
. If differentiated or guaranteed
quality of service
Quality of service (QoS) is the description or measurement of the overall performance of a service, such as a telephony or computer network, or a cloud computing service, particularly the performance seen by the users of the network. To quantitat ...
is offered, as opposed to best-effort communication,
weighted fair queuing
Weighted fair queueing (WFQ) is a network scheduling algorithm. WFQ is both a packet-based implementation of the generalized processor sharing (GPS) policy, and a natural extension of fair queuing (FQ). Whereas FQ shares the link's capacity in ...
may be utilized.
In advanced packet radio wireless networks such as
HSDPA
High Speed Packet Access (HSPA) is an amalgamation of two mobile protocols—High Speed Downlink Packet Access (HSDPA) and High Speed Uplink Packet Access (HSUPA)—that extends and improves the performance of existing 3G mobile telecommunicat ...
(High-Speed Downlink Packet Access)
3.5G cellular system, channel-dependent scheduling may be used to take advantage of
channel state information In wireless communications, channel state information (CSI) is the known channel properties of a communication link. This information describes how a signal propagates from the transmitter to the receiver and represents the combined effect of, for ...
. If the channel conditions are favourable, the
throughput
Network throughput (or just throughput, when in context) refers to the rate of message delivery over a communication channel, such as Ethernet or packet radio, in a communication network. The data that these messages contain may be delivered ov ...
and
system spectral efficiency may be increased. In even more advanced systems such as
LTE, the scheduling is combined by channel-dependent packet-by-packet
dynamic channel allocation
In radio resource management for wireless and cellular networks, channel allocation schemes allocate bandwidth and communication channels to base stations, access points and terminal equipment. The objective is to achieve maximum system spectral e ...
, or by assigning
OFDMA
Orthogonal frequency-division multiple access (OFDMA) is a multi-user version of the popular orthogonal frequency-division multiplexing (OFDM) digital modulation scheme. Multiple access is achieved in OFDMA by assigning subsets of subcarriers t ...
multi-carriers or other
frequency-domain equalization
Single-carrier FDMA (SC-FDMA) is a frequency-division multiple access scheme. It is also called linearly precoded OFDMA (LP-OFDMA). Like other multiple access schemes (TDMA, FDMA, CDMA, OFDMA), it deals with the assignment of multiple users to a ...
components to the users that best can utilize them.
First come, first served
![Thread pool](https://upload.wikimedia.org/wikipedia/commons/0/0c/Thread_pool.svg)
''First in, first out'' (
FIFO), also known as ''first come, first served'' (FCFS), is the simplest scheduling algorithm. FIFO simply queues processes in the order that they arrive in the ready queue. This is commonly used for a , for example as illustrated in this section.
* Since context switches only occur upon process termination, and no reorganization of the process queue is required, scheduling overhead is minimal.
* Throughput can be low, because long processes can be holding the CPU, causing the short processes to wait for a long time (known as the convoy effect).
* No starvation, because each process gets chance to be executed after a definite time.
*
Turnaround time
Turnaround time (TAT) is the amount of time taken to complete a process or fulfill a request. The concept thus overlaps with lead time and can be contrasted with cycle time.
Meaning in computing
In computing, turnaround time is the total time t ...
, waiting time and response time depend on the order of their arrival and can be high for the same reasons above.
* No prioritization occurs, thus this system has trouble meeting process deadlines.
* The lack of prioritization means that as long as every process eventually completes, there is no starvation. In an environment where some processes might not complete, there can be starvation.
* It is based on queuing.
Priority scheduling
Earliest deadline first (EDF) or ''least time to go'' is a dynamic scheduling algorithm used in real-time operating systems to place processes in a priority queue. Whenever a scheduling event occurs (a task finishes, new task is released, etc.), the queue will be searched for the process closest to its deadline, which will be the next to be scheduled for execution.
Shortest remaining time first
Similar to
shortest job first
Shortest job next (SJN), also known as shortest job first (SJF) or shortest process next (SPN), is a scheduling policy that selects for execution the waiting process with the smallest execution time. SJN is a non- preemptive algorithm. Shortest r ...
(SJF). With this strategy the scheduler arranges processes with the least estimated processing time remaining to be next in the queue. This requires advanced knowledge or estimations about the time required for a process to complete.
* If a shorter process arrives during another process' execution, the currently running process is interrupted (known as preemption), dividing that process into two separate computing blocks. This creates excess overhead through additional context switching. The scheduler must also place each incoming process into a specific place in the queue, creating additional overhead.
* This algorithm is designed for maximum throughput in most scenarios.
* Waiting time and response time increase as the process's computational requirements increase. Since turnaround time is based on waiting time plus processing time, longer processes are significantly affected by this. Overall waiting time is smaller than FIFO, however since no process has to wait for the termination of the longest process.
* No particular attention is given to deadlines, the programmer can only attempt to make processes with deadlines as short as possible.
* Starvation is possible, especially in a busy system with many small processes being run.
* To use this policy we should have at least two processes of different priority
Fixed priority pre-emptive scheduling
The operating system assigns a fixed priority rank to every process, and the scheduler arranges the processes in the ready queue in order of their priority. Lower-priority processes get interrupted by incoming higher-priority processes.
* Overhead is not minimal, nor is it significant.
* FPPS has no particular advantage in terms of throughput over FIFO scheduling.
* If the number of rankings is limited, it can be characterized as a collection of FIFO queues, one for each priority ranking. Processes in lower-priority queues are selected only when all of the higher-priority queues are empty.
* Waiting time and response time depend on the priority of the process. Higher-priority processes have smaller waiting and response times.
* Deadlines can be met by giving processes with deadlines a higher priority.
* Starvation of lower-priority processes is possible with large numbers of high-priority processes queuing for CPU time.
Round-robin scheduling
The scheduler assigns a fixed time unit per process, and cycles through them. If process completes within that time-slice it gets terminated otherwise it is rescheduled after giving a chance to all other processes.
* RR scheduling involves extensive overhead, especially with a small time unit.
* Balanced throughput between FCFS/ FIFO and SJF/SRTF, shorter jobs are completed faster than in FIFO and longer processes are completed faster than in SJF.
* Good average response time, waiting time is dependent on number of processes, and not average process length.
* Because of high waiting times, deadlines are rarely met in a pure RR system.
* Starvation can never occur, since no priority is given. Order of time unit allocation is based upon process arrival time, similar to FIFO.
* If Time-Slice is large it becomes FCFS /FIFO or if it is short then it becomes SJF/SRTF.
Multilevel queue scheduling
This is used for situations in which processes are easily divided into different groups. For example, a common division is made between foreground (interactive) processes and background (batch) processes. These two types of processes have different response-time requirements and so may have different scheduling needs. It is very useful for
shared memory
In computer science, shared memory is memory that may be simultaneously accessed by multiple programs with an intent to provide communication among them or avoid redundant copies. Shared memory is an efficient means of passing data between progr ...
problems.
Work-conserving schedulers
A
work-conserving scheduler In computing and communication systems, a work-conserving scheduler is a scheduler that always tries to keep the scheduled resource(s) busy, if there are submitted jobs ready to be scheduled. In contrast, a non-work conserving scheduler is a schedu ...
is a scheduler that always tries to keep the scheduled resources busy, if there are submitted jobs ready to be scheduled. In contrast, a non-work conserving scheduler is a scheduler that, in some cases, may leave the scheduled resources idle despite the presence of jobs ready to be scheduled.
Scheduling optimization problems
There are several scheduling problems in which the goal is to decide which job goes to which station at what time, such that the total
makespan
In operations research, the makespan of a project is the length of time that elapses from the start of work to the end. This type of multi-mode resource constrained project scheduling problem (MRCPSP) seeks to create the shortest logical project sc ...
is minimized:
*
Job shop scheduling Job-shop scheduling, the job-shop problem (JSP) or job-shop scheduling problem (JSSP) is an optimization problem in computer science and operations research. It is a variant of optimal job scheduling. In a general job scheduling problem, we are give ...
there are jobs and identical stations. Each job should be executed on a single machine. This is usually regarded as an online problem.
*
Open-shop scheduling Open-shop scheduling or open-shop scheduling problem (OSSP) is an optimization problem in computer science and operations research. It is a variant of optimal job scheduling. In a general job-scheduling problem, we are given ''n'' jobs ''J''1, ...
there are jobs and different stations. Each job should spend some time at each station, in a free order.
*
Flow shop scheduling
Flow-shop scheduling is an optimization problem in computer science and operations research. It is a variant of optimal job scheduling. In a general job-scheduling problem, we are given ''n'' jobs ''J''1, ''J''2, ..., ''Jn'' of varyi ...
there are jobs and different stations. Each job should spend some time at each station, in a pre-determined order.
Manual scheduling
A very common method in embedded systems is to schedule jobs manually. This can for example be done in a time-multiplexed fashion. Sometimes the kernel is divided in three or more parts: Manual scheduling, preemptive and interrupt level. Exact methods for scheduling jobs are often proprietary.
* No resource starvation problems
* Very high predictability; allows implementation of hard real-time systems
* Almost no overhead
* May not be optimal for all applications
* Effectiveness is completely dependent on the implementation
Choosing a scheduling algorithm
When designing an operating system, a programmer must consider which scheduling algorithm will perform best for the use the system is going to see. There is no universal "best" scheduling algorithm, and many operating systems use extended or combinations of the scheduling algorithms above.
For example,
Windows NT
Windows NT is a proprietary graphical operating system
An operating system (OS) is system software that manages computer hardware, software resources, and provides common services for computer programs.
Time-sharing operating systems sc ...
/XP/Vista uses a
multilevel feedback queue In computer science, a multilevel feedback queue is a scheduling (computing), scheduling algorithm. ''Scheduling algorithms'' are designed to have some process running at all times to keep the central processing unit (CPU) busy. The ''multilevel fee ...
, a combination of fixed-priority preemptive scheduling, round-robin, and first in, first out algorithms. In this system, threads can dynamically increase or decrease in priority depending on if it has been serviced already, or if it has been waiting extensively. Every priority level is represented by its own queue, with
round-robin scheduling
Round-robin (RR) is one of the algorithms employed by process and network schedulers in computing.Guowang Miao, Jens Zander, Ki Won Sung, and Ben Slimane, Fundamentals of Mobile Data Networks, Cambridge University Press, , 2016.
As the term is ...
among the high-priority threads and
FIFO among the lower-priority ones. In this sense, response time is short for most threads, and short but critical system threads get completed very quickly. Since threads can only use one time unit of the round-robin in the highest-priority queue, starvation can be a problem for longer high-priority threads.
Operating system process scheduler implementations
The algorithm used may be as simple as
round-robin in which each process is given equal time (for instance 1 ms, usually between 1 ms and 100 ms) in a cycling list. So, process A executes for 1 ms, then process B, then process C, then back to process A.
More advanced algorithms take into account process priority, or the importance of the process. This allows some processes to use more time than other processes. The kernel always uses whatever resources it needs to ensure proper functioning of the system, and so can be said to have infinite priority. In
SMP systems,
processor affinity
Processor affinity, or CPU pinning or "cache affinity", enables the binding and unbinding of a process or a thread to a central processing unit (CPU) or a range of CPUs, so that the process or thread will execute only on the designated CPU or CPU ...
is considered to increase overall system performance, even if it may cause a process itself to run more slowly. This generally improves performance by reducing
cache thrashing
In computer science, thrashing occurs when a computer's virtual memory resources are overused, leading to a constant state of paging and page faults, inhibiting most application-level processing. This causes the performance of the computer to d ...
.
OS/360 and successors
IBM
OS/360
OS/360, officially known as IBM System/360 Operating System, is a discontinued batch processing operating system developed by IBM for their then-new System/360 mainframe computer, announced in 1964; it was influenced by the earlier IBSYS/IBJOB ...
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.
* The ''Multiple Sequential Scheduler'' option, known as ''Multiprogramming with a Fixed Number of Tasks (MFT)'' provided execution of multiple concurrent jobs. Execution was governed by a priority which had a default for each stream or could be requested separately for each job. MFT version II added subtasks (threads), which executed at a priority based on that of the parent job. Each job stream defined the maximum amount of memory which could be used by any job in that stream.
* The ''Multiple Priority Schedulers'' option, or ''Multiprogramming with a Variable Number of Tasks (MVT)'', featured subtasks from the start; each job requested the priority and memory it required before execution.
Later virtual storage versions of MVS added a ''
Workload Manager
In IBM mainframes, Workload Manager (WLM) is a base component of MVS/ESA mainframe operating system, and its successors up to and including z/OS. It controls the access to system resources for the work executing on z/OS based on administrator-defi ...
'' feature to the scheduler, which schedules processor resources according to an elaborate scheme defined by the installation.
Windows
Very early
MS-DOS
MS-DOS ( ; acronym for Microsoft Disk Operating System, also known as Microsoft DOS) is an operating system for x86-based personal computers mostly developed by Microsoft. Collectively, MS-DOS, its rebranding as IBM PC DOS, and a few ope ...
and Microsoft Windows systems were non-multitasking, and as such did not feature a scheduler.
Windows 3.1x
Windows 3.1 is a major release of Microsoft Windows. It was released to manufacturing on April 6, 1992, as a successor to Windows 3.0.
Like its predecessors, the Windows 3.1 series ran as a shell on top of MS-DOS. Codenamed Janus, Windows 3. ...
used a non-preemptive scheduler, meaning that it did not interrupt programs. It relied on the program to end or tell the OS that it didn't need the processor so that it could move on to another process. This is usually called cooperative multitasking. Windows 95 introduced a rudimentary preemptive scheduler; however, for legacy support opted to let 16 bit applications run without preemption.
Windows NT
Windows NT is a proprietary graphical operating system
An operating system (OS) is system software that manages computer hardware, software resources, and provides common services for computer programs.
Time-sharing operating systems sc ...
-based operating systems use a multilevel feedback queue. 32 priority levels are defined, 0 through to 31, with priorities 0 through 15 being "normal" priorities and priorities 16 through 31 being soft real-time priorities, requiring privileges to assign. 0 is reserved for the Operating System. User interfaces and APIs work with priority classes for the process and the threads in the process, which are then combined by the system into the absolute priority level.
The kernel may change the priority level of a thread depending on its I/O and CPU usage and whether it is interactive (i.e. accepts and responds to input from humans), raising the priority of interactive and I/O bounded processes and lowering that of CPU bound processes, to increase the responsiveness of interactive applications. The scheduler was modified in
Windows Vista
Windows Vista is a major release of the Windows NT operating system developed by Microsoft. It was the direct successor to Windows XP, which was released five years before, at the time being the longest time span between successive releases of ...
to use the
cycle counter register of modern processors to keep track of exactly how many CPU cycles a thread has executed, rather than just using an interval-timer interrupt routine. Vista also uses a priority scheduler for the I/O queue so that disk defragmenters and other such programs do not interfere with foreground operations.
Classic Mac OS and macOS
Mac OS 9 uses cooperative scheduling for threads, where one process controls multiple cooperative threads, and also provides preemptive scheduling for multiprocessing tasks. The kernel schedules multiprocessing tasks using a preemptive scheduling algorithm. All Process Manager processes run within a special multiprocessing task, called the "blue task". Those processes are scheduled cooperatively, using a
round-robin scheduling
Round-robin (RR) is one of the algorithms employed by process and network schedulers in computing.Guowang Miao, Jens Zander, Ki Won Sung, and Ben Slimane, Fundamentals of Mobile Data Networks, Cambridge University Press, , 2016.
As the term is ...
algorithm; a process yields control of the processor to another process by explicitly calling a
blocking function
Blocking may refer to:
Science, technology, and mathematics
Computing and telecommunications
*Blacklist (computing)
*Blocking (computing), holding up a task until an event occurs
*Blocking (radio), interference by an off-frequency signal
*Block ...
such as
WaitNextEvent
. Each process has its own copy of the
Thread Manager that schedules that process's threads cooperatively; a thread yields control of the processor to another thread by calling
YieldToAnyThread
or
YieldToThread
.
macOS uses a multilevel feedback queue, with four priority bands for threadsnormal, system high priority, kernel mode only, and real-time. Threads are scheduled preemptively; macOS also supports cooperatively scheduled threads in its implementation of the Thread Manager in
Carbon
Carbon () is a chemical element with the symbol C and atomic number 6. It is nonmetallic and tetravalent
In chemistry, the valence (US spelling) or valency (British spelling) of an element is the measure of its combining capacity with o ...
.
[
]
AIX
In AIX Version 4 there are three possible values for thread scheduling policy:
* First In, First Out: Once a thread with this policy is scheduled, it runs to completion unless it is blocked, it voluntarily yields control of the CPU, or a higher-priority thread becomes dispatchable. Only fixed-priority threads can have a FIFO scheduling policy.
* Round Robin: This is similar to the AIX Version 3 scheduler round-robin scheme based on 10 ms time slices. When a RR thread has control at the end of the time slice, it moves to the tail of the queue of dispatchable threads of its priority. Only fixed-priority threads can have a Round Robin scheduling policy.
* OTHER: This policy is defined by POSIX1003.4a as implementation-defined. In AIX Version 4, this policy is defined to be equivalent to RR, except that it applies to threads with non-fixed priority. The recalculation of the running thread's priority value at each clock interrupt means that a thread may lose control because its priority value has risen above that of another dispatchable thread. This is the AIX Version 3 behavior.
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.
Linux
Linux 2.4
In Linux
Linux ( or ) is a family of open-source Unix-like operating systems based on the Linux kernel, an operating system kernel first released on September 17, 1991, by Linus Torvalds. Linux is typically packaged as a Linux distribution, which ...
2.4, an O(n) scheduler
The O(n) scheduler is the scheduler used in the Linux kernel between versions 2.4 and 2.6. Since version 2.6.0, it has been replaced by the O(1) scheduler and in 2.6.23 by the current Completely Fair Scheduler
The Completely Fair Scheduler (CF ...
with a multilevel feedback queue In computer science, a multilevel feedback queue is a scheduling (computing), scheduling algorithm. ''Scheduling algorithms'' are designed to have some process running at all times to keep the central processing unit (CPU) busy. The ''multilevel fee ...
with priority levels ranging from 0 to 140 was used; 0–99 are reserved for real-time tasks and 100–140 are considered nice
Nice ( , ; Niçard: , classical norm, or , nonstandard, ; it, Nizza ; lij, Nissa; grc, Νίκαια; la, Nicaea) is the prefecture of the Alpes-Maritimes department in France. The Nice agglomeration extends far beyond the administrative c ...
task levels. For real-time tasks, the time quantum for switching processes was approximately 200 ms, and for nice tasks approximately 10 ms. The scheduler ran through the run queue
In modern computers many processes run at once. Active processes are placed in an array called a run queue, or runqueue. The run queue may contain priority values for each process, which will be used by the scheduler to determine which process to ...
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
A Linux distribution (often abbreviated as distro) is an operating system made from a software collection that includes the Linux kernel and, often, a package management system. Linux users usually obtain their operating system by downloading one ...
such as SUSE Linux Enterprise Server
SUSE Linux Enterprise (often abbreviated to SLE) is a Linux-based operating system developed by SUSE. It is available in two editions, suffixed with Server (SLES) for servers and mainframes, and Desktop (SLED) for workstations and desktop compu ...
replaced this scheduler with a backport of the O(1) scheduler
An O(1) scheduler (pronounced "O of 1 scheduler", "Big O of 1 scheduler", or "constant time scheduler") is a kernel scheduling design that can schedule processes within a constant amount of time, regardless of how many processes are running on the ...
(which was maintained by 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
An O(1) scheduler (pronounced "O of 1 scheduler", "Big O of 1 scheduler", or "constant time scheduler") is a kernel scheduling design that can schedule processes within a constant amount of time, regardless of how many processes are running on the ...
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
Con Kolivas' work, most significantly his implementation of " fair scheduling" named "Rotating Staircase Deadline", inspired Ingo Molnár to develop the Completely Fair Scheduler
The Completely Fair Scheduler (CFS) is a process scheduler that was merged into the 2.6.23 (October 2007) release of the Linux kernel and is the default scheduler of the tasks of the SCHED_NORMAL class (i.e., tasks that have no real-time execution ...
as a replacement for the earlier O(1) scheduler
An O(1) scheduler (pronounced "O of 1 scheduler", "Big O of 1 scheduler", or "constant time scheduler") is a kernel scheduling design that can schedule processes within a constant amount of time, regardless of how many processes are running on the ...
, crediting Kolivas in his announcement. CFS is the first implementation of a fair queuing process scheduler
In computing, scheduling is the action of assigning ''resources'' to perform ''tasks''. The ''resources'' may be processors, network links or expansion cards. The ''tasks'' may be threads, processes or data flows.
The scheduling activity is ca ...
widely used in a general-purpose operating system.
The Completely Fair Scheduler
The Completely Fair Scheduler (CFS) is a process scheduler that was merged into the 2.6.23 (October 2007) release of the Linux kernel and is the default scheduler of the tasks of the SCHED_NORMAL class (i.e., tasks that have no real-time execution ...
(CFS) uses a well-studied, classic scheduling algorithm called fair queuing originally invented for packet network
In telecommunications, packet switching is a method of grouping data into '' packets'' that are transmitted over a digital network. Packets are made of a header and a payload. Data in the header is used by networking hardware to direct the pack ...
s. Fair queuing had been previously applied to CPU scheduling under the name stride scheduling The stride scheduling is a type of scheduling mechanism that has been introduced as a simple concept to achieve proportional CPU capacity reservation among concurrent processes. Stride scheduling aims to sequentially allocate a resource for the ...
. The fair queuing CFS scheduler has a scheduling complexity of , where is the number of tasks in the runqueue. Choosing a task can be done in constant time, but reinserting a task after it has run requires operations, because the run queue
In modern computers many processes run at once. Active processes are placed in an array called a run queue, or runqueue. The run queue may contain priority values for each process, which will be used by the scheduler to determine which process to ...
is implemented as a red–black tree
In computer science, a red–black tree is a kind of self-balancing binary search tree. Each node stores an extra bit representing "color" ("red" or "black"), used to ensure that the tree remains balanced during insertions and deletions.
When the ...
.
The Brain Fuck Scheduler
The Brain Fuck Scheduler (BFS) is a process scheduler designed for the Linux kernel in August 2009 as an alternative to the Completely Fair Scheduler (CFS) and the O(1) scheduler. BFS was created by an experienced kernel programmer Con Koliv ...
, also created by Con Kolivas, is an alternative to the CFS.
FreeBSD
FreeBSD
FreeBSD is a free and open-source Unix-like operating system descended from the Berkeley Software Distribution (BSD), which was based on Research Unix. The first version of FreeBSD was released in 1993. In 2005, FreeBSD was the most popular ...
uses a multilevel feedback queue with priorities ranging from 0–255. 0–63 are reserved for interrupts, 64–127 for the top half of the kernel, 128–159 for real-time user threads, 160–223 for time-shared user threads, and 224–255 for idle user threads. Also, like Linux, it uses the active queue setup, but it also has an idle queue.
NetBSD
NetBSD
NetBSD is a free and open-source Unix operating system based on the Berkeley Software Distribution (BSD). It was the first open-source BSD descendant officially released after 386BSD was forked. It continues to be actively developed and is a ...
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
A modern computer operating system usually segregates virtual memory into user space and kernel space. Primarily, this separation serves to provide memory protection and hardware protection from malicious or errant software behaviour.
Kernel ...
, 96-128 for kernel threads, 128–191 for user real-time threads (SCHED_FIFO and SCHED_RR policies), and 192–223 for software interrupts.
Solaris
Solaris
Solaris may refer to:
Arts and entertainment Literature, television and film
* ''Solaris'' (novel), a 1961 science fiction novel by Stanisław Lem
** ''Solaris'' (1968 film), directed by Boris Nirenburg
** ''Solaris'' (1972 film), directed by ...
uses a multilevel feedback queue with priorities ranging between 0 and 169. Priorities 0–59 are reserved for time-shared threads, 60–99 for system threads, 100–159 for real-time threads, and 160–169 for low priority interrupts. Unlike Linux, when a process is done using its time quantum, it is given a new priority and put back in the queue. Solaris 9 introduced two new scheduling classes, namely fixed priority class and fair share class. The threads with fixed priority have the same priority range as that of the time-sharing class, but their priorities are not dynamically adjusted. The fair scheduling class uses CPU ''shares'' to prioritize threads for scheduling decisions. CPU shares indicate the entitlement to CPU resources. They are allocated to a set of processes, which are collectively known as a project.
Summary
See also
* Activity selection problem
The activity selection problem is a combinatorial optimization problem concerning the selection of non-conflicting task (project management), activities to perform within a given time frame, given a set of activities each marked by a start time ( ...
* Aging (scheduling)
In computer science for Operating systems, aging (US English) or ageing is a scheduling technique used to avoid starvation. Fixed priority scheduling is a scheduling discipline, in which tasks queued for utilizing a system resource are assigned ...
* Atropos scheduler
* Automated planning and scheduling
Automation describes a wide range of technologies that reduce human intervention in processes, namely by predetermining decision criteria, subprocess relationships, and related actions, as well as embodying those predeterminations in machines ...
* Cyclic executive A cyclic executive is an alternative to a real-time operating system. It is a form of cooperative multitasking, in which there is only one task. The sole task is typically realized as an infinite loop in main(), e.g. in C.
The basic scheme is t ...
* Dynamic priority scheduling
Dynamic priority scheduling is a type of scheduling algorithm in which the priorities are calculated during the execution of the system. The goal of dynamic priority scheduling is to adapt to dynamically changing progress and to form an optimal con ...
* Foreground-background Foreground-background is a scheduling algorithm that is used to control an execution of multiple processes on a single processor. It is based on two waiting lists, the first one is called foreground because this is the one in which all processes ini ...
* Interruptible operating system
An interruptible operating system is an operating system with ability to handle multiple interrupts concurrently, or in other words, which allow interrupts to be interrupted.
Concurrent interrupt handling essentially mean concurrent execution of ...
* Least slack time scheduling
Least slack time (LST) scheduling is an algorithm for dynamic priority scheduling. It assigns priorities to processes based on their ''slack time''. Slack time is the amount of time left after a job if the job was started now. This algorithm is als ...
* Lottery scheduling Lottery scheduling is a probabilistic scheduling algorithm for processes in an operating system. Processes are each assigned some number of lottery tickets, and the scheduler draws a random ticket to select the next process. The distribution of ti ...
* Priority inversion
In computer science, priority inversion is a scenario in scheduling in which a high priority task is indirectly superseded by a lower priority task effectively inverting the assigned priorities of the tasks. This violates the priority model that h ...
* Process states In a multitasking computer system, processes may occupy a variety of states. These distinct states may not be recognized as such by the operating system kernel. However, they are a useful abstraction for the understanding of processes.
Primar ...
* Queuing Theory
Queueing theory is the mathematical study of waiting lines, or queues. A queueing model is constructed so that queue lengths and waiting time can be predicted. Queueing theory is generally considered a branch of operations research because the ...
* Rate-monotonic scheduling In computer science, rate-monotonic scheduling (RMS) is a priority assignment algorithm used in real-time operating systems (RTOS) with a static-priority scheduling class. The static priorities are assigned according to the cycle duration of the job ...
* Resource-Task Network
* Scheduling (production processes)
Scheduling is the process of arranging, controlling and optimizing work and workloads in a production process or manufacturing process. Scheduling is used to allocate plant and machinery resources, plan human resources, plan production processes an ...
* Stochastic scheduling
Stochastic scheduling concerns scheduling problems involving random attributes, such as random processing times, random due dates, random weights, and stochastic machine breakdowns. Major applications arise in manufacturing systems, computer system ...
* Time-utility function A Time/Utility Function (''TUF''), née ''Time/Value Function'', specifies the application-specific ''utility'' that an ''action'' (e.g., computational task, mechanical movement) yields depending on its completion time. TUFs and their utility interp ...
Notes
References
*
*
Information on the Linux 2.6 O(1)-scheduler
Further reading
Operating Systems: Three Easy Pieces
by Remzi H. Arpaci-Dusseau and Andrea C. Arpaci-Dusseau. Arpaci-Dusseau Books, 2014. Relevant chapters:
Scheduling: IntroductionMulti-level Feedback QueueProportional-share SchedulingMultiprocessor Scheduling
Brief discussion of Job Scheduling algorithms
* ttp://kerneltrap.org/scheduler Kerneltrap: Linux kernel scheduler articlesbr>AIX CPU monitoring and tuning
Josh Aas' introduction to the Linux 2.6.8.1 CPU scheduler implementation
*Peter Brucker, Sigrid Knust. Complexity results for scheduling problem
TORSCHE Scheduling Toolbox for Matlab
is a toolbox of scheduling and graph algorithms.
A survey on cellular networks packet scheduling
Large-scale cluster management at Google with Borg
{{DEFAULTSORT:Scheduling (Computing)
Scheduling (computing),
Operations research
Planning
Software design patterns