SYS Системы и большие данные Алгоритм
Планирование задач
Также: Scheduling · расписание · очередь задач · кратчайшая первой · SPT · правило Смита · Smith's rule · Мур — Ходжсон · Moore–Hodgson · SRPT · кратчайший остаток · списочное расписание · list scheduling · LPT · аномалии Грэма · makespan
В каком порядке выполнять работу, если от порядка зависит, сколько ждут, сколько опоздает и когда закончится последнее. На настоящем времени проверки всех задач этого каталога: «короткие сначала» в 1,7 раза сокращает ожидание на одном ядре и оказывается худшим порядком на шестидесяти четырёх, прерывания помогают всем, кроме самых долгих, а лишнее ядро может всё замедлить.
Перед выкаткой каталога эталонное решение каждой задачи прогоняется на всех её тестах заново: 206 задач, 1776 запусков, 81 секунда работы ядра. Пусть каждая задача — это сдача, автор которой ждёт вердикта, и все 206 пришли одновременно. Ядро одно. В каком порядке проверять?
По алфавиту вердикта ждут в среднем 42,4 секунды, короткие сначала — 24,3, длинные сначала — 57,3. Работа одна и та же, ядро занято без перерыва и заканчивает в один и тот же момент, а среднее ожидание у лучшего и худшего порядков различается в 2,4 раза. Это и есть задача планирования: работа задана, а от порядка зависит, кто и сколько ждёт.
Идея
Расписание — это порядок, в котором задачи получают ядро, а когда ядер несколько, ещё и какое ядро. Что считать хорошим расписанием, решает цель: малое среднее ожидание, мало опоздавших, ранний конец всей работы. У разных целей разные лучшие правила, и почти все они жадные: отсортировать задачи или каждый раз брать лучшую по простому признаку. Доказываются они обменом, как в статье о жадных алгоритмах, а когда лучшее расписание найти слишком трудно, жадное правило сравнивают с нижней границей.
Статья идёт от простого к сложному: одно ядро и все задачи сразу; сроки; задачи, которые приходят по одной; много ядер; зависимости между задачами. Как операционная система делит ядро между программами, не зная, сколько каждая проработает, рассказано в главе курса. Здесь длительности известны, и вопрос в другом: какой порядок лучший и почему.
Одно ядро: короткие сначала
Время до вердикта — от прихода сдачи до конца её проверки; в главе курса оно называется временем оборота. Когда все пришли в момент 0, это просто момент, когда сдача закончилась.
Если все задачи готовы с самого начала, сумма времён до вердикта на одном ядре наименьшая, когда задачи идут по возрастанию длительности.
Пусть задачи идут в порядке с длительностями p1, p2, …, pn. Задача на месте k заканчивается в момент p1 + … + pk. Сложим эти моменты и посчитаем, сколько раз в сумму вошла каждая длительность: pk входит в момент окончания самой задачи k и всех задач после неё, то есть n − k + 1 раз. Сумма равна Σ (n − k + 1)·pk: длительность на первом месте берётся n раз, на последнем — один.
Если где-то длинная задача стоит раньше короткой — на местах k < l, и pk > pl, — поменяем их. Сумма изменится на (n − k + 1)(pl − pk) + (n − l + 1)(pk − pl) = −(l − k)(pk − pl) < 0, то есть уменьшится. Значит, в лучшем порядке — а он есть, порядков конечное число, — нет ни одной такой пары: задачи идут по возрастанию длительности.
В сцене то же видно без формул. Лесенка внизу показывает, сколько сдач ещё ждут, и площадь под ней равна сумме времён до вердикта: каждая сдача добавляет полоску высотой 1 от нуля до своего конца. Короткие сначала роняют лесенку быстрее всего, длинные сначала дольше всего держат её наверху.
Сдачи бывают неравноценны: вердикта по одной ждёт целая группа, по другой — один человек. Если у задачи есть вес w — цена секунды её ожидания, — то уменьшать нужно Σ w·C, где C — момент окончания. Правило нашёл Уэйн Смит в 1956 году: по возрастанию p/w, то есть сначала то, где на секунду работы приходится больше веса.
Сумма Σ w·C на одном ядре наименьшая, когда задачи идут по возрастанию p/w.
Возьмём две соседние задачи i и j; всё, что перед ними, заканчивается в момент t. Если первой идёт i, их вклад — wi(t + pi) + wj(t + pi + pj), если j — то wj(t + pj) + wi(t + pj + pi). Остальные задачи заканчиваются в те же моменты. Второе минус первое равно wipj − wjpi, поэтому ставить i первой не хуже, когда pi/wi ≤ pj/wj. Возьмём лучший порядок. Пока в нём есть соседи против правила, меняем их местами: сумма не растёт, а пар против правила становится меньше, как в сортировке пузырьком. В конце получится порядок по p/w с той же наименьшей суммой.
При w = 1 это снова «короткие сначала». В коде дроби удобнее сравнивать без деления: pi·wj < pj·wi, — так не будет ошибок округления.
Сроки: сколько опоздает
В статье о жадных алгоритмах у типографии восемь заказов со сроками, и правило Джексона — по возрастанию сроков — делает худшее опоздание наименьшим: три часа. Но часто важно другое: не на сколько опоздали, а сколько заказов опоздало, потому что опоздавший заказ клиенту уже не нужен. По этой мерке порядок по сроку плох: в нём опаздывают пять заказов из восьми.
Алгоритм Мура — Ходжсона идёт по заказам в порядке сроков и берёт их в работу. Как только очередной заказ опаздывает, из взятых выбрасывается самый долгий; его делают в самом конце, уже с опозданием. У типографии выбрасываются плакаты, и опаздывают только они. Перебор всех 256 наборов заказов в листинге подтверждает, что восемь вовремя не сделать, а семь можно. Цена — плакаты опаздывают на 16 часов: правило уменьшает число опоздавших и не смотрит, насколько они опоздали.
Алгоритм Мура — Ходжсона делает вовремя наибольшее возможное число заказов.
Сначала заметим: набор заказов можно сделать вовремя, только если его успевает порядок по сроку. Это правило Джексона: если в порядке по сроку худшее опоздание больше нуля, то и в любом другом порядке оно больше нуля.
Докажем теорему индукцией по числу заказов. Если в порядке по сроку никто не опаздывает, алгоритм берёт всё, и лучше не бывает. Иначе занумеруем заказы по сроку; пусть k — первый опоздавший, а m — самый долгий среди заказов 1, …, k. Его алгоритм выбросит первым. Покажем, что есть лучший набор без m. Возьмём любой лучший набор S заказов, сделанных вовремя. Заказы 1, …, k не могут войти в него все: вместе они не успевают к сроку k. Пусть r ≤ k — заказ, которого в S нет. Если и m в S нет, доказывать нечего. Иначе заменим в S заказ m на r и проверим, что всё успевает в порядке по сроку.
Заказ с номером j < k заканчивается не позже p1 + … + pj, а это не позже его срока: до k в общем порядке никто не опаздывал. Заказ k, если он в наборе, заканчивается не позже p1 + … + pk − pm ≤ p1 + … + pk−1, потому что pm ≥ pk; а это не позже срока k − 1 и тем более срока k. Заказы после k — те же, что в S, и перед ними вместо m стоит не более долгий r: они заканчиваются не позже, чем в S. Получился набор того же размера, сделанный вовремя и без m.
Значит, лучший ответ для всех заказов равен лучшему ответу для заказов без m. А алгоритм, выбросив m, дальше идёт ровно так же, как шёл бы на заказах без m: там до k никто не опаздывает, а k успевает по только что доказанному. По предположению индукции на заказах без m алгоритм находит лучший ответ — значит, и на всех заказах.
Хранить взятые заказы удобно в куче с самым долгим наверху; одного выбрасывания всегда хватает, потому что без нового заказа всё успевало, а выброшенный не короче нового. Это первая задача статьи.
Сдачи приходят по одной
На настоящем сервере сдачи не приходят разом. Пусть те же 206 задач приходят по одной в случайные моменты, так что ядро занято 90 % времени, и сравним четыре правила. «По приходу» — обычная очередь. «По кругу» — каждой ждущей по 10 миллисекунд по очереди, как делят ядро операционные системы. «Короткая следующей» — освободившись, ядро берёт самую короткую из ждущих и делает её до конца. SRPT (shortest remaining processing time, кратчайший остаток) — всегда работает та сдача, которой осталось меньше всех, и новая сдача может прервать текущую.
| правило | в среднем | медиана | самая долгая сдача, 2,6 с, ждёт |
|---|---|---|---|
| по приходу | 1,9 с | 1,6 с | 4,5 с |
| по кругу, по 10 мс | 2,1 с | 1,5 с | 15,5 с |
| короткая следующей | 1,2 с | 0,7 с | 12,6 с |
| SRPT | 1,0 с | 0,4 с | 18,1 с |
SRPT вдвое сокращает среднее время до вердикта по сравнению с очередью и вчетверо — медиану. Сцена показывает почему. Работы в очереди у всех правил поровну, ведь ядро всё время чем-то занято, но у SRPT эта работа лежит в немногих больших сдачах, а у остальных правил — во множестве мелких, и каждая мелкая — чьё-то ожидание. На графике внизу линия SRPT ни разу не поднимается выше других. Линус Шраге в 1968 году доказал, что так при любом потоке: в любой момент у SRPT не закончено не больше сдач, чем у любого другого правила.
Если сдачи можно прерывать и возвращаться к ним без потерь, SRPT даёт наименьшую сумму времён до вердикта при любых моментах прихода.
Будем считать время целым: работа идёт шагами по миллисекунде, и на каждом шаге ядро работает над одной сдачей или стоит. Возьмём любое расписание и найдём первый шаг, на котором оно поступает не как SRPT. Если на этом шаге ядро стоит, хотя кто-то ждёт, отдадим шаг ждущей сдаче: она закончит не позже, остальные не изменятся. Если же ядро работает над сдачей j, а у пришедшей сдачи i осталось меньше всех, соберём все шаги начиная с этого, которые расписание отдаёт i или j, и раздадим их заново: первые ri — сдаче i, где ri — её остаток, остальные — j. Обе сдачи уже пришли, так что так можно.
Последний из собранных шагов остался последним, и на нём теперь заканчивает j; раньше на нём заканчивала одна из двух. А i закончит не позже, чем раньше заканчивала первая из двух: к тому моменту прошли все шаги закончившей сдачи, а их не меньше ri, потому что её остаток не меньше. Сумма двух моментов окончания не выросла, остальные сдачи не задеты, а расписание теперь совпадает с SRPT на шаг дольше. Повторяя это, превратим любое расписание в SRPT, и сумма по дороге ни разу не вырастет.
Решать, кого делать, нужно только в моменты прихода и окончания: между ними сдача с наименьшим остатком остаётся наименьшей, её остаток только уменьшается. Поэтому SRPT — это куча остатков и проход по событиям; это вторая задача статьи.
Цену платят самые долгие. Самая долгая сдача, 2,6 секунды работы, при SRPT ждёт 18,1 секунды: её прерывает каждая новая сдача покороче. Если короткие идут сплошным потоком, длинная может не дождаться никогда. Но сравнивать честнее не с очередью, а с делением по кругу. Оно задумано справедливым, и всё же самая долгая ждёт при нём 15,5 секунды, почти столько же, а среднее у него хуже даже, чем у простой очереди: по кругу каждая сдача растягивается на время всех, кто делит с ней ядро. Мор Харчол-Балтер с соавторами в 2003 году встроили SRPT в отдачу ответов веб-сервера, где остаток — это сколько байтов файла ещё не отправлено. Среднее время ответа заметно сократилось, а большие файлы по сравнению с честным делением канала почти не проиграли.
Операционная система длительностей не знает, и SRPT ей напрямую недоступен. Многоуровневая очередь из главы курса приближает его: программа, которая долго не отдаёт ядро, опускается в очереди с низким приоритетом и перестаёт задерживать короткие.
Много ядер: когда закончится последний
Теперь у сервера m ядер, и цель другая: прогнать все 1776 тестов как можно раньше, потому что каталог выкатывается, когда закончится последний. Самое простое расписание — списочное: тесты стоят в списке, и освободившееся ядро берёт следующий. Так работает любой пул обработчиков с общей очередью. Раньше, чем через max(вся работа / m, самый долгий тест), не закончить никак: ядра не сделают работу быстрее, чем если разделить её поровну, а самый долгий тест не делится.
| ядер | граница, с | по алфавиту | короткие сначала | длинные сначала |
|---|---|---|---|---|
| 8 | 10,15 | 10,28 | 10,71 | 10,16 |
| 32 | 2,54 | 2,90 | 3,25 | 2,54 |
| 64 | 1,27 | 1,76 | 2,06 | 1,27 |
«Короткие сначала», лучший порядок для ожидания на одном ядре, здесь худший: самые долгие тесты достаются концу, когда выровнять их уже нечем, и на 64 ядрах всё заканчивается на 62 % позже границы. «Длинные сначала» — LPT, longest processing time — почти на самой границе, а на 32 ядрах ровно на ней; значит, там это расписание лучшее из возможных.
Списочное расписание при любом порядке списка заканчивает не позже, чем через (2 − 1/m)·OPT, где OPT — время лучшего расписания.
Пусть последним заканчивается тест j длительности pj, начатый в момент s. До момента s все ядра были заняты, иначе свободное ядро взяло бы j раньше. Значит, к моменту s сделано не меньше m·s работы, и вся она — работа других тестов: m·s ≤ P − pj, где P — вся работа. Конец расписания — s + pj ≤ (P − pj)/m + pj = P/m + (1 − 1/m)·pj. Каждое из двух слагаемых не больше нижней границы: P/m ≤ OPT и pj ≤ OPT. Итого не больше (2 − 1/m)·OPT.
Оценка точная. Если в списке сначала m(m − 1) тестов по секунде, а последним — тест на m секунд, короткие займут все ядра ровно на m − 1 секунду, и долгий начнётся только потом: всё закончится через 2m − 1 секунду. А лучшее расписание заканчивает через m: долгий тест сразу идёт на одно ядро, короткие — на остальные.
Списочное расписание с длинными тестами сначала заканчивает не позже, чем через 3/2·OPT.
Пусть последним заканчивается тест j. Тесты после j в списке не длиннее его и на его конец не влияют; выбросим их, OPT от этого не вырастет. Теперь j — последний в списке и самый короткий. Если тестов не больше m, каждый идёт на своём ядре с нуля, и всё заканчивается вместе с самым долгим тестом, то есть не позже OPT. Иначе в любом расписании два из m + 1 самых долгих тестов попадут на одно ядро, поэтому OPT ≥ 2pm+1 ≥ 2pj. По рассуждению из теоремы Грэма конец не больше P/m + pj ≤ OPT + OPT/2.
В 1969 году Грэм довёл оценку для «длинных сначала» до 4/3 − 1/(3m), и она тоже точная. Найти же само лучшее расписание трудно: уже для двух ядер это задача разбиения — поделить числа на две кучки с равными суммами, — а она NP-трудная, как задачи из главы курса о трудных задачах. Для небольших целых длительностей её решает динамика, как рюкзак, но для тысяч тестов на десятках ядер это не помогает. Поэтому на практике берут «длинные сначала» и сверяются с границей: если расписание совпало с ней, оно лучшее, и искать больше нечего.
Если тест можно прервать и доделать на другом ядре, граница достижима всегда. Роберт Макнотон в 1959 году предложил правило с переносом: кладём тесты подряд на первое ядро до отметки max(P/m, самый долгий тест), а то, что не поместилось, переносим на начало следующего ядра. Один тест не окажется на двух ядрах одновременно: его куски — конец одного ядра и начало следующего — не пересекаются по времени, потому что тест не длиннее отметки.
Аномалии Грэма
Добавим зависимости: задача не может начаться, пока не закончены нужные ей, как при сборке проекта, где компоновка ждёт компиляции. Списочное расписание остаётся тем же: свободное ядро берёт первую по списку задачу, у которой всё нужное готово. И здесь оно ведёт себя странно. Рональд Грэм показал пример из девяти задач: на трёх ядрах всё готово через 12. Добавим четвёртое ядро — через 15. Сделаем каждую задачу на единицу короче — через 13. Уберём две зависимости — через 16.
Причина везде одна. Самая долгая задача, девятая, стоит в списке последней и получает ядро, только когда ничего более раннего не готово. На трёх ядрах задачи 5–8 ждут четвёртую, и в момент 3, когда освобождается ядро первой задачи, девятой некому помешать. С четвёртым ядром четвёртая задача начинается сразу, задачи 5–8 готовы уже к моменту 2 и занимают ядра раньше девятой, и она начинается только в момент 6. Любая из трёх перемен — лишнее ядро, укороченные задачи, снятые зависимости — меняет, кто первым окажется готов, и жадное правило отдаёт ядро не той задаче.
Значит, дело в порядке списка. Поставим вперёд задачи, за которыми тянется самая длинная цепочка работы, — это список по критическому пути: 1, 9, 4, 5, 6, 7, 8, 2, 3. С ним на трёх и на четырёх ядрах всё готово через 12, с укороченными задачами — через 10, без двух зависимостей — через 12: в этом примере аномалии пропадают. Гарантии это не даёт — предел Грэма ниже верен для любого списка, — но показывает, откуда берутся странности.
Грэм доказал и предел этих странностей: если расписание на m ядрах заканчивало через T, то после любых перемен — другие длительности, меньше зависимостей, другой список, m′ ядер — оно закончит не позже чем через (1 + (m − 1)/m′)·T. Для четырёх ядер вместо трёх это 1,5·12 = 18, а пример даёт 15.
Код
Листинг повторяет статью на тех же данных: одно ядро и три порядка; типография с проверкой перебором; поток сдач и четыре правила; много ядер против границы; девять задач Грэма со списком по номерам и по критическому пути.
Сколько это стоит
Все правила статьи дешёвые. «Короткие сначала», правило Смита и порядок по сроку — сортировка, O(n log n). Мур — Ходжсон — сортировка и куча взятых заказов: каждый заказ один раз кладётся в кучу и не больше одного раза вынимается, тоже O(n log n). SRPT — куча остатков, а решать нужно только в 2n моментов прихода и окончания, поэтому весь поток стоит O(n log n). Списочное расписание на m ядрах — куча моментов, когда ядра освободятся, O(n log m); «длинные сначала» добавляют сортировку.
Дорого только лучшее. Лучшее расписание на нескольких ядрах — NP-трудная задача, с зависимостями она не проще. Число опоздавших тоже становится трудным, если у опоздания разная цена: уже при общем сроке выбрать заказы, которые успеть, — это в точности рюкзак. Поэтому на практике планируют жадно и сравнивают с нижней границей, а на настоящих данных разрыв обычно мал, как у «длинных сначала» выше.
Где работает
Проверка и тесты. Серверы проверки решений и системы непрерывной интеграции раскладывают тесты по ядрам и машинам. CircleCI, например, делит тесты между параллельными машинами по замерам времени прошлых прогонов: это задача из раздела о ядрах — выровнять концы.
Веб-серверы. Отдача по кратчайшему остатку: первым уходит ответ, которому осталось меньше байтов. В опытах Харчол-Балтер с соавторами это заметно сократило среднее время ответа и почти не задело большие файлы.
Операционные системы. Длительностей программ система не знает и приближает «короткие сначала» многоуровневой очередью: кто долго держит ядро, опускается ниже.
Сборка. make -j и похожие сборщики запускают задачи, у которых готовы зависимости, по мере освобождения ядер. По сути это списочное расписание с зависимостями, и аномалии Грэма относятся к нему напрямую.
История
Теория расписаний выросла из задач о станках и заказах в 1950-х годах. Джеймс Джексон в 1955 году доказал правило «по сроку», Уэйн Смит в 1956-м — правило отношений p/w, Роберт Макнотон в 1959-м — расписание с переносом для нескольких станков. В 1966 году Рональд Грэм оценил, во сколько раз списочное расписание может проиграть лучшему, и описал его аномалии, а в 1969-м разобрал «длинные сначала». В 1968 году вышли статья Дж. Майкла Мура о наименьшем числе опоздавших, где он привёл и упрощённый вариант Ходжсона, и доказательство Линуса Шраге, что SRPT оптимален. Короткое доказательство алгоритма Мура — Ходжсона, близкое к приведённому выше, опубликовали в 2021 году Джозеф Черьян, Р. Рави и Мартин Скутелла.
Задачи
Первая — сколько заказов успеть к сроку: Мур — Ходжсон с кучей. Вторая — наименьшая сумма времён оборота, когда сдачи можно прерывать: SRPT на событиях, и среди тестов — поток всех тестов каталога.
Сколько успеть к сроку Кратчайший остатокДанные: Время эталонных решений задач каталога на каждом тесте (замер в песочнице, 17.10.2026)