Планировщик

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

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

Понятие планирования возникло задолго до появления компьютеров — в управлении проектами, военном деле и промышленности. Однако современное значение термин приобрёл с развитием вычислительной техники в середине XX века.

Ранние этапы (1940–1960-е годы)

Первые компьютеры работали в пакетном режиме: программы выполнялись последовательно, одна за другой, без вмешательства пользователя. Планировщика как отдельного компонента не существовало — задачи ставились в очередь оператором вручную. С появлением мультипрограммирования (способность системы одновременно держать в памяти несколько программ) возникла необходимость в алгоритме, решающем, какую задачу выполнять следующей. Первые планировщики (например, в системе CTSS, созданной в Массачусетском технологическом институте в 1961 году) использовали простые очереди с циклическим перебором (Round Robin).

Эра многозадачности (1970–1980-е годы)

С развитием операционных систем UNIX и её планировщика (алгоритм с приоритетами и динамическим пересчётом квантов времени) планировщики стали сложнее. В 1970-х годах появились системы реального времени (RTOS), где планировщик должен гарантировать выполнение критичных задач за строго определённое время. В этот же период разработаны алгоритмы «кратчайшая задача следующая» (SJF) и «гарантированное планирование».

Современный этап (1990-е — настоящее время)

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

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

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

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

• Планировщики операционных систем — управляют выполнением процессов и потоков. Делятся на планировщики длительного планирования (выбор, какие процессы загрузить в память), среднесрочного (свопинг) и краткосрочного (выбор, какой процесс получит CPU).
• Планировщики задач (Task Scheduler) — компоненты ОС или приложений для автоматического запуска программ по расписанию (например, cron в UNIX, Планировщик заданий в Windows).
• Планировщики проектов — инструменты для управления сроками, ресурсами и зависимостями (Microsoft Project, Jira, Trello).
• Планировщики производства — системы MES (Manufacturing Execution Systems) и APS (Advanced Planning and Scheduling), оптимизирующие загрузку оборудования и очереди заказов.
• Планировщики сети — управляют очередями пакетов в маршрутизаторах и коммутаторах (алгоритмы FIFO, WFQ, RED).
• Планировщики баз данных — оптимизируют порядок выполнения запросов (например, планировщик запросов в PostgreSQL).

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

• Вытесняющие (Preemptive) — планировщик может прервать выполняющуюся задачу и передать CPU другой задаче. Используется в большинстве современных ОС для обеспечения отзывчивости.
• Невытесняющие (Non-preemptive) — задача выполняется до завершения или добровольной передачи управления. Применяется в простых встраиваемых системах.

По алгоритму

• FIFO (First In, First Out) — задачи выполняются в порядке поступления.
• Round Robin — каждой задаче выделяется фиксированный квант времени, после чего управление передаётся следующей.
• Приоритетное планирование — задачи с более высоким приоритетом получают CPU раньше.
• Многоуровневые очереди — задачи группируются по приоритетам, каждая группа обслуживается по своему алгоритму.
• Гарантированное планирование — для систем реального времени (Rate Monotonic, Earliest Deadline First).

Устройство и характеристики

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

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

Основные характеристики, по которым оценивается планировщик:

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

Применение

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

Планировщик ОС — критически важный компонент, определяющий производительность системы. В ядре Linux (начиная с версии 2.6.23) используется алгоритм CFS (Completely Fair Scheduler), который стремится предоставить каждому процессу «справедливую» долю процессорного времени, моделируя «идеальное мультизадачное устройство». В Windows (начиная с NT) применяется вытесняющий планировщик с приоритетами (32 уровня), поддерживающий многопроцессорные системы и группы процессоров (NUMA).

В облачных и распределённых системах

Планировщики в системах контейнеризации (например, Kubernetes) распределяют контейнеры по узлам кластера, учитывая доступные ресурсы (CPU, память, диски), ограничения (affinity/anti-affinity) и политики восстановления. Планировщики Hadoop и Spark оптимизируют выполнение MapReduce-задач, минимизируя перемещение данных.

В реальном времени

В системах управления (авионика, медицинское оборудование, промышленные контроллеры) используются планировщики с гарантированным временем отклика. Например, алгоритм Rate Monotonic Scheduling (RMS) назначает фиксированные приоритеты на основе периода задачи: чем короче период, тем выше приоритет.

В логистике и производстве

Планировщики маршрутов (Vehicle Routing Problem) оптимизируют последовательность доставки товаров, учитывая время, затраты и загрузку транспорта. Планировщики производства (например, на основе теории ограничений Голдратта) строят расписание загрузки станков, минимизируя простои и время выполнения заказов.

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

• cron — утилита UNIX для запуска задач по расписанию (минуты, часы, дни месяца).
• Windows Task Scheduler — встроенный компонент Windows для автоматизации задач.
• CFS (Completely Fair Scheduler) — планировщик процессов в ядре Linux.
• Kubernetes Scheduler — компонент оркестратора контейнеров, распределяющий поды по узлам.
• Oozie — планировщик рабочих процессов в экосистеме Hadoop.
• Airflow — платформа для программного создания, планирования и мониторинга рабочих процессов (разработана в Airbnb, с открытым исходным кодом).

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

• Сложность настройки — современные планировщики ОС имеют множество параметров (приоритеты, кванты, группы), неправильная настройка может снизить производительность.
• Несправедливость в многопользовательских системах — при высокой нагрузке планировщик может отдавать предпочтение одним задачам в ущерб другим, что требует дополнительных механизмов (например, fair scheduling в Hadoop).
• Энергопотребление — в мобильных и встраиваемых системах планировщик должен балансировать между производительностью и энергосбережением, что не всегда удаётся оптимально.
• Проблемы реального времени — в общих ОС (Linux, Windows) планировщики не гарантируют жёсткого времени отклика, что ограничивает их применение в критических системах без специальных расширений (PREEMPT_RT для Linux).
• Планировщики проектов и задач — часто критикуются за избыточную функциональность, сложность интерфейса и неспособность адекватно моделировать неопределённость (например, человеческий фактор).

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

• Первый планировщик задач в современном понимании появился в операционной системе Multics (1960-е годы), которая впервые реализовала вытесняющую многозадачность.
• В ядре Linux планировщик CFS не использует фиксированные кванты времени — он моделирует «идеальный» мультизадачный процессор, делящий время пропорционально весу задач.
• Планировщик Windows (до версии 10) имел особенность: приоритет процессов мог динамически повышаться, если процесс долго не получал CPU (так называемый «boost»), что иногда приводило к неожиданным задержкам.
• В системах реального времени существует понятие «инверсии приоритетов» — когда низкоприоритетная задача блокирует ресурс, необходимый высокоприоритетной, что может нарушить временные гарантии. Для борьбы с этим применяются протоколы наследования приоритетов (Priority Inheritance Protocol).

Источники

• Таненбаум Э., Бос Х. «Современные операционные системы». 4-е издание. — СПб.: Питер, 2015.
• Silberschatz A., Galvin P.B., Gagne G. «Operating System Concepts». 10th Edition. — Wiley, 2018.
• Документация ядра Linux: «CFS Scheduler» (kernel.org).
• Документация Microsoft: «Windows Kernel — Scheduling, Thread Priorities».
• Burns A., Wellings A. «Real-Time Systems and Programming Languages». 4th Edition. — Addison-Wesley, 2009.
• Документация Kubernetes: «Kubernetes Scheduler» (kubernetes.io).
• Статья «Планировщик задач» в Большой российской энциклопедии.