Раздел 05 — Планирование процессора

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

1. выполняющийся поток завершился;
2. он перешёл в ожидание — запросил диск, сеть, ввод с клавиатуры;
3. появился новый готовый поток (создан или дождался события);
4. сработал таймер — у потока кончился выделенный отрезок времени, квант.

Если планировщик вмешивается только в случаях 1 и 2, планирование невытесняющее: поток работает, пока сам не отдаст процессор. Если и в случаях 3 и 4 — вытесняющее: поток можно снять с ядра в любой момент. Все современные настольные и серверные ОС вытесняющие: иначе одна зависшая программа останавливала бы всю систему, как это бывало в Windows 3.1.

Хорошее планирование — компромисс между критериями, которые противоречат друг другу:

Две формулы для расчётов:

• время оборота = момент завершения − момент поступления;
• время ожидания = время оборота − длительность работы.

Ещё одно наблюдение: процессы бывают вычислительными — долго считают, редко обращаются к устройствам (архиватор, компилятор) — и ориентированными на ввод-вывод — немного считают и снова ждут (текстовый редактор, веб-сервер). Хороший планировщик быстро пропускает вторых: им нужен процессор ненадолго, а пользователь ждёт их ответа.

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

$ cat procs.txt
# имя поступление длительность приоритет
P1 0 8 2
P2 1 4 4
P3 2 9 1
P4 3 5 3

Результат каждого алгоритма — диаграмма Ганта: какой процесс на каком отрезке времени занимал процессор. Запись P1[0–8] значит, что P1 работал с момента 0 до момента 8. По диаграмме находят момент завершения каждого процесса, а по формулам — время оборота и ожидания.

Как строить диаграмму вручную:

1. Нарисуйте ось времени. Отметьте моменты поступления процессов.
2. В момент 0 выберите процесс по правилу алгоритма из тех, что уже поступили.
3. Двигайтесь до следующего момента принятия решения (завершение; для вытесняющих — ещё и поступление нового процесса или конец кванта) и снова выбирайте.
4. При равенстве выбирайте процесс, поступивший раньше.
5. Для каждого процесса запишите момент завершения, посчитайте оборот и ожидание, затем средние.

FCFS (first come, first served) — очередь, как в кассу: процессор получает процесс, пришедший раньше всех, и держит его до завершения. Алгоритм невытесняющий.

$ python3 calc/sched.py fcfs < procs.txt
Алгоритм: FCFS
Диаграмма: P1[0–8] P2[8–12] P3[12–21] P4[21–26]
Процесс  Поступл.  Длит.  Заверш.  Оборот  Ожидание
P1              0      8        8       8         0
P2              1      4       12      11         7
P3              2      9       21      19        10
P4              3      5       26      23        18
Среднее время оборота: 61/4 = 15,25
Среднее время ожидания: 35/4 = 8,75

Проверим P4: поступил в 3, завершился в 26 — оборот 23; работал 5 — значит, 18 единиц стоял в очереди.

FCFS прост и честен, но среднее ожидание сильно зависит от порядка. Классический пример — один длинный процесс и два коротких:

$ python3 calc/sched.py fcfs < convoy.txt
Алгоритм: FCFS
Диаграмма: P1[0–24] P2[24–27] P3[27–30]
Процесс  Поступл.  Длит.  Заверш.  Оборот  Ожидание
P1              0     24       24      24         0
P2              0      3       27      27        24
P3              0      3       30      30        27
Среднее время оборота: 81/3 = 27,00
Среднее время ожидания: 51/3 = 17,00
$ python3 calc/sched.py fcfs < convoy2.txt
Алгоритм: FCFS
Диаграмма: P2[0–3] P3[3–6] P1[6–30]
Процесс  Поступл.  Длит.  Заверш.  Оборот  Ожидание
P2              0      3        3       3         0
P3              0      3        6       6         3
P1              0     24       30      30         6
Среднее время оборота: 39/3 = 13,00
Среднее время ожидания: 9/3 = 3,00

Одни и те же процессы, а среднее ожидание — 17 или 3. Когда длинный процесс впереди, короткие стоят за ним, как легковые машины за грузовиком на однополосной дороге. Это называют эффектом конвоя. Для пользователя он выглядит так: копирование большого файла, и все остальные программы «подвисают».

Раз короткие процессы страдают за длинными — пропустим их вперёд. SJF (shortest job first) из поступивших выбирает процесс с наименьшей длительностью и не прерывает его:

$ python3 calc/sched.py sjf < procs.txt
Алгоритм: SJF
Диаграмма: P1[0–8] P2[8–12] P4[12–17] P3[17–26]
Процесс  Поступл.  Длит.  Заверш.  Оборот  Ожидание
P1              0      8        8       8         0
P2              1      4       12      11         7
P3              2      9       26      24        15
P4              3      5       17      14         9
Среднее время оборота: 57/4 = 14,25
Среднее время ожидания: 31/4 = 7,75

В момент 0 есть только P1 — он и работает до 8. К моменту 8 поступили все: самый короткий P2 (4), затем P4 (5), затем P3 (9). Среднее ожидание 7,75 против 8,75 у FCFS.

SRTF (shortest remaining time first) — вытесняющий вариант: когда приходит новый процесс, его длительность сравнивают с оставшимся временем текущего.

$ python3 calc/sched.py srtf < procs.txt
Алгоритм: SRTF
Диаграмма: P1[0–1] P2[1–5] P4[5–10] P1[10–17] P3[17–26]
Процесс  Поступл.  Длит.  Заверш.  Оборот  Ожидание
P1              0      8       17      17         9
P2              1      4        5       4         0
P3              2      9       26      24        15
P4              3      5       10       7         2
Среднее время оборота: 52/4 = 13,00
Среднее время ожидания: 26/4 = 6,50

В момент 1 приходит P2 (4), а P1 осталось 7 — P1 вытеснен. В момент 3 приходит P4 (5), но P2 осталось 2 — продолжает P2. В 5 из P1 (осталось 7), P3 (9) и P4 (5) выбираем P4, затем P1 и P3. Среднее ожидание 6,5 — лучшее из всех алгоритмов этого раздела: доказано, что SRTF даёт минимальное среднее ожидание.

Почему тогда его не используют в чистом виде? Длительность работы заранее неизвестна: ОС не знает, сколько ещё будет считать программа. Реальные планировщики её предсказывают по прошлому поведению: поток, который до сих пор быстро уходил в ожидание, скорее всего, уйдёт и сейчас. Вторая проблема — голодание: если короткие процессы приходят постоянно, длинный P3 может не получить процессор никогда.

Round Robin (RR, карусель) — FCFS с вытеснением по таймеру. Каждый процесс получает квант времени; не успел — встаёт в конец очереди. Процессы, поступившие к концу кванта, встают в очередь раньше вытесненного.

$ python3 calc/sched.py rr 3 < procs.txt
Алгоритм: RR, квант 3
Диаграмма: P1[0–3] P2[3–6] P3[6–9] P4[9–12] P1[12–15] P2[15–16] P3[16–19] P4[19–21] P1[21–23] P3[23–26]
Процесс  Поступл.  Длит.  Заверш.  Оборот  Ожидание
P1              0      8       23      23        15
P2              1      4       16      15        11
P3              2      9       26      24        15
P4              3      5       21      18        13
Среднее время оборота: 80/4 = 20,00
Среднее время ожидания: 54/4 = 13,50

Проследим начало. 0–3 работает P1, к моменту 3 пришли P2, P3, P4 и встали в очередь перед вытесненным P1: очередь P2, P3, P4, P1. P2 работает 3–6, у него осталась 1 единица — в конец очереди. Дальше по кругу, пока все не завершатся.

Среднее ожидание у RR хуже, чем у SJF и даже FCFS, но RR даёт другое — быстрый отклик: каждый процесс получает процессор не позже, чем через (число процессов − 1) × квант. Поэтому RR — основа планирования в интерактивных системах.

Всё решает размер кванта:

$ python3 calc/sched.py rr 1 < procs.txt | tail -1
Среднее время ожидания: 50/4 = 12,50
$ python3 calc/sched.py rr 2 < procs.txt | tail -1
Среднее время ожидания: 51/4 = 12,75
$ python3 calc/sched.py rr 4 < procs.txt | tail -1
Среднее время ожидания: 47/4 = 11,75
$ python3 calc/sched.py rr 8 < procs.txt | tail -1
Среднее время ожидания: 39/4 = 9,75
$ python3 calc/sched.py rr 30 < procs.txt | tail -1
Среднее время ожидания: 35/4 = 8,75

С большим квантом (30 — длиннее любого процесса) RR превращается в FCFS: 8,75. С маленьким процессы чаще переключаются, и среднее ожидание растёт. В расчётах переключение бесплатное, а в жизни нет: ядру нужно сохранить регистры одного потока, загрузить другого, а кэш процессора остывает. Квант делают намного больше времени переключения: в реальных ОС это от нескольких до сотни миллисекунд.

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

$ python3 calc/sched.py prio < procs.txt
Алгоритм: приоритеты без вытеснения
Диаграмма: P1[0–8] P3[8–17] P4[17–22] P2[22–26]
Процесс  Поступл.  Длит.  Заверш.  Оборот  Ожидание
P1              0      8        8       8         0
P2              1      4       26      25        21
P3              2      9       17      15         6
P4              3      5       22      19        14
Среднее время оборота: 67/4 = 16,75
Среднее время ожидания: 41/4 = 10,25
$ python3 calc/sched.py pprio < procs.txt
Алгоритм: приоритеты с вытеснением
Диаграмма: P1[0–2] P3[2–11] P1[11–17] P4[17–22] P2[22–26]
Процесс  Поступл.  Длит.  Заверш.  Оборот  Ожидание
P1              0      8       17      17         9
P2              1      4       26      25        21
P3              2      9       11       9         0
P4              3      5       22      19        14
Среднее время оборота: 70/4 = 17,50
Среднее время ожидания: 44/4 = 11,00

Без вытеснения P1 доработал до 8, хотя в момент 2 пришёл более важный P3. С вытеснением P3 сразу снял P1 с процессора и отработал 2–11. Среднее ожидание при этом выросло — приоритеты служат не средним цифрам, а важным задачам. P2 с самым низким приоритетом в обоих случаях ждал до конца: пришёл в 1, начал работать в 22.

Это то же голодание: при постоянном потоке важных задач неважная не выполнится никогда. Лекарство — старение (aging): приоритет долго ждущего процесса постепенно повышают, пока он не получит процессор.

Реальные ОС совмещают все идеи в многоуровневых очередях с обратной связью: несколько очередей с разными приоритетами, внутри очереди — RR; поток, который съел весь квант (вычислительный), опускается ниже, а тот, что быстро ушёл в ожидание (интерактивный), поднимается выше или получает временную прибавку приоритета.

Windows планирует потоки по 32 уровням приоритета: 0 — служебный поток обнуления памяти, 1–15 — обычные (динамические), 16–31 — реального времени. Процессу задают класс приоритета, из него получается базовый приоритет потоков:

PS> Get-Process | Group-Object PriorityClass | Select-Object Count, Name
Count Name
----- ----
  120 Normal
   20
    3 High
    3 AboveNormal
PS> Get-Process -Name csrss, explorer, MsMpEng | Select-Object ProcessName, PriorityClass, BasePriority
ProcessName PriorityClass BasePriority
----------- ------------- ------------
csrss                               13
csrss                               13
explorer    Normal                   8
MsMpEng                              8

У части процессов класс пустой: это защищённые системные процессы, и Windows не показывает их свойства даже администратору. BasePriority при этом виден: у csrss 13 — класс High.

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

Проверим, как работает класс приоритета. Запустим две копии PowerShell с бесконечным циклом, привяжем обе к одному ядру (ProcessorAffinity = 1 — битовая маска, бит 0 — ядро 0) и одной дадим класс Idle:

PS> $loop = '-NoProfile -Command "while ($true) {}"'
PS> $a = Start-Process powershell -ArgumentList $loop -WindowStyle Hidden -PassThru
PS> $b = Start-Process powershell -ArgumentList $loop -WindowStyle Hidden -PassThru
PS> $a.ProcessorAffinity = 1; $b.ProcessorAffinity = 1     # оба — только на ядро 0
PS> $b.PriorityClass = "Idle"
PS> Start-Sleep 5
PS> Get-Process -Id $a.Id, $b.Id | Select-Object Id, PriorityClass, ProcessorAffinity, TotalProcessorTime
  Id PriorityClass ProcessorAffinity TotalProcessorTime
  -- ------------- ----------------- ------------------
5808          Idle                 1 00:00:00.8906250
7308        Normal                 1 00:00:05.8750000

За 5 секунд процесс класса Normal получил почти всё время ядра, а процесс Idle — меньше секунды, и почти всё это время ушло ещё до смены класса, на запуск PowerShell. Планировщик Windows строгий: пока готов поток с более высоким приоритетом, низкий не выполняется. От полного голодания его спасает только встроенное старение: потоку, который несколько секунд не получал процессор, Windows ненадолго поднимает приоритет.

В графике класс меняют в Диспетчере задач: Подробности → правая кнопка по процессу → Задать приоритет, а привязку — Задать сходство. Запустить программу сразу с нужными настройками можно в cmd: start /low /affinity 1 program.exe.

Обычные процессы Linux планирует не по строгим приоритетам, а по справедливым долям: каждый готовый поток получает долю процессора, пропорциональную своему весу. С версии 2.6.23 это делал планировщик CFS (Completely Fair Scheduler), с версии 6.6 его сменил EEVDF — принцип долей сохранился, а интерактивные задачи стали получать процессор быстрее.

Вес задаётся значением nice от −20 (самый «невежливый», больше всех процессора) до 19 (уступает всем). По умолчанию 0. Каждая ступень nice меняет долю примерно на 10 %. Повышать nice может любой пользователь, понижать ниже 0 — только администратор.

$ nice
0
$ ps -o pid,ni,pri,cls,comm -p $$
    PID  NI PRI CLS COMMAND
2685317   0  19  TS bash
$ chrt -p $$
pid 2685317's current scheduling policy: SCHED_OTHER
pid 2685317's current scheduling priority: 0
pid 2685317's current runtime parameter: 1400000

NI — значение nice, CLS TS — обычный класс планирования (time sharing, в ядре — SCHED_OTHER). Для задач реального времени есть классы SCHED_FIFO и SCHED_RR — они всегда впереди обычных и задаются командой chrt.

Тот же опыт, что в Windows: два бесконечных цикла на ядре 0 (taskset -c 0), второй с nice -n 10:

$ taskset -c 0 sh -c "while :; do :; done" &
$ taskset -c 0 nice -n 10 sh -c "while :; do :; done" &
$ ps -o pid,ni,psr,pcpu,time,args -p 2685385,2685386
    PID  NI PSR %CPU     TIME COMMAND
2685385   0   0 90.3 00:00:03 sh -c while :; do :; done
2685386  10   0  9.6 00:00:00 sh -c while :; do :; done

Столбец PSR подтверждает, что оба работают на ядре 0. Доли — 90 % и 10 %, ровно по весам: у nice 0 вес 1024, у nice 10 — 110, и 1024 / (1024 + 110) ≈ 0,90. В отличие от Windows, процесс с низким приоритетом не стоит на месте, а получает свою меньшую долю.

Зачем привязывать к ядрам? Чтобы тяжёлая фоновая задача не мешала остальным (отдать ей одно ядро из восьми), чтобы поток не терял кэш процессора при переездах между ядрами, а иногда — по условиям лицензии программы, которая считается по числу ядер.