§7.1–7.4Workload Assumptions … Shortest Job First (SJF)

The mechanisms are in place; now the intelligence. This chapter develops the first scheduling policies (sometimes disciplines) — ideas that predate computers, borrowed from operations management: assembly lines needed scheduling first, with the same laser-like desire for efficiency.

7.1 Workload Assumptions

First, simplifying assumptions about the running processes — collectively, the workload workload The collective description of the processes/jobs running in a system; the more you know about it, the better your policy. defined in ch. 7 — open in glossary . Knowing your workload is critical to building policies; ours starts out cartoonishly simple, and the chapter relaxes the assumptions one at a time until we reach (dramatic pause) a fully-operational scheduling discipline. The jobs job Scheduling's name for a unit of work (a process, or a CPU burst treated independently). defined in ch. 7 — open in glossary in the system:

7.2 Scheduling Metrics

To compare policies we need a metric. For now, exactly one — the turnaround time turnaround time T_completion − T_arrival — the performance metric batch systems care about. defined in ch. 7 — open in glossary :

Since (for now) all jobs arrive at $T_{arrival} = 0$, turnaround equals completion time. Turnaround is a performance metric — the other axis is fairness fairness Evenly dividing the resource among contenders (e.g., Jain's index); often at odds with turnaround performance. defined in ch. 7 — open in glossary (measured, e.g., by Jain’s Fairness Index), and the two are often at odds: a scheduler may optimize performance precisely by not running some jobs for a while. Life isn’t always perfect.

7.3 First In, First Out (FIFO)

The most basic algorithm: First In, First Out fifo First In, First Out (a.k.a. FCFS) — run jobs in arrival order to completion; simple, but suffers the convoy effect. defined in ch. 7 — open in glossary (a.k.a. First Come, First Served) — simple, easy to implement, and under our assumptions, pretty good. Three jobs, 10 seconds each (A a hair before B before C):

Now relax assumption 1 — jobs may have different lengths. The book asks: what workload makes FIFO look terrible? (Think first.) Answer: put the long job first. A needs 100 seconds; B and C need 10 each:

This is the convoy effect convoy effect Short jobs queued behind a heavyweight resource consumer — the three-cart grocery line. defined in ch. 7 — open in glossary : relatively-short consumers of a resource queued behind a heavyweight consumer — the grocery-store line behind a person with three full carts and a checkbook. (Recommended action: switch lines, or breathe. It will be OK.)

7.4 Shortest Job First (SJF)

The fix is an idea stolen from operations research: Shortest Job First sjf Shortest Job First — run the shortest job to completion first; optimal turnaround when all jobs arrive together. defined in ch. 7 — open in glossary — run the shortest job, then the next shortest, and so on. The name is the complete policy description. Try it on the convoy workload above (flip the policy selector in Figure 7.2): B and C go first, and average turnaround falls from 110 to 50 — more than 2× better. In fact, with all jobs arriving together, SJF is provably optimal. (This is a systems class, not theory: no proofs allowed.)

Now relax assumption 2: jobs arrive over time. A (100s) arrives at t=0; B and C (10s each) arrive at t=10 — just after A started:

Even under SJF, B and C suffer the convoy: SJF as defined is non-preemptive — once A starts, it runs to completion. The average climbs back to 103.33 seconds. What can a scheduler do?