Планирование: метрики и базовые политики

Откуда берётся вопрос

После прошлой главы у ОС есть механизм: таймер регулярно возвращает ей управление, и она может переключиться на другой процесс. Не хватает правила: кого запускать следующим. Это правило называется политикой планирования, а часть ядра ОС, которая его применяет, — планировщиком.

Бэкендеру эта тема ближе, чем кажется. У вас есть пул из N воркеров и очередь задач: тяжёлые выгрузки отчётов и лёгкие запросы профиля. В каком порядке их брать? Это та же задача планирования, и ответы ОС к ней прямо применимы.

Чтобы сравнивать политики, начнём с упрощённой модели. Есть набор задач (jobs), у каждой известно время прихода и сколько процессорного времени ей нужно (это называют burst). Задачи только считают, не ходят на диск. Ядро CPU одно. Позже упрощения будем снимать.

Две метрики

Для каждой задачи считаем:

• Время оборота (turnaround) = момент завершения − момент прихода. Сколько задача провела в системе целиком. Важно для фоновой работы: батчи, отчёты, сборка.
• Время отклика (response) = момент первого запуска − момент прихода. Сколько задача ждала, прежде чем вообще получила процессор. Важно там, где ждёт человек или клиент: интерактивные программы, первые байты ответа.

Иногда считают ещё время ожидания (wait) = оборот − burst: сколько задача простояла в очереди в сумме.

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

FIFO и эффект конвоя

Самая простая политика — FIFO (first in, first out, она же FCFS): кто пришёл первым, тот и считается до конца, без вытеснения.

Пример. В момент 0 пришли три задачи в порядке A, B, C:

FIFO
время   0        8   10   12
CPU     [   A    ][ B ][ C ]

Две короткие задачи стоят за длинной, хотя сами заняли бы процессор ненадолго. Это эффект конвоя (convoy effect): лёгкие машины едут за медленной фурой.

Если бы та же тройка пришла в порядке B, C, A, средний оборот был бы (2 + 4 + 12) / 3 = 6. FIFO не виновата в длине задач, но зависит от случайного порядка прихода.

На бэкенде это выглядит так: в общий пул из четырёх воркеров пришли четыре тяжёлых выгрузки по 30 секунд, и все лёгкие запросы за ними ждут полминуты. Типичное лекарство из практики — отдельный пул или отдельная очередь для тяжёлых задач.

Запустите симулятор с той же тройкой задач и переключите политику с FIFO на SJF.

SJF: сначала короткие

SJF (shortest job first) из всех готовых задач запускает самую короткую. На примере выше получаем B, C, A, то есть средний оборот 6 вместо 10, и средний отклик (0 + 2 + 4) / 3 = 2.

Если все задачи пришли одновременно, SJF даёт минимально возможный средний оборот. Идея доказательства — обмен соседей. Пусть в расписании длинная задача L стоит сразу перед короткой S, и до них всё закончилось к моменту t. Сумма их моментов завершения:

L, потом S:  (t + L) + (t + L + S) = 2t + 2L + S
S, потом L:  (t + S) + (t + S + L) = 2t + 2S + L

Второе меньше на L − S. Значит, любое расписание, где длинная стоит перед короткой, можно улучшить перестановкой, а лучшее — то, где все отсортированы по длине.

STCF: SJF с вытеснением

SJF без вытеснения ломается, когда задачи приходят в разное время. Пусть A пришла в момент 0 и требует 10, а B и C пришли в момент 2 и требуют по 2. SJF в момент 0 видит только A и запускает её до конца:

SJF без вытеснения
время   0           10   12   14
CPU     [     A     ][ B ][ C ]
оборот: A = 10, B = 12 − 2 = 10, C = 14 − 2 = 12   среднее 10,67

STCF (shortest time-to-completion first) при каждом приходе новой задачи сравнивает, кому осталось меньше, и при необходимости вытесняет текущую:

STCF
время   0    2    4    6           14
CPU     [ A ][ B ][ C ][     A     ]
оборот: A = 14, B = 4 − 2 = 2, C = 6 − 2 = 4      среднее 6,67

В момент 2 у A осталось 8, у пришедших B и C по 2, поэтому A уходит в очередь. STCF оптимален по среднему обороту и при разном времени прихода.

У SJF и STCF две проблемы. Первая: нужно заранее знать длительность задачи, а ОС её почти никогда не знает. Вторая: длинные задачи могут ждать бесконечно, если короткие приходят постоянно. Это голодание (starvation).

Round Robin: ради отклика

Если задача интерактивная, человеку важно, чтобы она начала отвечать быстро, а не закончила рано. Для этого есть Round Robin (RR): каждая задача получает небольшой квант времени (time slice), затем вытесняется и встаёт в конец очереди.

Возьмём три задачи по 5 единиц, все пришли в 0, квант 2:

RR, квант 2
время   0    2    4    6    8   10   12 13 14 15
CPU     [ A ][ B ][ C ][ A ][ B ][ C ][A][B][C]

RR выигрывает по отклику и проигрывает по обороту: он размазывает все задачи во времени, и они заканчиваются почти одновременно в самом конце. Если все N задач пришли одновременно, каждая впервые получит процессор не позже чем через (N − 1) × квант.

Если квант сделать больше любой задачи (здесь 5 и больше), RR превращается в FIFO. Если сделать очень маленьким, отклик улучшается, но растёт доля времени на переключения. Пусть переключение контекста стоит 5 мкс:

квант 1 мс:   5 / (1000 + 5) ≈ 0,5 % времени на переключения
квант 10 мкс: 5 / (10 + 5)   ≈ 33 % времени на переключения

С учётом косвенной цены (холодные кэши и TLB, см. процесс) крошечный квант разоряет систему. Реальные планировщики используют кванты порядка миллисекунд.

Поиграйте с квантом в симуляторе и посмотрите, как меняются оба средних.

А если задача ходит на диск

Реальные процессы не только считают. Задача, которая 1 мс считает и затем 10 мс ждёт диск, во время ожидания процессор не использует. Планировщик рассматривает каждый её кусок счёта как отдельную короткую задачу. SJF или STCF охотно запустят её первой, она быстро уйдёт в ожидание, а процессор тем временем займут другие. Так ввод-вывод перекрывается с вычислениями, как в примере из главы процесс.

Сводка

Реальной системе нужны хороший отклик и хороший оборот одновременно, а длину задач она не знает. Как к этому приблизиться, учась на поведении задач, — следующая глава про MLFQ.

Частые ошибки

• Путать оборот и отклик. Оборот считается до завершения, отклик — до первого запуска.
• Считать оборот от нуля, а не от момента прихода. Задача, пришедшая в 2 и завершившаяся в 6, имеет оборот 4, а не 6.
• Думать, что RR «справедливее, значит, лучше во всём». По среднему обороту RR один из худших.

Проверьте себя

1. FIFO, задачи пришли в 0 в порядке A (burst 6), B (2), C (4). Найдите средний оборот и средний отклик.
2. Те же задачи по SJF.
3. RR с квантом 1, задачи A (3) и B (3) пришли в 0. Когда завершится каждая?
4. Почему RR с квантом 100 на задачах длиной до 10 ведёт себя как FIFO?

Что спрашивают на собесе

• Разница между turnaround и response и какая политика под какую метрику.
• Почему SJF оптимален по среднему обороту (аргумент с перестановкой соседей).
• Что такое convoy effect, где он встречается в бэкенде и как с ним бороться.
• Как квант в RR влияет на отклик и на накладные расходы.
• Почему SJF/STCF не применимы напрямую в ОС (длительность неизвестна, голодание).