Планировщик потоков¶

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

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

Первые операционные системы, такие как ранние версии UNIX (1970-е годы), использовали простые алгоритмы планирования, основанные на фиксированных приоритетах и временных квантах. В 1980-х годах с появлением многозадачных систем (например, Windows 3.0, OS/2) планировщики стали более сложными, внедряя вытесняющую многозадачность. В 1990-х годах, с развитием многопроцессорных систем, возникла необходимость в планировщиках, поддерживающих симметричную многопроцессорность (SMP). В 2000-х годах, с распространением многоядерных процессоров, планировщики стали учитывать топологию кэш-памяти и NUMA (неоднородный доступ к памяти). В современных ОС (Linux, Windows, macOS) планировщики постоянно совершенствуются, включая поддержку реального времени, энергоэффективности и виртуализации.

¶Классификация планировщиков

Планировщики потоков можно классифицировать по нескольким признакам.

¶По типу многозадачности

• Вытесняющая многозадачность (preemptive multitasking) — планировщик может принудительно прервать выполнение текущего потока по истечении его временного кванта или при поступлении более приоритетного потока. Используется в большинстве современных ОС (Windows, Linux, macOS).
• Кооперативная многозадачность (cooperative multitasking) — поток сам решает, когда уступить процессор, обычно при вызове системных функций или при завершении работы. Применялась в ранних версиях Windows (до Windows 95) и Mac OS (до Mac OS X).

¶По цели планирования

• Планировщики общего назначения — ориентированы на баланс между производительностью, отзывчивостью и справедливостью. Используются в настольных и серверных ОС.
• Планировщики реального времени — гарантируют выполнение потоков в строго определённые временные рамки. Делятся на жёсткое реальное время (hard real-time) и мягкое реальное время (soft real-time). Применяются в системах управления, робототехнике, авионике.
• Планировщики для встраиваемых систем — оптимизированы под ограниченные ресурсы (память, энергопотребление).

¶По способу распределения процессорного времени

• Циклические (Round Robin, RR) — каждому потоку выделяется фиксированный квант времени, после чего он перемещается в конец очереди готовых потоков.
• По приоритетам — потоки с более высоким приоритетом получают процессор раньше или чаще. Может быть статическим (приоритет задаётся один раз) или динамическим (приоритет меняется в зависимости от поведения потока).
• Смешанные — комбинируют несколько подходов, например, циклическое планирование с приоритетами (как в Linux Completely Fair Scheduler — CFS).

¶Устройство и принцип работы

Планировщик потоков состоит из нескольких ключевых компонентов:

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

¶Алгоритмы планирования

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

• First-Come, First-Served (FCFS) — первый пришедший поток выполняется первым. Прост, но может приводить к эффекту «конвоя», когда короткие потоки ждут длинных.
• Shortest Job First (SJF) — выбирается поток с наименьшим оставшимся временем выполнения. Оптимален по среднему времени ожидания, но требует знания времени выполнения, что часто невозможно.
• Priority Scheduling — потоки выполняются в порядке приоритета. Может приводить к голоданию низкоприоритетных потоков, что решается старением (повышением приоритета со временем).
• Multilevel Queue — потоки разделяются на несколько очередей по приоритетам, каждая очередь использует свой алгоритм (например, RR для интерактивных, FCFS для фоновых).
• Multilevel Feedback Queue — потоки могут перемещаться между очередями в зависимости от их поведения (например, если поток использует весь квант, его приоритет понижается).

¶Применение в различных операционных системах

¶Linux

В ядре Linux используется планировщик Completely Fair Scheduler (CFS), введённый в версии 2.6.23 (2007 год). CFS основан на модели «виртуального времени»: каждому потоку выделяется доля процессорного времени, пропорциональная его весу (приоритету). Потоки хранятся в красно-чёрном дереве, отсортированном по времени выполнения. CFS не использует фиксированные кванты; вместо этого он стремится к идеальной многозадачности, где каждый поток получает равную долю времени. Для потоков реального времени применяются отдельные классы планирования (SCHED_FIFO, SCHED_RR, SCHED_DEADLINE).

¶Windows

В Windows (начиная с Windows NT) используется планировщик с вытесняющей многозадачностью и динамическими приоритетами. Потоки делятся на 32 уровня приоритета (от 0 до 31), где 0 — самый низкий, 31 — самый высокий. Планировщик использует циклический алгоритм внутри каждого уровня приоритета с квантом времени, который может варьироваться в зависимости от версии ОС и настроек. Приоритеты могут динамически повышаться для интерактивных потоков (например, при нажатии клавиши) и понижаться для фоновых. В Windows 10 и 11 также реализована поддержка NUMA и энергоэффективного планирования (например, для процессоров Intel с технологией Speed Shift).

¶macOS

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

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

Планировщики потоков сталкиваются с рядом проблем:

• Голодание (starvation) — низкоприоритетные потоки могут никогда не получить процессорное время, если постоянно поступают высокоприоритетные. Решается старением или использованием справедливых алгоритмов.
• Инверсия приоритетов — высокоприоритетный поток может быть заблокирован низкоприоритетным, если последний удерживает ресурс. Для предотвращения применяются протоколы наследования приоритетов (priority inheritance).
• Накладные расходы — частое переключение контекста увеличивает накладные расходы (сохранение/восстановление состояния, сброс кэша). Оптимальный квант времени — компромисс между отзывчивостью и производительностью.
• Масштабируемость — на многопроцессорных системах планировщик должен эффективно распределять потоки между ядрами, минимизируя конкуренцию за общие ресурсы (кэш, шины памяти). Используются алгоритмы балансировки нагрузки (load balancing).

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

• В Linux CFS был разработан венгерским программистом Инго Мольнаром (Ingo Molnár) и заменил предыдущий планировщик O(1), который имел проблемы с интерактивностью.
• В Windows NT планировщик изначально использовал 32 уровня приоритета, но в Windows 2000 их число было сокращено до 16 для пользовательских потоков (остальные зарезервированы для системы).
• В macOS планировщик может мигрировать потоки между ядрами не только для балансировки, но и для экономии энергии: при низкой нагрузке потоки концентрируются на одном ядре, позволяя другим перейти в спящий режим.
• Планировщики реального времени в ОС общего назначения (например, Linux с патчами PREEMPT_RT) используются в промышленных контроллерах, медицинском оборудовании и автомобильных системах.

¶Источники

• Таненбаум Э., Бос Х. «Современные операционные системы» (4-е издание), 2015.
• Сильбершац А., Гэлвин П., Гэгн Г. «Операционные системы: концепции и проектирование» (9-е издание), 2014.
• Документация ядра Linux: «CFS Scheduler» (kernel.org).
• Microsoft Docs: «Windows Scheduling» (docs.microsoft.com).
• Apple Developer Documentation: «Scheduling and Thread Priorities» (developer.apple.com).