Scheduling

We have talked of processes, and task-switching, and interrupts and blocking... but we have so far entirely glossed over the real decisions that the kernel must make about which process (or thread) to run, and when. The policy decisions are made by the scheduler. (It is sometimes useful to think about the division between policy and mechanism.)

scheduler---makes policy decisions about which tasks to run
dispatcher---provides mechanism by actually switching between tasks

We have descibed how the processes switches rapidly between tasks to provide the illusion of concurrency. Indeed the simplest approach is to give each runnable task an equal slice of the CPU. This is known as round robin scheduling. It's common, simple, and the basis of scheduling techniques on all modern OSs. Equal time slices are not the only approach, however. We may wish to increase or decrease the time-slices based on the priority of each task. Or always run high-priority tasks in preference to low-priority tasks...

There are several approaches, so we need some criteria on which to judge the different policies:

Fairness---each process gets a metaphorical bite at the cherry
Efficiency---the processor should be busy 100% of the time
Response time---users (or other real-time hardware) should not have to wait long
Turnaround---minimise time for batch jobs
Throughput---maximise number of jobs per hour

The time we give to any one task before swapping to another is called the task's quantum, or time slice.

The actual process of task-switching incurs an overhead of several milliseconds, which is essentially 'wasted' time (because it is spent on OS bookkeeping rather than processing tasks).

Scheduling policies:

First-come, first-served (and Shortest Job First): Don't preempt processes at all
Round-robin: Give each process an equal go on the processor
Priority: Some tasks are more important than others
Real-time: Respect the deadlines of processes
Multilevel: Multiple process queues

Summary

In reality, scheduling policies are often a mixture of several of the above approaches, often based on a mixture of round-robin and priority scheduling.

For example, consider Linux's scheduling policy.

last updated 20 February 1997