task scheduling
   HOME

TheInfoList




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 computer hardware , hardware and software. It has sci ...

computing
, 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 (computing), processor, is the electronic circuitry that executes Instruction (computing), instructions comprising a computer program. The CPU per ...

processors
, network links or
expansion card 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 computer hardware , hardware a ...
s. The ''tasks'' may be threads,
processes A process is a series or set of Action (philosophy), 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 pro ...
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. 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 terms ...
of a computer system; the concept of scheduling makes it possible to have
computer multitasking 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 computer hardware , hardware and s ...
with a single
central processing unit A central processing unit (CPU), also called a central processor, main processor or just processor, is the electronic circuit 200px, A circuit built on a printed circuit board (PCB). An electronic circuit is composed of individual electroni ...

central processing unit
(CPU).


Goals

A scheduler may aim at one or more goals, for example: * maximizing ''
throughput In general terms, throughput is the rate of production or the rate at which something is processed. When used in the context of communication networks, such as Ethernet Ethernet () is a family of wired ing technologies commonly used in s ...
'' (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 Latency or latent may refer to: Science and technology * Latent heat, energy released or absorbed, by a body or a thermodynamic system, during a constant-temperature process * Latent variable, a variable that is not directly observed but inferred i ...
'' or '' response time'' (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 computer is a machine that can be programmed to carry out Sequence, sequences of arithmetic or logical operations automatically. Modern computers can perform generic sets of operations known as Co ...
s for
automatic control Automation describes a wide range of technologies that reduce human intervention in processes. Human intervention is reduced by predetermining decision criteria, subprocess relationships, and related actions — and embodying those predeterm ...
in industry (for example
robotics Robotics is an interdisciplinary Interdisciplinarity or interdisciplinary studies involves the combination of two or more academic disciplines into one activity (e.g., a research project). It draws knowledge from several other fields like ...

robotics
), 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
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 The federal subject The federal subjects of Russia, also referred to as the subjects of the Russian Federation (russian: субъекты Российск ...
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 queueIn a computer multitasking, multitasking computer system, process (computing), processes may occupy a variety of state (computer science), states. These distinct states may not be recognized as such by the operating system kernel (computer science), ...
(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 Computer science deals with the theoretical foundations of information, algorithms and the architectures of its computation as well as practical techniques for their application. Computer science is the study of Algorit ...
or
CPU-bound {{Unreferenced, date=April 2007 In computer science Computer science deals with the theoretical foundations of information, algorithms and the architectures of its computation as well as practical techniques for their application. Compu ...
. 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 the running of "jobs that can run without end user interaction, or can be scheduled to run as resources permit." History The term "batch processing" originates in the traditional classification of methods of produc ...
systems,
computer cluster A computer cluster is a set of computers A computer is a machine that can be programmed to Execution (computing), carry out sequences of arithmetic or logical operations automatically. Modern computers can perform generic sets of operati ...
s,
supercomputer upright=1.5, Computing power of the top 1 supercomputer each year, measured in FLOPS 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 mea ...

supercomputer
s, and
render farm A render farm is a high-performance computer system, e.g. a 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 ...
s. For example, in concurrent systems,
coscheduling Coscheduling is the principle for concurrent systems of scheduling (computing), scheduling related process (computing), processes to run on different processors at the same time (in parallel computing, parallel). There are various specific implemen ...
of interacting processes is often required to prevent them from blocking due to waiting on each other. In these cases, special-purpose
job scheduler #REDIRECT 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 Com ...
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 On a reel-to-reel tape recorder (Sony TC-630), the recorder is data storage equipment and the magnetic tape is a data stora ...

hard disk drive
) or vice versa, which is commonly referred to as "swapping out" or "swapping in" (also incorrectly as "
paging In computer A computer is a machine that can be programmed to Execution (computing), carry out sequences of arithmetic or logical operations automatically. Modern computers can perform generic sets of operations known as Computer program ...

paging
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 could be used with the Motorola 68010 The Motorola MC68010 processor is a 16/32-bit microprocessor A microprocessor is a ...
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 A computer is a machine that can be programmed to Execution (computing), carry out sequences of arithmetic or logical operations automatically. Modern computers can perform generic sets of operations known as Computer program, pro ...
.


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 computer A computer is a machine A machine is a man-made device that uses power to apply forces and control movement to perform an action. Machines can be driven by animals and people A people is a plurality of pe ...

interrupt
, an I/O interrupt, an operating
system call 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 computer hardware , hardware and so ...
or another form of
signal In signal processing Signal processing is an electrical engineering subfield that focuses on analysing, modifying, and synthesizing signals such as audio signal processing, sound, image processing, images, and scientific measurements. Sig ...
. 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 #REDIRECT Programmable interval timer#REDIRECT Programmable interval timerIn computing Computing is any goal-oriented activity requiring, benefiting from, or creating computing machinery. It includes the study and experimentation of algorithmic pr ...
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 In digital computers, an interrupt is a response by the central processi ...
that runs in
kernel mode In computer science Computer science deals with the theoretical foundations of information, algorithms and the architectures of its computation as well as practical techniques for their application. Computer science is the study ...
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 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 computer hardware , hardware and soft ...
es, in which the dispatcher saves the
state State may refer to: Arts, entertainment, and media Literature * ''State Magazine ''State Magazine'' is a digital magazine published by the U.S. Department of State's Bureau of Global Talent Management. Its mission is to acquaint Department o ...
(also known as
context Context may refer to: * Context (language use) In semiotics, linguistics, sociology and anthropology, context refers to those objects or entities which surround a ''focal event'', in these disciplines typically a communication, communicative event ...
) 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 A business process, business method ...
or
thread Thread or threads may refer to: Objects * Thread (yarn), a kind of thin yarn used for sewing ** Thread (unit of measurement), a cotton yarn measure * Screw thread, a helical ridge on a cylindrical fastener Arts and entertainment * Thread (film), ...
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 System software is software designed to provide a platform for other software. Examples of system software include operating systems (OS) like macOS, Linux, Android (operating system), Android and Mi ...

operating system
s (to share
CPU time CPU time (or process time) is the amount of time Time is the continued sequence of existence and event (philosophy), events that occurs in an apparently irreversible process, irreversible succession from the past, through the present, int ...

CPU time
among both threads and
processes A process is a series or set of Action (philosophy), 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 pro ...
), disk drives (
I/O scheduling Input/output (I/O) scheduling is the method that computer operating systems use to decide in which order the block Input/output, I/O operations will be submitted to Volume (computing), storage volumes. I/O scheduling is sometimes called disk sch ...
), printers ( print spooler), most embedded systems, etc. The main purposes of scheduling algorithms are to minimize
resource starvation In computer science Computer science deals with the theoretical foundations of information, algorithms and the architectures of its computation as well as practical techniques for their application. Computer science is the study of Algor ...
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 telecommunication Telecommunication is the transmission of information Information can be thought of as the resolution of uncertainty; it answers the question of "What an entity is" and thus defines both its essence and the nature of ...
computer networks A computer network is a group of computer A computer is a machine that can be programmed to carry out sequences of arithmetic or logical operations automatically. Modern computers can perform generic sets of operations known as Compute ...
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 d ...
, 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 wikt:queue, 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 be ...
queuing of data packets. The simplest best-effort scheduling algorithms are round-robin,
fair queuing Fair queuing is a family of scheduling algorithms used in some process and network schedulers. The algorithm is designed to achieve fairness when a limited resource is shared, for example to prevent flows with large packets or processes that gen ...
(a max-min fair scheduling algorithm), proportional-fair scheduling and
maximum throughput In general terms, throughput is the rate of production or the rate at which something is processed. When used in the context of communication networks, such as Ethernet or packet radio, throughput or network throughput is the rate of ''successf ...
. 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 Telephony ( ) is the field of technology involving the development, application, and deployment of telecommunication Tel ...
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 eq ...
may be utilized. In advanced packet radio wireless networks such as
HSDPA High Speed Packet Access (HSPA) is an amalgamation of two mobile protocols Protocol may refer to: Sociology and politics * Protocol (politics)Protocol originally (in Late Middle English, c. 15th century) meant the minute or logbook taken at a ...
(High-Speed Downlink Packet Access)
3.5G 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 telecommunicati ...
cellular system, channel-dependent scheduling may be used to take advantage of channel state information. If the channel conditions are favourable, the
throughput In general terms, throughput is the rate of production or the rate at which something is processed. When used in the context of communication networks, such as Ethernet Ethernet () is a family of wired ing technologies commonly used in s ...
and
system spectral efficiency Spectral efficiency, spectrum efficiency or bandwidth efficiency refers to the information rate that can be transmitted over a given bandwidth in a specific communication system. It is a measure of how efficiently a limited frequency spectrum is u ...
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 channel Image:Communications men.jpg, 220px, Old telephone wires are a challenging communications channel for modern ...
, or by assigning
OFDMA Orthogonal frequency-division multiple access (OFDMA) is a multi-user version of the popular orthogonal frequency-division multiplexing In telecommunications Telecommunication is the transmission of information Information can be thou ...
multi-carriers or other frequency-domain equalization components to the users that best can utilize them.


First come, first served

''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 In general, turnaround time (TAT) means 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 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 (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 Computer science deals with the theoretical foundations of information, algorithms and the architectures of its computation as well as practical techniques for their application. Computer science is the study of , ...

shared memory
problems.


Work-conserving schedulers

A work-conserving scheduler 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 distance in 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 s ...
is minimized: *
Job shop schedulingJob-shop scheduling or the job-shop problem (JSP) is an optimization problem in computer science and Operations Research, operations research. It is a variant of optimal job scheduling. In a general job scheduling problem, we are given ''n'' jobs ''J ...
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 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 problems, are a class of scheduling File:Departure for the south - Nashville.jpg, A train schedule informs travelers of the trains going to various locations, and indicates the times of departure. A schedule or a timetabl ...
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 {{Short pages monitor