What ordering forbids
Who pays when declared run times are wrong?
What this subsection forbids
- You cannot schedule your way out of oversubscription. Work-conserving policies have identical throughput, so ordering only moves delay between parties.
- You cannot minimize the mean response time and bound the worst case with the same policy.
- You cannot hold guaranteed shares, full utilization and no preemption at the same time. This is a genuine trilemma, and which corner you drop is the whole personality of a cluster manager.
- No priority scheme whose key is set by the beneficiary stays stratified.
The escapes, and their prices
| Escape | Buys | Pays |
|---|---|---|
| Preemption | reclaim latency | destroyed work |
| Reservation and gang hoarding | feasibility for coupled jobs | idle capacity |
| Size estimation (declared, or learned by demotion) | most of SRPT's gain | the jobs that are misclassified |
| Incentive design (walltime limits, quotas, chargeback) | the missing information, outright | an enforcement mechanism, and gaming |
| Overcommit | utilization from the gap between requests and usage | failures paid elsewhere, so it looks free until it does not |