Алгоритм планирования задач

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

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

Первые алгоритмы планирования появились в 1950-х — 1960-х годах вместе с первыми операционными системами. В ранних пакетных системах (например, IBM OS/360) использовались простые очереди с последовательным выполнением задач (First-Come, First-Served). С развитием мультипрограммирования и появлением интерактивных систем (Multics, Unix) возникла потребность в более сложных алгоритмах, способных обрабатывать множество пользователей одновременно. В 1970-х годах были предложены алгоритмы с приоритетами и вытесняющим планированием (round-robin). В 1980-х — 1990-х годах, с распространением многопроцессорных систем и реального времени, появились алгоритмы, учитывающие временные ограничения (rate-monotonic scheduling, earliest deadline first). Современные ОС, такие как Linux, Windows и macOS, используют гибридные алгоритмы, адаптирующиеся к текущей нагрузке.

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

Алгоритмы планирования делятся на несколько категорий в зависимости от принципов работы и целей.

По способу принятия решений

• Вытесняющие (preemptive): ОС может прервать выполнение текущей задачи в любой момент, чтобы передать процессор другой задаче. Это обеспечивает более равномерное распределение времени, но требует дополнительных затрат на переключение контекста. Примеры: Round-Robin, Priority Scheduling с вытеснением.
• Невытесняющие (non-preemptive): Задача выполняется до завершения или до добровольной уступки процессора (например, при ожидании ввода-вывода). Проще в реализации, но может приводить к задержкам для других задач. Примеры: First-Come, First-Served, Shortest Job Next (без вытеснения).

По целям использования

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

По способу назначения приоритетов

• Статические: Приоритет задачи фиксирован и не меняется во время выполнения. Просты, но могут приводить к «голоданию» низкоприоритетных задач.
• Динамические: Приоритет может изменяться в зависимости от времени ожидания, загрузки системы или других факторов. Более гибкие, но сложнее в реализации.

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

First-Come, First-Served (FCFS)

Простейший невытесняющий алгоритм, при котором задачи выполняются в порядке поступления в очередь. Реализуется с помощью FIFO (First In, First Out). Достоинства: простота, отсутствие «голодания». Недостатки: «эффект конвоя» — короткая задача может долго ждать выполнения длинной, что увеличивает среднее время ожидания.

Shortest Job Next (SJN) / Shortest Job First (SJF)

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

Round-Robin (RR)

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

Priority Scheduling

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

Multilevel Queue (MLQ)

Очередь задач делится на несколько уровней, каждый со своим алгоритмом планирования (например, верхний уровень — Round-Robin для интерактивных задач, нижний — FCFS для фоновых). Задачи распределяются по уровням в зависимости от типа. Недостаток: невозможность перемещения между уровнями, что может приводить к неэффективности.

Multilevel Feedback Queue (MLFQ)

Развитие MLQ: задачи могут перемещаться между уровнями в зависимости от их поведения. Например, задача, часто использующая процессор (CPU-bound), может быть понижена в приоритете, а задача, часто ожидающая ввода-вывода (I/O-bound), — повышена. Используется в большинстве современных ОС (например, в планировщике Linux CFS — Completely Fair Scheduler).

Earliest Deadline First (EDF)

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

Rate-Monotonic Scheduling (RMS)

Статический алгоритм для периодических задач реального времени: приоритет назначается обратно пропорционально периоду задачи (чем больше частота, тем выше приоритет). Гарантирует выполнение всех задач, если сумма их загрузок не превышает определённого порога (теорема Лью и Лейланда).

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

В современных ОС алгоритмы планирования реализованы в виде компонента ядра — планировщика (scheduler). В Linux используется Completely Fair Scheduler (CFS), основанный на модели виртуального времени: каждая задача получает пропорциональную долю процессорного времени, а приоритеты определяются на основе «виртуального времени выполнения». В Windows применяется гибридный планировщик с приоритетами (32 уровня), основанный на Round-Robin с динамическим изменением приоритета для интерактивных задач. В macOS используется планировщик на основе MLFQ с поддержкой многопроцессорности и энергоэффективности.

Критерии эффективности

Эффективность алгоритма планирования оценивается по нескольким метрикам:

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

Ни один алгоритм не может одновременно оптимизировать все критерии; выбор зависит от требований конкретной системы.

Проблемы и ограничения

• «Голодание» (starvation): низкоприоритетные задачи могут никогда не получить процессор, если постоянно поступают более приоритетные.
• Инверсия приоритетов: высокоприоритетная задача блокируется в ожидании ресурса, удерживаемого низкоприоритетной задачей, что может приводить к сбоям в системах реального времени.
• Переключение контекста: частое переключение между задачами увеличивает накладные расходы (сохранение/восстановление состояния), снижая общую производительность.
• Сложность реализации: некоторые алгоритмы (MLFQ, EDF) требуют значительных вычислительных ресурсов для принятия решений, что может быть критично во встраиваемых системах.

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

• В ранних версиях ОС Unix планировщик был основан на простом Round-Robin с приоритетами, что приводило к «голоданию» фоновых процессов. В BSD Unix была введена система динамических приоритетов.
• Планировщик CFS в Linux был представлен в версии 2.6.23 (2007 год) и заменил предыдущий планировщик O(1). Его название — «полностью справедливый планировщик» — отражает стремление к равномерному распределению времени.
• В системах реального времени, таких как авионика (стандарт ARINC 653), используется планирование с фиксированными временными окнами (time partitioning), чтобы гарантировать изоляцию задач.
• В операционной системе RTEMS (Real-Time Executive for Multiprocessor Systems) применяется алгоритм RMS для управления периодическими задачами в космических аппаратах.

Источники

• Таненбаум Э., Бос Х. «Современные операционные системы» (4-е издание). — СПб.: Питер, 2015.
• Silberschatz A., Galvin P.B., Gagne G. «Operating System Concepts» (10th edition). — Wiley, 2018.
• Love R. «Linux Kernel Development» (3rd edition). — Addison-Wesley, 2010.
• Liu C.L., Layland J.W. «Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment» // Journal of the ACM, 1973.
• Документация ядра Linux: «CFS — Completely Fair Scheduler» (kernel.org/doc).