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

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

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

Концепция невытесняющих алгоритмов восходит к ранним операционным системам 1950–1960-х годов, когда вычислительные машины работали в пакетном режиме. В системах, таких как IBM OS/360, задачи выполнялись последовательно, без возможности прерывания, что упрощало аппаратную реализацию и снижало накладные расходы на переключение контекста. С развитием многозадачности в 1970-х годах (например, в UNIX) стали применяться вытесняющие алгоритмы, однако невытесняющие методы сохранились в специализированных областях, включая встраиваемые системы и реальное время.

В 1980-х годах невытесняющие алгоритмы активно использовались в операционных системах для микроконтроллеров, где ресурсы были ограничены, а предсказуемость времени выполнения критична. В XXI веке, с ростом популярности многопоточных приложений, невытесняющие подходы применяются в некоторых языках программирования (например, в Python с Global Interpreter Lock) и в системах с кооперативной многозадачностью, таких как ранние версии Windows (до Windows 95) и Mac OS (до Mac OS X).

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

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

¶По принципу выбора

• First-Come, First-Served (FCFS) — задачи выполняются в порядке поступления. Простейший алгоритм, не требующий приоритетов.
• Shortest Job Next (SJN) — выбирается задача с наименьшим ожидаемым временем выполнения. Требует априорного знания длительности задач.
• Priority-based (без вытеснения) — задачи с более высоким приоритетом выполняются раньше, но без прерывания текущей задачи. Приоритет может быть статическим или динамическим.
• Round Robin (невытесняющий) — задачи получают процессор по очереди, но без прерывания; каждая задача выполняется до завершения или до добровольной уступки.

¶По области применения

• Кооперативная многозадачность — задачи явно передают управление (например, через вызов yield). Используется в пользовательских потоках (green threads) и некоторых языках программирования.
• Пакетная обработка — задачи выполняются последовательно без взаимодействия с пользователем. Характерно для мейнфреймов и серверов.
• Встраиваемые системы реального времени — невытесняющие алгоритмы применяются в системах с жёсткими ограничениями по времени, где предсказуемость важнее гибкости.

¶Характеристики и особенности

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

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

¶Недостатки

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

¶Применение

¶Операционные системы

• MS-DOS — однозадачная система, где программы выполнялись без вытеснения.
• Windows 3.x — кооперативная многозадачность, где приложения должны были добровольно передавать управление.
• Mac OS 9 и ранее — использовали кооперативную многозадачность для приложений.
• Linux — в некоторых конфигурациях ядра (например, CONFIG_PREEMPT_NONE) для серверов с низкой нагрузкой.

¶Встраиваемые системы

• Микроконтроллеры — в системах с ограниченной памятью (например, на базе ARM Cortex-M) невытесняющие планировщики, такие как FreeRTOS, используются для задач с фиксированным временем выполнения.
• Автомобильные системы — в контроллерах двигателя и ABS, где предсказуемость критична.
• Промышленные контроллеры — в PLC (программируемые логические контроллеры) для управления оборудованием.

¶Языки программирования

• Python — Global Interpreter Lock (GIL) делает потоки невытесняемыми на уровне интерпретатора, что упрощает управление памятью.
• JavaScript (Node.js) — однопоточная модель с кооперативной многозадачностью через цикл событий.
• Go — горутины используют кооперативное планирование, но с возможностью вытеснения на уровне рантайма.

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

¶Алгоритм FCFS

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

¶Кооперативная многозадачность в Python

```python import threading

def task(): for i in range(5): print("Task running")

¶Добровольная передача управления

threading._sleep(0)

thread = threading.Thread(target=task) thread.start() ```

¶Встраиваемая система на FreeRTOS

``c void vTaskFunction(void *pvParameters) { for (;;) { // Выполнение задачи vTaskDelay(100); // Переход в состояние ожидания } } ``

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

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

Основной недостаток — риск блокировки системы из-за ошибок в прикладном ПО. В кооперативных системах, таких как Mac OS 9, зависание одного приложения могло привести к краху всей системы. Современные реализации (например, в Go) решают эту проблему за счёт встроенных механизмов тайм-аутов и мониторинга.

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

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

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

¶Источники

• Таненбаум Э., Бос Х. «Современные операционные системы». 4-е изд. — СПб.: Питер, 2015.
• Silberschatz A., Galvin P. B., Gagne G. «Operating System Concepts». 10th ed. — Wiley, 2018.
• Stallings W. «Operating Systems: Internals and Design Principles». 9th ed. — Pearson, 2017.
• Документация FreeRTOS: «Task Scheduling and Priority».
• «Non-Preemptive Scheduling» — статья в Encyclopedia of Computer Science.