Priority Scheduling

Priority Scheduling (планирование с приоритетами) — это алгоритм планирования процессов в операционных системах, при котором каждому процессу (или потоку) присваивается числовой приоритет, и центральный процессор (ЦП) выделяется процессу с наивысшим приоритетом среди всех готовых к выполнению. В случае равенства приоритетов обычно применяется дополнительный алгоритм, например, First-Come, First-Served (FCFS) или Round Robin (RR). Priority Scheduling является одним из фундаментальных методов диспетчеризации, наряду с FCFS, SJF (Shortest Job First) и RR.

История

Концепция приоритетного планирования возникла в ранних многозадачных операционных системах 1960-х годов, таких как CTSS (Compatible Time-Sharing System) и MULTICS. В этих системах приоритеты использовались для разграничения доступа к ресурсам между системными и пользовательскими задачами. В 1970-х годах алгоритм был реализован в UNIX, где приоритеты процессов динамически пересчитывались на основе их поведения (например, для процессов, интенсивно использующих ЦП, приоритет снижался). В современных операционных системах, таких как Linux, Windows и macOS, Priority Scheduling используется как часть гибридных схем, сочетающих статические и динамические приоритеты.

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

Priority Scheduling делится на два основных типа в зависимости от способа управления приоритетами:

Статическое приоритетное планирование

При статическом планировании приоритет присваивается процессу один раз при его создании и остаётся неизменным до завершения. Приоритеты могут задаваться пользователем (например, через команду nice в UNIX) или администратором системы. Достоинства: простота реализации и низкие накладные расходы. Недостатки: риск «голодания» (starvation) низкоприоритетных процессов, если высокоприоритетные процессы постоянно поступают в систему.

Динамическое приоритетное планирование

При динамическом планировании приоритет процесса может изменяться во время выполнения. Изменения обычно происходят на основе факторов, таких как время ожидания процесса в очереди готовности, количество использованных квантов ЦП или тип выполняемой операции (например, ввод-вывод). Динамические приоритеты позволяют снизить риск «голодания» и повысить справедливость распределения ресурсов. Примером является алгоритм, используемый в ядре Linux (Completely Fair Scheduler, CFS), где приоритеты косвенно регулируются через виртуальное время выполнения.

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

Очереди готовности

В Priority Scheduling обычно используется несколько очередей готовности — по одной для каждого уровня приоритета. Планировщик выбирает процесс из очереди с наивысшим приоритетом, которая не пуста. Внутри очереди может применяться любой дополнительный алгоритм (FCFS, RR и т.д.).

Вытесняющее и невытесняющее планирование

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

Проблема «голодания»

«Голодание» (starvation) — это ситуация, при которой низкоприоритетный процесс никогда не получает ЦП, потому что постоянно поступают процессы с более высоким приоритетом. Для решения этой проблемы применяются:

• Повышение приоритета со временем (aging): приоритет процесса постепенно увеличивается по мере его ожидания в очереди готовности. Например, каждые N секунд ожидания приоритет процесса повышается на единицу. Это гарантирует, что даже самый низкоприоритетный процесс рано или поздно получит ЦП.
• Динамическое перераспределение приоритетов: приоритеты пересчитываются на основе времени ожидания или других метрик.

Инверсия приоритетов

Инверсия приоритетов — это нежелательное явление, при котором высокоприоритетный процесс косвенно блокируется низкоприоритетным процессом, удерживающим общий ресурс (например, мьютекс). Классический пример произошёл в 1997 году в системе Mars Pathfinder, где из-за инверсии приоритетов происходили сбои. Для предотвращения инверсии используются протоколы наследования приоритетов (priority inheritance) или потолка приоритетов (priority ceiling).

Применение

Priority Scheduling широко применяется в различных областях вычислительной техники:

• Операционные системы общего назначения: Windows (приоритеты потоков от 0 до 31), Linux (приоритеты реального времени от 0 до 99, обычные процессы — динамические приоритеты), macOS (аналогично UNIX).
• Системы реального времени (RTOS): в жёстких системах реального времени (например, VxWorks, FreeRTOS) Priority Scheduling является основным алгоритмом, так как позволяет гарантировать выполнение критических задач в заданные сроки. В таких системах приоритеты обычно статические и назначаются вручную разработчиком.
• Планировщики задач в базах данных: для управления параллельными запросами и транзакциями.
• Сетевые маршрутизаторы: для обработки пакетов с разными приоритетами (например, QoS — Quality of Service).

Примеры

Пример 1: Статическое невытесняющее планирование

Пусть в систему поступают три процесса:

• Процесс A: приоритет 3, время выполнения 10 мс
• Процесс B: приоритет 1 (наивысший), время выполнения 5 мс
• Процесс C: приоритет 2, время выполнения 8 мс

При невытесняющем планировании порядок выполнения: B (5 мс) → C (8 мс) → A (10 мс). Среднее время ожидания: (0 + 5 + 13) / 3 = 6 мс.

Пример 2: Динамическое вытесняющее планирование с aging

Процесс D с приоритетом 10 ожидает в очереди 100 секунд. Каждые 10 секунд его приоритет повышается на 1. Через 100 секунд его приоритет станет 20, что позволит ему вытеснить процесс с приоритетом 15, который только что поступил.

Критика

Priority Scheduling критикуется за:

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

Источники

• Таненбаум Э., Бос Х. «Современные операционные системы» (4-е издание), 2015.
• Silberschatz A., Galvin P.B., Gagne G. «Operating System Concepts» (10th edition), 2018.
• Stallings W. «Operating Systems: Internals and Design Principles» (9th edition), 2017.
• Документация ядра Linux: «CFS Scheduler» (kernel.org/doc/Documentation/scheduler/sched-design-CFS.txt).
• «Priority Inversion» — Mars Pathfinder bug report, 1997 (NASA JPL).