Queue
A queue is a line: items join at the back and leave from the front, so the first in is the first out. Round robin uses that to be fair. Each task gets one short slice of time, then goes to the back of the line if it is not done yet.
5273
Share the processor between 4 tasks, 2 units of time each turn. Press play to start.
1function roundRobin(times, slice) {2 const queue = times.map((_, i) => i);3 const left = [...times];4 const order = [];5 while (queue.length > 0) {6 const task = queue.shift();7 left[task] -= Math.min(slice, left[task]);8 if (left[task] > 0) queue.push(task);9 else order.push(task);10 }11 return order;12}Keys: Space play or pause, ← → step. The URL always points at the frame you are on.
What it costs
| Case | Time | When |
|---|---|---|
| best | 1 | per enqueue or dequeue, with a real queue |
| average | W / s | turns in total: total work W over slice s |
| worst | n | per dequeue with an array shift, as in the JS here |
| space | n | every waiting task sits in the queue |
Where it breaks
- Using an array as a queue. JavaScript's
shift()moves every remaining item up one place, so each dequeue costs n. Fine for a few tasks, slow for millions. Python'sdeque, or a ring buffer, takes from the front in one step. - Choosing the slice. Pick Slice 1 and then Slice 4. Smaller slices share the processor more evenly but take more turns, and every switch has a cost in a real system.
- Short tasks stuck behind long ones. Pick One long task: the three short tasks still finish early, because the long one keeps going to the back. Without slices, they would all wait for it.