Multilevel Feedback Queue

Multilevel Feedback Queue (MLFQ) — это алгоритм планирования процессов в операционных системах, предназначенный для организации выполнения вычислительных задач (процессов или потоков) с целью достижения баланса между временем отклика для интерактивных задач и пропускной способностью для фоновых (пакетных) задач. MLFQ является развитием алгоритма Multilevel Queue (многоуровневая очередь) и отличается от него возможностью миграции процесса между очередями разного приоритета в зависимости от его поведения (в первую очередь — от использования процессорного времени). Алгоритм был впервые описан в 1962 году Фернандо Корбато и его коллегами в Массачусетском технологическом институте (MIT) в рамках проекта Compatible Time-Sharing System (CTSS) и впоследствии стал основой для планировщиков во многих UNIX-подобных системах, включая 4.4BSD и Linux (в модифицированном виде).

История и предпосылки создания

До появления MLFQ в первых операционных системах использовались простые алгоритмы планирования, такие как First-Come, First-Served (FCFS) и Round Robin (RR). FCFS приводил к длительному ожиданию для коротких задач, если перед ними запускалась длительная. RR, хотя и обеспечивал приемлемое время отклика для всех процессов, неэффективно обрабатывал задачи, требующие большого количества процессорного времени, из-за частых переключений контекста.

К началу 1960-х годов возникла потребность в системе, которая могла бы одновременно обслуживать как интерактивных пользователей (например, ввод с терминала), так и пакетные задания (компиляция, расчёты). Алгоритм MLFQ был разработан для решения этой дилеммы: он даёт высокий приоритет коротким и интерактивным задачам, автоматически понижая приоритет задач, потребляющих много процессорного времени, тем самым предотвращая «голодание» длительных процессов.

Принцип работы

Основная идея MLFQ заключается в использовании нескольких очередей готовых к выполнению процессов, каждая из которых имеет свой приоритет и свой временной квант. Процессы могут перемещаться между очередями в зависимости от их поведения.

Структура очередей

Алгоритм определяет фиксированное количество очередей (обычно от 3 до 10). Каждая очередь имеет:

• Приоритет: очередь с номером 0 (или 1) имеет наивысший приоритет, с увеличением номера приоритет понижается.
• Временной квант (time quantum): на верхних (высокоприоритетных) очередях квант мал (например, 10–100 мс), на нижних — увеличивается (например, 200–500 мс). Это сделано для того, чтобы короткие интерактивные задачи быстро обрабатывались, а длительные задачи получали более крупные кванты, снижая накладные расходы на переключение контекста.

Правила планирования

Классический алгоритм MLFQ, описанный в учебной литературе (например, в книге «Operating Systems: Three Easy Pieces»), использует набор правил:

1. Правило 1 (Приоритет): Если процесс A находится в очереди с более высоким приоритетом, чем процесс B, то A выполняется первым.
2. Правило 2 (Round Robin внутри очереди): Если два процесса находятся в одной очереди, они выполняются по принципу Round Robin с квантом, заданным для этой очереди.
3. Правило 3 (Миграция вниз): Когда процесс использует свой полный временной квант без блокировки (например, не ожидая ввода/вывода), он перемещается в очередь на один уровень ниже (с меньшим приоритетом). Это наказывает процесс за «процессорную интенсивность».
4. Правило 4 (Миграция вверх): Если процесс добровольно уступает процессор до истечения кванта (например, выполняет операцию ввода/вывода), он остаётся в той же очереди или перемещается в очередь на один уровень выше (в некоторых реализациях). Это поощряет интерактивное поведение.

Пример работы

Предположим, есть три очереди: Q0 (квант 10 мс), Q1 (квант 50 мс), Q2 (квант 200 мс). Процесс A запускается в Q0. Он использует 10 мс, не блокируясь, и переходит в Q1. Затем он использует ещё 50 мс в Q1, переходит в Q2, где может выполняться долго. Если же процесс B (интерактивный) в Q0 использует только 5 мс и затем блокируется на ввод/вывод, он остаётся в Q0 и при следующем пробуждении снова получает высокий приоритет.

Разновидности и модификации

MLFQ с обратной связью с вытеснением (Preemptive MLFQ)

Большинство современных реализаций MLFQ являются вытесняющими: если в очередь с более высоким приоритетом поступает новый процесс, текущий процесс с более низкого приоритета немедленно вытесняется, и управление передаётся новому. Это обеспечивает быструю реакцию на интерактивные запросы.

MLFQ с приоритетным повышением (Priority Boost)

Одна из проблем классического MLFQ — возможность «голодания» длительных процессов, которые могут никогда не получить процессорного времени, если постоянно поступают короткие задачи. Для решения этой проблемы вводится механизм приоритетного повышения (priority boost): через определённые интервалы времени (например, каждые 100 мс) все процессы из нижних очередей перемещаются в самую верхнюю очередь. Это гарантирует, что даже длительные процессы в конечном итоге получат процессорное время.

MLFQ с учётом использования процессора (CPU Accounting)

В некоторых реализациях (например, в планировщике CFS в Linux, который не является чистым MLFQ, но использует схожие идеи) вместо простого подсчёта использования кванта применяется более точный учёт времени, проведённого процессом в состоянии выполнения. Это позволяет точнее определять «интерактивность» процесса.

MLFQ в современных ОС

• Linux: Планировщик CFS (Completely Fair Scheduler), начиная с версии 2.6.23, использует алгоритм, основанный на красно-чёрных деревьях, но в более ранних версиях (O(1) scheduler) применялась модификация MLFQ с 140 уровнями приоритета (0–99 для реального времени, 100–139 для обычных процессов).
• BSD: Планировщик 4.4BSD использовал MLFQ с 32 очередями и механизмом приоритетного повышения. В FreeBSD и macOS (XNU) применяются модифицированные версии MLFQ.
• Windows: Планировщик Windows NT (и его потомки, включая Windows 10/11) использует гибридный подход, основанный на приоритетах (0–31), с элементами MLFQ, но с более сложной эвристикой для определения приоритета процессов.

Применение

MLFQ широко применяется в операционных системах общего назначения для планирования пользовательских процессов. Он также используется в:

• Виртуализация: планировщики гипервизоров (например, Xen) могут использовать MLFQ для распределения процессорного времени между виртуальными машинами.
• Встроенные системы: в системах реального времени с мягкими ограничениями (soft real-time), где требуется баланс между интерактивностью и производительностью.
• Эмуляция и симуляция: алгоритм часто используется в учебных целях для демонстрации принципов планирования.

Критика и ограничения

Несмотря на широкое распространение, MLFQ имеет ряд недостатков:

• Сложность настройки: количество очередей, размеры квантов, правила миграции и интервалы приоритетного повышения требуют тщательной подстройки под конкретную рабочую нагрузку. Неправильная настройка может привести к неэффективности или «голоданию».
• Неоптимальность для некоторых нагрузок: для задач с равномерным потреблением процессорного времени (например, научные расчёты) MLFQ может давать худшую производительность, чем простые алгоритмы вроде FCFS.
• Непредсказуемость времени выполнения: из-за миграции между очередями время выполнения одного и того же процесса может сильно варьироваться в зависимости от текущей загрузки системы.
• Проблема «интерактивности»: алгоритм может ошибочно классифицировать процесс как интерактивный, если он часто блокируется по другим причинам (например, из-за синхронизации), что приводит к неоправданно высокому приоритету.

Сравнение с другими алгоритмами

Интересные факты

• Название «Multilevel Feedback Queue» впервые появилось в статье Фернандо Корбато и Марвина Мински (да, того самого, известного работами по искусственному интеллекту) в 1962 году.
• В ранних версиях CTSS использовалось всего 2 очереди, что уже давало существенное улучшение по сравнению с однопроцессными системами.
• В планировщике O(1) в Linux было 140 очередей, что позволяло очень точно управлять приоритетами, но требовало сложного кода для поддержания баланса.

Источники

• Корбато, Ф. Дж., Мервин-Даггетт, М., Далли, Р. К. «An Experimental Time-Sharing System» (1962).
• Сильбершац, А., Гэлвин, П. Б., Гэгн, Г. «Operating System Concepts» (10-е издание).
• Арпачи-Дюссо, Р. Э., Арпачи-Дюссо, А. Ч. «Operating Systems: Three Easy Pieces» (глава 8: «Scheduling: The Multi-Level Feedback Queue»).
• Документация ядра Linux: «Documentation/scheduler/sched-design-CFS.rst».
• Таненбаум, Э. С., Бос, Х. «Современные операционные системы» (4-е издание).