Part 3 of 6 · 2 min read
Who decides
In plain words: In a restaurant, the head waiter decides which party is seated next, and a junior waiter walks them to the table. The decision and the walking are different jobs. The analogy stops in one place: a party can ask to stay at the table, while a process cannot refuse a switch ordered by the kernel.
The scheduler is the part of the kernel that chooses which ready process (or thread, Level 2) runs next. The ready queue is the list of processes that could run now, if a processor were free. The dispatcher is the code that carries out the choice: it saves the old context, loads the new one and returns to user mode (Level 1, page 5). The time this takes is the dispatch latency. A test in Level 1 measured a switch at about one microsecond on this machine, so the dispatcher is cheap compared with a burst of milliseconds. The cost matters only when switches become very frequent (page 3).
Scheduling decisions are needed in four situations:
- A running process changes to waiting (for example, it calls
read). - A running process changes to ready (for example, a timer interrupt arrives).
- A waiting process changes to ready (its I/O finished).
- A process ends.
For cases 1 and 4, the processor is free, and a choice must be made. For cases 2 and 3, the running process could continue, and the scheduler may let it. A system that makes choices only in cases 1 and 4 is non-preemptive (or cooperative): once a process has the processor, it keeps it until it waits or ends. A system that also decides in cases 2 and 3 is preemptive: the kernel may take the processor away from a running process. Modern general-purpose systems, Linux among them, are preemptive, and the timer interrupt of Level 0 is what makes it possible.
Preemption has a price. Two threads can be interrupted in the middle of updating shared data, which is the race condition of Level 2, page 4. Level 4 is about managing that.
Preemptive scheduling
Preemptive scheduling is a policy in which the kernel may stop a running process and give the processor to another one before the first has waited or ended, usually on a timer interrupt or when a more important process becomes ready.
Example: a process that computes in an endless loop still loses the processor after its time slice on Linux, because the kernel preempts it.
Check yourself: 1. What is the difference between the scheduler and the dispatcher? 2. In which of the four situations does a non-preemptive system decide? 3. Why does preemption make shared data dangerous?