Scheduling, head-of-line blocking and fairness

Waiting depends on who receives service next, as well as traffic and job sizes. Scheduling trades among mean response, tails, fairness, deadlines and completed work. One overall average is insufficient to judge it.

A finite batch reveals head-of-line blocking

Five jobs arrive at time zero with service sizes $[8,1,1,1,1]$ s. IDs break simultaneous FIFO ties. There is one server, no preemption and no switching cost. FIFO completion times are $[8,9,10,11,12]$, averaging 10 s. Shortest-job-first (SJF) executes sizes $[1,1,1,1,8]$, giving completion times $[1,2,3,4,12]$ and mean 4.4 s.

Both require 12 s of service. Improving the mean did not increase capacity: short jobs simply leave sooner. The long job's wait increases from zero to 4 s.

Switch the order and inspect each job's waiting and service bars, then increase the long job's size. All arrive at zero, so the distance from the origin to completion is system time. IDs preserve identity while row order shows execution order.

Why shortest first minimizes this batch's mean

Suppose adjacent jobs have sizes $x>y$ and earlier work takes time $t$. Serving $x$ first gives a sum of completion times $2t+2x+y$. Swapping gives $2t+2y+x$, reducing the sum by $x-y$ without changing later start times. Repeatedly removing such inversions produces shortest-processing-time order.

The argument assumes simultaneously available jobs, known sizes, one server and no preemption cost or other constraints. Online arrivals, unknown sizes, release times and switching costs require a different analysis; the batch proof cannot simply be transferred.

Scheduling and fairness

FCFS follows arrival order. SJF selects the smallest estimated ready job. SRPT permits preemption and chooses the least remaining work. An ideal single server with known sizes and free preemption admits strong mean-response optimality results for SRPT. Real implementations must estimate sizes and account for cache, transaction and resource-restoration costs.

Slowdown $T_i/S_i$ measures a job's relative penalty. In this batch, the maximum slowdown is 12 under FIFO and 4 under SJF. Finite batches eventually finish, so this does not establish long-run fairness. A continuing stream of short work can delay low-priority long jobs for a very long time.

Priority aging, reserved tenant shares, weighted fair queues and separate batch pools change who bears congestion. Report per-class and per-tenant waits, oldest unfinished age, deadline violations and service shares. An overall p99 can conceal harm to a group representing less than 1% of requests.

Blocking can cross queue boundaries

Ordering within a partition lets one slow operation delay later operations in that partition. A shared pool lets batch jobs occupy every worker. Separation can isolate interference while sacrificing some pooling benefits. Prioritizing fresh updates suits data that can expire; it may be inappropriate for orders or financial operations that must eventually execute.

Check your understanding

1. SJF reduces mean response from 10 s to 4.4 s. Has throughput doubled?

2. Can completed-job p99 reliably expose starvation?

Further reading

The CMU SRPT research treats scheduling as resource allocation. AWS's backlog article discusses isolation and separating fresh from old work, subject to durability and completion requirements. See consumer groups and collaboration for ordering and parallel consumption.