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

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

¶История

Концепция вытесняющего планирования возникла в 1960-х годах с развитием многозадачных операционных систем, таких как CTSS (Compatible Time-Sharing System) и MULTICS. Ранние системы, например, ранние версии UNIX, использовали невытесняющее планирование, что приводило к неэффективному использованию процессора при выполнении длительных задач. В 1970-х годах с появлением систем разделения времени и интерактивных интерфейсов вытесняющие алгоритмы стали стандартом. В 1980-х годах, с развитием микропроцессоров и операционных систем реального времени (RTOS), таких как VxWorks и QNX, вытесняющее планирование стало обязательным для обеспечения детерминизма. В современных операционных системах, включая Linux, Windows и macOS, вытесняющие алгоритмы используются в ядре для управления потоками и процессами.

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

Вытесняющий алгоритм основан на механизме прерываний. Операционная система устанавливает таймер (квант времени) или использует события (например, завершение ввода-вывода) для генерации прерывания. При возникновении прерывания планировщик (scheduler) оценивает состояние всех процессов в очереди готовности и выбирает процесс с наивысшим приоритетом или наибольшей необходимостью. Текущий процесс сохраняет свой контекст (регистры, счётчик команд, стек) в структуре данных (PCB — Process Control Block), после чего загружается контекст нового процесса. Этот процесс называется переключением контекста (context switch) и связан с накладными расходами, которые могут снижать производительность системы.

¶Ключевые компоненты

• Планировщик (scheduler) — компонент ядра, отвечающий за выбор следующего процесса для выполнения.
• Диспетчер (dispatcher) — модуль, выполняющий переключение контекста и передачу управления выбранному процессу.
• Очередь готовности (ready queue) — структура данных, содержащая процессы, ожидающие процессор.
• Таймер прерываний (timer interrupt) — аппаратный или программный механизм, генерирующий прерывания через заданные интервалы времени.

¶Виды вытесняющих алгоритмов

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

¶На основе приоритета (Priority-based Preemptive Scheduling)

Каждому процессу присваивается числовой приоритет. Процесс с более высоким приоритетом вытесняет процесс с более низким. Приоритеты могут быть статическими (заданными при создании) или динамическими (изменяющимися во времени, например, для предотвращения голодания). Пример: алгоритм с фиксированными приоритетами, используемый в RTOS.

¶Циклическое планирование (Round Robin, RR)

Процессы получают фиксированный квант времени (обычно 10–100 миллисекунд). По истечении кванта процесс вытесняется и помещается в конец очереди готовности. RR обеспечивает равномерное распределение процессорного времени и подходит для интерактивных систем. Размер кванта критичен: слишком малый квант увеличивает накладные расходы на переключение, слишком большой — снижает интерактивность.

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

Процессы распределяются по нескольким очередям с разными приоритетами и квантами времени. Процесс может перемещаться между очередями в зависимости от поведения (например, если процесс использует весь квант, его приоритет понижается). MLFQ используется в ядре Linux (Completely Fair Scheduler, CFS) и Windows.

¶Планирование с наименьшим оставшимся временем (Shortest Remaining Time First, SRTF)

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

¶Планирование реального времени (Real-Time Scheduling)

Для систем с жёсткими временными ограничениями (deadline) используются алгоритмы, такие как Rate-Monotonic (RM) и Earliest Deadline First (EDF). RM назначает приоритеты обратно пропорционально периоду задачи, EDF — по ближайшему сроку завершения. Оба алгоритма гарантируют выполнение задач при соблюдении условий загрузки.

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

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

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

¶Недостатки

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

¶Применение

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

• Операционные системы общего назначения — Windows, Linux, macOS, FreeBSD. Например, в ядре Linux используется Completely Fair Scheduler (CFS), который реализует вытесняющее планирование на основе виртуального времени.
• Системы реального времени — авионика, медицинское оборудование, промышленные контроллеры. В RTOS, таких как FreeRTOS, VxWorks, QNX, используются вытесняющие алгоритмы с фиксированными приоритетами для обеспечения детерминизма.
• Встроенные системы — микроконтроллеры и устройства Интернета вещей (IoT), где вытесняющее планирование позволяет эффективно управлять ограниченными ресурсами.
• Облачные вычисления — гипервизоры (например, KVM, Xen) используют вытесняющее планирование для виртуальных машин, распределяя процессорное время между гостевыми ОС.

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

¶Linux (Completely Fair Scheduler, CFS)

CFS, введённый в ядре Linux 2.6.23, использует вытесняющее планирование на основе модели «виртуального времени». Каждому процессу назначается «виртуальное время выполнения» (vruntime), которое увеличивается пропорционально реальному времени, но с учётом приоритета (nice value). Планировщик выбирает процесс с наименьшим vruntime. Вытеснение происходит, когда vruntime текущего процесса превышает минимальное значение в очереди. CFS не использует фиксированные кванты, а динамически подстраивается под нагрузку.

¶Windows (Multilevel Feedback Queue)

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

¶FreeRTOS (Fixed Priority Preemptive Scheduling)

FreeRTOS, популярная RTOS для встраиваемых систем, реализует вытесняющее планирование с фиксированными приоритетами. Каждая задача имеет приоритет от 0 (самый низкий) до configMAX_PRIORITIES-1. Планировщик всегда выполняет задачу с наивысшим приоритетом, готовую к запуску. При появлении более высокоприоритетной задачи текущая вытесняется. FreeRTOS также поддерживает кооперативное планирование (невытесняющее) как опцию.

¶Критика и альтернативы

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

¶Источники

• Таненбаум Э., Бос Х. «Современные операционные системы». 4-е издание, 2015.
• Silberschatz A., Galvin P. B., Gagne G. «Operating System Concepts». 10th Edition, 2018.
• Love R. «Linux Kernel Development». 3rd Edition, 2010.
• Документация FreeRTOS: «FreeRTOS Reference Manual», 2023.
• Stallings W. «Operating Systems: Internals and Design Principles». 9th Edition, 2017.