Алгоритм планирования процессов¶

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

¶История

Первые операционные системы, такие как ранние пакетные системы, использовали простейшие алгоритмы планирования, например, «первым пришёл — первым обслужен» (FIFO). С развитием мультипрограммирования и появлением интерактивных систем в 1960-х годах возникла необходимость в более сложных подходах. В 1970-х годах были разработаны алгоритмы, учитывающие приоритеты и временные кванты, такие как циклическое планирование (Round Robin). В 1980-х годах для систем реального времени появились алгоритмы с фиксированными приоритетами (Rate-Monotonic Scheduling). Современные ОС, включая Linux, Windows и macOS, используют комбинации нескольких алгоритмов, адаптирующиеся к текущей нагрузке.

¶Цели планирования

Основные цели алгоритмов планирования включают:

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

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

Алгоритмы планирования процессов классифицируются по нескольким признакам.

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

• Вытесняющие (preemptive): ОС может прервать выполнение текущего процесса в любой момент, например, по истечении кванта времени или при появлении более приоритетного процесса. Примеры: Round Robin, приоритетное планирование с вытеснением.
• Невытесняющие (non-preemptive): процесс выполняется до тех пор, пока сам не освободит ЦП (завершится, перейдёт в состояние ожидания или выполнит системный вызов). Примеры: FIFO, кратчайшая задача первой (SJF) в невытесняющем варианте.

¶По очереди

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

¶По типу системы

• Для пакетных систем (пакетная обработка): FIFO, SJF.
• Для интерактивных систем: Round Robin, приоритетное планирование.
• Для систем реального времени: Rate-Monotonic Scheduling, Earliest Deadline First (EDF).

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

¶Первым пришёл — первым обслужен (FIFO/FCFS)

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

¶Кратчайшая задача первой (SJF)

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

¶Циклическое планирование (Round Robin)

Round Robin (RR) — вытесняющий алгоритм, в котором каждому процессу выделяется фиксированный квант времени (обычно 10–100 миллисекунд). По истечении кванта процесс перемещается в конец очереди, а ЦП передаётся следующему. Обеспечивает хорошую отзывчивость для интерактивных систем, но эффективность зависит от выбора кванта: слишком малый квант увеличивает накладные расходы на переключение контекста, слишком большой — приближает поведение к FIFO.

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

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

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

MLFQ (Multilevel Feedback Queue) — сложный алгоритм, использующий несколько очередей с разными приоритетами и квантами времени. Процессы начинают в верхней очереди с наименьшим квантом; если они не завершаются за квант, их приоритет понижается, и они перемещаются в следующую очередь с большим квантом. Это позволяет коротким задачам быстро завершаться, а длительным — получать процессорное время, но с меньшим приоритетом. MLFQ используется в большинстве современных ОС, включая Linux и Windows.

¶Применение в современных ОС

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

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

Ни один алгоритм не является универсальным. Например, Round Robin может быть неэффективен для пакетных задач, а SJF требует точных прогнозов, что затруднительно. Приоритетное планирование без старения приводит к голоданию. В системах реального времени жёсткие требования к срокам выполнения могут нарушаться при использовании алгоритмов, не гарантирующих детерминированность. Кроме того, накладные расходы на переключение контекста и работу планировщика могут снижать общую производительность при большом количестве процессов.

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

• В ранних версиях ОС Windows 9x планирование было основано на кооперативной многозадачности, где процессы сами должны были уступать ЦП.
• Алгоритм CFS, разработанный Ингваром Молнаром для Linux, заменил предыдущий планировщик O(1) в версии 2.6.23 (2007 год).
• В некоторых встраиваемых системах реального времени используется алгоритм Rate-Monotonic Scheduling, который гарантирует выполнение задач с периодическими интервалами, если загрузка ЦП не превышает определённого порога (теорема Лю и Лейланда).

¶Источники

• Таненбаум Э. Современные операционные системы. 4-е изд. — СПб.: Питер, 2015.
• Silberschatz A., Galvin P. B., Gagne G. Operating System Concepts. 10th ed. — Wiley, 2018.
• Документация ядра Linux: «CFS Scheduler» (kernel.org).
• Stallings W. Operating Systems: Internals and Design Principles. 9th ed. — Pearson, 2017.