---
title: "Планирование: метрики и базовые политики"
description: "После прошлой главы у ОС есть механизм: таймер регулярно возвращает ей управление, и она может переключиться на другой процесс. Не хватает правила: кого запускать следующим. Это…"
canonical: https://graphlms.ru/os/book/scheduling
course: "Операционные системы"
updated: 2026-10-12
lang: ru
publisher: GraphLMS
---

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

> Источник: https://graphlms.ru/os/book/scheduling — курс «Операционные системы», GraphLMS.

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

После [прошлой главы](/os/book/limited-direct-execution) у ОС есть механизм: таймер
регулярно возвращает ей управление, и она может переключиться на другой процесс. Не
хватает правила: кого запускать следующим. Это правило называется **политикой
планирования**, а часть ядра ОС, которая его применяет, — **планировщиком**.

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

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

## Две метрики

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

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

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

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

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

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

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

| Задача | Приход | Burst |
|---|---|---|
| A | 0 | 8 |
| B | 0 | 2 |
| C | 0 | 2 |

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

| Задача | Завершилась | Оборот | Первый запуск | Отклик |
|---|---|---|---|---|
| A | 8 | 8 | 0 | 0 |
| B | 10 | 10 | 8 | 8 |
| C | 12 | 12 | 10 | 10 |
| **Среднее** | | **10** | | **6** |

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

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

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

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

> Интерактивный симулятор «Convoy effect (FIFO)»: Длинная задача A пришла первой, и две короткие стоят за ней в очереди. При FIFO средний оборот получается 10, при SJF всего 6. Переключите политику и убедитесь сами. Запустить: https://graphlms.ru/os/book/scheduling

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

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

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

```text
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 и запускает её до конца:

```text
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) при каждом приходе новой задачи
сравнивает, кому осталось меньше, и при необходимости вытесняет текущую:

```text
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:

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

| Политика | Обороты A, B, C | Средний оборот | Отклики A, B, C | Средний отклик |
|---|---|---|---|---|
| FIFO | 5, 10, 15 | 10 | 0, 5, 10 | 5 |
| RR, квант 2 | 13, 14, 15 | 14 | 0, 2, 4 | 2 |
| RR, квант 1 | 13, 14, 15 | 14 | 0, 1, 2 | 1 |

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

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

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

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

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

> Интерактивный симулятор «Round Robin»: Round Robin режет время на кванты и крутит задачи по кругу. Отклик хороший, но оборот растёт. Меняйте квант: чем он меньше, тем быстрее каждая задача получает первый тик и тем больше переключений контекста. Запустить: https://graphlms.ru/os/book/scheduling

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

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

## Сводка

| Политика | Хороша по | Плохо | Требует знать длину |
|---|---|---|---|
| FIFO | простоте | эффект конвоя | нет |
| SJF | обороту, если все пришли сразу | отклик, поздние короткие ждут | да |
| STCF | обороту всегда | отклик длинных, голодание | да |
| RR | отклику | обороту; накладные расходы при малом кванте | нет |

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

> Квиз по разделу: см. вопросы в конце документа или на https://graphlms.ru/os/book/scheduling

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

- Путать оборот и отклик. Оборот считается до **завершения**, отклик — до
  **первого** запуска.
- Считать оборот от нуля, а не от момента прихода. Задача, пришедшая в 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?

Ответы. (1) Завершения 6, 8, 12, средний оборот 26 / 3 ≈ 8,67; отклики 0, 6, 8,
среднее 14 / 3 ≈ 4,67. (2) Порядок B, C, A: завершения 2, 6, 12, средний оборот
20 / 3 ≈ 6,67; отклики 0, 2, 6, среднее 8 / 3 ≈ 2,67. (3) A B A B A B: A
завершится в 5, B в 6. (4) Каждая задача успевает закончиться внутри первого
кванта, вытеснения не происходит.

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

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

## Вопросы для самопроверки

**Квиз «Метрики и политики планирования»**

1. Какая политика даёт оптимальное среднее время оборота, если все задачи пришли одновременно?
   - MLFQ
   - SJF (верно)
   - FIFO
   - RR
   - Пояснение: SJF пускает первой самую короткую — любая перестановка с длинной впереди только увеличивает сумму оборотов.
2. Какую метрику оптимизируете для интерактивного API-запроса, где человек ждёт ответа?
   - turnaround (оборот)
   - wait в очереди
   - response (отклик) (верно)
   - Пояснение: Отклик — это задержка до первой реакции. Для интерактивности он важнее, чем когда задача полностью завершится.
3. Что помогает улучшить отклик? (несколько вариантов)
   - FIFO
   - маленький квант (верно)
   - Round Robin (верно)
   - длинный квант
   - Пояснение: RR с маленьким квантом быстро доходит до каждой задачи. Длинный квант вырождает RR в FIFO, а FIFO страдает от convoy effect.
4. FIFO: задача A (burst 6) и B (burst 2) пришли в момент 0, A раньше в очереди. Чему равно время оборота B?
   - Ответ: 8
   - Пояснение: B ждёт, пока A досчитает (6), потом сама считает 2 → завершается в 8. Оборот = 8 − 0 = 8. Это и есть convoy effect.
5. Три задачи по 3 единицы времени пришли в момент 0. Round Robin с квантом 1. Чему равно время оборота последней задачи (третьей в очереди)?
   - Ответ: 9
   - Пояснение: Тайминг идёт A B C A B C A B C: третья задача заканчивает на 9-м тике. Оборот считаем от момента прихода (0), поэтому он равен 9. Заметьте, что для SJF оборот всех троих был бы 3, 6 и 9: RR хорош откликом, но не оборотом.