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

Из прошлой главы остался открытый вопрос: хочется и хорошего отклика (как у RR), и хорошего оборота (как у SJF), но при этом мы не знаем длительность задач заранее. MLFQ (Multi-Level Feedback Queue) решает это красивым приёмом: раз будущее неизвестно — будем учиться на прошлом.

Идея: смотрим, как задача себя ведёт. Если она быстро отдаёт CPU (сходила в I/O, ждёт ввод) — наверное, она интерактивная, держим её в приоритете ради отклика. Если она жадно молотит весь квант — наверное, она счётная (CPU-bound), понижаем её приоритет, чтобы не мешала интерактивным. Это и есть «feedback» в названии.

Правила MLFQ

Есть несколько очередей с разным приоритетом. Внутри уровня — Round Robin.

1. Если приоритет(A) > приоритет(B) — выполняется A.
2. Если приоритеты равны — A и B крутятся по RR.
3. Новая задача стартует на самом верху (максимальный приоритет). Мы оптимистично считаем её короткой/интерактивной, пока не доказано обратное.
4. Когда задача израсходовала свой бюджет времени на уровне — её приоритет понижается (демоушен), она падает на уровень ниже. Неважно, сожгла она его за один присест или урывками между I/O.

Этих правил уже хватает, чтобы система сама «рассортировала» задачи: счётные оседают внизу, интерактивные держатся вверху и получают мгновенный отклик.

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

Две проблемы и как их чинят

Базовые правила наивны, и их легко сломать:

1. Голодание (starvation). Если интерактивных задач много, счётные внизу могут не получить CPU вообще. Лечение — priority boost: раз в период S поднимаем все задачи обратно наверх. Это гарантирует, что даже задача на дне периодически получит ход, и заодно подстраивается под смену поведения (была счётной — стала интерактивной).

2. Гейминг планировщика. Хитрый процесс может почти весь квант молотить, а за миг до его конца сделать пустяковый I/O — формально он «отдал CPU сам», бюджет не сгорел, приоритет сохранился. Так можно почти монополизировать ядро. Лечение — учитывать суммарное время на уровне (а не «сгорел ли квант за раз»): набрал свой бюджет урывками — всё равно падаешь вниз.

Почему это важно за пределами ОС

MLFQ — это не музейный экспонат. Та же логика «новым клиентам — кредит доверия, жадных — понижаем» встречается в:

• планировщиках задач и пулах воркеров (приоритетные очереди с деградацией);
• rate limiting и QoS (приоритезация трафика);
• шедулерах Kubernetes и облачных платформах.

Когда на собесе по System Design просят «как приоритезировать запросы, не зная их стоимости заранее» — MLFQ это ровно тот паттерн, который стоит вспомнить: оптимистично пускай новых вверх, понижай прожорливых, периодически поднимай всех, чтобы никто не голодал.

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

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