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

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

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

Концепция вытесняющего планирования возникла в 1960-х годах в рамках разработки многозадачных операционных систем для мэйнфреймов. Одной из первых реализаций стала система CTSS (Compatible Time-Sharing System) в Массачусетском технологическом институте, где использовалось квантование времени (time-slicing) для обеспечения интерактивной работы нескольких пользователей. В 1970-х годах вытесняющее планирование стало стандартом для Unix-подобных систем, а в 1980-х — для операционных систем реального времени, таких как VxWorks и QNX. В современных ОС (Windows, Linux, macOS) вытесняющее планирование является основным режимом работы для большинства процессов.

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

Основные понятия

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

• Контекстное переключение — сохранение состояния текущего процесса (регистры, счётчик команд, стек) и загрузка состояния другого процесса.
• Планировщик — компонент ядра ОС, который выбирает следующий процесс для выполнения на основе заданных алгоритмов.
• Квант времени (time slice) — фиксированный интервал времени, выделяемый процессу для работы на ЦП. По истечении кванта процесс принудительно вытесняется.
• Приоритет процесса — числовое значение, определяющее важность процесса; процессы с более высоким приоритетом имеют преимущество при выборе на выполнение.

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

Наиболее распространённые алгоритмы:

1. Round Robin (RR) — циклическое планирование с квантованием. Каждому процессу выделяется равный квант времени; после его истечения процесс помещается в конец очереди готовых процессов. Обеспечивает равномерное распределение времени, но не учитывает приоритеты.

1. Priority-based Preemptive Scheduling — планирование на основе приоритетов с вытеснением. Процесс с более высоким приоритетом может прервать выполнение процесса с низким приоритетом. Используется в системах реального времени, где критически важные задачи должны выполняться без задержек.

1. Multilevel Feedback Queue (MLFQ) — многоуровневая очередь с обратной связью. Процессы распределяются по нескольким очередям с разными квантами и приоритетами. Система динамически перемещает процессы между очередями в зависимости от их поведения (например, если процесс часто использует ЦП, он может быть понижен в приоритете). Этот алгоритм применяется в ядре Linux (с модификациями).

1. Earliest Deadline First (EDF) — планирование на основе ближайшего крайнего срока. Используется в жёстких системах реального времени: процесс, у которого крайний срок выполнения наступает раньше, получает приоритет. Теоретически оптимален для однопроцессорных систем.

1. Rate Monotonic Scheduling (RMS) — монотонное планирование по частоте. Приоритет назначается обратно пропорционально периоду задачи: чем короче период, тем выше приоритет. Применяется в системах с периодическими задачами.

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

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

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

Недостатки

• Накладные расходы — каждое контекстное переключение требует времени на сохранение и восстановление состояния процесса. При слишком малом кванте времени система может тратить больше ресурсов на переключения, чем на полезную работу (эффект «дрожания»).
• Сложность реализации — необходимо корректно обрабатывать синхронизацию доступа к общим данным, чтобы избежать состояний гонки (race conditions) при вытеснении процесса в критической секции.
• Необходимость в планировщике реального времени — для жёстких систем реального времени требуется гарантировать, что все задачи будут выполнены до своих крайних сроков, что накладывает жёсткие требования на алгоритм планирования.
• Возможность инверсии приоритетов — ситуация, когда высокоприоритетный процесс ожидает ресурса, удерживаемого низкоприоритетным процессом, который в свою очередь вытесняется среднеприоритетным. Для решения этой проблемы применяются протоколы наследования приоритетов (priority inheritance) или потолка приоритетов (priority ceiling protocol).

Применение

Операционные системы общего назначения

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

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

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

• Авионика — системы управления полётом (FADEC), автопилоты.
• Медицинское оборудование — аппараты ИВЛ, инфузионные насосы.
• Промышленная автоматика — контроллеры (PLC) на базе ОСРВ (например, VxWorks, QNX, RTEMS).
• Автомобильная электроника — системы управления двигателем (ECU), антиблокировочная система (ABS).

В таких системах часто используется комбинация алгоритмов: для периодических задач — RMS или EDF, для апериодических — планирование на основе приоритетов.

Многопроцессорные и многоядерные системы

Вытесняющее планирование в многопроцессорных системах усложняется необходимостью балансировки нагрузки между ядрами и миграции процессов. Современные планировщики (например, в Linux — CFS с поддержкой SMP) используют механизмы, такие как «pull» и «push» миграция, чтобы равномерно распределять процессы по ядрам, избегая перегрузки одних и простоя других.

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

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

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

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

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

• В ранних версиях Windows (до Windows 95) использовалось кооперативное планирование для 16-битных приложений, что приводило к частым зависаниям системы при зависании одного приложения. Переход на вытесняющее планирование в Windows NT и последующих версиях значительно повысил стабильность.
• В ядре Linux версии 2.6 (2003 год) был внедрён O(1)-планировщик, который гарантировал постоянное время выбора процесса независимо от их количества. Позднее он был заменён на CFS (Completely Fair Scheduler) в версии 2.6.23 (2007 год).
• В системах реального времени на базе VxWorks используется алгоритм «priority preemption» с поддержкой до 256 уровней приоритетов, что позволяет точно настраивать поведение системы под конкретные задачи.

Источники

• Таненбаум Э., Бос Х. «Современные операционные системы» (4-е издание). — СПб.: Питер, 2015.
• Сильбершац А., Гэлвин П., Ганье Г. «Операционные системы: внутренняя структура и принципы проектирования» (9-е издание). — М.: Вильямс, 2018.
• Лю Дж. «Основы систем реального времени». — М.: Бином. Лаборатория знаний, 2008.
• Документация ядра Linux: «CFS Scheduler» (kernel.org/doc/Documentation/scheduler/sched-design-CFS.txt).
• Документация Microsoft: «Scheduling, Threads, and Fibers» (docs.microsoft.com).