Scheduling

On a busy computer hundreds of processes are ready to run, but each core can run only one at a time. The scheduler is the part of the OS that decides who goes next and for how long. Different methods trade off different goals: getting through as much work as possible, keeping waiting times short, responding quickly to the user, and treating every process fairly.

• Burst time: how much CPU time a process needs.
• Turnaround time = finish time − arrival time: how long the whole job took, from the process's point of view.
• Waiting time = turnaround time − burst time: time spent ready but not running.
• Response time: from arriving to first getting the CPU. It matters most for interactive programs.
• Throughput: how many processes are completed per unit of time.
• CPU utilisation: the percentage of time the CPU is doing useful work rather than sitting idle or switching between processes.

A good schedule keeps CPU utilisation and throughput high and turnaround, waiting and response times low, while treating every process fairly. No method wins on all of these at once, which is why there are several.

Some methods let a process run until it finishes or blocks. Others are pre-emptive: the scheduler can take the CPU away mid-task (pre-emption). Every switch from one process to another is a context switch: the leaving process's registers are saved and the next one's restored. It is necessary, but time spent switching does no useful work.

Processes run in the order they arrive, each until it finishes. It is the simplest method and fair in the sense of a queue at a shop. But it is not pre-emptive, so one long job holds up everything behind it: the convoy effect. Short jobs, which could have finished almost at once, wait a long time, so the average waiting time is high.

Each process gets a fixed time quantum (say 10 ms). If it has not finished when the quantum ends, it is pre-empted and goes to the back of the queue. No process can hog the CPU, and every process gets a turn regularly, so the system feels responsive. Choosing the quantum is a balance: too short and the CPU spends a large share of its time on context switches; too long and round robin turns back into FCFS.

Every process has a priority (here, 1 is the most important) and the highest-priority ready process runs. In the pre-emptive version, a more important process that arrives takes the CPU at once; in the non-pre-emptive version it waits for the current one to finish. Urgent work is handled quickly, but a low-priority process can wait for ever if more important ones keep arriving: starvation. The usual cure is ageing, raising a process's priority the longer it waits.

A static priority is set when the process is created and never changes; a dynamic one is adjusted as it runs (ageing is one example; another is raising the priority of a process that has just been woken by user input). Priority also interacts badly with shared resources: if a low-priority process holds a lock that a high-priority one needs, the important process is stuck behind the unimportant one. That is priority inversion, covered in A1.3.5.

Processes are sorted into separate queues by type, for example system processes, interactive programs and background jobs, and each queue has its own method (round robin for interactive work, FCFS for background jobs). A lower queue only gets the CPU when every higher queue is empty. This handles a mix of very different processes well, but it is more complicated, processes are stuck in the queue they were put in, and the bottom queue can starve.

Real operating systems combine these ideas. In a multilevel feedback queue, processes can move between queues according to how they behave. A process that uses up its whole quantum (a long calculation) drops to a lower queue with a longer quantum; one that keeps giving up the CPU early to wait for input (an interactive program) stays high; and one that has waited a long time is moved up, which is ageing. The result is round robin's responsiveness for interactive work, few context switches for long jobs, and no starvation. Windows, macOS and Linux all use hybrids of this kind.

Four processes (the simulator's starting set). For round robin and the top queue of the multilevel queue, the quantum is 2. In the multilevel queue P2 and P4 are in the top queue and P1 and P3 in the lower one.

Under FCFS they simply run in order: P1 0–7, P2 7–10, P3 10–14, P4 14–16. P2 arrives at 1 but finishes at 10, so its turnaround is 9 and its waiting time 6. Under round robin the order is P1 0–2, P2 2–4, P3 4–6, P1 6–8, P4 8–10, P2 10–11, P3 11–13, P1 13–16. The results of all five methods: