Многоуровневые очереди¶

Многоуровневые очереди (англ. multilevel queue scheduling) — это алгоритм планирования процессов в операционных системах, при котором все процессы распределяются по нескольким очередям с различными приоритетами и дисциплинами обслуживания. Каждая очередь имеет собственный алгоритм планирования (например, FIFO, Round Robin, SJF), а процессы могут перемещаться между очередями в зависимости от их характеристик или поведения. Данный подход позволяет эффективно сочетать требования разных типов задач: интерактивных, фоновых, пакетных и системных.

¶История

Концепция многоуровневых очередей возникла в 1960-х годах в рамках развития операционных систем с разделением времени. Одной из первых реализаций стала система CTSS (Compatible Time-Sharing System), разработанная в Массачусетском технологическом институте (MIT) в 1961 году. В CTSS использовалась двухуровневая очередь: процессы с высоким приоритетом получали кванты времени, а низкоприоритетные — обслуживались по остаточному принципу.

В 1970-х годах алгоритм был усовершенствован в операционной системе MULTICS, где впервые появилась динамическая многоуровневая очередь с обратной связью (multilevel feedback queue). В 1980-х годах этот подход стал стандартом для UNIX-подобных систем, в частности, для планировщика в BSD и System V. Современные операционные системы, такие как Linux, Windows и macOS, используют модифицированные версии многоуровневых очередей, адаптированные под многопроцессорные архитектуры и реальное время.

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

Многоуровневые очереди делятся на два основных типа:

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

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

• Очередь системных процессов (высший приоритет) — использует алгоритм FIFO, так как системные задачи требуют немедленного выполнения.
• Очередь интерактивных процессов — использует Round Robin с малым квантом времени (10–50 мс) для обеспечения отзывчивости.
• Очередь пакетных процессов (низший приоритет) — использует SJF (Shortest Job First) или FCFS (First-Come, First-Served) для минимизации среднего времени ожидания.

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

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

¶Устройство и характеристики

¶Структура

Многоуровневая очередь состоит из набора очередей (обычно от 3 до 10), каждая из которых имеет:

• Приоритет — числовое значение, определяющее порядок выбора очереди для выполнения. Чем выше приоритет, тем чаще процессор обслуживает задачи из этой очереди.
• Алгоритм планирования — может быть как вытесняющим (preemptive), так и невытесняющим (non-preemptive).
• Квант времени — максимальный период непрерывного выполнения процесса из данной очереди.

¶Параметры планирования

Основные параметры, определяющие работу многоуровневых очередей:

• Количество очередей — влияет на гибкость системы: большее число очередей позволяет точнее настраивать приоритеты, но увеличивает накладные расходы на переключение.
• Приоритеты очередей — обычно задаются статически, но могут изменяться динамически.
• Алгоритмы внутри очередей — выбираются в зависимости от типа задач. Например, для очередей реального времени используется FIFO, для интерактивных — Round Robin.
• Механизм перемещения между очередями — в динамических очередях определяет, как часто и на каких условиях процесс меняет очередь.

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

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

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

Недостатки:

• Сложность реализации и настройки — требуется точное определение параметров очередей.
• Риск «голодания» низкоприоритетных процессов, если не предусмотрены механизмы повышения приоритета.
• Накладные расходы на переключение между очередями и перемещение процессов.

¶Применение

¶Операционные системы

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

• Linux — планировщик CFS (Completely Fair Scheduler) использует красно-чёрное дерево для хранения процессов, но концептуально реализует многоуровневую очередь с динамическими приоритетами. В реальном времени (RT) применяются статические очереди с приоритетами.
• Windows — планировщик использует 32 уровня приоритета (0–31), где 0–15 — динамические, 16–31 — реального времени. Процессы могут перемещаться между уровнями в зависимости от активности.
• macOS — использует многоуровневую очередь с обратной связью, основанную на алгоритме Mach.

¶Системы реального времени

В системах жёсткого реального времени (например, в авионике, медицинском оборудовании) применяются статические многоуровневые очереди с фиксированными приоритетами, чтобы гарантировать выполнение критических задач в заданные сроки. Пример — ОС QNX и VxWorks.

¶Веб-серверы и базы данных

В веб-серверах (nginx, Apache) и системах управления базами данных (PostgreSQL, MySQL) многоуровневые очереди используются для планирования запросов: запросы с высоким приоритетом (например, административные) обслуживаются раньше, чем фоновые задачи.

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

¶Пример 1: Простая трёхуровневая очередь

В этой схеме процессор сначала обслуживает Q1, пока она не опустеет, затем Q2, затем Q3. Если в Q1 появляется новый процесс, он прерывает выполнение Q2 или Q3.

¶Пример 2: Динамическая очередь с обратной связью

В операционной системе Windows процесс, который активно использует процессор (CPU-bound), постепенно понижается в приоритете с 15 до 1, а процесс, часто блокирующийся на вводе-выводе (I/O-bound), повышается. Это предотвращает «голодание» интерактивных задач.

¶Критика

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

Критики также отмечают, что в современных системах с многопроцессорными архитектурами и большим количеством ядер многоуровневые очереди уступают по производительности более простым алгоритмам, таким как CFS в Linux, который лучше масштабируется на многие ядра.

¶Источники

• Таненбаум Э., Бос Х. «Современные операционные системы» (4-е издание), 2015.
• Silberschatz A., Galvin P. B., Gagne G. «Operating System Concepts» (10th edition), 2018.
• Документация Linux Kernel: планировщик CFS (Completely Fair Scheduler).
• Техническая документация Microsoft Windows: планирование процессов.
• Stallings W. «Operating Systems: Internals and Design Principles» (9th edition), 2017.