A free lunch#
and the person who pays for it#
SLOP2710 · Week 6
Five people. One server.#
Transactions of 1, 2, 3, 4 and 10 minutes.
You cannot make anyone faster. You cannot add staff.
You can only decide the order.
How much difference#
can the order possibly make?#
Three times the waiting#
Shortest first — 20 person-minutes
Longest first — 60 person-minutes
Same twenty minutes of work. Server finishes at the same moment either way.
- W arrival order
- —
- W smallest first
- —
- W 80+ items, arrival
- —
- W 80+ items, smallest
- —
- passed since opening
- —
The proof is two lines#
Longer job ahead of a shorter one? Swap them.
Short job saves a lot. Long job loses a little. Total falls.
So the optimal order has no such pair. So it is sorted.
The express lane is not a courtesy
to people buying milk.
Find the person paying#
Mean visit 17 → 8.5 minutes
Full trolley 26 → 60 minutes
Longest wait in a simulated month: 1h45 → 13h40
Not delayed.#
Starved.#
The family, as worked out in an OS#
| Rule | Failure it fixes |
|---|---|
| FCFS | — (convoy effect) |
| SJF | long job at the front |
| SRPT | SJF, preemptive. Best mean, worst tail |
| Round robin | starvation. Mean much worse |
| Multi-level feedback | needing to know the length |
What is that last one doing?#
Two general moves#
Infer, don’t ask. Behaviour cannot be misreported as easily as a form.
Age the queue. Priority rises with waiting. Bounds the tail, costs the mean.
The dial#
Ageing up → FCFS: fair, bounded, slower
Ageing down → SJF: fast, with somebody there at closing time
No correct setting. Only a defensible one.
The prerequisite nobody mentions#
You must know the job length before you run it.
- observe a proxy — basket size, page count
- predict from history — fails silently on anyone new
- ask — and now you have built an incentive