What scheduling forbids, what escapes cost, and who pays
Who really pays for scheduling's escapes?
What this mechanism forbids
- Ordering cannot create capacity. Work-conserving policies have identical throughput, so every policy is a distribution of delay.
- No policy minimizes mean response time and bounds the tail at the same time.
- Guaranteed share, full utilization and no preemption cannot coexist.
- Utilization is ceilinged by shape mismatch before any algorithm runs.
- No quota governs an unattributable resource.
- No control loop regulates a disturbance faster than its own delay.
The escapes, and what each one costs
| Escape | Buys | Pays in |
|---|---|---|
| Preemption | fast reclaim | destroyed work |
| Reservation, gangs, lanes | predictability, feasibility | idle capacity |
| Size inference (MLFQ, lanes) | most of SRPT's gain | misclassified jobs |
| Incentives (walltime limits, chargeback) | the missing number, disclosed | enforcement and gaming |
| Caps and killers | a bounded tail | sunk work, on a threshold you guessed |
| Overcommit and multiplexing | utilization | correlated demand, paid at peak |
| Spot and tiered hardware | 60–90% off the bill | an interruption distribution, correlated |
| Sampled scheduling | scheduler throughput | global constraints and fairness |
Every row is the same law: costs are conserved. Nothing is eliminated, only moved: onto idle capacity, onto a co-tenant, onto the future, or burned outright.
What this mechanism assumes it cannot verify, and who pays
A scheduler assumes that:
- declared resource requests are honest,
- declared run times are honest,
- declared priority reflects real urgency,
- tasks terminate,
- tenant demands are independent,
- and the requested resources are the ones that actually contend.
The declarer pays for none of these
| Broken assumption | Who pays |
|---|---|
| Over-requested resources | the co-tenant |
| A task that never ends | the queue behind it |
| Inflated priority | the low-priority pool |
| Independent demand (it was not) | everyone, at the peak |
That asymmetry, not algorithm choice, is what almost every production scheduling incident actually is.