Системная очередь

Системная очередь — это структура данных, работающая по принципу «первым пришёл — первым обслужен» (FIFO, First In — First Out), используемая в операционных системах (ОС) для организации доступа процессов к ограниченным ресурсам, таким как центральный процессор (ЦП), устройства ввода-вывода или файлы. В отличие от пользовательских очередей (например, в принтерах или мессенджерах), системная очередь управляется ядром ОС и является частью механизма планирования задач, обеспечивая справедливое распределение процессорного времени между конкурирующими процессами или потоками.

История и происхождение

Понятие очереди как способа организации доступа к ресурсам возникло в ранних операционных системах 1960-х годов, таких как CTSS (Compatible Time-Sharing System) и MULTICS. В этих системах, где несколько пользователей одновременно работали с одним компьютером, требовалось упорядочить выполнение программ. Первоначально использовались простые циклические очереди, где каждый процесс получал фиксированный квант времени (time slice). В 1970-х годах, с развитием многозадачности, появились более сложные схемы, включающие многоуровневые очереди (multi-level feedback queues), которые позволяли приоритезировать задачи. В современных ОС (Linux, Windows, macOS) системные очереди реализованы в виде списков готовых процессов (run queue) и списков ожидания (wait queue), управляемых планировщиком.

Классификация системных очередей

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

По типу ресурса

• Очередь готовых процессов (run queue) — содержит процессы, готовые к выполнению и ожидающие выделения процессорного времени. Управляется планировщиком ЦП.
• Очередь ожидания (wait queue) — объединяет процессы, заблокированные в ожидании завершения операции ввода-вывода или освобождения ресурса (например, семафора, мьютекса).
• Очередь устройств (device queue) — используется для доступа к конкретному устройству (диск, принтер, сетевая карта). Каждое устройство может иметь собственную очередь запросов.
• Очередь сообщений (message queue) — применяется для межпроцессного взаимодействия (IPC), где процессы обмениваются данными через буферы, организованные по принципу FIFO.

По приоритету

• Очередь с абсолютным приоритетом — процессы с более высоким приоритетом всегда обслуживаются раньше, чем с низким. Может приводить к «голоданию» (starvation) низкоприоритетных процессов.
• Очередь с относительным приоритетом — приоритет учитывается, но не блокирует полностью обслуживание низкоприоритетных задач (например, в многоуровневых очередях).
• Циклическая очередь (Round Robin) — все процессы получают равные кванты времени, независимо от приоритета. Используется в системах с разделением времени.

По способу реализации

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

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

Системная очередь в ядре ОС представляет собой структуру данных, содержащую указатели на дескрипторы процессов (task_struct в Linux, PCB — Process Control Block в Windows). Каждый элемент очереди включает идентификатор процесса (PID), состояние, приоритет, время ожидания и другие параметры.

Основные характеристики

• Длина очереди — количество процессов, ожидающих обслуживания. Может быть ограничена или динамически изменяться.
• Время ожидания — среднее время, которое процесс проводит в очереди до начала обслуживания. Критично для систем реального времени.
• Пропускная способность — количество процессов, обслуженных за единицу времени.
• Справедливость — мера равномерности распределения ресурсов между процессами. В системах с приоритетами справедливость может быть нарушена.

Применение

Системные очереди являются фундаментальным механизмом во всех современных операционных системах, обеспечивая многозадачность, отзывчивость и стабильность работы.

Планирование процессов

В ядре Linux планировщик CFS (Completely Fair Scheduler) использует красно-чёрное дерево для хранения готовых процессов, но в основе лежит концепция очереди: каждый процесс имеет виртуальное время выполнения, и планировщик выбирает процесс с наименьшим значением. В Windows планировщик использует многоуровневые очереди с динамическим приоритетом, где приоритет процесса может повышаться или понижаться в зависимости от поведения (интерактивные vs фоновые задачи).

Управление вводом-выводом

Драйверы устройств часто используют собственные очереди запросов. Например, в подсистеме блочного ввода-вывода Linux (block I/O layer) запросы к диску объединяются в очередь и сортируются по номеру блока (алгоритм лифта — elevator algorithm) для минимизации перемещения головок. В сетевых стеках (например, в ядре FreeBSD) очереди пакетов (ring buffer) используются для приёма и передачи данных.

Межпроцессное взаимодействие

Очереди сообщений (System V IPC, POSIX mq) позволяют процессам обмениваться данными асинхронно. В отличие от каналов (pipes), очереди сообщений поддерживают множественный доступ и приоритеты сообщений. В Windows для IPC используются почтовые ящики (mailslots) и именованные каналы, которые также реализуют очередь.

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

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

Примеры

• Очередь прерываний (IRQ queue) в ядре Linux: при возникновении аппаратного прерывания контроллер (APIC) помещает номер прерывания в очередь, а ядро обрабатывает их по порядку. В многопроцессорных системах используется распределение очередей между ядрами.
• Очередь печати (spool queue) в Windows: документы, отправленные на печать, помещаются в очередь диспетчера печати (Print Spooler), который последовательно передаёт их драйверу принтера.
• Очередь задач в планировщике Hadoop (YARN): приложения (jobs) ставятся в очередь и выполняются в соответствии с политиками (FIFO, Fair Scheduler, Capacity Scheduler).

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

• В ранних версиях UNIX (1970-е) очередь процессов была реализована как простой массив фиксированного размера. При заполнении очереди система блокировала создание новых процессов.
• В Windows NT (1993) впервые была применена многоуровневая очередь с 32 уровнями приоритета, что позволило эффективно обрабатывать как интерактивные, так и фоновые задачи.
• В ядре Linux существует понятие «очереди с обратным вызовом» (callback queue), используемое в механизме workqueue для отложенного выполнения задач в контексте процесса.
• В системах с гипервизором (например, KVM, VMware) очереди виртуальных машин управляются гипервизором, который может применять приоритеты на основе аренды ресурсов (CPU cap, shares).

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

• Голодание (starvation) — в системах с абсолютными приоритетами низкоприоритетные процессы могут никогда не получить ресурс, если постоянно поступают высокоприоритетные задачи. Для борьбы с этим используются механизмы повышения приоритета с течением времени (aging).
• Инверсия приоритетов — высокоприоритетный процесс может быть заблокирован низкоприоритетным, если они совместно используют ресурс (например, мьютекс). В ОСРВ применяются протоколы наследования приоритета (priority inheritance) для предотвращения этой проблемы.
• Перегрузка очередей — при большом количестве процессов время ожидания может расти нелинейно, что приводит к деградации производительности. В современных системах используются алгоритмы динамического управления нагрузкой (например, контроллеры TCP в сетевых стеках).
• Сложность отладки — ошибки в управлении очередями (например, потеря элемента, циклические блокировки) могут приводить к «зависанию» системы или утечкам памяти.

Источники

• Таненбаум Э., Бос Х. «Современные операционные системы» (4-е издание, 2015).
• Love R. «Linux Kernel Development» (3rd edition, 2010).
• Silberschatz A., Galvin P. B., Gagne G. «Operating System Concepts» (10th edition, 2018).
• Документация ядра Linux: «Process Scheduling» и «Wait Queues» (kernel.org).
• Microsoft Docs: «Windows Kernel-Mode Scheduler» (learn.microsoft.com).