Планування CPU
Навіщо це
Section titled “Навіщо це”Процесів завжди більше, ніж ядер, тож хтось мусить вирішувати, кого пустити на процесор наступним і як надовго. Це рішення ухвалюється тисячі разів за секунду.
Наслідки видно неозброєним оком. Чому інтерфейс лишається чутливим, поки
компілюється проєкт? Чому nice -n 19 майже не сповільнює фонову задачу,
а nice -n -20 помітно прискорює? Чому відеодзвінок заїкається, коли поруч
працює архіватор, хоча процесор і близько не завантажений на сто відсотків?
Передумови. Стани процесу і контекстне перемикання (модуль 6), переривання від таймера (модуль 2).
Що оптимізуємо
Section titled “Що оптимізуємо”Найкращого алгоритму не існує, бо цілі суперечать одна одній.
| Метрика | Що означає | Кому важлива |
|---|---|---|
| Пропускна здатність | процесів, завершених за одиницю часу | пакетні обчислення |
| Час обороту | від запуску до завершення | збірка, рендеринг |
| Час очікування | скільки процес простояв у черзі готових | усі |
| Час відгуку | від дії до першої реакції | інтерактивні програми |
| Справедливість | ніхто не голодує | багатокористувацькі системи |
Найпростіший спосіб підняти пропускну здатність — ставити довгі задачі підряд і не перемикатися взагалі. Найпростіший спосіб зменшити час відгуку — перемикатися якнайчастіше. Планувальник завжди живе десь між цими двома крайнощами.
Класичні алгоритми
Section titled “Класичні алгоритми”Три базові стратегії на одному наборі процесів. Процес A довгий, B і C короткі, усі готові з нульового моменту.
FCFS (first-come, first-served) є чергою в чистому вигляді. Простий і справедливий за порядком надходження, але катастрофічний, коли першою прийшла довга задача: два тривіальні процеси чекають по 24 одиниці через один чужий. Це називають ефектом конвою, коли одна довга задача збирає за собою хвіст із коротких.
SJF (shortest job first) пускає спершу найкоротші. Математично доведено, що він дає мінімальний середній час очікування, і водночас у чистому вигляді він незастосовний. Тривалість наступної задачі невідома наперед, а довгі процеси голодуватимуть, поки надходять короткі.
Round Robin роздає кожному по кванту, по колу. За середнім часом очікування він не найкращий, зате єдиний із трьох дає передбачуваний час відгуку: за один обхід черги процесор гарантовано дістанеться кожному. На цій ідеї й побудовані всі інтерактивні системи.
Розмір кванта тут завжди компроміс. Великий квант вироджує алгоритм у FCFS, малий покращує відгук, але частка процесорного часу, що йде на самі перемикання контексту, швидко стає неприйнятною.
Багаторівневі черги зі зворотним зв’язком
Section titled “Багаторівневі черги зі зворотним зв’язком”MLFQ є практичною відповіддю на проблему «SJF ідеальний, але тривалість невідома». Замість питати тривалість, планувальник спостерігає за поведінкою.
Влаштовано це так:
- процеси розкладені по кількох чергах із різним пріоритетом;
- новий процес потрапляє в найвищу, бо авансом вважається коротким;
- витратив увесь квант і не заблокувався — опускається на рівень нижче;
- заблокувався до кінця кванта, чекаючи на диск, мережу чи клавіатуру, — лишається де був.
Інтерактивні процеси більшість часу чекають на ввід, тому природно осідають у високих чергах і отримують швидкий відгук. Обчислювальні з’їдають кванти цілком і опускаються вниз, де процесор дістається їм рідше, зате довшими шматками, що добре для їхніх кешів.
Щоб довгі задачі не голодували назавжди, час від часу всі процеси піднімають назад угору. Це називається старінням.
Як це працює в Linux сьогодні
Section titled “Як це працює в Linux сьогодні”На MLFQ більшість курсів зупиняється, а Linux тим часом пішов далі.
CFS, completely fair scheduler, працював із 2007 по 2023 рік і відмовився
від фіксованих черг та квантів. Замість них він рахував для кожного процесу
віртуальний час виконання, тобто скільки той уже отримав процесора
з поправкою на вагу, і завжди пускав процес із найменшим значенням.
Процеси з меншою вагою накопичують віртуальний час швидше й повертаються
рідше, а nice задає якраз цю вагу.
У ядрі 6.6 CFS замінили на EEVDF, earliest eligible virtual deadline first. Відмінність у тому, що EEVDF враховує не тільки справедливість загалом, а й терміновість: кожному процесу приписується віртуальний дедлайн, і першим іде той, чий дедлайн найближчий. Інтерактивні задачі, яким потрібні короткі й часті відрізки, отримують процесор швидше, і загальний баланс від цього не страждає.
Окремо в Linux є класи планування, і вони важливіші за будь-які пріоритети всередині класу:
| Клас | Для чого |
|---|---|
SCHED_OTHER |
звичайні процеси, ними керує EEVDF |
SCHED_BATCH |
обчислення без вимог до відгуку |
SCHED_IDLE |
працює лише коли більше нікому |
SCHED_FIFO, SCHED_RR |
реальний час: витісняють усе зі SCHED_OTHER |
SCHED_DEADLINE |
задачі з явно заданим періодом і дедлайном |
Процес класу реального часу з пріоритетом 1 завжди виграє в процесу
SCHED_OTHER з nice -20. Це різні ліги, а не сусідні щаблі однієї шкали.
Як це насправді в Linux
Section titled “Як це насправді в Linux”chrt -p $$Клас планування і пріоритет поточної оболонки. Для звичайного процесу —
SCHED_OTHER з пріоритетом 0.
ps -eo pid,cls,rtprio,ni,pri,comm --sort=-rtprio | headCLS — клас (TS звичайний, FF/RR реального часу, IDL), RTPRIO —
пріоритет реального часу, NI — значення nice.
cat /proc/$$/sched | head -12Статистика планувальника для процесу: sum_exec_runtime — скільки процесорного
часу спожито, nr_switches — скільки разів його перемикали,
nr_involuntary_switches — скільки з них були витісненням.
grep -E 'ctxt|processes|procs_' /proc/statctxt — сумарна кількість контекстних перемикань з моменту завантаження.
Два виміри з паузою дають частоту перемикань — корисний показник,
коли система «зайнята, але нічого не робить».
taskset -c 0 nice -n 19 sh -c 'while :; do :; done' &sleep 3; ps -o pid,psr,ni,pcpu,comm -p $!; kill $!Процес прив’язується до нульового ядра з найнижчим пріоритетом.
PSR показує, на якому ядрі він фактично виконується.
Типові помилки розуміння
Section titled “Типові помилки розуміння”«nice задає відсоток процесора». Не задає. nice змінює вагу процесу
відносно інших, тож якщо конкурентів немає, процес із nice 19 спокійно
отримає всі сто відсотків: ділити просто нема з ким.
«Планувальник обирає, що виконувати». Обирає він лише серед готових. Заблокований процес у виборі не бере участі взагалі, хоч який у нього пріоритет.
«Високий пріоритет пришвидшить процес». Пришвидшить, тільки якщо процес
чекає на процесор. Коли він чекає на диск, пріоритет планування не змінює
нічого, і потрібен уже пріоритет вводу-виводу — ionice.
«Реальний час означає швидко». Означає передбачувано. SCHED_FIFO
гарантує, що звичайні задачі процес не витіснять, і саме тому зациклена
задача реального часу здатна підвісити систему: зупинити її нікому.
«Чим менший квант, тим кращий відгук». До певної межі так, а далі накладні витрати на перемикання починають з’їдати той самий процесорний час, який ви намагалися розподілити чесніше.
Перевір себе
Лабораторна
Section titled “Лабораторна”A2 — симулятор планувальника. FCFS, SJF, RR і MLFQ на одному наборі задач, з обчисленням часу очікування, обороту та відгуку. Мета — побачити, що жодна конфігурація не виграє за всіма метриками одночасно.
Джерела
Section titled “Джерела”- OSTEP, Scheduling: Introduction і MLFQ
- Silberschatz, Operating System Concepts, розділ 5
man 7 sched,man 1 chrt,man 1 nice,man 2 sched_setscheduler- Documentation/scheduler — зокрема опис EEVDF
- An EEVDF CPU scheduler for Linux — LWN про заміну CFS