Многоуровневая очередь с обратной связью

Многоуровневая очередь с обратной связью (англ. Multilevel Feedback Queue, MLFQ) — это алгоритм планирования процессов в операционных системах, предназначенный для распределения времени центрального процессора (ЦП) между несколькими выполняющимися процессами. Он относится к классу алгоритмов с вытеснением и динамическими приоритетами, позволяя эффективно сочетать преимущества алгоритмов, ориентированных на интерактивные (с коротким временем выполнения) и фоновые (длительные) задачи. Основная идея MLFQ заключается в организации нескольких очередей с разными приоритетами и временными квантами, при этом процесс может перемещаться между очередями в зависимости от его поведения (например, использования ЦП или ожидания ввода-вывода).

История

Разработка многоуровневых очередей с обратной связью восходит к 1960-м годам, когда в операционных системах возникла необходимость обслуживать как интерактивные задачи (например, ввод команд с терминала), так и пакетные задания (длительные вычисления). Одним из первых известных примеров реализации MLFQ стала операционная система CTSS (Compatible Time-Sharing System), созданная в Массачусетском технологическом институте (MIT) в 1962 году. В CTSS использовалась система с несколькими очередями, где процессы с более высоким приоритетом получали меньший квант времени, а при длительном выполнении перемещались в очереди с более низким приоритетом. Позднее алгоритм был усовершенствован в системе MULTICS (1965–1969) и затем в операционной системе UNIX, где в версии 4.3BSD (1986) была реализована одна из наиболее известных версий MLFQ.

В 1970-х годах алгоритм получил теоретическое обоснование в работах Фернандо Корбато и других исследователей, которые показали его эффективность для систем с разделением времени. В современных операционных системах, таких как Linux, Windows и macOS, используются различные модификации MLFQ, хотя точные параметры и детали реализации часто являются коммерческой тайной.

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

Многоуровневая очередь с обратной связью состоит из нескольких уровней (очередей), каждая из которых имеет свой приоритет и временной квант. Обычно очереди нумеруются от 0 (самый высокий приоритет) до N-1 (самый низкий). Процессы, поступающие в систему, изначально помещаются в очередь с наивысшим приоритетом (например, очередь 0). Алгоритм работает по следующим правилам:

1. Выбор процесса: Планировщик всегда выбирает процесс из очереди с наивысшим приоритетом, в которой есть хотя бы один процесс. Если в очереди 0 есть процессы, они обслуживаются в порядке очереди (FIFO) или по круговому алгоритму (Round Robin) в пределах этой очереди.

1. Вытеснение: Если в очередь с более высоким приоритетом поступает новый процесс, текущий процесс вытесняется (прерывается) и возвращается в свою очередь. Это обеспечивает приоритет интерактивным задачам.

1. Перемещение между очередями (обратная связь): После выполнения процесса в течение определённого временного кванта (или при его исчерпании) процесс может быть перемещён в очередь с более низким приоритетом. Если процесс завершается или переходит в состояние ожидания (например, ожидает ввода-вывода) до истечения кванта, он остаётся в той же очереди или перемещается в очередь с более высоким приоритетом. Это позволяет «награждать» короткие задачи (интерактивные) и «наказывать» длительные (фоновые).

1. Периодическое повышение приоритета: Для предотвращения «голодания» (starvation) процессов с низким приоритетом, которые могут никогда не получить ЦП, в некоторых реализациях MLFQ предусмотрено периодическое повышение приоритета всех процессов, находящихся в очередях с низким приоритетом, до самого высокого уровня. Это гарантирует, что даже длительные процессы в конечном итоге получат время ЦП.

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

Рассмотрим систему с тремя очередями:

• Очередь 0 (высший приоритет): квант 10 мс.
• Очередь 1 (средний приоритет): квант 50 мс.
• Очередь 2 (низший приоритет): квант 200 мс.

Процесс A (интерактивный, короткое выполнение) поступает в очередь 0. Он выполняется 5 мс и завершается, оставаясь в очереди 0. Процесс B (длительное вычисление) поступает в очередь 0, выполняется 10 мс, не завершается и перемещается в очередь 1. Затем он выполняется 50 мс, не завершается, перемещается в очередь 2. После этого процесс B будет выполняться в очереди 2, пока не завершится или не будет вытеснен новым процессом из очереди 0. Если в очередь 0 поступит процесс C, он вытеснит B, и B вернётся в очередь 2.

Классификация и виды

Многоуровневые очереди с обратной связью можно классифицировать по нескольким параметрам:

По количеству очередей

• Фиксированное количество очередей — наиболее распространённый вариант, где число очередей задаётся при настройке системы (например, 3, 4 или 8). В современных системах, таких как Linux, число очередей может быть фиксированным (например, 140 в планировщике O(1) в ядре 2.6).
• Динамическое количество очередей — теоретическая модель, где очереди создаются по мере необходимости, но на практике встречается редко из-за сложности реализации.

По правилам перемещения

• Стандартная MLFQ — процесс перемещается только вниз по приоритетам при исчерпании кванта.
• MLFQ с повышением приоритета — периодически все процессы возвращаются в очередь с наивысшим приоритетом (например, каждые 1–2 секунды).
• MLFQ с обратной связью по времени ожидания — процесс может перемещаться вверх, если он долго не получал ЦП (для предотвращения голодания).

По типу обслуживания в очереди

• FIFO — процессы в очереди обслуживаются в порядке поступления.
• Round Robin — процессы в очереди обслуживаются циклически с квантом, равным кванту данной очереди.

Характеристики и параметры

Основные параметры, которые необходимо задать при реализации MLFQ:

• Количество очередей (N).
• Временной квант для каждой очереди (обычно увеличивается с понижением приоритета, например, 10, 50, 200 мс).
• Правила перемещения между очередями (например, после исчерпания кванта — вниз, при завершении до истечения — вверх или остаться).
• Интервал периодического повышения приоритета (если используется).
• Размер очереди (максимальное количество процессов в одной очереди, если ограничено).

Применение и значение

Многоуровневая очередь с обратной связью широко применяется в операционных системах общего назначения, где требуется поддерживать как интерактивные приложения (текстовые редакторы, веб-браузеры, игры), так и фоновые задачи (компиляция, загрузка файлов, обновление системы). Основные достоинства алгоритма:

• Адаптивность — автоматически подстраивается под поведение процессов, не требуя ручного задания приоритетов.
• Эффективность для интерактивных задач — короткие процессы получают ЦП с минимальной задержкой.
• Справедливость — длительные процессы не блокируются полностью, хотя и получают меньше времени ЦП.

Недостатки включают:

• Сложность настройки — оптимальные параметры (количество очередей, кванты) зависят от нагрузки и могут требовать тонкой настройки.
• Возможность голодания — при неправильной настройке длительные процессы могут не получать ЦП длительное время.
• Накладные расходы — перемещение между очередями и вытеснение процессов требуют дополнительных ресурсов ЦП.

Примеры в современных ОС

• Linux — в ядре 2.6 использовался планировщик O(1) с 140 очередями (0–139), где приоритеты задавались статически и динамически. В более новых версиях (начиная с 2.6.23) используется Completely Fair Scheduler (CFS), который не является прямой реализацией MLFQ, но использует некоторые идеи, такие как динамическое распределение времени.
• Windows — в Windows NT и более поздних версиях (Windows 2000, XP, 7, 10, 11) используется планировщик с 32 уровнями приоритетов (0–31), где 0–15 — динамические приоритеты для обычных процессов, а 16–31 — реального времени. Процессы могут перемещаться между уровнями в зависимости от использования ЦП и ожидания ввода-вывода.
• macOS — использует гибридный планировщик, основанный на MLFQ, с несколькими очередями (например, для потоков реального времени, интерактивных и фоновых).

Критика и альтернативы

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

• Completely Fair Scheduler (CFS) — использует красное-чёрное дерево для справедливого распределения времени ЦП, не требует очередей с приоритетами.
• Earliest Deadline First (EDF) — алгоритм реального времени, ориентированный на задачи с жёсткими сроками.
• Lottery Scheduling — вероятностный алгоритм, где процессы получают «лотерейные билеты» для доступа к ЦП.

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

• В оригинальной реализации CTSS квант времени для очереди с наивысшим приоритетом составлял всего 1 миллисекунду, что было обусловлено медленными процессорами того времени.
• В операционной системе MULTICS использовалось до 64 уровней очередей, что позволяло тонко настраивать приоритеты для большого числа пользователей.
• В современных версиях Windows (например, Windows 10) планировщик использует MLFQ с 32 уровнями, но динамические приоритеты могут повышаться только на 2 уровня за раз, чтобы избежать резких скачков.

Источники

• Таненбаум Э., Бос Х. «Современные операционные системы». 4-е изд. — СПб.: Питер, 2015.
• Silberschatz A., Galvin P. B., Gagne G. «Operating System Concepts». 10th ed. — Wiley, 2018.
• Corbato F. J., Daggett M. M., Daley R. C. «An Experimental Time-Sharing System» (1962) — описание CTSS.
• McKusick M. K., Bostic K., Karels M. J., Quarterman J. S. «The Design and Implementation of the 4.4BSD Operating System». — Addison-Wesley, 1996.
• Love R. «Linux Kernel Development». 3rd ed. — Addison-Wesley, 2010.