Multitasking: Greedy vs Fair Scheduling

If you have a bunch of tasks to do, and each has a bunch of independent steps, is it better to

1. Fair: Do the tasks in parallel, or
2. Greedy: Finish one task at a time as fast as possible?

Here's an example. You have 10 tasks Q ... Z each with 10 independent steps where each step takes a second. The tables below have time going down, top to bottom, with each horizontal row showing what work is done in parallel.

The Fair strategy will do tasks Q ... Z like so:

Q	R	S	T	U	V	W	X	Y	Z
Q	R	S	T	U	V	W	X	Y	Z
Q	R	S	T	U	V	W	X	Y	Z
Q	R	S	T	U	V	W	X	Y	Z
Q	R	S	T	U	V	W	X	Y	Z
Q	R	S	T	U	V	W	X	Y	Z
Q	R	S	T	U	V	W	X	Y	Z
Q	R	S	T	U	V	W	X	Y	Z
Q	R	S	T	U	V	W	X	Y	Z
Q	R	S	T	U	V	W	X	Y	Z

All tasks are done in parallel. Every one finishes after 10 seconds.

The Greedy strategy does tasks Q ... Z them like so:

Q	Q	Q	Q	Q	Q	Q	Q	Q	Q
R	R	R	R	R	R	R	R	R	R
S	S	S	S	S	S	S	S	S	S
T	T	T	T	T	T	T	T	T	T
U	U	U	U	U	U	U	U	U	U
V	V	V	V	V	V	V	V	V	V
W	W	W	W	W	W	W	W	W	W
X	X	X	X	X	X	X	X	X	X
Y	Y	Y	Y	Y	Y	Y	Y	Y	Y
Z	Z	Z	Z	Z	Z	Z	Z	Z	Z

The longest wait is for task Z, which finished 10 seconds after the start, same as the Fair strategy. But every other task finished faster, in 1..9 steps, on average 5.5 steps. Same throughput, but Greedy has half the latency as Fair.

But it gets better. Suppose you always have tasks coming in at different times and you have to get them done. You could work on all the tasks you have in parallel, or you could finish each task as fast as possible. Now instead of tasks Q..Z, we will have Q1..Z1, Q2..Z2, and so forth, each with 10 independent 1-second steps, which Qn coming in 10 seconds after Qn-1. And the initial tasks come in at different times.

The Fair strategy will look like this (all the *0 tasks are already running, this starts when Q1 is received and is shown until Q2 ends):

Q1	R0	S0	T0	U0	V0	W0	X0	Y0	Z0
Q1	R1	S0	T0	U0	V0	W0	X0	Y0	Z0
Q1	R1	S1	T0	U0	V0	W0	X0	Y0	Z0
Q1	R1	S1	T1	U0	V0	W0	X0	Y0	Z0
Q1	R1	S1	T1	U1	V0	W0	X0	Y0	Z0
Q1	R1	S1	T1	U1	V1	W0	X0	Y0	Z0
Q1	R1	S1	T1	U1	V1	W1	X0	Y0	Z0
Q1	R1	S1	T1	U1	V1	W1	X1	Y0	Z0
Q1	R1	S1	T1	U1	V1	W1	X1	Y1	Z0
Q1	R1	S1	T1	U1	V1	W1	X1	Y1	Z1
Q2	R1	S1	T1	U1	V1	W1	X1	Y1	Z1
Q2	R2	S1	T1	U1	V1	W1	X1	Y1	Z1
Q2	R2	S2	T1	U1	V1	W1	X1	Y1	Z1
Q2	R2	S2	T2	U1	V1	W1	X1	Y1	Z1
Q2	R2	S2	T2	U2	V1	W1	X1	Y1	Z1
Q2	R2	S2	T2	U2	V2	W1	X1	Y1	Z1
Q2	R2	S2	T2	U2	V2	W2	X1	Y1	Z1
Q2	R2	S2	T2	U2	V2	W2	X2	Y1	Z1
Q2	R2	S2	T2	U2	V2	W2	X2	Y2	Z1
Q2	R2	S2	T2	U2	V2	W2	X2	Y2	Z2

A new job starts every second, every second 10 jobs are running in parallel. Q2 finished 10 seconds after Q1.

The Greedy strategy will look like this (this starts when Q1 is received and is shown until all *2 jobs end):

Q1	Q1	Q1	Q1	Q1	Q1	Q1	Q1	Q1	Q1
R1	R1	R1	R1	R1	R1	R1	R1	R1	R1
S1	S1	S1	S1	S1	S1	S1	S1	S1	S1
T1	T1	T1	T1	T1	T1	T1	T1	T1	T1
U1	U1	U1	U1	U1	U1	U1	U1	U1	U1
V1	V1	V1	V1	V1	V1	V1	V1	V1	V1
W1	W1	W1	W1	W1	W1	W1	W1	W1	W1
X1	X1	X1	X1	X1	X1	X1	X1	X1	X1
Y1	Y1	Y1	Y1	Y1	Y1	Y1	Y1	Y1	Y1
Z1	Z1	Z1	Z1	Z1	Z1	Z1	Z1	Z1	Z1
Q2	Q2	Q2	Q2	Q2	Q2	Q2	Q2	Q2	Q2
R2	R2	R2	R2	R2	R2	R2	R2	R2	R2
S2	S2	S2	S2	S2	S2	S2	S2	S2	S2
T2	T2	T2	T2	T2	T2	T2	T2	T2	T2
U2	U2	U2	U2	U2	U2	U2	U2	U2	U2
V2	V2	V2	V2	V2	V2	V2	V2	V2	V2
W2	W2	W2	W2	W2	W2	W2	W2	W2	W2
X2	X2	X2	X2	X2	X2	X2	X2	X2	X2
Y2	Y2	Y2	Y2	Y2	Y2	Y2	Y2	Y2	Y2
Z2	Z2	Z2	Z2	Z2	Z2	Z2	Z2	Z2	Z2

A job comes in every 10 seconds as before. Q2 finished 10 seconds after Q1 as before. But only one job runs at a time, and each job finishes in 1 second, the second after it is received. The throughput is the same, but the latency is 10x better with the Greedy strategy than the Fair strategy. (User Q might want to use that by submitting Q2 one second after Q1, but they can't be allowed to, because throughput is the same as before.)

Suppose each job needs a fixed amount of space for temporary work-in-progress. With the Greedy strategy and jobs coming in all the time, you need 1/10th the space for holding that temporary work, because each job holds its space for 1/10th as long.

Jenny: a pairwise testing tool
Index of testing techniques
Ye Olde Catalogue of Boy Scout Skits
Index of Birds
Table of Contents