---
title: Scheduling, head-of-line blocking and fairness
url: https://doc.liz6.com/en/theory/03-queueing-theory/07-scheduling-and-fairness
locale: en
area: theory
tags:
- Queueing theory
- Theory
date: 2026-09-10
modified: 2026-09-10
description: 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.
---
# 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.
**Scheduling, head-of-line blocking and fairness ยท Experiment**
All five jobs arrive at 0 s; job ID breaks FIFO ties. Job 1 is long, all others take 1 s. SJF knows true sizes, is nonpreemptive and has no switching cost. This finite batch finishes and does not demonstrate online starvation.
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?
Reasoning
No. Both finish the same five jobs in 12 s. Completion timing and occupancy area change, but total work and service speed do not. Short-window throughput may differ while full-batch throughput is identical.
Reasoning
No. Jobs never selected are absent from completed-job statistics. Track queue counts, oldest age, unfinished work and service shares by group, alongside completion distributions.