Планировщик операционной системы

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

История развития планировщиков

Ранние вычислительные системы

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

Появление многозадачности

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

Эра персональных компьютеров

В 1980-е годы, с выходом MS-DOS и ранних версий Windows, планировщики были кооперативными: процесс сам должен был добровольно уступать процессор. Это делало систему уязвимой к зависаниям. Перелом наступил с появлением Windows 95 и Linux (1991 год), которые внедрили вытесняющее планирование реального времени.

Современные подходы

В XXI веке планировщики эволюционировали для работы с многоядерными процессорами (SMP — симметричная многопроцессорность), гибридными архитектурами (big.LITTLE в ARM) и виртуализацией. Современные алгоритмы, такие как CFS (Completely Fair Scheduler) в Linux, ориентированы на энергоэффективность и минимальные задержки.

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

По способу переключения контекста

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

По приоритетности

• Статические приоритеты — приоритет процесса задаётся один раз при создании и не меняется. Простота реализации, но негибкость.
• Динамические приоритеты — приоритет может изменяться в зависимости от поведения процесса (например, повышаться для интерактивных задач). Используется в Windows (с 1993 года) и Linux.

По цели оптимизации

• Планирование реального времени (RT) — гарантирует выполнение задачи за строго определённое время. Делится на жёсткое (hard real-time — опоздание недопустимо) и мягкое (soft real-time — опоздания допустимы, но снижают качество). Примеры: VxWorks, QNX, RT-Linux.
• Планирование общего назначения — стремится к балансу между пропускной способностью, временем отклика и справедливостью. Примеры: CFS (Linux), планировщик Windows NT.

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

First-Come, First-Served (FCFS)

Простейший алгоритм — первый пришедший процесс получает процессор первым и работает до завершения. Недостаток: эффект «конвоя» — короткие задачи ждут длинных. Реализован в пакетных системах 1960-х годов.

Shortest Job First (SJF)

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

Round Robin (RR)

Каждому процессу выделяется фиксированный квант времени (обычно 10–100 мс). После его истечения процесс перемещается в конец очереди. Базовая реализация — циклическая очередь. Применяется в ядре Linux для задач реального времени (SCHED_RR).

Priority Scheduling

Процессы получают приоритеты; планировщик всегда выбирает процесс с наивысшим приоритетом. Для предотвращения «голодания» низкоприоритетных задач используется старение (aging) — постепенное повышение приоритета ожидающих процессов. Реализован в Windows (32 уровня приоритета) и Linux (140 уровней).

Completely Fair Scheduler (CFS)

Алгоритм, принятый в ядре Linux с версии 2.6.23 (2007 год). Вместо очередей использует красно-чёрное дерево, где каждый процесс представлен виртуальным временем выполнения. Планировщик выбирает процесс с минимальным виртуальным временем, обеспечивая почти идеальную справедливость. Поддерживает симметричную многопроцессорность и энергосбережение.

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

Процессы распределяются по нескольким очередям с разными приоритетами и квантами времени. Если процесс не завершается за квант, он понижается в очереди. Интерактивные процессы (короткие прерывания) остаются в верхних очередях, получая быстрый отклик. Реализован в Windows NT и macOS.

Устройство и компоненты планировщика

Диспетчер (dispatcher)

Модуль, непосредственно выполняющий переключение контекста: сохранение состояния текущего процесса (регистры, счётчик команд) и загрузка состояния нового. Время переключения контекста — критический параметр (обычно 1–10 микросекунд).

Очереди процессов

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

Таймер прерываний

Аппаратный таймер (например, Intel 8254 или HPET) генерирует прерывания через заданные интервалы (тики). Планировщик обрабатывает каждое прерывание, проверяя, не истёк ли квант времени текущего процесса. В современных ОС (Linux с ядром 3.x+) тики могут быть динамическими (tickless) для экономии энергии.

Планировочные политики

В каждой ОС реализован набор политик, определяющих поведение планировщика для разных типов задач:

• SCHED_OTHER (Linux) — стандартная политика для обычных процессов.
• SCHED_FIFO — политика реального времени с первой очередью.
• SCHED_RR — политика реального времени с циклическим переключением.
• Windows — классы приоритетов (Idle, Below Normal, Normal, Above Normal, High, Realtime).

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

Linux

Ядро Linux использует CFS как планировщик по умолчанию с 2007 года. Для задач реального времени доступны SCHED_FIFO и SCHED_RR. Поддерживается привязка процессов к конкретным ядрам (CPU affinity). Планировщик учитывает архитектуру NUMA (неравномерный доступ к памяти) для минимизации задержек доступа.

Windows

Планировщик Windows (начиная с Windows NT 3.1) основан на 32-уровневой приоритетной модели с динамическим повышением приоритета для интерактивных процессов (например, при нажатии клавиш). Используется вытесняющее планирование с квантом времени 20–120 мс (зависит от версии и конфигурации). Поддерживает гибридную архитектуру (Thread Scheduling).

macOS

Планировщик macOS (XNU) сочетает элементы Mach и BSD. Используется многоуровневая очередь с обратной связью (MLFQ) с 4 приоритетными уровнями. Особое внимание уделяется энергоэффективности на мобильных устройствах (MacBook, iPad). С 2020 года поддерживает планирование для архитектуры Apple Silicon (M1, M2).

Встраиваемые системы (RTOS)

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

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

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

Возникает, когда высокоприоритетный процесс ожидает ресурса, занятого низкоприоритетным, который, в свою очередь, вытесняется средним приоритетом. Решение — протоколы наследования приоритетов (Priority Inheritance Protocol), реализованные в VxWorks и Linux (RT-mutex).

Энергопотребление

Современные планировщики сталкиваются с дилеммой: высокая частота переключений контекста увеличивает отзывчивость, но повышает энергопотребление. В мобильных ОС (Android, iOS) применяются алгоритмы, снижающие частоту тиков таймера и объединяющие короткие простаивающие периоды (tickless idle).

Масштабирование на многоядерные системы

На системах с десятками ядер (например, AMD EPYC, Intel Xeon) планировщик должен минимизировать миграцию процессов между ядрами (cache thrashing) и учитывать топологию кэша. В Linux для этого используется группа планирования (scheduling domain) и алгоритм load balancing.

Виртуализация

В виртуальных средах (KVM, VMware, Hyper-V) планировщик гостевой ОС не имеет прямого доступа к аппаратному таймеру, что может приводить к временны́м искажениям. Для решения применяется паравиртуализация таймера и механизмы steal time (учёт времени, украденного гипервизором).

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

• Первый вытесняющий планировщик был реализован в операционной системе CTSS (1961 год) Массачусетского технологического института.
• В ядре Linux версии 2.4 (2001 год) использовался алгоритм O(n) — планировщик просматривал все процессы в очереди, что замедляло работу на многопроцессорных системах. С версии 2.5 (2003 год) был внедрён O(1) планировщик.
• Планировщик Windows XP (2001 год) имел ошибку, из-за которой процессы с приоритетом «Realtime» могли заблокировать мышь и клавиатуру — это было исправлено в Windows Vista.
• В 2010 году в ядро Linux был добавлен планировщик BFS (Brain Fuck Scheduler) как альтернатива CFS, ориентированный на десктопные системы с малым числом ядер.
• В операционной системе QNX (используется в автомобильной электронике и медицинском оборудовании) планировщик гарантирует время переключения контекста менее 1 микросекунды.

Источники

• Таненбаум Э., Бос Х. «Современные операционные системы» (4-е издание, 2015)
• Лав Р. «Ядро Linux. Описание процесса разработки» (3-е издание, 2010)
• Silberschatz A., Galvin P., Gagne G. «Operating System Concepts» (10th edition, 2018)
• Документация ядра Linux: «Documentation/scheduler/sched-design-CFS.txt»
• Microsoft Docs: «Windows Kernel-Mode Scheduler» (2023)
• Stallings W. «Operating Systems: Internals and Design Principles» (9th edition, 2017)