Multilevel Queue

Multilevel Queue (многоуровневая очередь) — это алгоритм планирования процессов в операционных системах, предназначенный для организации работы с задачами, имеющими различные приоритеты и требования к времени выполнения. В отличие от простых очередей (FIFO, Round Robin), данный подход разделяет все процессы на несколько групп (уровней), каждая из которых обслуживается по собственному алгоритму. Основная цель — обеспечить баланс между интерактивностью (быстрым откликом для пользовательских задач) и пропускной способностью (эффективным выполнением фоновых и пакетных заданий).

История и развитие

Концепция многоуровневых очередей возникла в 1960-х годах в рамках развития многозадачных операционных систем. Одной из первых реализаций стала система CTSS (Compatible Time-Sharing System), разработанная в Массачусетском технологическом институте. В ней процессы делились на два уровня: интерактивные (с высоким приоритетом) и фоновые (с низким). В 1970-х годах алгоритм был усовершенствован в системах UNIX, где появилась поддержка нескольких очередей с разными квантами времени. В современных операционных системах (Windows, Linux, macOS) Multilevel Queue используется как часть гибридных планировщиков, комбинирующих статические и динамические приоритеты.

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

Multilevel Queue предполагает, что все процессы в системе распределяются по фиксированному числу очередей (уровней). Каждая очередь имеет собственный приоритет и алгоритм обслуживания. Планировщик выбирает процесс для выполнения из очереди с наивысшим приоритетом, которая не пуста. Если в очереди с высоким приоритетом есть процессы, они выполняются первыми, а процессы из низкоприоритетных очередей могут бесконечно долго ждать (эффект «голодания»). Для предотвращения этого применяются механизмы вытеснения и повышения приоритета.

Типичные уровни

В классической реализации выделяют три-четыре уровня:

• Системные процессы (самый высокий приоритет). К ним относятся задачи ядра ОС, обработчики прерываний, драйверы. Обслуживаются по алгоритму FIFO (First In, First Out) без вытеснения, так как требуют минимальных задержек.
• Интерактивные процессы (средний приоритет). Пользовательские приложения (редакторы, браузеры, терминалы). Используют алгоритм Round Robin (RR) с небольшим квантом времени (10–50 мс) для обеспечения быстрого отклика.
• Фоновые процессы (низкий приоритет). Пакетные задания, обновления, антивирусные сканеры. Обслуживаются по алгоритму FIFO или RR с большим квантом (100–500 мс).
• Пакетные процессы (самый низкий приоритет). Долгие вычисления, научные расчёты, компиляция. Могут выполняться в режиме «по возможности» (best-effort) с минимальным приоритетом.

Алгоритмы внутри очередей

Каждая очередь может использовать свой алгоритм планирования:

• FIFO — процессы выполняются в порядке поступления, без вытеснения. Подходит для коротких системных задач.
• Round Robin — каждому процессу выделяется фиксированный квант времени, после чего он перемещается в конец очереди. Обеспечивает равномерное распределение процессорного времени среди интерактивных задач.
• Priority Scheduling — процессы внутри очереди сортируются по динамическому приоритету. Используется редко, так как может привести к голоданию.

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

Multilevel Queue делится на два основных типа:

Статическая многоуровневая очередь

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

Динамическая многоуровневая очередь (Multilevel Feedback Queue)

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

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

При проектировании Multilevel Queue необходимо задать несколько параметров:

• Количество очередей — обычно от 2 до 10. Чем больше очередей, тем точнее настройка, но сложнее управление.
• Алгоритм для каждой очереди — выбор между FIFO, RR, Priority Scheduling.
• Квант времени — для RR-очередей. Для интерактивных задач квант мал (10–50 мс), для фоновых — велик (100–500 мс).
• Приоритет очередей — фиксированный или динамический.
• Механизм вытеснения — если процесс из высокоприоритетной очереди появляется, когда выполняется процесс из низкоприоритетной, последний вытесняется.
• Правила перемещения (для Feedback Queue) — условия повышения и понижения приоритета.

Применение

Multilevel Queue используется в операционных системах общего назначения, где требуется одновременная поддержка интерактивных и пакетных задач:

• Windows (NT-ядро) — планировщик использует 32 уровня приоритета, объединённых в две группы: реального времени (16–31) и переменного (1–15). Внутри групп применяются разные алгоритмы (RR для интерактивных, FIFO для фоновых). Процессы могут перемещаться между уровнями в зависимости от активности.
• Linux — в ядре до версии 2.6 использовалась O(1)-планировщик с 140 очередями (100 для реального времени, 40 для обычных). В современных версиях (CFS — Completely Fair Scheduler) концепция очередей заменена красно-чёрным деревом, но для задач реального времени сохраняется многоуровневая очередь.
• macOS — планировщик XNU (ядро Darwin) использует 4 уровня: реального времени, timeshare, фоновый и idle. Каждый уровень имеет свой алгоритм (RR, FIFO, CFS).
• Встраиваемые системы — в RTOS (FreeRTOS, QNX) для задач с жёсткими сроками применяются статические очереди с фиксированными приоритетами.

Преимущества и недостатки

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

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

Недостатки

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

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

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

• В операционной системе MINIX (учебная версия UNIX) используется трёхуровневая очередь: системные задачи, драйверы, пользовательские процессы.
• Алгоритм Multilevel Feedback Queue был впервые описан в 1962 году в работе Фернандо Корбато «An Experimental Time-Sharing System».
• В современных процессорах (Intel, AMD) аппаратные планировщики (Hyper-Threading) также используют многоуровневые очереди для распределения потоков между ядрами.
• В облачных вычислениях (например, в планировщике Kubernetes) применяется аналогичная концепция — очереди с разными приоритетами для pod'ов.

Источники

• Таненбаум Э., Бос Х. «Современные операционные системы» (4-е издание). — СПб.: Питер, 2015. — 1120 с.
• Silberschatz A., Galvin P.B., Gagne G. «Operating System Concepts» (10th edition). — Wiley, 2018. — 976 p.
• Stallings W. «Operating Systems: Internals and Design Principles» (9th edition). — Pearson, 2017. — 800 p.
• Документация Linux Kernel: «Process Scheduler» (kernel.org).
• Документация Microsoft: «Windows Kernel-Mode Scheduler» (learn.microsoft.com).