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

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

Основные принципы

При невытесняющем планировании планировщик операционной системы назначает задачу на выполнение, после чего она работает без прерываний до тех пор, пока не произойдёт одно из следующих событий:

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

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

История

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

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

Классификация алгоритмов

Невытесняющие алгоритмы планирования можно разделить на несколько основных типов:

First-Come, First-Served (FCFS)

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

Shortest Job First (SJF) — невытесняющая версия

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

Priority Scheduling — невытесняющая версия

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

Round Robin — невытесняющая модификация

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

Применение

Невытесняющее планирование используется в следующих областях:

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

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

Встроенные системы

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

Пакетные системы

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

Операционные системы с кооперативной многозадачностью

Исторические примеры: Windows 3.x (до Windows 95) и классическая Mac OS (до Mac OS X) использовали кооперативную многозадачность, которая по сути является невытесняющим планированием. В современных системах этот подход редко применяется в полной мере, но может использоваться в некоторых пользовательских пространствах (например, в библиотеках для сопрограмм).

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

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

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

Недостатки

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

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

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

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

• Сопрограммы в Python (asyncio) работают в кооперативном режиме: корутина выполняется до тех пор, пока не встретит await, после чего управление возвращается циклу событий.
• Go-рутины в языке Go изначально используют вытесняющее планирование, но в некоторых реализациях (например, в ранних версиях) применялся невытесняющий подход.
• Операционная система FreeRTOS поддерживает как вытесняющий, так и кооперативный (невытесняющий) режимы планирования, что позволяет разработчику выбирать подходящий вариант для встроенных систем.

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

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

Источники

• Таненбаум Э., Бос Х. «Современные операционные системы». 4-е издание. — СПб.: Питер, 2015.
• Сильбершац А., Гэлвин П., Гэгн Г. «Операционные системы: внутренняя структура и принципы проектирования». 9-е издание. — М.: Вильямс, 2016.
• Stallings W. «Operating Systems: Internals and Design Principles». 9th Edition. — Pearson, 2017.
• Liu J. W. S. «Real-Time Systems». — Prentice Hall, 2000.