Editing Scheduling (computing) (section)

==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 [[router (computing)|router]]s (to handle packet traffic) as well as in [[operating system]]s (to share [[CPU time]] among both [[thread (computer science)|threads]] and [[process (computing)|processes]]), disk drives ([[I/O scheduling]]), printers ([[print spooler]]), most embedded systems, etc.

The main purposes of scheduling algorithms are to minimize [[resource starvation]] 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]], the notion of a '''scheduling algorithm''' is used as an alternative to [[FIFO (computing and electronics)|first-come first-served]] queuing of data packets.

The simplest best-effort scheduling algorithms are [[round-robin scheduling|round-robin]], [[fair queuing]] (a [[max-min fair]] scheduling algorithm), [[proportional-fair scheduling]] and [[maximum throughput scheduling|maximum throughput]]. If differentiated or guaranteed [[quality of service]] is offered, as opposed to best-effort communication, [[weighted fair queuing]] 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]]. If the channel conditions are favourable, the [[throughput]] and [[system spectral efficiency]] may be increased. In even more advanced systems such as [[LTE Advanced|LTE]], the scheduling is combined by channel-dependent packet-by-packet [[dynamic channel allocation]], or by assigning [[OFDMA]] multi-carriers or other [[frequency-domain equalization]] components to the users that best can utilize them.<ref name=Miao>{{cite book|author1=Guowang Miao|author2=Jens Zander|author3=Ki Won Sung|author4=Ben Slimane|title=Fundamentals of Mobile Data Networks|publisher=[[Cambridge University Press]]|isbn=978-1107143210|year=2016|author1-link=Guowang Miao}}</ref>

===First come, first served===
{{Main|FIFO (computing and electronics)}}

[[File:Thread pool.svg|thumb|400px|A sample [[thread pool]] (green boxes) with a queue (FIFO) of waiting tasks (blue) and a queue of completed tasks (yellow)]]

''First in, first out'' ([[FIFO (computing and electronics)|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 '''{{visible anchor|task queue}}''', 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]], 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===
{{Main|Earliest deadline first scheduling}}
{{See also|Deadline-monotonic 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 ===
{{Main|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 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===
{{Main|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===
{{Main|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===
{{Main|Multilevel queue}}

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]] problems.

===Work-conserving schedulers===
{{Main|Work-conserving scheduler}}

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]] is minimized:
* [[Job-shop scheduling]]{{snd}} there are {{mvar|n}} jobs and {{mvar|m}} identical stations. Each job should be executed on a single machine. This is usually regarded as an online problem.
* [[Open-shop scheduling]]{{snd}} there are {{mvar|n}} jobs and {{mvar|m}} different stations. Each job should spend some time at each station, in a free order.
* [[Flow-shop scheduling]]{{snd}} there are {{mvar|n}} jobs and {{mvar|m}} 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]]/XP/Vista uses a [[multilevel feedback queue]], a combination of fixed-priority preemptive scheduling, round-robin, and first in, first out algorithms. In this system, threads can dynamically increase or decrease in priority depending on if it has been serviced already, or if it has been waiting extensively. Every priority level is represented by its own queue, with [[round-robin scheduling]] among the high-priority threads and [[FIFO (computing and electronics)|FIFO]] among the lower-priority ones. In this sense, response time is short for most threads, and short but critical system threads get completed very quickly. Since threads can only use one time unit of the round-robin in the highest-priority queue, starvation can be a problem for longer high-priority threads.