MLFQ: планировщик, который угадывает будущее

Задача: совместить несовместимое

Прошлая глава закончилась противоречием. SJF и STCF хороши по обороту, но требуют знать длительность задачи. RR хорош по отклику, но плох по обороту. ОС длительность не знает и хочет и того, и другого.

MLFQ (multi-level feedback queue, многоуровневая очередь с обратной связью) решает это так: раз будущее неизвестно, будем судить о задаче по её прошлому поведению. Задача, которая быстро отдаёт процессор (сходила в I/O, ждёт ввода с клавиатуры), похожа на интерактивную: ей нужен быстрый отклик. Задача, которая съедает весь отведённый квант раз за разом, похожа на долгую вычислительную (CPU-bound): её можно отодвинуть. «Обратная связь» в названии — это именно наблюдение за поведением.

Устройство

Есть несколько очередей, у каждой свой приоритет. Внутри одной очереди задачи крутятся по RR. Каждой задаче планировщик отводит бюджет времени на её уровне (allotment), обычно один или несколько квантов.

Итоговые правила:

1. Если приоритет A выше приоритета B, выполняется A.
2. Если приоритеты равны, A и B делят процессор по RR.
3. Новая задача попадает в самую верхнюю очередь.
4. Когда задача израсходовала свой бюджет на уровне, её приоритет понижается на один уровень. Неважно, израсходовала она его за один присест или кусками между операциями ввода-вывода.
5. Раз в период S все задачи поднимаются в самую верхнюю очередь (priority boost).

Правило 3 — кредит доверия: ОС не знает, короткая задача или длинная, и оптимистично считает её короткой. Если это так, она быстро закончится на верхнем уровне, как при SJF. Если нет, правило 4 постепенно спустит её вниз.

Трасса на числах

Три уровня: Q2 (верхний), Q1, Q0. Квант 10 мс, бюджет на уровне — один квант.

• Задача A: долгая, приходит в 0, нужно 200 мс процессора.
• Задача B: короткая, приходит в 100 мс, нужно 20 мс.

время, мс   0     10    20                    100   110   120
Q2          [ A ]                              [ B ]
Q1                [ A ]                              [ B ]
Q0                      [ A  A  A  A  A  A  A  A]          [ A ...

• 0–10: A на Q2, израсходовала бюджет, спускается на Q1.
• 10–20: A на Q1, снова съела бюджет, спускается на Q0.
• 20–100: A одна, крутится на Q0.
• 100: приходит B на Q2. По правилу 1 она вытесняет A.
• 100–110: B на Q2, бюджет кончился, спускается на Q1.
• 110–120: B на Q1, по-прежнему выше A, и к 120 заканчивает.
• 120: A продолжает на Q0.

Отклик B = 0, оборот B = 20 мс: ровно столько, сколько ей нужно процессора. MLFQ повёл себя как SJF, не зная заранее длину B.

Посмотрите то же в симуляторе: долгие A и B быстро проваливаются вниз (цвет блока показывает уровень), а поздняя короткая C стартует наверху и сразу получает процессор.

Зачем правило 5: голодание

Без правила 5 возможна такая картина: на верхних уровнях постоянно живут десятки интерактивных задач, каждая понемногу, но вместе они занимают процессор целиком. Задача на Q0 не получит ни миллисекунды. Это голодание.

Priority boost раз в период S поднимает всех наверх. Задача с самого дна гарантированно получит несколько квантов хотя бы раз в S. Заодно boost исправляет ошибки классификации: если вычислительная задача стала интерактивной (например, закончила загрузку данных и начала отвечать на запросы), после подъёма она останется наверху, потому что больше не съедает бюджет.

Выбор S — компромисс. Слишком большой S, и задачи внизу голодают долго. Слишком маленький, и долгие задачи слишком часто оказываются наверху, мешая интерактивным.

Зачем правило 4 устроено именно так: обман планировщика

В ранних версиях правило 4 звучало иначе: «если задача отдала процессор до конца кванта, её приоритет сохраняется». Это легко обмануть. Программа считает 9,9 мс из 10, а за мгновение до конца кванта делает пустяковый ввод-вывод, например читает один байт из файла в кэше. Формально она «отдала процессор сама», приоритет сохранён. Повторяя трюк, она получает около 99 % процессора и вытесняет всех на нижних уровнях.

Правило 4 в нынешнем виде считает суммарное время на уровне. Девять с половиной миллисекунд плюс ещё девять с половиной — это уже больше бюджета в 10 мс, и задача спускается вниз, как бы она ни дробила свою работу.

Настройка

У MLFQ много параметров: сколько очередей, какой квант на каждом уровне, какой бюджет, как часто делать boost. Обычно квант на верхних уровнях короткий (интерактивным задачам нужен быстрый отклик, они всё равно скоро уйдут в I/O), а на нижних длинный (вычислительным задачам лучше реже переключаться). Например, планировщик класса TS в Solaris по умолчанию имел 60 уровней с квантами от 20 мс наверху до нескольких сотен миллисекунд внизу и поднимал приоритеты примерно раз в секунду.

Подходящих значений «на все случаи» нет, их подбирают под нагрузку. Отдельные системы добавляют ручное управление: в Unix есть утилита nice, которой можно понизить приоритет фоновой задачи. К ней вернёмся в главе пропорциональное планирование.

Где MLFQ живёт сейчас. Идеи многоуровневых очередей с понижением и повышением приоритета лежат в основе планировщиков Windows, Solaris и BSD-систем. Linux пошёл другим путём: его планировщик основан на справедливом делении времени, а не на очередях приоритетов, это тема следующей главы про пропорциональное планирование.

Тот же приём в бэкенде

Схема «новым — кредит доверия, прожорливых понижаем, периодически поднимаем всех» полезна далеко за пределами ядра ОС. Пример: очередь фоновых задач, где цена задачи заранее неизвестна. Новые задачи кладём в быструю очередь. Задачу, которая проработала дольше порога, переносим в медленную очередь с отдельными воркерами. Чтобы задачи в медленной очереди не застряли навсегда, раз в какое-то время поднимаем самые старые. На собеседовании по system design этот ответ подходит к вопросу «как приоритизировать запросы, стоимость которых заранее неизвестна».

Частые ошибки

• Считать, что задача падает вниз сразу после первого кванта. Падает после исчерпания бюджета на уровне, а бюджет может быть больше одного кванта.
• Думать, что boost нужен для интерактивных задач. Он нужен в первую очередь задачам на дне, чтобы они не голодали.
• Путать «отдала процессор раньше» с «интерактивная». По одному такому событию ничего сказать нельзя, поэтому правило 4 считает сумму.

Проверьте себя

1. В трассе выше уберите задачу B. На каком уровне A будет работать в момент 50 мс?
2. Задача делает 2 мс счёта и уходит в I/O на 20 мс, и так по кругу. Бюджет на уровне 10 мс. Через сколько циклов она опустится с Q2 на Q1?
3. Какое правило защищает от программы, которая делает I/O за мгновение до конца кванта?
4. Почему boost помогает задаче, которая сменила поведение?

Что спрашивают на собесе

• Как MLFQ приближает поведение SJF, не зная длительности задач.
• Пять правил MLFQ и зачем каждое.
• Зачем priority boost и какую проблему он решает.
• Как процесс может обмануть наивный MLFQ и как это исправили.
• Какие параметры у MLFQ и почему квант на нижних уровнях делают длиннее.