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

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

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

Первые операционные системы, работавшие в пакетном режиме (например, ранние версии OS/360), использовали простейшие дисциплины планирования: процессы выполнялись последовательно один за другим до полного завершения. С появлением систем с разделением времени (time-sharing) в 1960-х годах, таких как CTSS и Multics, возникла необходимость в более сложных алгоритмах, способных быстро переключаться между задачами для обеспечения интерактивности. В 1970-х годах разработчики UNIX внедрили алгоритм циклического планирования (Round Robin) с динамическими приоритетами, который стал стандартом де-факто для многих ОС. Современные системы, такие как Linux и Windows, используют гибридные схемы, сочетающие приоритетное планирование с вытесняющей многозадачностью и поддержкой множества ядер процессора.

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

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

По вытесняемости

• Невытесняющее (кооперативное) планирование: Процесс, получив управление, удерживает ЦП до тех пор, пока добровольно не освободит его (например, при завершении, ожидании ввода-вывода или явном вызове планировщика). Пример — ранние версии Windows (до Windows 95) и MS-DOS. Преимущество — простота реализации; недостаток — риск монополизации ресурсов одним процессом.
• Вытесняющее (превентивное) планирование: Операционная система может принудительно прервать выполнение текущего процесса (обычно по таймеру или при появлении более приоритетного процесса) и передать управление другому. Этот подход используется в большинстве современных ОС (Linux, Windows, macOS). Он обеспечивает более равномерное распределение времени и гарантирует отзывчивость системы.

По целям и критериям

Алгоритмы различаются по тому, какие метрики они оптимизируют:

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

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

First-Come, First-Served (FCFS) — «Первым пришёл — первым обслужен»

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

Shortest Job First (SJF) — «Кратчайшая работа первой»

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

Round Robin (RR) — «Циклическое планирование»

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

Priority Scheduling — «Планирование по приоритетам»

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

Multilevel Queue — «Многоуровневые очереди»

Процессы разделяются на несколько очередей по типу (например, интерактивные, фоновые, системные). Каждая очередь использует собственный алгоритм (например, RR для интерактивных, FCFS для фоновых). Очереди также имеют приоритеты: сначала обрабатываются процессы из очередей с более высоким приоритетом. Разновидность — Multilevel Feedback Queue (MLFQ), где процесс может перемещаться между очередями в зависимости от его поведения (например, если процесс использует весь квант, его понижают в приоритете). MLFQ является основой планирования в современных ОС общего назначения.

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

В системах с несколькими процессорами (или ядрами) планирование усложняется. Необходимо решать задачи:

• Балансировка нагрузки: равномерное распределение процессов между ядрами для избежания простоев одних и перегрузки других.
• Привязка к процессору (processor affinity): закрепление процесса за конкретным ядром для минимизации потерь на миграцию кэша.
• Планирование с учётом кэша: предпочтение отдаётся ядру, в кэше которого уже находятся данные процесса.

Используются алгоритмы, такие как глобальная очередь (один планировщик для всех ядер) и локальные очереди (отдельный планировщик на каждое ядро). В Linux используется Completely Fair Scheduler (CFS), основанный на концепции «виртуального времени» и красно-чёрных деревьях, что обеспечивает высокую масштабируемость и справедливость.

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

Для систем жёсткого реального времени (hard real-time), где нарушение сроков выполнения недопустимо (например, в автопилотах, медицинском оборудовании), применяются специализированные алгоритмы:

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

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

Критика и проблемы

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

Источники

• Таненбаум Э., Бос Х. «Современные операционные системы» (4-е издание, 2015).
• Сильбершац А., Гэлвин П., Гэгн Г. «Операционные системы: внутренняя структура и принципы проектирования» (9-е издание, 2018).
• Документация ядра Linux: «CFS Scheduler» (kernel.org).
• Stallings W. «Operating Systems: Internals and Design Principles» (9th edition, 2017).