---
title: "MLFQ: планировщик, который угадывает будущее"
description: "Прошлая глава закончилась противоречием. SJF и STCF хороши по обороту, но требуют знать длительность задачи. RR хорош по отклику, но плох по обороту. ОС длительность не знает и…"
canonical: https://graphlms.ru/os/book/mlfq
course: "Операционные системы"
updated: 2026-10-12
lang: ru
publisher: GraphLMS
---

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

> Источник: https://graphlms.ru/os/book/mlfq — курс «Операционные системы», GraphLMS.

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

[Прошлая глава](/os/book/scheduling) закончилась противоречием. 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 мс.

```text
время, мс   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 стартует наверху и сразу получает
процессор.

> Интерактивный симулятор «MLFQ»: Новые задачи стартуют на верхнем уровне, а те, что съели весь квант, опускаются ниже: так A и B сползают вниз. Цвет полоски показывает текущий уровень. Короткая задача C приходит в момент 8, попадает наверх и обгоняет обеих. Поменяйте квант и посмотрите, как изменится порядок. Запустить: https://graphlms.ru/os/book/mlfq

## Зачем правило 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`, которой можно
понизить приоритет фоновой задачи. К ней вернёмся в главе
[пропорциональное планирование](/os/book/proportional-scheduling).

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

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

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

> Квиз по разделу: см. вопросы в конце документа или на https://graphlms.ru/os/book/mlfq

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

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

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

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

Ответы. (1) На Q0: она спустилась туда в 20 мс. (2) Через 5 циклов: 5 × 2 мс = 10 мс
бюджета. (3) Правило 4 с учётом суммарного времени на уровне. (4) После подъёма
задача снова наверху, и если она больше не съедает бюджет, там и останется.

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

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

## Вопросы для самопроверки

**Квиз «Правила MLFQ»**

1. На каком уровне приоритета стартует новая задача в MLFQ?
   - на верхнем (максимальный приоритет) (верно)
   - в середине
   - на нижнем (минимальный приоритет)
   - Пояснение: Новая задача может оказаться и короткой интерактивной, и долгой счётной, а заранее это не известно. Планировщик ставит её на верхний уровень: если она короткая, то успеет закончиться или уйти в I/O, не потеряв приоритет; если долгая, то быстро сползёт вниз.
2. Какую проблему решает priority boost (периодический подъём всех задач наверх)?
   - convoy effect
   - гейминг планировщика
   - голодание (starvation) задач внизу (верно)
   - Пояснение: Без boost счётные задачи на дне могут не получить CPU вовсе. Boost гарантирует им ход и подхватывает смену поведения.
3. Как хитрый процесс обманывает наивный MLFQ, чтобы удержать приоритет?
   - занимает меньше памяти
   - делает крошечный I/O за миг до конца кванта (верно)
   - создаёт много потоков
   - Пояснение: Формально процесс «сам отдал CPU», бюджет уровня не сгорел. Чинится учётом суммарного времени на уровне, а не «сгорел ли квант за раз».
4. Задача полностью израсходовала свой квант на текущем уровне. Что делает MLFQ по базовым правилам?
   - Повышает её приоритет
   - Завершает её принудительно
   - Понижает её приоритет на один уровень (верно)
   - Оставляет на том же уровне навсегда
   - Пояснение: Это правило на тот случай, когда задача оказалась счётной: если она заняла CPU на весь квант, она не интерактивная, и её опускают вниз. Так короткие и интерактивные задачи остаются сверху и получают CPU первыми.
5. Две задачи сидят на одном уровне приоритета. Как MLFQ выбирает, кого запускать?
   - По кругу (Round Robin) с квантом этого уровня (верно)
   - Ту, у которой короче оставшееся время
   - Случайную, по жребию
   - Ту, что пришла раньше, до полного завершения
   - Пояснение: Правило MLFQ: выше приоритет — запускаем его. Если приоритеты равны, задачи на этом уровне крутятся по кругу. Планировщик не знает длины задач и потому не может выбирать по оставшемуся времени, как это делал бы SJF.
6. В очереди только интерактивные задачи с короткими вспышками CPU и одна счётная на нижнем уровне. Зачем всё же раз в несколько секунд поднимать все задачи наверх?
   - Чтобы ускорить переключение контекста
   - Счётная задача иначе может не получить CPU вообще, а если её поведение изменилось, планировщик об этом не узнает (верно)
   - Чтобы интерактивные задачи опустились вниз и освободили CPU
   - Чтобы увеличить квант на верхнем уровне
   - Пояснение: Здесь две причины сразу: голодание нижних уровней и смена поведения. Задача, которая долго считала и стала интерактивной, без подъёма так и осталась бы на дне. После boost она снова наверху, и планировщик заново оценит её по поведению.