Scheduling (computing)
Encyclopedia
In computer science
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...

, a scheduling is the method by which threads
Thread (computer science)
In computer science, a thread of execution is the smallest unit of processing that can be scheduled by an operating system. The implementation of threads and processes differs from one operating system to another, but in most cases, a thread is contained inside a process...

, processes
Process (computing)
In computing, a process is an instance of a computer program that is being executed. It contains the program code and its current activity. Depending on the operating system , a process may be made up of multiple threads of execution that execute instructions concurrently.A computer program is a...

 or data flows
Flow (computer networking)
In packet switching networks, traffic flow, packet flow or network flow is a sequence of packets from a source computer to a destination, which may be another host, a multicast group, or a broadcast domain...

 are given access to system resources (e.g. processor time, communications bandwidth). This is usually done to load balance
Load balancing (computing)
Load balancing is a computer networking methodology to distribute workload across multiple computers or a computer cluster, network links, central processing units, disk drives, or other resources, to achieve optimal resource utilization, maximize throughput, minimize response time, and avoid...

 a system effectively or achieve a target quality of service
Quality of service
The quality of service refers to several related aspects of telephony and computer networks that allow the transport of traffic with special requirements...

. The need for a scheduling algorithm arises from the requirement for most modern systems to perform multitasking
Computer multitasking
In computing, multitasking is a method where multiple tasks, also known as processes, share common processing resources such as a CPU. In the case of a computer with a single CPU, only one task is said to be running at any point in time, meaning that the CPU is actively executing instructions for...

 (execute more than one process at a time) and multiplexing
Multiplexing
The multiplexed signal is transmitted over a communication channel, which may be a physical transmission medium. The multiplexing divides the capacity of the low-level communication channel into several higher-level logical channels, one for each message signal or data stream to be transferred...

 (transmit multiple flows simultaneously).

The scheduler is concerned mainly with:
  • Throughput
    Throughput
    In communication networks, such as Ethernet or packet radio, throughput or network throughput is the average rate of successful message delivery over a communication channel. This data may be delivered over a physical or logical link, or pass through a certain network node...

     - number of processes that complete their execution per time unit.
  • Latency
    Latency (engineering)
    Latency is a measure of time delay experienced in a system, the precise definition of which depends on the system and the time being measured. Latencies may have different meaning in different contexts.-Packet-switched networks:...

    , specifically:
    • Turnaround - total time between submission of a process and its completion.
    • Response time
      Response time
      In technology, response time is the time a system or functional unit takes to react to a given input.- Data processing :In data processing, the response time perceived by the end user is the interval between the instant at which an operator at a terminal enters a request for a response from a...

       - amount of time it takes from when a request was submitted until the first response is produced.
  • Fairness / Waiting Time - Equal CPU time to each process (or more generally appropriate times according to each process' priority).


In practice, these goals often conflict (e.g. throughput versus latency), thus a scheduler will implement a suitable compromise.
Preference is given to any one of the above mentioned concerns depending upon the user's needs and objectives.

In real-time
Real-time computing
In computer science, real-time computing , or reactive computing, is the study of hardware and software systems that are subject to a "real-time constraint"— e.g. operational deadlines from event to system response. Real-time programs must guarantee response within strict time constraints...

 environments, such as mobile devices for automatic control
Automatic control
Automatic control is the application of concepts derived from the research area of modern control theory. Automatic control is also a technology for application of control strategies. The implementing requires prior of analyzing and modeling of the subject to be controlled...

 in industry (for example robotics
Robotics
Robotics is the branch of technology that deals with the design, construction, operation, structural disposition, manufacture and application of robots...

), the scheduler also must ensure that processes can meet deadlines
Time limit
A time limit or deadline is a narrow field of time, or particular point in time, by which an objective or task must be accomplished.In project management, deadlines are most often associated with milestone goals....

; this is crucial for keeping the system stable. Scheduled tasks are sent to mobile devices and managed through an administrative back end.

Types of operating system schedulers

Operating systems may feature up to 3 distinct types of scheduler, 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 these functions are performed.
The Scheduler is an operating system module that selects the next jobs to be admitted into the system and the next process to run.

Long-term scheduling

The long-term, or admission scheduler, decides which jobs or processes are to be admitted to the ready queue (in the 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 - i.e.: whether a high or low amount of processes are to be executed concurrently, and how the split between IO intensive and CPU intensive processes is to be handled. In modern OS's, this is used to make sure that real time processes get enough CPU time to finish their tasks. Without proper real time scheduling, modern GUI interfaces would seem sluggish.
The long term queue exists in the Hard Disk or the "Virtual Memory". [Stallings, 399].

Long-term scheduling is also important in large-scale systems such as batch processing
Batch processing
Batch processing is execution of a series of programs on a computer without manual intervention.Batch jobs are set up so they can be run to completion without manual intervention, so all input data is preselected through scripts or command-line parameters...

 systems, computer clusters, supercomputer
Supercomputer
A supercomputer is a computer at the frontline of current processing capacity, particularly speed of calculation.Supercomputers are used for highly calculation-intensive tasks such as problems including quantum physics, weather forecasting, climate research, molecular modeling A supercomputer is a...

s and render farm
Render farm
A render farm is a computer cluster built to render computer-generated imagery , typically for film and television visual effects, using off-line batch processing. This is different from a render wall, which is a networked, tiled display used for real-time rendering...

s. In these cases, special purpose job scheduler
Job scheduler
A job scheduler is a software application that is in charge of unattended background executions, commonly known for historical reasons as batch processing....

 software is typically used to assist these functions, in addition to any underlying admission scheduling support in the operating system.'Italic text

Medium-term scheduling

The medium-term scheduler temporarily removes processes from main memory and places them on secondary memory (such as a disk drive) or vice versa. This is commonly referred to as "swapping out" or "swapping in" (also incorrectly as "paging
Paging
In computer operating systems, paging is one of the memory-management schemes by which a computer can store and retrieve data from secondary storage for use in main memory. In the paging memory-management scheme, the operating system retrieves data from secondary storage in same-size blocks called...

 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
Page fault
A page fault is a trap to the software raised by the hardware when a program accesses a page that is mapped in the virtual address space, but not loaded in physical memory. In the typical case the operating system tries to handle the page fault by making the required page accessible at a location...

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. [Stallings, 396] [Stallings, 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". [stallings, 394]

Short-term scheduling

The short-term scheduler (also known as the CPU scheduler) decides which of the ready, in-memory processes are to be executed (allocated a CPU) next following a clock interrupt
Interrupt
In computing, an interrupt is an asynchronous signal indicating the need for attention or a synchronous event in software indicating the need for a change in execution....

, an IO interrupt, an operating system call
System call
In computing, a system call is how a program requests a service from an operating system's kernel. This may include hardware related services , creating and executing new processes, and communicating with integral kernel services...

 or another form of signal
Signal programming
Signal programming is used in the same sense as dataflow programming, and is similar to event-driven programming.The word signal is used instead of the word dataflow in documentation of such libraries as Qt, GTK+ and libsigc++...

. Thus the short-term scheduler makes scheduling decisions much more frequently than the long-term or mid-term schedulers - a scheduling decision will at a minimum have to be made after every time slice, and these are very short. This scheduler can be preemptive
Preemption (computing)
In computing, preemption is the act of temporarily interrupting a task being carried out by a computer system, without requiring its cooperation, and with the intention of resuming the task at a later time. Such a change is known as a context switch...

, 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. [Stallings, 396]. In most cases short-term scheduler is written in assembler because it is a critical part of the operating system.

Dispatcher

Another component involved in the CPU-scheduling function is the dispatcher. The dispatcher is the module that gives control of the CPU to the process selected by the short-term scheduler. This function involves the following:
  • Switching context
  • Switching to user mode
  • Jumping to the proper location in the user program to restart that program


The dispatcher should be as fast as possible, since it is invoked during every process switch. The time it takes for the dispatcher to stop one process and start another running is known as the dispatch latency. [Gravin, 155].

Scheduling disciplines

Scheduling disciplines are algorithms 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
Operating system
An operating system is a set of programs that manage computer hardware resources and provide common services for application software. The operating system is the most important type of system software in a computer system...

s (to share CPU time
CPU time
CPU time is the amount of time for which a central processing unit was used for processing instructions of a computer program, as opposed to, for example, waiting for input/output operations. The CPU time is often measured in clock ticks or as a percentage of the CPU's capacity...

 among both threads
Thread (computer science)
In computer science, a thread of execution is the smallest unit of processing that can be scheduled by an operating system. The implementation of threads and processes differs from one operating system to another, but in most cases, a thread is contained inside a process...

 and processes
Process (computing)
In computing, a process is an instance of a computer program that is being executed. It contains the program code and its current activity. Depending on the operating system , a process may be made up of multiple threads of execution that execute instructions concurrently.A computer program is a...

), disk drives (I/O scheduling
I/O scheduling
Input/output scheduling is a term used to describe the method computer operating systems decide the order that block I/O operations will be submitted to storage volumes...

), printers (print spooler), most embedded systems, etc.

The main purposes of scheduling algorithms are to minimize resource starvation
Resource starvation
In computer science, starvation is a multitasking-related problem, where a process is perpetually denied necessary resources. Without those resources, the program can never finish its task....

 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 computer networks and other statistical multiplexing
Statistical multiplexing
Statistical multiplexing is a type of communication link sharing, very similar to dynamic bandwidth allocation . In statistical multiplexing, a communication channel is divided into an arbitrary number of variable bit-rate digital channels or data streams. The link sharing is adapted to the...

, the notion of a scheduling algorithm is used as an alternative to first-come first-served queuing of data packets.

The simplest best-effort scheduling algorithms are round-robin
Round-robin scheduling
Round-robin is one of the simplest scheduling algorithms for processes in an operating system. As the term is generally used, time slices are assigned to each process in equal portions and in circular order, handling all processes without priority . Round-robin scheduling is simple, easy to...

, fair queuing (a max-min fair scheduling algorithm), proportionally fair
Proportionally Fair
Proportional fair is a compromise-based scheduling algorithm. It's based upon maintaining a balance between two competing interests: Trying to maximize total wireless network throughput while at the same time allowing all users at least a minimal level of service...

 scheduling and maximum throughput
Maximum throughput scheduling
Maximum throughput scheduling is a procedure for scheduling data packets in a packet-switched best-effort communications network, typically a wireless network, in view to maximize the total throughput of the network, or the system spectral efficiency in a wireless network...

. If differentiated or guaranteed quality of service
Quality of service
The quality of service refers to several related aspects of telephony and computer networks that allow the transport of traffic with special requirements...

 is offered, as opposed to best-effort communication, weighted fair queuing
Weighted fair queuing
Weighted fair queuing is a data packet scheduling technique allowing different scheduling priorities to statistically multiplexed data flows.WFQ is a generalization of fair queuing . Both in WFQ and FQ, each data flow has a separate FIFO queue...

 may be utilized.

In advanced packet radio wireless networks such as HSDPA (High-Speed Downlink Packet Access ) 3.5G cellular system, channel-dependent scheduling may be used to take advantage of channel state information
Channel state information
In wireless communications, channel state information refers to 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 example, scattering, fading, and power decay with...

. If the channel conditions are favourable, the throughput
Throughput
In communication networks, such as Ethernet or packet radio, throughput or network throughput is the average rate of successful message delivery over a communication channel. This data may be delivered over a physical or logical link, or pass through a certain network node...

 and system spectral efficiency may be increased. In even more advanced systems such as LTE
LTE Advanced
LTE Advanced is a preliminary mobile communication standard, formally submitted as a candidate 4G system to ITU-T in late 2009, was approved into ITU, International Telecommunications Union, IMT-Advanced and expected to be finalized by 3GPP in early 2011...

, the scheduling is combined by channel-dependent packet-by-packet dynamic channel allocation, or by assigning OFDMA
OFDMA
Orthogonal Frequency-Division Multiple Access is a multi-user version of the popular Orthogonal frequency-division multiplexing digital modulation scheme. Multiple access is achieved in OFDMA by assigning subsets of subcarriers to individual users as shown in the illustration below...

 multi-carriers or other frequency-domain equalization components to the users that best can utilize them.

First in first out

Also known as First­ Come, First ­Served (FCFS), is the simplest scheduling algorithm, FIFO
FIFO
FIFO is an acronym for First In, First Out, an abstraction related to ways of organizing and manipulation of data relative to time and prioritization...

 simply queues processes in the order that they arrive in the ready queue.
  • 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, since long processes can hog the CPU
  • Turnaround time, waiting time and response time 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

Shortest remaining time

Similar to Shortest­ Job­ First (SJF). With this strategy the scheduler arranges processes with the least estimated processing time remaining to be next in the queue. This requires advance 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 may be 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' 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.

Fixed priority pre-emptive scheduling

The O/S 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.
  • 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 amounts of high priority processes queuing for CPU time.

Round-robin scheduling

The scheduler assigns a fixed time unit per process, and cycles through them.
  • RR scheduling involves extensive overhead, especially with a small time unit.
  • Balanced throughput between FCFS and SJF, shorter jobs are completed faster than in FCFS and longer processes are completed faster than in SJF.
  • Poor 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 FCFS.

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 problem

Overview

Scheduling algorithm CPU Overhead Throughput
Throughput
In communication networks, such as Ethernet or packet radio, throughput or network throughput is the average rate of successful message delivery over a communication channel. This data may be delivered over a physical or logical link, or pass through a certain network node...

Turnaround time Response time
Response time
In technology, response time is the time a system or functional unit takes to react to a given input.- Data processing :In data processing, the response time perceived by the end user is the interval between the instant at which an operator at a terminal enters a request for a response from a...

First In First Out Low Low High Low
Shortest Job First Medium High Medium Medium
Priority based scheduling
Fixed priority pre-emptive scheduling
Fixed-priority pre-emptive scheduling is a scheduling system commonly used in real-time systems. With fixed priority pre-emptive scheduling, the scheduler ensures that at any given time, the processor executes the highest priority task of all those tasks that are currently ready to execute.The...

Medium Low High High
Round-robin scheduling
Round-robin scheduling
Round-robin is one of the simplest scheduling algorithms for processes in an operating system. As the term is generally used, time slices are assigned to each process in equal portions and in circular order, handling all processes without priority . Round-robin scheduling is simple, easy to...

High Medium Medium High
Multilevel Queue scheduling
Multilevel Feedback Queue
In computer science, a multilevel feedback queue is a scheduling algorithm. It is intended to meet the following design requirements for multimode systems:#Give preference to short jobs.#Give preference to I/O bound processes....

High High Medium Medium

How to choose 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
Windows NT is a family of operating systems produced by Microsoft, the first version of which was released in July 1993. It was a powerful high-level-language-based, processor-independent, multiprocessing, multiuser operating system with features comparable to Unix. It was intended to complement...

/XP/Vista uses a Multilevel feedback queue
Multilevel Feedback Queue
In computer science, a multilevel feedback queue is a scheduling algorithm. It is intended to meet the following design requirements for multimode systems:#Give preference to short jobs.#Give preference to I/O bound processes....

, a combination of fixed priority preemptive scheduling, round-robin, and first in first out.
In this system, processes 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 scheduling
Round-robin is one of the simplest scheduling algorithms for processes in an operating system. As the term is generally used, time slices are assigned to each process in equal portions and in circular order, handling all processes without priority . Round-robin scheduling is simple, easy to...

 amongst the high priority processes and FIFO
FIFO
FIFO is an acronym for First In, First Out, an abstraction related to ways of organizing and manipulation of data relative to time and prioritization...

 among the lower ones. In this sense, response time is short for most processes, and short but critical system processes get completed very quickly. Since processes can only use one time unit of the round robin
Round-robin scheduling
Round-robin is one of the simplest scheduling algorithms for processes in an operating system. As the term is generally used, time slices are assigned to each process in equal portions and in circular order, handling all processes without priority . Round-robin scheduling is simple, easy to...

 in the highest priority queue, starvation can be a problem for longer high priority processes.

Operating system scheduler implementations

The algorithm used may be as simple as round-robin
Round-robin scheduling
Round-robin is one of the simplest scheduling algorithms for processes in an operating system. As the term is generally used, time slices are assigned to each process in equal portions and in circular order, handling all processes without priority . Round-robin scheduling is simple, easy to...

 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
Symmetric multiprocessing
In computing, symmetric multiprocessing involves a multiprocessor computer hardware architecture where two or more identical processors are connected to a single shared main memory and are controlled by a single OS instance. Most common multiprocessor systems today use an SMP architecture...

(symmetric multiprocessing) systems, processor affinity
Processor affinity
Processor affinity is a modification of the native central queue scheduling algorithm in a symmetric multiprocessing operating system. Each task in the queue has a tag indicating its preferred / kin processor...

 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.

Windows

Very early MS-DOS
MS-DOS
MS-DOS is an operating system for x86-based personal computers. It was the most commonly used member of the DOS family of operating systems, and was the main operating system for IBM PC compatible personal computers during the 1980s to the mid 1990s, until it was gradually superseded by operating...

 and Microsoft Windows systems were non-multitasking, and as such did not feature a scheduler. Windows 3.1x
Windows 3.1x
Windows 3.1x is a series of 16-bit operating systems produced by Microsoft for use on personal computers. The series began with Windows 3.1, which was first sold during March 1992 as a successor to Windows 3.0...

 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
Windows NT is a family of operating systems produced by Microsoft, the first version of which was released in July 1993. It was a powerful high-level-language-based, processor-independent, multiprocessing, multiuser operating system with features comparable to Unix. It was intended to complement...

-based operating systems use a multilevel feedback queue
Multilevel Feedback Queue
In computer science, a multilevel feedback queue is a scheduling algorithm. It is intended to meet the following design requirements for multimode systems:#Give preference to short jobs.#Give preference to I/O bound processes....

. 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. Users can select 5 of these priorities to assign to a running application from the Task Manager application, or through thread management APIs. 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
Windows Vista is an operating system released in several variations developed by Microsoft for use on personal computers, including home and business desktops, laptops, tablet PCs, and media center PCs...

 to use the cycle counter register
Time Stamp Counter
The Time Stamp Counter is a 64-bit register present on all x86 processors since the Pentium. It counts the number of ticks since reset. The instruction "RDTSC" returns the TSC in EDX:EAX. In x86_64 mode, RDTSC also clears the higher 32 bits of RAX. Its opcode is 0F 31. Pentium competitors such as...

 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 don't interfere with foreground operations.

Mac OS

Mac OS 9 uses cooperative scheduling for threads, where one process controls multiple cooperative threads, and also provides preemptive scheduling for MP tasks. The kernel schedules MP tasks using a preemptive scheduling algorithm. All Process Manager processes run within a special MP task, called the "blue task". Those processes are scheduled cooperatively, using a round-robin scheduling
Round-robin scheduling
Round-robin is one of the simplest scheduling algorithms for processes in an operating system. As the term is generally used, time slices are assigned to each process in equal portions and in circular order, handling all processes without priority . Round-robin scheduling is simple, easy to...

 algorithm; a process yields control of the processor to another process by explicitly calling a blocking function 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.

Mac OS X uses a multilevel feedback queue
Multilevel Feedback Queue
In computer science, a multilevel feedback queue is a scheduling algorithm. It is intended to meet the following design requirements for multimode systems:#Give preference to short jobs.#Give preference to I/O bound processes....

, with four priority bands for threads - normal, system high priority, kernel mode only, and real-time. Threads are scheduled preemptively; Mac OS X also supports cooperatively-scheduled threads in its implementation of the Thread Manager in Carbon
Carbon (API)
Carbon is one of Apple Inc.'s procedural application programming interfaces for the Macintosh operating system. It provides C programming language access to Macintosh system services...

.

AIX

In AIX Version 4 there are three possible values for thread scheduling policy :
  • FIFO: 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.
  • RR: This is similar to the AIX Version 3 scheduler round-robin scheme based on 10ms 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 RR 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. This link provides additional information on AIX 5 scheduling: http://www.ibm.com/developerworks/aix/library/au-aix5_cpu/index.html#N100F6 .

Linux 2.4

In Linux
Linux
Linux is a Unix-like computer operating system assembled under the model of free and open source software development and distribution. The defining component of any Linux system is the Linux kernel, an operating system kernel first released October 5, 1991 by Linus Torvalds...

 2.4, an O(n) scheduler
O(n) scheduler
The O scheduler is the scheduler used in the Linux kernel between versions 2.4 and 2.6. Since version 2.6, it has been replaced by the O scheduler and later by the Completely Fair Scheduler .- Algorithm :...

 with a multilevel feedback queue
Multilevel Feedback Queue
In computer science, a multilevel feedback queue is a scheduling algorithm. It is intended to meet the following design requirements for multimode systems:#Give preference to short jobs.#Give preference to I/O bound processes....

 with priority levels ranging from 0-140. 0-99 are reserved for real-time tasks and 100-140 are considered nice
Nice (Unix)
nice is a program found on Unix and Unix-like operating systems such as Linux. nice directly maps to a kernel call of the same name. For a given process, it changes the priority in the kernel's scheduler. A niceness of −20 is the highest priority and 19 or 20 is the lowest priority...

 task levels was used. 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
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 run next...

 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 such as SUSE Linux Enterprise Server
SUSE Linux Enterprise Server
SUSE Linux Enterprise Server is a Linux distribution supplied by SUSE and targeted at the business market. It is targeted for servers, mainframes, and workstations but can be installed on desktop computers for testing as well. New major versions are released at an interval of 3-4 years, while...

 replaced this scheduler with a backport of the O(1) scheduler
O(1) scheduler
An O 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 operating system. One of the major goals of operating system designers is to minimize overhead and jitter of OS services, so that...

 (which was maintained by Alan Cox
Alan Cox
Alan Cox is a British computer programmer who formerly maintained the 2.2 branch of the Linux kernel and continues to be heavily involved in the development of the Linux kernel, an association that dates back to 1991...

 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

From versions 2.6 to 2.6.22, the kernel used an O(1) scheduler
O(1) scheduler
An O 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 operating system. One of the major goals of operating system designers is to minimize overhead and jitter of OS services, so that...

 developed by Ingo Molnar
Ingo Molnar
Ingo Molnár, currently employed by Red Hat, is a Hungarian Linux hacker. He is best known for his contributions to the operating system in terms of security and performance...

 and many other kernel developers during the Linux 2.5 development. For many kernel in time frame, Con Kolivas
Con Kolivas
Con Kolivas is an Australian anaesthetist who is known on the Internet for his programming work on the Linux kernel in his spare time. He has written patches for the kernel to improve its desktop performance, particularly reducing I/O impact...

 developed patch sets which improved interactivity with this scheduler or even replaced it with his own schedulers.

Since Linux 2.6.23

Con Kolivas
Con Kolivas
Con Kolivas is an Australian anaesthetist who is known on the Internet for his programming work on the Linux kernel in his spare time. He has written patches for the kernel to improve its desktop performance, particularly reducing I/O impact...

's work, most significantly his implementation of "fair scheduling
Fair-share scheduling
Fair-share scheduling is a scheduling strategy for computer operating systems in which the CPU usage is equally distributed among system users or groups, as opposed to equal distribution among processes....

" named "Rotating Staircase Deadline", inspired Ingo Molnár to develop the Completely Fair Scheduler
Completely Fair Scheduler
The Completely Fair Scheduler is the name of a task scheduler which was merged into the 2.6.23 release of the Linux kernel. It handles CPU resource allocation for executing processes, and aims to maximize overall CPU utilization while also maximizing interactive performance.Con Kolivas's work with...

 as a replacement for the earlier O(1) scheduler
O(1) scheduler
An O 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 operating system. One of the major goals of operating system designers is to minimize overhead and jitter of OS services, so that...

, crediting Kolivas in his announcement.

The Completely Fair Scheduler (CFS) uses a well-studied, classic scheduling algorithm called fair queuing
originally invented for packet networks. Fair queuing had been previously applied to CPU scheduling under the name stride scheduling
Stride scheduling
Stride scheduling mechanism 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 duration of standard time-slices in a fashion, that performs periodic recurrences of...

.

The fair queuing CFS scheduler has a scheduling complexity of O(log
Logarithm
The logarithm of a number is the exponent by which another fixed value, the base, has to be raised to produce that number. For example, the logarithm of 1000 to base 10 is 3, because 1000 is 10 to the power 3: More generally, if x = by, then y is the logarithm of x to base b, and is written...

 N), where N is the number of tasks in the runqueue
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 run next...

. Choosing a task can be done in constant time, but reinserting a task after it has run requires O(log N) operations, because the run queue
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 run next...

 is implemented as a red-black tree
Red-black tree
A red–black tree is a type of self-balancing binary search tree, a data structure used in computer science, typically to implement associative arrays. The original structure was invented in 1972 by Rudolf Bayer and named "symmetric binary B-tree," but acquired its modern name in a paper in 1978 by...

.

CFS is the first implementation of a fair queuing process scheduler widely used in a general-purpose operating system.

FreeBSD

FreeBSD
FreeBSD
FreeBSD is a free Unix-like operating system descended from AT&T UNIX via BSD UNIX. Although for legal reasons FreeBSD cannot be called “UNIX”, as the direct descendant of BSD UNIX , FreeBSD’s internals and system APIs are UNIX-compliant...

 uses a multilevel feedback queue
Multilevel Feedback Queue
In computer science, a multilevel feedback queue is a scheduling algorithm. It is intended to meet the following design requirements for multimode systems:#Give preference to short jobs.#Give preference to I/O bound processes....

 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
NetBSD is a freely available open source version of the Berkeley Software Distribution Unix operating system. It was the second open source BSD descendant to be formally released, after 386BSD, and continues to be actively developed. The NetBSD project is primarily focused on high quality design,...

 uses a multilevel feedback queue
Multilevel Feedback Queue
In computer science, a multilevel feedback queue is a scheduling algorithm. It is intended to meet the following design requirements for multimode systems:#Give preference to short jobs.#Give preference to I/O bound processes....

 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-128 for kernel threads, 128-191 for user real-time threads (SCHED_FIFO and SCHED_RR policies), and 192-223 for software interrupts
Interrupt
In computing, an interrupt is an asynchronous signal indicating the need for attention or a synchronous event in software indicating the need for a change in execution....

.

Solaris

Solaris uses a multilevel feedback queue
Multilevel Feedback Queue
In computer science, a multilevel feedback queue is a scheduling algorithm. It is intended to meet the following design requirements for multimode systems:#Give preference to short jobs.#Give preference to I/O bound processes....

 with priorities ranging from 0-169. 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's given a new priority and put back in the queue.

Summary

Operating System Preemption Algorithm
Windows 3.1x
Windows 3.1x
Windows 3.1x is a series of 16-bit operating systems produced by Microsoft for use on personal computers. The series began with Windows 3.1, which was first sold during March 1992 as a successor to Windows 3.0...

None Cooperative Scheduler
Windows 95
Windows 95
Windows 95 is a consumer-oriented graphical user interface-based operating system. It was released on August 24, 1995 by Microsoft, and was a significant progression from the company's previous Windows products...

, 98
Windows 98
Windows 98 is a graphical operating system by Microsoft. It is the second major release in the Windows 9x line of operating systems. It was released to manufacturing on 15 May 1998 and to retail on 25 June 1998. Windows 98 is the successor to Windows 95. Like its predecessor, it is a hybrid...

, Me
Windows Me
Windows Millennium Edition, or Windows Me , is a graphical operating system released on September 14, 2000 by Microsoft, and was the last operating system released in the Windows 9x series. Support for Windows Me ended on July 11, 2006....

Half Preemptive for 32-bit processes, Cooperative Scheduler for 16-bit processes
Windows NT
Windows NT
Windows NT is a family of operating systems produced by Microsoft, the first version of which was released in July 1993. It was a powerful high-level-language-based, processor-independent, multiprocessing, multiuser operating system with features comparable to Unix. It was intended to complement...

 (including 2000, XP, Vista, 7, and Server)
Yes Multilevel feedback queue
Multilevel Feedback Queue
In computer science, a multilevel feedback queue is a scheduling algorithm. It is intended to meet the following design requirements for multimode systems:#Give preference to short jobs.#Give preference to I/O bound processes....

Mac OS
Mac OS
Mac OS is a series of graphical user interface-based operating systems developed by Apple Inc. for their Macintosh line of computer systems. The Macintosh user experience is credited with popularizing the graphical user interface...

 pre-9
None Cooperative Scheduler
Mac OS
Mac OS
Mac OS is a series of graphical user interface-based operating systems developed by Apple Inc. for their Macintosh line of computer systems. The Macintosh user experience is credited with popularizing the graphical user interface...

 9
Some Preemptive for MP tasks, Cooperative Scheduler for processes and threads
Mac OS X
Mac OS X
Mac OS X is a series of Unix-based operating systems and graphical user interfaces developed, marketed, and sold by Apple Inc. Since 2002, has been included with all new Macintosh computer systems...

Yes Multilevel feedback queue
Multilevel Feedback Queue
In computer science, a multilevel feedback queue is a scheduling algorithm. It is intended to meet the following design requirements for multimode systems:#Give preference to short jobs.#Give preference to I/O bound processes....

Linux
Linux
Linux is a Unix-like computer operating system assembled under the model of free and open source software development and distribution. The defining component of any Linux system is the Linux kernel, an operating system kernel first released October 5, 1991 by Linus Torvalds...

 pre-2.6
Yes Multilevel feedback queue
Multilevel Feedback Queue
In computer science, a multilevel feedback queue is a scheduling algorithm. It is intended to meet the following design requirements for multimode systems:#Give preference to short jobs.#Give preference to I/O bound processes....

Linux
Linux
Linux is a Unix-like computer operating system assembled under the model of free and open source software development and distribution. The defining component of any Linux system is the Linux kernel, an operating system kernel first released October 5, 1991 by Linus Torvalds...

 2.6-2.6.23
Yes O(1) scheduler
O(1) scheduler
An O 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 operating system. One of the major goals of operating system designers is to minimize overhead and jitter of OS services, so that...

Linux
Linux
Linux is a Unix-like computer operating system assembled under the model of free and open source software development and distribution. The defining component of any Linux system is the Linux kernel, an operating system kernel first released October 5, 1991 by Linus Torvalds...

 post-2.6.23
Yes Completely Fair Scheduler
Completely Fair Scheduler
The Completely Fair Scheduler is the name of a task scheduler which was merged into the 2.6.23 release of the Linux kernel. It handles CPU resource allocation for executing processes, and aims to maximize overall CPU utilization while also maximizing interactive performance.Con Kolivas's work with...

Solaris Yes Multilevel feedback queue
Multilevel Feedback Queue
In computer science, a multilevel feedback queue is a scheduling algorithm. It is intended to meet the following design requirements for multimode systems:#Give preference to short jobs.#Give preference to I/O bound processes....

NetBSD
NetBSD
NetBSD is a freely available open source version of the Berkeley Software Distribution Unix operating system. It was the second open source BSD descendant to be formally released, after 386BSD, and continues to be actively developed. The NetBSD project is primarily focused on high quality design,...

Yes Multilevel feedback queue
Multilevel Feedback Queue
In computer science, a multilevel feedback queue is a scheduling algorithm. It is intended to meet the following design requirements for multimode systems:#Give preference to short jobs.#Give preference to I/O bound processes....

FreeBSD
FreeBSD
FreeBSD is a free Unix-like operating system descended from AT&T UNIX via BSD UNIX. Although for legal reasons FreeBSD cannot be called “UNIX”, as the direct descendant of BSD UNIX , FreeBSD’s internals and system APIs are UNIX-compliant...

Yes Multilevel feedback queue
Multilevel Feedback Queue
In computer science, a multilevel feedback queue is a scheduling algorithm. It is intended to meet the following design requirements for multimode systems:#Give preference to short jobs.#Give preference to I/O bound processes....


See also

  • Activity selection problem
    Activity selection problem
    The activity selection problem is a mathematical optimization problem concerning the selection of non-conflicting activities to perform within a given time frame, given a set of activities each marked by a start time and finish time...

  • Aging (scheduling)
    Aging (scheduling)
    Aging is the process of gradually increasing the priority of a task, based on its waiting time. The aging technique estimates the time a process will run based on a weighted average of previous estimates and measured values. Aging can be used to reduce starvation of low priority tasks...

  • Atropos scheduler
    Atropos scheduler
    In computer science, Atropos is a real-time scheduling algorithm developed at Cambridge University. It combines the Earliest Deadline First algorithm with a best effort scheduler to make use of slack time, while exercising strict admission control....

  • Automated planning and scheduling
    Automated planning and scheduling
    Automated planning and scheduling is a branch of artificial intelligence that concerns the realization of strategies or action sequences, typically for execution by intelligent agents, autonomous robots and unmanned vehicles. Unlike classical control and classification problems, the solutions are...

  • Brain Fuck Scheduler
    Brain Fuck Scheduler
    The Brain Fuck Scheduler is a task scheduler designed for the Linux kernel in August of 2009 as an alternative to the Completely Fair Scheduler and the O scheduler...

  • Completely Fair Scheduler
    Completely Fair Scheduler
    The Completely Fair Scheduler is the name of a task scheduler which was merged into the 2.6.23 release of the Linux kernel. It handles CPU resource allocation for executing processes, and aims to maximize overall CPU utilization while also maximizing interactive performance.Con Kolivas's work with...

  • Computer multitasking
    Computer multitasking
    In computing, multitasking is a method where multiple tasks, also known as processes, share common processing resources such as a CPU. In the case of a computer with a single CPU, only one task is said to be running at any point in time, meaning that the CPU is actively executing instructions for...

  • Cyclic executive
    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/C++....

  • Dynamic priority scheduling
    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 form an optimal configuration in self-sustained manner...

  • Earliest deadline first scheduling
    Earliest deadline first scheduling
    Earliest deadline first or least time to go is a dynamic scheduling algorithm used in real-time operating systems. It places processes in a priority queue. Whenever a scheduling event occurs the queue will be searched for the process closest to its deadline...

  • Foreground-background
    Foreground-background
    Foreground-background is a scheduling algorithm that is used to control 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 initially enter, and the second one is called background...

  • Interruptible operating system
    Interruptible operating system
    Interruptible operating systems are the operating systems with ability to handle multiple interrupts concurrently, or in other words, which allow interrupts to be interrupted....

  • I/O scheduling
    I/O scheduling
    Input/output scheduling is a term used to describe the method computer operating systems decide the order that block I/O operations will be submitted to storage volumes...

  • Job Shop Scheduling
    Job Shop Scheduling
    Job shop scheduling is an optimization problem in computer science in which ideal jobs are assigned to resources at particular times. The most basic version is as follows:...

  • Least slack time scheduling
    Least slack time scheduling
    Least Slack Time scheduling is a scheduling algorithm. It assigns priority based on the slack time of a process. Slack time is the amount of time left after a job if the job was started now. This algorithm is also known as Least Laxity First. Its most common use is in embedded systems, especially...

  • Lottery scheduling
    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 tickets need not be uniform; granting a process more...

  • Multilevel feedback queue
    Multilevel Feedback Queue
    In computer science, a multilevel feedback queue is a scheduling algorithm. It is intended to meet the following design requirements for multimode systems:#Give preference to short jobs.#Give preference to I/O bound processes....

  • O(1) scheduler
    O(1) scheduler
    An O 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 operating system. One of the major goals of operating system designers is to minimize overhead and jitter of OS services, so that...

  • Priority inversion
    Priority inversion
    In computer science, priority inversion is a problematic scenario in scheduling when a higher priority task is indirectly preempted by a lower priority task effectively "inverting" the relative priorities of the two tasks....

  • Process (computing)
    Process (computing)
    In computing, a process is an instance of a computer program that is being executed. It contains the program code and its current activity. Depending on the operating system , a process may be made up of multiple threads of execution that execute instructions concurrently.A computer program is a...

  • Process states
    Process states
    In a multitasking computer system, processes may occupy a variety of states. These distinct states may not actually be recognized as such by the operating system kernel, however they are a useful abstraction for the understanding of processes....

  • Rate-monotonic scheduling
    Rate-monotonic scheduling
    In computer science, rate-monotonic scheduling is a scheduling algorithm used in real-time operating systems with a static-priority scheduling class...

  • Round-robin scheduling
    Round-robin scheduling
    Round-robin is one of the simplest scheduling algorithms for processes in an operating system. As the term is generally used, time slices are assigned to each process in equal portions and in circular order, handling all processes without priority . Round-robin scheduling is simple, easy to...


Further reading

The source of this article is wikipedia, the free encyclopedia.  The text of this article is licensed under the GFDL.
 
x
OK