Планировщик задач CPU

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

История

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

В первых однозадачных операционных системах (например, MS-DOS) планировщик как таковой отсутствовал: программа получала полный контроль над процессором до своего завершения или вызова системного прерывания. С появлением многозадачности в 1960-х годах (системы CTSS, MULTICS) возникла необходимость в программном переключении контекста.

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

В 1970-х годах в UNIX был реализован алгоритм циклического планирования (Round Robin) с динамическими приоритетами. В 1980-х годах в системах реального времени (VxWorks, QNX) появились жёсткие приоритетные планировщики. С распространением многопроцессорных систем в 1990-х годах (Windows NT, Linux) возникли алгоритмы балансировки нагрузки между ядрами. Современные планировщики (например, CFS в Linux, планировщик Windows NT) используют сложные модели на основе виртуального времени и энергоэффективности.

Основные функции

Планировщик выполняет следующие задачи:

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

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

По способу выбора процесса

• Вытесняющие (preemptive) — планировщик может прервать выполняющийся процесс по таймеру или по событию (например, Round Robin, приоритетное планирование с вытеснением).
• Невытесняющие (non-preemptive) — процесс удерживает процессор до завершения или добровольной блокировки (например, FCFS, SJF без вытеснения).

По критериям оптимизации

• Пакетные системы — максимизация пропускной способности (например, FCFS, SJF).
• Интерактивные системы — минимизация времени отклика (например, Round Robin, многоуровневые очереди).
• Системы реального времени — гарантированное соблюдение временных ограничений (например, Rate-Monotonic Scheduling, EDF).

По типу очередей

• Одноуровневые — все процессы в одной очереди (Round Robin).
• Многоуровневые — процессы разделены по приоритетам или типам (например, многоуровневые очереди с обратной связью в Windows).

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

First-Come, First-Served (FCFS)

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

Shortest Job First (SJF)

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

Round Robin (RR)

Вытесняющий алгоритм с фиксированным квантом времени (обычно 10–100 мс). Процессы выполняются по кругу; при исчерпании кванта управление передаётся следующему. Обеспечивает быстрый отклик в интерактивных системах, но при малом кванте увеличиваются накладные расходы на переключение контекста.

Приоритетное планирование

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

Многоуровневые очереди с обратной связью (MLFQ)

Процессы распределяются по нескольким очередям с разными приоритетами и квантами. Новый процесс попадает в очередь с наивысшим приоритетом; если не завершается за квант, перемещается в очередь ниже. Алгоритм адаптируется к поведению процессов (интерактивные — короткие, фоновые — длинные). Используется в современных ОС (Windows, Linux).

Планирование реального времени

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

Реализации в современных ОС

Linux

В ядре Linux используется планировщик Completely Fair Scheduler (CFS), внедрённый в версии 2.6.23 (2007 год). CFS моделирует «идеальный мультизадачный процессор», распределяя процессорное время пропорционально весам процессов. Вместо квантов используется виртуальное время (vruntime). Для многопроцессорных систем применяется алгоритм балансировки нагрузки на основе групп (scheduling domains). В версии 6.0 (2022) добавлена поддержка планирования для гибридных архитектур (big.LITTLE).

Windows

В Windows NT (начиная с версии 3.1) используется вытесняющий планировщик с 32 уровнями приоритетов (0–31). Приоритеты делятся на классы: реального времени (16–31), переменные (1–15) и системный (0). Для интерактивных процессов применяется динамическое повышение приоритета (boost). Планировщик Windows поддерживает многопроцессорные системы с помощью групп процессоров (processor groups) и NUMA-узлов.

macOS и iOS

В XNU (ядро macOS) используется планировщик на основе многоуровневых очередей с обратной связью, дополненный механизмом Quality of Service (QoS). Приоритеты процессов зависят от их назначения (пользовательский интерфейс, фоновая задача, энергосбережение). В iOS планировщик оптимизирован для мобильных устройств с учётом энергопотребления.

Проблемы и критика

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

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

• В ранних версиях UNIX (1970-е) планировщик использовал приоритеты, вычисляемые на основе использования процессора и времени ожидания, что позволяло избегать голодания.
• В Linux CFS вместо фиксированного кванта использует «целевой латентный период» (targeted latency), который автоматически увеличивается при большом числе процессов.
• В Windows существует механизм «мягкого реального времени» для мультимедийных приложений, повышающий приоритет потоков, обрабатывающих звук и видео.
• В суперкомпьютерах часто применяются специализированные планировщики (например, Slurm, PBS), работающие на уровне заданий, а не отдельных процессов.

Источники

• Таненбаум Э., Бос Х. Современные операционные системы. 4-е изд. — СПб.: Питер, 2015.
• Silberschatz A., Galvin P. B., Gagne G. Operating System Concepts. 10th ed. — Wiley, 2018.
• Love R. Linux Kernel Development. 3rd ed. — Addison-Wesley, 2010.
• Russinovich M., Solomon D., Ionescu A. Windows Internals, Part 1. 7th ed. — Microsoft Press, 2017.
• Документация ядра Linux: «CFS Scheduler» (kernel.org).