Планировщик процессов

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

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

Ранние системы

В первых операционных системах (например, в пакетных системах 1950-х годов) планировщик отсутствовал как отдельный компонент. Задачи выполнялись последовательно, одна за другой, без прерываний. С появлением мультипрограммирования в 1960-х годах возникла необходимость в планировании, чтобы несколько программ могли одновременно находиться в памяти и поочерёдно использовать процессор.

Развитие алгоритмов

В 1970-х годах были разработаны первые алгоритмы планирования, такие как циклическое планирование (Round Robin) и планирование на основе приоритетов. В 1980-х годах, с появлением интерактивных систем (Unix, Windows), акцент сместился на минимизацию времени отклика. В 1990-х годах, с ростом многопроцессорных систем, возникли алгоритмы для симметричной многопроцессорной обработки (SMP). Современные планировщики (например, Completely Fair Scheduler в Linux) используют сложные эвристики для адаптации к изменяющейся нагрузке.

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

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

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

По типу системы

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

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

Вытесняющие и невытесняющие

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

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

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

Современные реализации

• Completely Fair Scheduler (CFS) — планировщик по умолчанию в ядре Linux (с версии 2.6.23). Моделирует «идеальный, справедливый процессор» и распределяет время пропорционально весу (приоритету) процессов. Использует красно-чёрное дерево для хранения очереди.
• Windows NT Scheduler — использует многоконтурную очередь с приоритетами (32 уровня). Приоритеты могут динамически повышаться для интерактивных процессов (например, при получении ввода с клавиатуры). Поддерживает привязку к ядрам процессора (CPU affinity).
• XNU Scheduler (macOS/iOS) — основан на гибридном подходе, сочетающем приоритеты и кванты времени. Поддерживает многопроцессорность и энергоэффективность.

Характеристики и метрики

Ключевые показатели

• Пропускная способность (throughput) — количество процессов, завершённых за единицу времени.
• Время ожидания (waiting time) — суммарное время, которое процесс провёл в очереди готовых к выполнению.
• Время отклика (response time) — время от отправки запроса до первого отклика системы (важно для интерактивных приложений).
• Время оборота (turnaround time) — полное время от момента поступления процесса до его завершения.
• Справедливость (fairness) — равномерность распределения процессорного времени между процессами с одинаковым приоритетом.

Компромиссы

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

Применение

В операционных системах общего назначения

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

В системах реального времени

• Жёсткое реальное время — используется в авионике, медицинском оборудовании, промышленных контроллерах. Планировщик гарантирует, что критичные задачи будут выполнены до дедлайна (алгоритмы Rate-Monotonic Scheduling, Earliest Deadline First).
• Мягкое реальное время — допускается пропуск дедлайнов, но с ухудшением качества (например, в мультимедийных приложениях).

В облачных и виртуальных средах

Гипервизоры (например, KVM, VMware) используют собственные планировщики для распределения ресурсов между виртуальными машинами. Учитываются приоритеты, гарантии производительности и изоляция.

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

• Сложность настройки — в многозадачных системах с разнородной нагрузкой (например, серверы баз данных + веб-серверы) оптимальные параметры планировщика могут сильно различаться.
• Энергопотребление — в мобильных и встраиваемых системах планировщик должен учитывать не только производительность, но и энергоэффективность (например, алгоритмы Dynamic Voltage and Frequency Scaling).
• Проблема голодания — при использовании приоритетов низкоприоритетные процессы могут никогда не получить процессорное время. Решается динамическим повышением приоритета (aging).
• Непредсказуемость в реальном времени — стандартные планировщики (например, CFS) не гарантируют соблюдения дедлайнов, что требует специализированных решений.

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

• В ядре Linux планировщик CFS использует виртуальное время (vruntime) для оценки «справедливости» — чем меньше vruntime у процесса, тем выше его приоритет.
• В Windows NT планировщик может временно повышать приоритет процесса, который получил ввод с клавиатуры или мыши, чтобы улучшить отзывчивость интерфейса.
• Первый алгоритм планирования для многозадачных систем был реализован в операционной системе CTSS (Compatible Time-Sharing System) в 1961 году в Массачусетском технологическом институте.

Источники

• Таненбаум Э., Бос Х. «Современные операционные системы» (4-е издание, 2015)
• Сильбершац А., Гэлвин П., Гэгн Г. «Операционные системы: внутренняя структура и принципы проектирования» (9-е издание, 2018)
• Документация ядра Linux: «CFS Scheduler» (kernel.org)
• Документация Microsoft: «Windows Kernel-Mode Scheduler» (Microsoft Docs)