Scheduling

Before the catalogue is deployed, the reference solution of each problem is rerun on all its tests: 206 problems, 1776 runs, 81 seconds of core time. Let each problem be a submission whose author is waiting for a verdict, and let all 206 arrive at once. There is one core. In what order should they be judged?

In alphabetical order the mean wait for a verdict is 42.4 seconds, shortest first 24.3, longest first 57.3. The work is the same, the core is busy without a break and finishes at the same moment, yet the mean wait of the best and worst orders differs 2.4 times. This is the scheduling problem: the work is given, and the order decides who waits and how long.

The idea

A schedule is the order in which tasks get the core, and when there are several cores, also which core. What counts as a good schedule depends on the goal: a small mean wait, few late tasks, an early end of all the work. Different goals have different best rules, and almost all of them are greedy: sort the tasks, or each time take the best by a simple criterion. They are proved by exchange, as in the article on greedy algorithms, and when the best schedule is too hard to find, the greedy rule is compared with a lower bound.

The article goes from simple to complex: one core and all tasks at once; deadlines; tasks arriving one at a time; many cores; dependencies between tasks. How an operating system shares a core between programs without knowing how long each will run is told in the course chapter. Here the durations are known, and the question is a different one: which order is best, and why.

One core: shortest first

The time to a verdict runs from a submission’s arrival to the end of its judging; in the course chapter it is called the turnaround time. When everything arrives at time 0, it is simply the moment the submission finishes.

The scene shows the same without formulas. The staircase at the bottom shows how many submissions are still waiting, and the area under it equals the sum of times to verdict: each submission adds a strip of height 1 from zero to its end. Shortest first brings the staircase down fastest, longest first keeps it up longest.

Submissions are not always equal: for one verdict a whole group is waiting, for another one person. If a task has a weight w, the price of a second of its waiting, then what must be reduced is Σ w·C, where C is the finishing moment. The rule was found by Wayne Smith in 1956: in increasing order of p/w, that is, first whatever carries more weight per second of work.

With w = 1 this is “shortest first” again. In code the fractions are better compared without division, p_i·w_j < p_j·w_i, so there are no rounding errors.

Deadlines: how many will be late

In the article on greedy algorithms a print shop has eight orders with deadlines, and Jackson’s rule (in increasing order of deadlines) makes the worst lateness smallest: three hours. But often something else matters: not how late, but how many orders are late, because a late order is of no use to the customer any more. By this measure the deadline order is bad: in it five orders out of eight are late.

The Moore–Hodgson algorithm goes through the orders by deadline and takes them on. As soon as the next order is late, the longest of those taken is thrown out; it is done at the very end, already late. In the print shop the posters are thrown out, and only they are late. Trying all 256 sets of orders in the listing confirms that eight cannot be done on time but seven can. The price: the posters are 16 hours late. The rule reduces the number of late orders and does not look at how late they are.

The orders taken are conveniently kept in a heap with the longest on top; one removal is always enough, because without the new order everything fitted, and the removed one is no shorter than the new one. This is the article’s first problem.

Submissions arriving one at a time

On a real server submissions do not arrive all at once. Let the same 206 problems arrive one at a time at random moments, so that the core is busy 90% of the time, and compare four rules. “First come” is an ordinary queue. “Round robin” gives each waiting submission 10 milliseconds in turn, as operating systems share a core. “Shortest next”: on becoming free, the core takes the shortest of the waiting submissions and runs it to the end. SRPT (shortest remaining processing time): the submission with the least work left always runs, and a new submission can preempt the current one.

SRPT halves the mean time to verdict compared with the queue and quarters the median. The scene shows why. All rules have the same amount of work queued, since the core is always busy with something, but under SRPT that work lies in a few big submissions, and under the other rules in many small ones, and each small one is someone’s wait. On the chart at the bottom the SRPT line never rises above the others. Linus Schrage proved in 1968 that this holds for any stream: at any moment SRPT has no more unfinished submissions than any other rule.

Decisions about what to run are needed only at moments of arrival and completion: between them the submission with the smallest remainder stays smallest, since its remainder only decreases. So SRPT is a heap of remainders and a pass over events; this is the article’s second problem.

The longest pay the price. The longest submission, 2.6 seconds of work, waits 18.1 seconds under SRPT: every new shorter submission preempts it. If short ones come in an unbroken stream, a long one may never get its turn. But it is fairer to compare not with the queue but with round robin. That is meant to be fair, and yet the longest submission waits 15.5 seconds under it, almost as long, and its mean is worse even than a plain queue’s: under round robin each submission is stretched over the time of everyone sharing the core with it. In 2003 Mor Harchol-Balter and co-authors built SRPT into a web server’s sending of responses, where the remainder is how many bytes of the file have not yet been sent. The mean response time dropped noticeably, and large files lost almost nothing compared with fair sharing of the link.

An operating system does not know durations, and SRPT is not directly available to it. The multilevel queue from the course chapter approximates it: a program that holds the core for long sinks into low-priority queues and stops delaying the short ones.

Many cores: when the last one finishes

Now the server has m cores, and the goal is different: run all 1776 tests as early as possible, because the catalogue is deployed when the last one finishes. The simplest schedule is list scheduling: the tests stand in a list, and a core that becomes free takes the next one. Any pool of workers with a shared queue works this way. It is impossible to finish earlier than max(all the work / m, the longest test): the cores cannot do the work faster than by splitting it evenly, and the longest test cannot be split.

“Shortest first”, the best order for waiting on one core, is the worst here: the longest tests are left to the end, when there is nothing to even them out with, and on 64 cores everything finishes 62% later than the bound. “Longest first”, LPT (longest processing time), is almost at the bound, and on 32 cores exactly on it, which means that there this schedule is the best possible.

The bound is tight. If the list starts with m(m − 1) one-second tests and ends with an m-second test, the short ones occupy all cores for exactly m − 1 seconds, and the long one starts only after that: everything finishes after 2m − 1 seconds. The best schedule finishes after m: the long test goes on one core at once, the short ones on the rest.

In 1969 Graham brought the bound for “longest first” down to 4/3 − 1/(3m), and it too is tight. Finding the best schedule itself is hard: already for two cores it is the partition problem, splitting numbers into two piles with equal sums, and that is NP-hard, like the problems in the course chapter on hard problems. For small integer durations dynamic programming solves it, like the knapsack, but that does not help for thousands of tests on dozens of cores. So in practice “longest first” is taken and checked against the bound: if the schedule meets it, it is the best, and there is nothing more to look for.

If a test can be interrupted and finished on another core, the bound is always achievable. Robert McNaughton proposed a wrap-around rule in 1959: lay the tests in a row on the first core up to the mark max(P/m, the longest test), and carry what does not fit to the start of the next core. No test ends up on two cores at once: its pieces, the end of one core and the start of the next, do not overlap in time, because the test is no longer than the mark.

Graham’s anomalies

Add dependencies: a task cannot start until those it needs are finished, as in a project build where linking waits for compilation. List scheduling stays the same: a free core takes the first task in the list whose prerequisites are all done. And here it behaves strangely. Ronald Graham gave an example of nine tasks: on three cores everything is done after 12. Add a fourth core: after 15. Make every task one unit shorter: after 13. Remove two dependencies: after 16.

The cause is the same everywhere. The longest task, the ninth, is last in the list and gets a core only when nothing earlier is ready. On three cores tasks 5–8 wait for the fourth, and at time 3, when the first task’s core frees up, nobody stands in the ninth’s way. With a fourth core the fourth task starts at once, tasks 5–8 are ready by time 2 and take the cores before the ninth, and it starts only at time 6. Any of the three changes (an extra core, shorter tasks, removed dependencies) changes who is ready first, and the greedy rule gives the core to the wrong task.

So it is all about the order of the list. Put first the tasks with the longest chain of work behind them: the list by critical path, 1, 9, 4, 5, 6, 7, 8, 2, 3. With it everything is done after 12 on three and on four cores, after 10 with the shortened tasks, after 12 without the two dependencies: in this example the anomalies disappear. That is no guarantee (Graham’s limit below holds for any list), but it shows where the oddities come from.

Graham also proved a limit on these oddities: if a schedule on m cores finished after T, then after any changes (different durations, fewer dependencies, a different list, m′ cores) it finishes no later than (1 + (m − 1)/m′)·T. For four cores instead of three that is 1.5·12 = 18, and the example gives 15.

Code

The listing repeats the article on the same data: one core and three orders; the print shop with a brute-force check; a stream of submissions and four rules; many cores against the bound; Graham’s nine tasks with the list by number and by critical path.

What it costs

All the rules of the article are cheap. “Shortest first”, Smith’s rule and deadline order are a sort, O(n log n). Moore–Hodgson is a sort and a heap of the orders taken: each order is pushed once and popped at most once, also O(n log n). SRPT is a heap of remainders, and decisions are needed only at 2n moments of arrival and completion, so the whole stream costs O(n log n). List scheduling on m cores is a heap of the moments when the cores become free, O(n log m); “longest first” adds a sort.

Only the best is expensive. The best schedule on several cores is NP-hard, and with dependencies it is no easier. The number of late orders also becomes hard if lateness has different prices: already with a common deadline, choosing the orders to complete is exactly the knapsack. So in practice scheduling is greedy and compared with a lower bound, and on real data the gap is usually small, as for “longest first” above.

Where it works

Judging and tests. Solution-judging servers and continuous integration systems spread tests over cores and machines. CircleCI, for example, splits tests between parallel machines by the timings of past runs: this is the problem from the section on cores, evening out the ends.

Web servers. Sending by shortest remainder: the response with the fewest bytes left goes first. In the experiments of Harchol-Balter and co-authors this noticeably reduced the mean response time and hardly affected large files.

Operating systems. The system does not know programs’ durations and approximates “shortest first” with a multilevel queue: whoever holds the core for long sinks lower.

Builds. make -j and similar build tools start tasks whose dependencies are ready as cores free up. In essence this is list scheduling with dependencies, and Graham’s anomalies apply to it directly.

History

Scheduling theory grew out of problems about machines and orders in the 1950s. James Jackson proved the deadline rule in 1955, Wayne Smith the p/w ratio rule in 1956, Robert McNaughton the wrap-around schedule for several machines in 1959. In 1966 Ronald Graham estimated how many times list scheduling can lose to the best and described its anomalies, and in 1969 analysed “longest first”. In 1968 came J. Michael Moore’s paper on the smallest number of late jobs, which also gave Hodgson’s simplified version, and Linus Schrage’s proof that SRPT is optimal. A short proof of the Moore–Hodgson algorithm, close to the one above, was published in 2021 by Joseph Cheriyan, R. Ravi and Martin Skutella.

Problems

The first is how many orders to complete by their deadlines: Moore–Hodgson with a heap. The second is the smallest sum of turnaround times when submissions can be preempted: SRPT over events, with a stream of all the catalogue’s tests among the tests.