Приоритетное планирование

Приоритетное планирование (англ. priority scheduling) — это алгоритм планирования задач в операционных системах и системах реального времени, при котором каждой задаче (процессу, потоку) присваивается числовой приоритет, и процессор выделяется задаче с наивысшим приоритетом среди готовых к выполнению.

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

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

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

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

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

Вытесняющее планирование обеспечивает более быструю реакцию на события высокого приоритета, но требует более сложной реализации и синхронизации.

Классификация приоритетов

Статические приоритеты

Приоритет задачи устанавливается один раз при её создании и не меняется в процессе выполнения. Такой подход прост в реализации, но может приводить к проблеме «голодания» (starvation), когда задачи с низким приоритетом никогда не получают процессор, если постоянно поступают задачи с более высокими приоритетами.

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

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

Приоритеты по типу задач

В некоторых системах приоритеты разделяют на классы:

• Приоритеты реального времени — присваиваются задачам с жёсткими временными ограничениями (hard real-time). Такие задачи имеют наивысший приоритет и не могут быть вытеснены обычными задачами.
• Приоритеты обычных пользовательских процессов — используются для фоновых и интерактивных задач.
• Приоритеты системных процессов — обслуживают критически важные функции операционной системы.

Алгоритмы на основе приоритетов

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

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

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

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

Планирование «по кратчайшему остатку» (Shortest Remaining Time)

Формально это вариант приоритетного планирования, где приоритетом является оставшееся время выполнения задачи. Чем меньше осталось до завершения, тем выше приоритет. Этот теоретически оптимальный по среднему времени ожидания алгоритм редко используется на практике из-за сложности оценки оставшегося времени.

Планирование по срокам

В системах жёсткого реального времени (например, Rate-Monotonic Scheduling) приоритет определяется периодом или сроком (deadline) задачи. Задача, у которой ближайший срок, получает самый высокий приоритет.

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

Голодание (Starvation)

Постоянное поступление задач с высоким приоритетом может навсегда заблокировать доступ к процессору для задач с низким приоритетом. Для борьбы с голоданием применяются:

• Повышение приоритета долго ожидающих задач («старение» — aging).
• Использование динамических приоритетов.
• Комбинирование с другими алгоритмами (например, циклическим планированием в рамках одного уровня приоритета).

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

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

Влияние на производительность

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

Применение

Приоритетное планирование широко применяется:

• В операционных системах общего назначения (Windows, Linux, macOS) для управления интерактивными и фоновыми процессами.
• В системах реального времени (ОСРВ, например, QNX, VxWorks, RTEMS) для обеспечения гарантированного времени реакции на события.
• Во встраиваемых системах, где важно обрабатывать критические прерывания и сигналы быстрее обычных.
• В коммутаторах и маршрутизаторах для обработки пакетов с разным уровнем сервиса (QoS).
• В планировщиках задач баз данных для выполнения запросов с разной срочностью.

Примеры в операционных системах

• Linux. Планировщик CFS (Completely Fair Scheduler) использует приоритеты в виде весов задач. Задачи реального времени (подклассы SCHED_FIFO и SCHED_RR) имеют статические приоритеты от 0 до 99. Обычные процессы (SCHED_NORMAL, SCHED_BATCH) имеют динамические nice-значения от -20 до +19, влияющие на долю процессора.
• Windows. Используется многоуровневая приоритетная очередь с 32 уровнями приоритетов (от 0 до 31). Приоритеты могут динамически корректироваться для интерактивных процессов.
• RTOS (FreeRTOS, ThreadX). Каждый поток имеет фиксированный приоритет (обычно от 0 до 255 или 0 до 31). Планирование исключительно приоритетное, вытесняющее.

См. также

• Планирование процессов
• Round-robin (планирование)
• Справедливое планирование
• Приоритет прерывания

Источники

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