All Seven Algorithms on One Problem

Average waiting time: 20 / 4 = 5

Average turnaround time: 36 / 4 = 9

Average response time: 6 / 4 = 1.50

Context switches: 8

Round robin, quantum 4

Schedule: round robin, quantum 4

Average waiting time: 18 / 4 = 4.50

Average turnaround time: 34 / 4 = 8.50

Average response time: 13 / 4 = 3.25

Context switches: 4

The comparison

Six things to read off that table, and each is a possible question.

1. Shortest remaining time first wins on waiting time, at 3 units, and it is not close. That

is Chapter forty eight's optimality, applied at every instant rather than only at completions.

1. It also wins on response time, at half a unit, because it starts a short newcomer

immediately.

1. Round robin at quantum 2 is second on response at 1.50, and it pays for it with eight

context switches, more than twice anybody else's. That is the trade of Chapter fifty one in one line of a table.

1. Round robin at quantum 4 is better than at quantum 2 on every measure except response. A

larger quantum means fewer switches and less waiting, and worse response. There is no quantum that is best at everything.

1. Priority is the worst on waiting and turnaround here, at 5.50 and 9.50, because the

priorities were not chosen to match the burst lengths. Priority scheduling optimises what the priorities say, and if they say the wrong thing it optimises the wrong thing.

1. Preemptive priority beats non preemptive priority on all three times and costs one more

switch. That is the general shape of preemption: better times, more switches.

The ranking, and what it is worth

And now the sentence that matters more than the table. Shortest remaining time first won everything on this problem and it is not the algorithm any general purpose system uses, for three reasons already given: it needs burst lengths nobody knows (Chapter forty eight), it can starve a long process while it is running (Chapter forty nine), and this problem has no input and output in it at all.

A comparison on one problem ranks the algorithms on that problem. What makes a scheduler good is how it behaves over every workload, including the ones that arrive tomorrow, and that is why the algorithm real systems use is the one that measures rather than assumes: the multilevel feedback queue of Chapter fifty three, which approximates the winner of this table without needing anything it cannot know.

What it does not mean

These averages are not properties of the algorithms. They are properties of this problem under those algorithms. Change one arrival time and the ranking can change.

Fewer context switches is not better by itself. First come first served has three and the worst response time of the non priority algorithms.

Utilisation is not a way to tell these apart. With no input and output in the problem, every algorithm keeps the processor busy for all sixteen units.

Quick revision

• The same four processes give seven different sets of averages. The

total work, the finishing time, utilisation and throughput are identical for all seven.

• Shortest remaining time first gave the lowest waiting, turnaround and response on this

problem.

• Round robin at quantum 2 gave the second best response and eight switches, against

three for the non preemptive algorithms.

• A larger quantum means fewer switches and lower waiting, and worse response.
• Priority was worst here because the priorities did not match the burst lengths: it

optimises what the priorities say.

• Preemption improved all three times and cost one more switch, which is its general shape.
• A comparison on one problem is a ranking on that problem. The winner here is unusable in

practice, and the multilevel feedback queue is what a real system runs.

Test yourself

1. Why are utilisation and throughput the same for all seven algorithms here? No process

waits for a device, so the processor is busy from 0 to 16 whatever the order, and all four finish by 16.

1. Which algorithm gave the lowest average waiting time, and why? Shortest remaining time

first, because at every instant it runs the process with the least work left, which is the optimal choice for average waiting time.

1. Which gave the best response time, and which was second? Shortest remaining time first at

0.50, then round robin at quantum 2 at 1.50.

1. What did round robin at quantum 2 pay for its response time? Eight context switches, more

than twice as many as any non preemptive algorithm.

1. Why did priority scheduling do worst here? Because the priorities were not related to the

burst lengths. Priority scheduling optimises the order the priorities specify, and here they specified an order that was bad for waiting time.

1. Compare preemptive and non preemptive priority on this problem. The preemptive form was

better on waiting, turnaround and response, and cost one more context switch.

1. If shortest remaining time first wins, why does no general purpose system use it? It needs

burst lengths that cannot be known, it can starve a long process, and a comparison on one problem with no input and output is not a comparison of workloads. A multilevel feedback queue approximates it using only what can be measured.