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

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

История

Идея многоуровневых очередей с обратной связью была впервые предложена в 1960-х годах в рамках разработки операционной системы Multics (Multiplexed Information and Computing Service). Multics, создававшаяся в Массачусетском технологическом институте (MIT), Bell Labs и General Electric, стремилась обеспечить поддержку многопользовательской работы с разделением времени. В этой системе требовалось справедливо распределять процессорное время между множеством пользователей, одновременно работающих с терминалами. Алгоритм MLFQ был реализован как компромисс между простотой реализации и гибкостью: он позволял быстро реагировать на интерактивные запросы (например, нажатие клавиш) и при этом не давал фоновым процессам «голодать» из-за отсутствия процессорного времени.

В 1970-х годах алгоритм был усовершенствован в операционной системе UNIX, где он стал основой для планировщика процессов. В частности, в версии 4.3BSD (1986 год) была внедрена версия MLFQ с экспоненциальным распределением квантов времени и механизмом приоритетных очередей. В последующие десятилетия MLFQ эволюционировал, адаптируясь к многопроцессорным системам, реальному времени и виртуализации. Современные реализации, такие как планировщик CFS (Completely Fair Scheduler) в Linux, используют модифицированные версии MLFQ, хотя и с другими подходами к управлению приоритетами.

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

Основные компоненты

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

• Несколько очередей (обычно от 3 до 10), каждая из которых имеет свой приоритет. Очереди с более высоким приоритетом обслуживаются в первую очередь.
• Квант времени (time quantum) — максимальный период непрерывного использования процессора, выделяемый процессу в каждой очереди. Обычно кванты различаются: в высокоприоритетных очередях они короткие (например, 1–10 миллисекунд), в низкоприоритетных — длинные (10–100 миллисекунд).
• Правила перехода между очередями: процесс может перемещаться вверх (повышать приоритет) или вниз (понижать приоритет) в зависимости от своего поведения.
• Механизм обратной связи — динамическое изменение приоритета на основе наблюдений за использованием процессора.

Алгоритм работы

1. Инициализация: Все процессы помещаются в самую высокоприоритетную очередь (например, очередь 0). Каждому процессу присваивается начальный приоритет и квант времени.
2. Выбор процесса: Планировщик выбирает процесс из очереди с наивысшим приоритетом, которая не пуста. Если в такой очереди несколько процессов, они обслуживаются в порядке очереди (FIFO) или по круговому алгоритму (Round Robin).
3. Выполнение: Процесс выполняется в течение своего кванта времени. Если процесс завершается до истечения кванта, он удаляется из системы. Если процесс блокируется (например, ожидает ввода-вывода), он временно покидает очередь и возвращается позже.
4. Обратная связь: Если процесс использует весь свой квант времени (то есть не завершается и не блокируется), его приоритет понижается: он перемещается в очередь с более низким приоритетом. Если процесс часто блокируется (например, для ввода-вывода), его приоритет может повышаться или оставаться высоким.
5. Повышение приоритета: Для предотвращения «голодания» (starvation) низкоприоритетных процессов, система периодически повышает приоритет всех процессов, находящихся в низких очередях, переводя их в более высокие очереди. Это может происходить, например, каждые 100 миллисекунд.

Пример

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

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

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

Классификация

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

• Двухуровневые (2 очереди): простейшая реализация, часто используется в учебных целях или в системах с ограниченными ресурсами. Одна очередь — для интерактивных процессов, другая — для фоновых.
• Многоуровневые (3–10 очередей): наиболее распространённые. Позволяют более тонко настраивать приоритеты.
• С большим числом очередей (более 10): используются в системах реального времени или в специализированных ОС, где требуется точное управление временем.

По правилам перехода

• Фиксированные правила: переходы между очередями жёстко заданы (например, после каждого полного использования кванта приоритет понижается на один уровень).
• Адаптивные правила: система анализирует историю процесса (например, среднее время между блокировками) и динамически корректирует приоритет.
• С приоритетным повышением: обязательное периодическое повышение приоритета для предотвращения голодания.

По типу обратной связи

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

Характеристики

Преимущества

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

Недостатки

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

Применение

В операционных системах общего назначения

• Linux: до внедрения CFS (2007 год) в ядре Linux использовался планировщик, основанный на MLFQ (O(1) scheduler). Современные версии Linux используют CFS, который реализует идею справедливого распределения времени, но с элементами MLFQ (например, приоритетные очереди для реального времени).
• Windows: планировщик Windows (начиная с Windows NT) использует многоуровневые очереди с динамическим приоритетом. Процессы с высоким приоритетом (например, системные) обслуживаются в первую очередь.
• macOS и iOS: XNU (ядро macOS) использует гибридный планировщик, сочетающий MLFQ с алгоритмами реального времени.

В системах реального времени

В системах жёсткого реального времени (например, в авионике или медицинском оборудовании) MLFQ применяется с фиксированными приоритетами и строгими гарантиями времени выполнения. Однако в таких системах чаще используются алгоритмы Rate-Monotonic Scheduling (RMS) или Earliest Deadline First (EDF), так как MLFQ может вносить недетерминированные задержки.

В эмуляторах и виртуализации

Виртуальные машины (например, KVM, VMware) используют MLFQ для распределения процессорного времени между гостевыми ОС. Это позволяет эффективно обслуживать как интерактивные рабочие станции, так и серверные нагрузки.

Примеры реализаций

• Планировщик O(1) в Linux (2.6.x): использовал 140 очередей (100 для реального времени, 40 для обычных процессов). Кванты времени варьировались от 1 до 200 мс. Приоритеты динамически изменялись на основе поведения процессов.
• Планировщик Windows NT: использует 32 очереди приоритетов (0–31). Процессы с приоритетом 0–15 — динамические, с 16–31 — реального времени. Приоритеты повышаются при блокировках ввода-вывода.
• FreeBSD ULE scheduler: реализует многоуровневые очереди с адаптивным повышением приоритета и поддержкой многопроцессорности.

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

• В классической реализации MLFQ в Multics использовалось до 64 очередей, что позволяло очень тонко настраивать приоритеты.
• Алгоритм MLFQ является основой для многих современных планировщиков, но его чистая форма редко используется из-за необходимости точной настройки. Вместо этого применяются гибридные подходы.
• В 1970-х годах была доказана теорема о том, что MLFQ может обеспечить оптимальное время отклика для интерактивных процессов при условии правильного выбора параметров.

Источники

• Silberschatz, A., Galvin, P. B., Gagne, G. (2018). Operating System Concepts (10th ed.). Wiley.
• Tanenbaum, A. S., Bos, H. (2015). Modern Operating Systems (4th ed.). Pearson.
• Королёв, Л. Н., Миков, А. И. (2005). Операционные системы (2-е изд.). М.: Бином.
• Документация ядра Linux: Linux Kernel Scheduler (kernel.org).
• Документация Microsoft: Windows Scheduling (MSDN).