Планировщик операционной системы: алгоритмы FCFS, SJF, Round Robin, CFS🔗
Архитектурный контекст: роль планировщика в ядре🔗
Планировщик (Scheduler) — это модуль ядра, который выбирает процесс из очереди готовых к исполнению и выделяет ему время процессора. Он управляет доступом потоков к CPU, создавая для пользователя эффект одновременной работы множества программ.
Возьмём пример с кухней: если процесс — это приготовление сложного блюда, а потоки — повара, то планировщик выступает в роли администратора. Он не готовит еду сам, но распределяет задачи и следит за загрузкой рабочих мест. Пока один мастер ждёт, когда закипит бульон (I/O Burst — ожидание ввода-вывода), администратор отправляет другого шинковать овощи (CPU Burst — активные вычисления). Жизненный цикл задачи внутри этой системы выглядит следующим образом:
Диаграмма загружается…
Производительность операционной системы напрямую зависит от того, как распределены задачи между тремя уровнями управления:
| Тип планировщика |
Обязанности |
Частота работы |
| Долгосрочный |
Отбор заданий из общего пула для загрузки в оперативную память. |
Низкая (при создании процесса) |
| Краткосрочный |
Выбор процесса из очереди готовых для немедленного исполнения. |
Высокая (каждые несколько мс) |
| Среднесрочный |
Выгрузка процессов на диск (swapping) при нехватке памяти. |
Средняя (по необходимости) |
Функционирование этой системы опирается на прерывания таймера. Каждые несколько миллисекунд аппаратный сигнал заставляет ядро приостановить текущую задачу. Почему это важно? Такая принудительная остановка позволяет планировщику проверить очередь: возможно, за это время появился более срочный «заказ».
Подумайте, что случится, если администратор будет тратить на раздумья больше времени, чем повара на саму готовку? Эффективность алгоритмов выбора — критический фактор для отзывчивости всей ОС.
Механика алгоритмов FCFS и SJF: минимизация времени ожидания🔗
FCFS и SJF — базовые стратегии планирования, распределяющие процессорное время на основе очередности задач или длительности их выполнения. Они определяют правила работы очередей и приоритетов в операционных системах.
First-Come, First-Served (FCFS): простота и «эффект конвоя»🔗
FCFS работает по принципу живой очереди. Как только процесс переходит в состояние Ready, его управляющий блок (PCB) встает в хвост списка. Планировщик всегда забирает задачу из начала очереди. Это невытесняющий алгоритм: заняв ядро, процесс не отдаст его до завершения или перехода в режим ожидания ввода-вывода.
Главный изъян схемы — эффект конвоя (Convoy Effect). Допустим ситуацию: в системе появился один тяжелый вычислительный поток и несколько быстрых утилит. Пока «гигант» занимает ядро, короткие интерактивные задачи простаивают. В итоге отзывчивость интерфейса падает, а ресурсы используются неэффективно.
Shortest Job First (SJF): математическая оптимальность🔗
Алгоритм SJF отдает приоритет задаче с минимальным временем следующего цикла выполнения (CPU burst). Если длительность совпадает, выбор происходит в порядке поступления.
С точки зрения математики SJF эталонен: он гарантирует минимальное среднее время ожидания. Быстрые операции завершаются мгновенно и освобождают очередь. Однако ядро не знает хронометраж работы программы заранее. Системе приходится прогнозировать длительность цикла, используя статистику прошлых тактов и метод экспоненциального сглаживания.
Сравнение методик через диаграмму Ганта🔗
Изучим три процесса, поступивших одновременно: P1 (24 мс), P2 (3 мс) и P3 (3 мс). Сравним, как алгоритм влияет на скорость обработки.
Диаграмма загружается…
Среднее время ожидания (Tavg) — это сумма времени в очереди до начала работы, деленная на количество задач:
Tavg=n1∑i=1n(Tstart,i−Tarrival,i)
С другой стороны, В примере для FCFS результат составит: Tavg=(0+24+27)/3=17 мс.
Для SJF показатель будет иным: Tavg=(0+3+6)/3=3 мс. Эффективность выросла в пять раз.
Вытесняющий SJF (SRTF)🔗
Планирование по кратчайшей задаче бывает двух типов:
- Невытесняющее: начав работу, процесс сохраняет контроль над CPU до конца своего CPU burst.
- Вытесняющее (Shortest Remaining Time First, SRTF): если в очередь заходит новая задача короче остатка текущей, планировщик прерывает текущий процесс и переключает контекст.
SRTF агрессивнее сокращает ожидание, но тратит ресурсы на переключения. В современных ОС чистый SJF почти не встречается из-за риска «голодания» (starvation) крупных задач. Длинный поток может бесконечно ждать в конце очереди, если система занята мелкими запросами.
Кроме того, Как найти баланс между скоростью выполнения коротких задач и справедливостью распределения ресурсов для всех остальных? Попробуйте оценить, будет ли выгоднее прерывать процессы через равные промежутки времени, независимо от их длительности.
Round Robin: квантование времени и интерактивность🔗
Round Robin (RR) — это алгоритм циклического планирования, выделяющий каждому процессу строго фиксированный отрезок времени (квант). Такая стратегия гарантирует равный доступ к ресурсам и отзывчивость системы, не позволяя одной задаче захватить процессор надолго.
Важно: В отличие от стратегии FCFS, Round Robin работает по принципу вытеснения (preemptive). Когда время выполнения истекает, аппаратный таймер инициирует прерывание. Ядро немедленно приостанавливает текущую задачу, сохраняет её состояние в PCB (Process Control Block) и передает управление следующему кандидату из очереди.
Диаграмма загружается…
Квант времени: баланс между скоростью и накладными расходами🔗
Производительность RR напрямую привязана к длительности кванта (q). Если задрать это значение до бесконечности, алгоритм превратится в обычную очередь FCFS, и интерактивность исчезнет. Слишком короткий интервал заставит систему тратить больше усилий на переключение контекста, чем на саму работу.
| Размер кванта |
Интерактивность (Latency) |
Накладные расходы (Overhead) |
Пример поведения |
| Слишком малый |
Идеальная |
Экстремально высокие |
CPU тратит 50% ресурсов на смену регистров |
| Оптимальный |
Хорошая |
Умеренные (1–5%) |
Стандарт десктопных ОС (10–100 мс) |
| Слишком большой |
Плохая (задержки ввода) |
Минимальные |
Система работает как пакетный обработчик |
Архитектурный компромисс🔗
Поиск «золотой середины» в настройке кванта — классическая инженерная задача. В современных ОС Windows и Linux интервал подбирают так, чтобы затраты на переключение контекста не превышали 1% от времени работы процесса. Важно учитывать: переключение между задачами обходится дорого, так как требует очистки кэшей процессора и обновления таблиц страниц.
Зависимость общей эффективности можно выразить формулой:
Ttotal=Tcomputation+N×Tswitch
Здесь N — число прерываний. Рост N при крошечном кванте резко снижает общую пропускную способность (throughput), хотя пользователь и получает иллюзию мгновенного отклика.
В то же время Как вы считаете, подойдет ли Round Robin для серверов базы данных, где важнее закончить тяжелый запрос целиком, чем быстро обновлять курсор мыши?
Алгоритм CFS в Linux: планирование на основе Fair Share и красных-черных деревьев🔗
Completely Fair Scheduler (CFS) — основной планировщик ядра Linux, который распределяет процессорное время между потоками максимально справедливо. Вместо нарезки фиксированных квантов он выделяет каждому процессу долю мощности CPU, пропорциональную его весу.
Однако В основе алгоритма лежит концепция vruntime (virtual runtime). Это индивидуальный счетчик, который фиксирует, сколько времени поток провел на исполнении. Когда задача работает, её vruntime увеличивается. Логика проста: система всегда выбирает поток с минимальным значением vruntime, давая шанс тому, кто получил меньше всего ресурсов.
Механика Fair Share и роль Nice-баллов🔗
Также При одинаковом приоритете всех задач планировщик просто удерживает их показатели vruntime на одном уровне. Но в реальности потоки имеют разный вес. Который регулируется индексом nice (от -20 до +19). Процессы с высоким приоритетом (низкий nice) накапливают виртуальное время медленнее, чем фоновые задачи.
Математическая логика выглядит так:
vruntimenew=vruntimeold+Δactual_time×weighttaskweightnice0
За счет этого «важный» процесс может дольше занимать ядро процессора, прежде чем его виртуальное время сравняется с остальными и планировщик инициирует переключение контекста.
# Упрощенная модель обновления vruntime в логике CFS
def update_vruntime(task, delta_exec):
# Коэффициент веса зависит от значения nice.
# Для nice=0 вес равен 1024. Для nice=10 он падает до 110.
weight_factor = NICE_0_LOAD / task.weight
# Виртуальное время растет медленнее у приоритетных задач
task.vruntime += delta_exec * weight_factor
return task.vruntime
Структура данных: почему красно-черное дерево?🔗
Для быстрого поиска задачи с наименьшим vruntime обычная очередь не подходит, так как вставка процесса обратно после работы требовала бы пересортировки за O(N). Изучим, почему CFS полагается на красно-черное дерево (RB-Tree) — самобалансирующуюся структуру поиска:
Однако 1. Поиск за O(logN): Задачи упорядочены по значению vruntime. Самый «обделенный» ресурс процессом поток всегда находится в левой части дерева.
2. Эффективная вставка: Когда поток возвращается в дерево после исполнения, перестроение узлов занимает логарифмическое время.
3. Оптимизация доступа: Ядро кеширует ссылку на самый левый узел. Это позволяет извлекать следующую на выполнение задачу мгновенно — за O(1).
Диаграмма загружается…
Планировщик забирает крайний левый узел, позволяет процессу поработать, обновляет его виртуальное время и возвращает в дерево. После этого задача смещается вправо, пропуская вперед другие потоки. Такой подход делает работу системы плавной и отзывчивой.
Попробуйте на практике изменить значение nice для ресурсоемкого процесса через команду renice. Как это отразится на отзывчивости других приложений в вашей системе?
Практика: системные вызовы и управление приоритетами из кода🔗
Управление ресурсами в Linux реализовано через «подсказки» ядру: программист использует системные вызовы, чтобы изменить вес процесса (nice) или его политику планирования. Это позволяет выделить мощности критически важным задачам, когда стандартных механизмов распределения времени CFS недостаточно.
Центральное понятие здесь — значение nice. Оно варьируется от -20 (наивысший приоритет) до 19 (минимальный). Новая программа обычно получает значение 0, занимая нейтральную позицию в очереди на процессорное время.
#include <unistd.h>
#include <sys/resource.h>
#include <sched.h>
#include <stdio.h>
int main() {
// Увеличиваем nice, тем самым добровольно уступая ресурсы другим
// Для установки отрицательных значений (повышения приоритета) требуются права root
if (nice(10) == -1) {
perror("nice failed");
}
struct sched_param param;
param.sched_priority = 50; // Приоритет для Real-time стратегий
// Переключаем процесс на алгоритм Round Robin
if (sched_setscheduler(0, SCHED_RR, ¶m) == -1) {
perror("sched_setscheduler failed");
}
return 0;
}
Для гибкого контроля поведения потоков существуют политики POSIX. Каждая из них определяет собственный сценарий взаимодействия с планировщиком:
| Политика |
Алгоритм |
Описание |
SCHED_OTHER |
CFS |
Стандартный режим «справедливого» распределения задач. |
SCHED_RR |
Round Robin |
Real-time: поток прерывается только по истечении кванта времени. |
SCHED_FIFO |
FIFO |
Real-time: процесс занимает ядро, пока сам не завершится или не уснет. |
Помните, что в ОС общего назначения эти настройки не дают стопроцентных гарантий. Планировщик может вмешаться в работу высокоприоритетного потока, чтобы защитить систему от перегрева или предотвратить «голодание» критических системных служб. Полная предсказуемость — прерогатива систем реального времени (RTOS), где задержки измеряются микросекундами.
Сможете ли вы спрогнозировать, что произойдет с системой, если запустить два бесконечных цикла с политикой SCHED_FIFO на одноядерном процессоре?
