A task scheduler from scratch

Below, a task scheduler at work. 60 tasks, some of which cannot start until others are done, handed to 4 workers at once. Press Start.

There is nothing to fault in the scheduling: no worker idles while there is something it could do, and no task starts before what it waits for. The trouble is in the three bars underneath. Halfway through, the one that counts tasks says 67%; at 76% of the time it crosses 90% and stays up there to the end. For almost a quarter of the job it has been telling you "nearly done".

This article does two things. It writes that scheduler from scratch, which takes four rules, including what happens when a task fails. Then it answers the question every scheduler gets asked: how long is left? The second is much harder than the first, and the best answer turns out to be calling the scheduler again.

The scheduler and the four progress bars that follow are 215 lines of TypeScript with no library, and every chart below is worked out by your browser as you read. It is a size you can read to the end: tasks fail and are scheduled again, but there are no priorities and nobody competes with you for machines. What else is missing is listed, item by item, at the end.

A scheduler is four rules

A job is a graph: every task remembers which tasks it is waiting for. The scheduler does four things over and over:

1. Who can start? Any task that is not finished, that nobody is working on, and whose dependencies have all gone through.
2. A free worker takes a task that can start.
3. Jump to the moment the next attempt ends, and give that worker back.
4. If that attempt failed, the task is not done: it goes back among the tasks that can start and waits for the next free worker; whatever depends on it keeps waiting. Then back to rule 1.

No clock ticks. Time only moves when an attempt ends, which is why a job that takes over two hours is scheduled in about 8 microseconds (measured on my machine). The core is two functions and a loop (Scheduler in sim/job.ts; only the book-keeping lines are left out here):

assign() {                                                     // rules 1 and 2
  for (const t of this.tasks) {
    if (!this.freeWorkers.length) break;
    const ready = !this.finished[t.id] && !this.busy[t.id] && t.deps.every((d) => this.finished[d]);
    if (ready) this.begin(t.id, this.now);                     // note the start, take a worker
  }
}
 
advance() {                                                    // rules 3 and 4
  const id = earliest(this.running, this.ends);
  const ok = this.tried[id] === this.attempts[id].length - 1;
  this.now = this.ends[id]; this.busy[id] = 0; this.freeWorkers.push(this.worker[id]);
  if (ok) { this.finished[id] = 1; this.left--; }
  else this.tried[id]++;                                       // not finished, so rule 1 finds it again
}
 
while (s.left > 0) { s.assign(); s.advance(); }                // the whole scheduler

Rule 4 is one line because a failed task needs no special retry queue: it is simply not marked as finished, so rule 1 sees it again on the next round.

Below is the same scheduler on a job small enough to see whole: 14 tasks, 3 workers. An arrow runs from a task to the task that waits for it. Keep pressing Next step and watch rules 2 and 3 take turns; then start over and click a task while it is running to make it fail on the spot, and watch rule 4 put it back.

One last thing: attempts — how long every attempt at every task takes — comes from outside. Pass what really happens and you get the real timeline. Pass "I think every task goes through first time and takes this long" and you get a forecast. That will matter below.

When a task fails

That was you breaking tasks by hand. Now let them break by themselves: below is the opening job again, the same tasks in the same order, except that every attempt has a chance of dying part-way. An empty pink outline is an attempt that failed; look to its right and the same task turns up again.

Measured offline (200 jobs, good estimates): when one attempt in five fails, a job has 15 extra, failed attempts on average, workers spend 13% of their time on work that comes to nothing, and the job goes from 38 minutes to 44.

That is only 15% longer, less than "20% fail" suggests, for two reasons: a failed attempt usually dies before it has run its full length, and this scheduler retries without ceremony — the failed task is ready again at once, and the worker that has just come free usually picks it straight back up.

Failures have one more consequence, which the next section runs into: nobody knows which attempt will fail, so every forecast leans optimistic.

How long is left: three different quantities

The three charts from here on switch failures off, to look at one thing at a time.

A progress bar can answer three questions:

• How many tasks are done? The easiest: count.
• How much work is done? Needs an estimate for every task, then a sum.
• How much time has passed? That is what the person waiting wants, and the answer only exists once the job is over.

The first two are what a program has. The third is what it is asked for. A progress bar misleads when it passes one of the first two off as the third.

How well that works depends on how unequal the tasks are. The next chart is not one job but the average of 150; every time you move the slider your browser runs them again in the background.

The number on the slider is the standard deviation of the logarithm of the task sizes: 0.2 is "all about the same", and at 1.2 (the default) the largest tenth of the tasks is a bit over four tenths of the work. With tasks all about the same size, both lines hug the diagonal and counting is perfectly good. Move right and the counting bar bulges: measured offline over 200 jobs at the default setting, it is off by 10 points on average and spends 24% of the run above 90% (an honest bar: 10%). Weighting by estimated work halves that, to 6 points.

Is 1.2 an exaggeration? I checked it against this project's own tests (one run each, on my machine): for the durations of its 168 end-to-end tests that number is 1.0; for its 237 unit tests it is 2.8, and the largest tenth of them take 98% of the time. Drag the slider to 2.8: the counting bar is off by 28 points on average and spends 45% of the run above 90%. Real work is more unequal than my default, not less.

The bar that weighs by work does not reach the diagonal either, and this time the estimates are not to blame, because here they are right.

The more workers, the less honest the bar

Work done is not time passed, because the number of busy workers keeps changing. At the start many tasks can run at once, all four workers are busy and the work drains fast; at the tail one or two tasks are waiting on earlier results, the other workers idle, and the clock keeps running.

Drag the slider from 1 to 32. Two things happen together.

First, the job gets faster and then meets a horizontal line and stops (the upper chart). On average: 122 minutes with one worker, 63 with two, 38 with four, 31.4 with eight, and 31.0 from there on however many you add. Those 31 minutes are the longest chain of tasks waiting on each other; more hands can only wait with it.

Second, the counting bar gets less honest: 10 points off with 4 workers, 17 with 16, a third of the run spent above 90%. More hands make the head of the job go faster; the tail is as long as ever.

The third line stays on the diagonal (under 1 point off). It is the thing promised above: calling the scheduler again. It does not ask how much is done; it takes the tasks that are not finished, with their estimated durations, schedules them on these same workers, and looks at how long that comes to. The scheduler is used twice: once to run the job, once to forecast itself. To answer a question about time, the graph and the number of workers have to be in the calculation, and those are exactly what a scheduler already has.

It has one blind spot, the failures from before: when it forecasts, it assumes every remaining task goes through first time. Switch on the 20% failures of the "When a task fails" figure and its average error goes from 0.7 points to 2.7. The counting and weighting bars hardly notice, because they were wrong already.

When the plan is wrong

The bar that forecasts from the plan has one more assumption: that the estimates are right. Real estimates are wrong, and wrong in a regular way: uploads, say, always take twice what you thought.

As soon as the estimates are off, the bar that replays the plan is off with them. Measured offline it is 8.2 points off on average — worse than the bar that merely weighs by work (6.7). The better model, fed wrong numbers, loses to the cruder one.

Turn the switch on. Each time a task finishes, this bar notes the real time over the estimated time for that kind of task, and applies it to the tasks of that kind that have not run yet. The average error goes from 8.2 points to 4.0. It is not a neural network, just one ratio per kind of task, but it is what this notebook keeps doing: a very small model that learns in your tab.

Of the 4 points that remain, part is each task's own luck, which nothing can learn, and part is the beginning of the job, when nothing has finished and there is nothing to learn from.

It has a price too: it goes backwards. When a task outruns its estimate, the bar has to admit that there is longer to go, and it steps back 2 or 3 points. The counting and weighting bars never do. A real progress bar usually chooses never to move back, so it stands still instead, which is one more way of not telling the truth.

What differs from the real thing, and how the numbers were measured

The task sizes are a distribution I chose (log-normal). I have only checked its spread against this project's own two test suites (1.0 and 2.8, above), not against anyone else's workload; what it is for your build or your CI, the slider in figure 04 lets you set.

The scheduling rule is the plainest there is: whichever task is ready goes first, and a failed one is retried at once with no waiting; no priorities, no pre-emption, no worker itself ever fails, and no job needs four workers to start together. Those are exactly what real schedulers of the Kubernetes or Airflow kind have to deal with. Clusters that train large models add one more: every member of a job has to get a machine at the same moment, or the whole job waits (gang scheduling). What to do downstream when a task is cancelled, and who should go first, are other articles too.

The unit is a whole job of tasks that wait for each other, not a single request. How one request queues, gets routed, and how long to wait before retrying it, Sam Rose has covered in three fine interactive essays (see the sources); this article does not repeat them.

A worker here is only a number. It could be a machine, a process, or one of the people in the city of entry 9: those three hundred each decide for themselves what to do next; here a scheduler decides for them. Both run into the same thing: work that waits on other work, and nobody knowing how long is left.

Real systems often do not even know how many tasks there are: the work grows as it goes. All four bars here assume the list is complete from the start.

Where the numbers come from: figures 03 to 06 and their read-outs are your browser's average of 150 jobs. What I say I measured was run offline on 200 jobs (seeds 1 to 200); the script and the full table are in this project's docs/research/task-scheduler/. The opening job is number 77.

Sources

• Queueing, retrying and routing single requests: Sam Rose, Queueing and Retries (encore.dev/blog), Load Balancing (samwho.dev).
• How people perceive progress bars: Harrison, Amento, Kuznetsov, Bell, Rethinking the Progress Bar, UIST 2007, pp. 115–118.
• The longest chain of dependencies sets the floor: Kelley, Walker, Critical-Path Planning and Scheduling, Eastern Joint Computer Conference, 1959, pp. 160–173.