Вытесняющая многозадачность

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

История

Концепция вытесняющей многозадачности возникла в 1960-х годах в рамках развития систем разделения времени. Одной из первых реализаций стала операционная система CTSS (Compatible Time-Sharing System), разработанная в Массачусетском технологическом институте. В ней использовался механизм прерываний, позволявший центральному процессору переключаться между несколькими пользовательскими сессиями.

Дальнейшее развитие принципов вытесняющей многозадачности связано с проектом Multics (1965—1969), где впервые была реализована вытесняющая модель на уровне ядра. Однако наибольшее распространение эта концепция получила в Unix-подобных системах, начиная с версий 1970-х годов. В 1980-х годах компания Microsoft внедрила вытесняющую многозадачность в операционную систему Windows NT (1993), а затем и в Windows 95 (для 32-битных приложений). В Linux вытесняющая многозадачность стала стандартной с версии 2.6 (2003).

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

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

1. Выделение кванта времени. Каждой задаче назначается фиксированный или динамический квант времени (обычно от нескольких миллисекунд до десятков миллисекунд). Пока задача выполняется, она использует процессор.
2. Прерывание. По истечении кванта или при возникновении внешнего события (например, запроса от устройства ввода-вывода) аппаратный таймер генерирует прерывание. Процессор сохраняет контекст текущей задачи (регистры, счётчик команд, состояние стека) и передаёт управление ядру.
3. Выбор новой задачи. Планировщик выбирает следующую задачу для выполнения на основе заданного алгоритма (например, циклический, приоритетный, справедливый). Новая задача получает процессор, и её контекст восстанавливается.
4. Переключение контекста. Операция переключения между задачами включает сохранение и восстановление состояния процессора. Время переключения контекста является накладным расходом и варьируется в зависимости от архитектуры системы.

Виды вытесняющей многозадачности

По типу планирования

• Циклическое планирование (Round-Robin). Каждой задаче выделяется равный квант времени. Применяется в системах с равноправными процессами.
• Приоритетное планирование. Задачи имеют приоритеты; задачи с более высоким приоритетом получают процессор раньше. Может быть статическим (приоритет задаётся один раз) или динамическим (приоритет изменяется в зависимости от поведения задачи).
• Справедливое планирование (Fair Scheduling). Планировщик стремится распределить процессорное время пропорционально весам или потребностям задач. Пример — алгоритм Completely Fair Scheduler (CFS) в Linux.
• Планирование реального времени. Для задач с жёсткими временными ограничениями используются алгоритмы Rate-Monotonic Scheduling (RMS) или Earliest Deadline First (EDF).

По уровню вытеснения

• Вытеснение на уровне процессов. Переключение происходит только между процессами (адресными пространствами). Потоки внутри одного процесса выполняются кооперативно.
• Вытеснение на уровне потоков. Переключение возможно между потоками одного процесса. Ядро управляет потоками как независимыми единицами планирования.
• Вытеснение ядра (Kernel Preemption). Позволяет прерывать выполнение системных вызовов и других операций ядра. Это повышает отзывчивость системы, но усложняет синхронизацию. В Linux вытеснение ядра стало возможным с версии 2.6.

Устройство и реализация

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

• Диспетчер прерываний — обрабатывает аппаратные и программные прерывания, инициируя переключение задач.
• Планировщик — содержит очереди готовых задач (ready queues) и алгоритм выбора следующей задачи.
• Механизмы синхронизации — семафоры, мьютексы, спин-блокировки, предотвращающие состояние гонки при доступе к общим данным.
• Управление контекстом — структура данных (PCB — Process Control Block), хранящая состояние задачи.

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

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

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

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

Недостатки

• Накладные расходы. Переключение контекста требует времени и ресурсов, особенно при высокой частоте переключений.
• Сложность синхронизации. Необходимость защиты общих данных от одновременного доступа увеличивает риск взаимных блокировок (deadlocks) и состояний гонки (race conditions).
• Проблемы с кэшем. Частое переключение задач приводит к промахам кэша (cache misses), снижая производительность.
• Неопределённость времени выполнения. В системах без жёсткого реального времени время выполнения задачи может варьироваться из-за вытеснений.

Применение

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

• Операционные системы общего назначения: Windows, Linux, macOS, BSD-системы.
• Системы реального времени: VxWorks, QNX, FreeRTOS (с поддержкой вытеснения), RT-Linux.
• Встраиваемые системы: автомобильные контроллеры, промышленные роботы, медицинские устройства.
• Виртуализация: гипервизоры (например, KVM, VMware ESXi) используют вытеснение для распределения ресурсов между виртуальными машинами.
• Мобильные платформы: Android (на базе Linux), iOS (на базе XNU).

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

Критика

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

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

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

• В операционной системе Linux планировщик CFS (Completely Fair Scheduler), введённый в версии 2.6.23, использует модель «виртуального времени», где каждая задача получает процессор пропорционально своему весу.
• В Windows NT планировщик использует 32 уровня приоритета (0—31), где 0 зарезервирован для нулевой страницы, а 16—31 — для потоков реального времени.
• В системах с вытесняющей многозадачностью существует понятие «инверсии приоритетов» (priority inversion), когда низкоприоритетная задача блокирует высокоприоритетную через общий ресурс. Для решения этой проблемы применяются протоколы наследования приоритетов (priority inheritance).

Источники

• Таненбаум Э., Бос Х. «Современные операционные системы» (4-е издание). — СПб.: Питер, 2015.
• Silberschatz A., Galvin P. B., Gagne G. «Operating System Concepts» (10th edition). — Wiley, 2018.
• Love R. «Linux Kernel Development» (3rd edition). — Addison-Wesley, 2010.
• Stallings W. «Operating Systems: Internals and Design Principles» (9th edition). — Pearson, 2017.
• Документация ядра Linux (kernel.org) — раздел «Scheduler».