Scheduling — Operating Systems

Overview

Scheduling is an operating system task which attempts to ensure that each process gets "fair" access to hardware resources such as processor time or communications bandwidth. Ensuring that each process has "fair" access to the hardware resources of the machine helps increase the quality of service and reduces the load on the system produced by any one program.

A scheduler can be used to target a number of criterion:

• Throughput - The total number of processes that complete their execution per time unit.
• Latency
  • Turnaround time - Total time between the start and end of any given process
  • Response time - The amount of time from the start of a process to the first usable output.
• Waiting Time - Reducing the amount of time that a given process spends in the "ready queue".
• Fairness - In which every process is given an appropriate amount of access to the CPU according to its priority.

There are various different algorithms that each try to cover different aspects of these criteria, it is down to the designers of the operating system which best fits their work case.

Scheduler types

The three types of scheduler are indicative of frequency in which they are invoked.

As in the diagram, these can be seen as nested within each other, and each state from our process states fits within a particular level of the nest. The long-term scheduler is used when a process is in the created or terminated state, the medium-term when virtual memory is in use and the short term scheduler for everything else.

Long-term scheduling

A long-term scheduler, or admission scheduler, is responsible for determining the overall concurrency of the system at a given moment, it can do this by determining the amount of processes that should be in the ready queue at any one time and disallowing or delaying new processes if that limit is exceeded.

The long term scheduler is essential for ensuring the responsiveness of a system as it helps to prevent thrashing and other negative consequences of overtaxing the processor. They are also commonly used in super computers and other large systems for sequencing the order of jobs to be executed.

Medium-term scheduling

The medium term scheduler is responsible for managing a system's virtual memory. When the system requires additional resources for high priority processes, the medium term scheduler may decide that processes with low priority, processes being blocked, or that have not performed any actions recently should be "swapped out" to virtual memory. It is then responsible for loading these processes back into main memory when they require execution again.

Short-term scheduling

The short-term scheduler is perhaps the most important of the schedulers, and thus is invoked most frequently by the operating system. Its function is to determine the next process that the CPU should spend time executing. A preemptive scheduler may force processes off the system if they exceed their allowed execution time, a non-preemptive scheduler must wait for the process to yield control back to it.

A preemptive scheduler relies on an interrupt being fired by a programmable timer within the hardware which relinquishes control of the processor back to the kernel.

Dispatcher

The dispatcher is not a scheduler. Its role is to perform the bidding of the short-term scheduler by giving control of the processor to the process that has been chosen for execution. It does this by:

1. Switch context (removing the old process from the registers and back into main memory and replacing it with the new one)
2. Switching the processor to user mode (lowering the privileges of the process being executed)
3. Jumping to the correct location in the loaded process and starting its execution.

The dispatcher should be as fast as possible as during a context switch the processor is idle.

Methods of scheduling

First come, first serve (FCFS or FIFO)

First come, first serve (or First in, first out), is the simplest way of scheduling processes. When a process finishes execution, it is placed at the back of a queue and every process in front of it is executed. As the queue is never reordered, the overhead of this implementation is low, however it also results in high turnaround, waiting and response times when long processes are in the queue ahead of shorter processes (throughput is low with long processes).

As long as a process can finish (i.e. it doesn't try to execute forever), starvation is not possible in a FCFS scheduler as every process is eventually serviced.

Round-robin (RR)

In round robin, each process is given a fixed amount of time to run and can not exceed this time, this is an example of a preemptive scheduler. The overhead of forcing processes off the processor is high, this is compounded with a small timestep. As processes are executed in a circular fashion, the waiting, turnaround and response times are based on the number of processes in the system as opposed to their length, as a result all of these times can be high.

As with FCFS, starvation can not occur as every process is eventually serviced.

Shortest process next (SPN)

Shortest process next schedules the process with the smallest overall execution time next. This bias towards short processes results in high throughput and low response times for them. However, long processes may suffer under this system with high waiting times, low throughput and possible starvation if short processes are continually added to the system in front of the long processes.

Shortest remaining time (SRT)

Shortest remain time is a preemptive version of SPN, and thus suffers from many of its downsides. The process with the smallest amount of time till completion is chosen for execution and the process will run until completion, or until a shorter process is added to the system. The overhead of this is low, as a scheduling decision only needs to be made when a new process has been added or an existing one has been completed. Again, like SPN, this is good for short processes but results in poor response and waiting times, and low throughput for long processes, as well as possible starvation.

Shortest process next and Shortest remaining time also typically requires a way of estimating the execution time of a process, which can be difficult in a general purpose computer.

Highest response ratio next (HRRN)

Another derivative of SPN, however it also takes into account the amount of time the process has been waiting, this allows long processes to compete with short processes for processor time, this prevents starvation, and decreases waiting and response times for long processes.

Multilevel feedback queue (MLFQ)

A multilevel feedback queue scheduler is designed to give priority to I/O bound and short processes and separate different priorities, based on their need for processor time. It is a preemptive scheduling algorithm.

It utilises multiple FIFO queues to function. A process starts in the highest level queue and is eventually scheduled to the processor:

• If the process completes, then it leaves the system without ever rejoining a queue.
• If the process manually relinquishes control of the system back to the scheduler, then it is allowed to rejoin the same queue level when it is ready for execution again.
• If the process exceeds the amount of time that it has been assigned, it is pre-empted and is moved down a queue level.

If a process reaches the bottom queue level, then they are executed in a round robin fashion until completion. However, if a process performs an I/O operation and causes a block, it will be moved up a queue level, giving it a higher priority again.

This approach results in low response time and high throughput for short processes and those that perform many I/O operations, and response times for long processes is based on the number of them in the system (as in round robin).

Comparison of scheduling methods

Decision function represents how the algorithm chooses the next process for execution, where:

• `w` is the time spent waiting in the system
• `s` is the total service time required for execution
• `e` is the total time spent executing this process so far

There is no single one size fits all scheduling algorithm, therefore the designer of the operating system must decide which algorithm best fits their use case. Many modern operating systems opt to implement multiple scheduling algorithms, for example: Windows NT/XP/Vista uses a mix of MLFQ, RR, FCFS and fixed priority preemptive scheduling.