Summary and key takeaways
The one sentence. Scheduling is the management of a rivalrous resource under unknown job durations. It conserves work and only relocates delay. So admission, not ordering, is the real control.
The three questions
- When (job and task scheduling): the order in which work uses a pool.
- Where (placement): which machine, given locality, shared fate, price and shape.
- Whether and how much (workload management): the gate, which keeps the other two solvable.
The two facts at the root
- Work-conserving policies have the same total busy time. Order changes only the mean flow time: for jobs of size 1 and 100, short first gives a mean of 51, long first gives 100.5.
- The best order (SRPT) needs the run time, and the run time is unknown at admission. Every mechanism answers "what do we do without that number?" (estimate, observe, declare, or refuse to need it).
Key mechanisms and what to remember
| Mechanism | One-line takeaway |
|---|---|
| FIFO | Zero information, minimum variance of wait, but inherits the variance of job sizes (head-of-line blocking) |
| Priority | Needs aging against starvation; inflates when the setter benefits; inversion needs inheritance |
| MLFQ | Approximates shortest-job-first from observed service; every short-query accelerator is this |
| Fair / DRF | Equalize each tenant's dominant share; leaves stranded resources |
| Capacity | A guarantee is only as fast as the grain of reclaim (about the p99 task duration) |
| SRPT folklore | On heavy-tailed workloads it helps most jobs, including most large ones |
| EDF | Optimal up to Σ(C/T) = 1, catastrophic after; needs admission control |
| Gang | All-or-nothing in the workload becomes atomic allocation and hoarded idle |
| Preemption | Kill the youngest, checkpoint, or migrate; the cost is the victim's unsaved progress |
| Delay scheduling | Wait briefly for a big ratio; the ratio moved from disk-vs-network to cache-vs-network |
| Packing vs. spreading | Packing maximizes blast radius; the problem is requests vs. usage, not NP-hardness |
| DAG | Makespan ≥ critical path; schedule by remaining path; Graham's anomaly |
| Backfill | Price the walltime so users disclose it |
| Locality | A bandwidth-per-core question: bytes per CPU-second against network-card bandwidth per core |
| Anti-affinity | Human-supplied correlation; costs packing; needs a descheduler |
| Spot | Viable for granular, idempotent work; correlated; compare $/work, not $/hour |
| Shape mismatch | Utilization is capped by machine shape versus task shape; the priciest resource sets the objective |
| Scheduler architecture | Monolithic, two-level, shared-state, sampling = single lock, pessimistic, optimistic, no coordination; two random probes capture most of the value |
| Admission | Queue depth = latency budget; goodput versus throughput; check the deadline at dequeue |
| Concurrency limits | Slots are static and wrong; AIMD on latency finds the ceiling |
| Isolation | Multiplexing gain ≈ √N for independent demand; vanishes when demand correlates at peak |
| Lanes | Priority alone does not help admitted queries; lanes cost idle; bias the classifier |
| Killers | Cap on early evidence, not on elapsed time |
| Quotas | Govern only what can be attributed; the rest is the noisy neighbor |
| Autoscaling | Handles trends, never spikes; loop delay sets what it can absorb |
| Routing | Route on cheap features; bias toward the recoverable mistake |
Four formulas
| Formula | Meaning |
|---|---|
| L = λ × W | Little's Law: concurrency, throughput and latency are tied; limiting one fixes the other |
| worst wait = queue depth ÷ service rate | The queue depth is a latency budget |
| Σ (Cᵢ / Tᵢ) ≤ 1 | Periodic tasks are schedulable by EDF if and only if this holds |
| wait iff expected_wait < (1 − 1/ratio) × runtime | The delay-scheduling rule |
Patterns that repeat
- Every guarantee is paid in idle capacity or destroyed work. There is no third currency.
- The declarer never pays. Over-requesting, runaway tasks and priority inflation are paid by others.
- Information is the binding constraint: estimate it, observe it, or price it.
- Cost is conserved: every escape moves cost onto idle capacity, a co-tenant, the future, or burns it.
- Admission is a precondition for scheduling: most "scheduler problems" are admission problems.