Part 2 of 7 · 2 min read
Priorities
In plain words: At a hospital, an emergency patient is treated before a patient with a sprained wrist, whatever the order of arrival. The analogy stops in one place: a hospital knows the severity from a diagnosis, while a scheduler must be told the priority or work it out.
In priority scheduling, each process has a priority, a number that ranks it, and the processor goes to the ready process with the best rank. In this book, a lower number means a higher priority, the convention of Unix (a nice value of -20 is the most favoured). Equal priorities are served in order of arrival. SJF is a special case: the priority is the predicted burst length, so shorter means more important.
Priorities come from two sources. Internal priorities are set by the system from measurements, such as the recent CPU use or the burst length. External priorities come from outside the system: the owner of the process, its importance or a payment (a nice command, or a real-time class, page 6).
Here is a workload made up to show the idea (arrival, CPU time, priority; lower is better): A (0, 5, 2), B (1, 3, 4), C (2, 8, 1), D (3, 2, 3).
Non-preemptive. A is alone at 0 and runs to 5. At 5, B (4), C (1) and D (3) are ready, and C wins. C runs from 5 to 13. Then D (3) beats B (4): D from 13 to 15, B from 15 to 18.
A 0-5 | C 5-13 | D 13-15 | B 15-18
Preemptive. A runs from 0. At time 2, C arrives with a better priority (1 against 2), so C preempts A. C runs from 2 to 10. Then A (priority 2) continues from 10 to 13, then D from 13 to 15 and B from 15 to 18.
A 0-2 | C 2-10 | A 10-13 | D 13-15 | B 15-18
| A | B | C | D | Average | |
|---|---|---|---|---|---|
| Waiting, non-preemptive | 0 | 14 | 3 | 10 | 6.75 |
| Waiting, preemptive | 8 | 14 | 0 | 10 | 8.00 |
| Response, non-preemptive | 0 | 14 | 3 | 10 | 6.75 |
| Response, preemptive | 0 | 14 | 0 | 10 | 6.00 |
The preemptive version helps the most important process (C waited 0) and costs the others. B, the lowest priority, waited 14 in both versions.
Priority scheduling
Priority scheduling is a policy in which every process has a numeric priority and the processor always goes to the ready process with the highest priority, with ties broken by order of arrival; in the preemptive form, a newly ready process with a higher priority takes the processor at once.
Example: with priorities A = 2 and C = 1 (lower is better), C preempts A when it arrives, as in the trace.
Check yourself: 1. In the non-preemptive trace, why did C run before D? 2. Which process waited longest, and why? 3. How is SJF a form of priority scheduling?