Priority Scheduling, Starvation and Ageing

Average turnaround time: 54 / 5 = 10.80

Average waiting time: 35 / 5 = 7

Context switches: 6

P1 appears three times. It started, was thrown off at 1 by P2 of priority 1, resumed, was thrown off again at 4 by P5 of priority 2, and finally finished at 16. Its completion time is the end of its last slice, which is Chapter forty six's second warning, and its two extra appearances are two extra context switches.

Starvation, and the fix

Indefinite blocking, or starvation, is the problem of priority scheduling. A low priority process is ready, and a higher priority one is always ready too, so the low priority process never runs. On a loaded system it may never run at all.

The story every textbook tells is worth repeating because it fixes the idea: when an IBM 7094 at MIT was shut down in 1973 a low priority process was found that had been submitted in 1967 and had not yet run.

Ageing

Ageing is the fix: increase the priority of a process the longer it waits. However bad its priority starts, it improves while it waits, and eventually it is the best in the queue.

Worked as a sum. Priorities run from 127, the worst, to 0, the best, and a waiting process's priority number is reduced by 1 for every 15 minutes it waits.

So the worst possible process is guaranteed to run within about thirty two hours, whatever else arrives. That turns "it might never run" into a number, which is Chapter thirty four's bounded waiting.

Ageing costs something. A process whose priority rises can overtake a process that genuinely is more important, so a real system usually resets a process's priority after it has run.

Distinctions that carry marks

What it does not mean

A priority is not a guarantee of speed. It decides order, not duration.

Preemptive priority is not unfair to the preempted process. It loses no work: its state is saved and it resumes exactly where it was.

Ageing is not the same as round robin. Round robin gives everybody a turn regardless of priority. Ageing keeps the priority order and makes the order change over time.

Quick revision

• Priority scheduling runs the ready process with the highest priority.

In this book a smaller number is a higher priority, and an answer must say which convention it uses.

• Both forms exist. The preemptive form throws the running process off when a better one

arrives; the non-preemptive form makes it wait.

• Priorities are internal, from something the system can measure, or external, from

outside it.

• Shortest job first is priority scheduling with the priority set to the inverse of the next

burst.

• The problem is indefinite blocking, or starvation: a low priority process may never

run.

• The fix is ageing: raise a process's priority the longer it waits. From 127 to 0 at one

step per fifteen minutes is 1,905 minutes, about 31.75 hours, which is a bound.

• Under the preemptive form a process appears several times on the chart and its completion is

the end of the last one.

Test yourself

1. State the rule and the convention you are using. The processor goes to the ready process

with the highest priority; in this answer a smaller number means a higher priority.

1. Why must the convention be stated? Because books and systems differ: Linux's nice value

treats a larger number as a lower priority, and an answer is unreadable without saying which way round it is.

1. Distinguish internal from external priorities. Internal priorities are computed from

quantities the system can measure, such as memory used or time limits. External ones come from outside, such as who is paying or how urgent the work is.

1. How is shortest job first a priority algorithm? Its priority is the inverse of the

predicted next CPU burst: the shorter the burst, the higher the priority.

1. What is the major problem with priority scheduling, and what is the solution? Indefinite

blocking, or starvation, of low priority processes. The solution is ageing: increasing a process's priority the longer it has waited. 6. Priorities run 127 to 0 and a waiting process gains one step every 15 minutes. What is the guaranteed bound? 127 times 15 equals 1,905 minutes, which is 1905 / 60 = 31.75 hours. 7. Under preemptive priority a process appears three times in the chart. Which slice gives its completion time, and what do the extra appearances cost? The last slice. Each extra appearance is an extra context switch, which is pure overhead.