Чем мерить планировщик

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

• Turnaround (оборот) = время завершения − время прихода. Сколько всего задача прожила в системе. Это метрика пропускной способности: важна для батчей, аналитики, фоновых джоб.
• Response (отклик) = время первого запуска − время прихода. Сколько задача ждала, прежде чем впервые получила CPU. Это метрика интерактивности: важна для запросов пользователя, API, всего, где человек ждёт ответа.
• Wait (ожидание) = оборот − время счёта. Сколько задача проторчала в очереди.

Ключевая мысль всего раздела: оборот и отклик тянут в разные стороны. Политика, которая лучшая по обороту, обычно ужасна по отклику, и наоборот. Хороший инженер не ищет «лучший планировщик» — он понимает, под какую метрику оптимизирует.

FIFO и convoy effect

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

Представьте: первой пришла тяжёлая задача (long-running запрос, выгрузка отчёта), а за ней — несколько лёгких. Лёгкие вынуждены стоять за тяжёлой, хотя сами по себе заняли бы ядро на миг. Среднее время оборота взлетает. Это convoy effect — короткие «застревают в колонне» за длинной.

Покрути симулятор: при FIFO задача A (burst 8) держит всех. Теперь переключи политику на SJF — и увидишь, как среднее время оборота резко падает.

SJF и STCF: оптимум по обороту

SJF (Shortest Job First) пускает первой самую короткую из доступных задач. Если все пришли одновременно, SJF даёт оптимальное среднее время оборота — это можно доказать: любая перестановка, ставящая длинную вперёд короткой, только ухудшает сумму.

Но SJF без вытеснения снова спотыкается о приходы: если длинная стартовала чуть раньше, короткая всё равно ждёт её завершения. Лечится вытеснением: STCF (Shortest Time-to-Completion First) — при каждом новом приходе пересматривает решение и пускает того, кому осталось меньше всего. STCF оптимален по обороту уже и при разном времени прихода.

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

Round Robin: оптимизируем отклик

Если важен отклик (а для интерактивных систем он важнее всего), нужна другая идея: не доводить задачу до конца, а давать каждому маленький квант времени и крутить по кругу. Это Round Robin.

RR блестящ по отклику: при N задачах и кванте q каждый получает CPU не позже чем через (N−1)·q. Но за это платим оборотом: RR размазывает все задачи, и они финишируют примерно одновременно и поздно. То есть RR — почти зеркальная противоположность SJF: лучший отклик, один из худших оборотов.

Поиграй с квантом. Маленький квант = честнее отклик, но больше переключений контекста (а каждое стоит, см. главу про прямое исполнение). Большой квант = RR вырождается в FIFO.

Так какой выбрать

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

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

• В чём разница между turnaround и response и какая политика под какую метрику.
• Почему SJF оптимален по среднему обороту (уметь объяснить идею доказательства).
• Что такое convoy effect и как с ним бороться.
• Как квант в RR влияет на отклик и на накладные расходы.