Дисциплина диспетчеризации процессов¶

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

¶Основные понятия и классификация

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

Классификация дисциплин диспетчеризации проводится по нескольким признакам:

• По способу переключения контекста:
• Вытесняющие (preemptive): Операционная система может прервать выполнение текущего процесса в любой момент (например, по истечении кванта времени или при поступлении более приоритетного процесса) и передать ЦП другому процессу. Решение о переключении принимает ядро ОС.
• Невытесняющие (non-preemptive, cooperative): Процесс, получив управление, удерживает ЦП до тех пор, пока сам не завершится, не перейдёт в состояние ожидания (например, запроса ввода-вывода) или добровольно не отдаст управление (например, вызовом yield). ОС не может принудительно отобрать процессор у процесса.
• По приоритетам:
• Без приоритетов (циклические, FIFO): Все процессы считаются равноправными. Порядок выполнения определяется только очередью поступления или временем.
• С приоритетами: Каждому процессу присваивается числовое значение приоритета. Процесс с более высоким приоритетом (меньшим числом, если приоритет — число, или большим — в зависимости от реализации) получает ЦП раньше. Приоритеты могут быть статическими (задаются один раз при создании процесса) или динамическими (изменяются во время выполнения, например, для предотвращения «голодания» низкоприоритетных процессов).
• По времени выполнения:
• С квантованием (time-sharing): Каждому процессу выделяется фиксированный или переменный квант времени. По истечении кванта процесс принудительно вытесняется, если не завершился раньше.
• Без квантования: Процесс выполняется до завершения, блокировки или добровольной передачи управления.

¶Основные дисциплины диспетчеризации

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

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

• Достоинства: Простота реализации, отсутствие «голодания» (каждый процесс рано или поздно получит ЦП).
• Недостатки: Высокое среднее время ожидания, особенно если в начале очереди оказывается длительный процесс. Эффект «конвоя» (convoy effect): короткие процессы вынуждены ждать завершения длительного. Не подходит для интерактивных систем.

¶Короткая задача первой (SJF, Shortest Job First)

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

• Достоинства: Минимизирует среднее время ожидания и среднее время оборота (turnaround time) в теории.
• Недостатки: Трудно реализуема на практике, так как операционная система не может точно знать, сколько времени будет выполняться процесс. Возможно «голодание» длительных процессов, которые могут никогда не получить ЦП, если постоянно поступают короткие задачи. Требует оценки времени выполнения (например, на основе истории предыдущих запусков).

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

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

• Достоинства: Обеспечивает равномерное распределение процессорного времени между всеми процессами. Хорошее время отклика для интерактивных систем. Отсутствие «голодания».
• Недостатки: Высокие накладные расходы на переключение контекста (при малом кванте). При большом кванте вырождается в FCFS. Среднее время ожидания может быть выше, чем у SJF.

¶Приоритетное планирование (Priority Scheduling)

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

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

¶Многоуровневые очереди (Multilevel Queue)

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

¶Планирование реального времени (Real-Time Scheduling)

Дисциплины для систем реального времени (RTOS) ориентированы на гарантированное выполнение задач в заданные сроки (deadline). Основные алгоритмы:

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

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

Выбор дисциплины диспетчеризации зависит от целей системы. Основные критерии оценки:

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

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

• Linux: Использует полностью вытесняющее планирование с приоритетами. Основной алгоритм — Completely Fair Scheduler (CFS), который стремится обеспечить каждому процессу справедливую долю процессорного времени. CFS использует красно-чёрное дерево для хранения готовых процессов и выбирает процесс с наименьшим временем выполнения (virtual runtime). Для задач реального времени применяются алгоритмы SCHED_FIFO и SCHED_RR.
• Windows (NT-ядро): Использует вытесняющее приоритетное планирование с динамическим повышением приоритетов. Приоритеты варьируются от 0 до 31. Процессы с высоким приоритетом (например, драйверы, системные потоки) выполняются в первую очередь. Для интерактивных приложений (например, оконный менеджер) приоритет может временно повышаться, чтобы улучшить отзывчивость.
• macOS (XNU): Комбинирует планирование на основе приоритетов с использованием многоуровневых очередей. Для задач реального времени используется отдельный класс.

¶Исторические аспекты

В ранних операционных системах (например, пакетной обработки) использовались простые дисциплины, такие как FCFS. С развитием многозадачности и интерактивных систем (1960-е — 1970-е годы) появились вытесняющие алгоритмы, в частности, Round Robin, реализованный в системе CTSS (Compatible Time-Sharing System). В 1980-х годах, с распространением UNIX, стали широко применяться приоритетные планировщики. Современные тенденции включают адаптивные алгоритмы, учитывающие энергопотребление (например, в мобильных устройствах) и архитектуру NUMA (Non-Uniform Memory Access).

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

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