Пріоритети, MLFQ, CFS і багатоядерне планування

Round-Robin ділить CPU приблизно порівну, але реальні навантаження різні: інтерактивний редактор має швидко реагувати, фонове кодування відео прагне пропускної здатності, а багатоядерна машина мусить ще й розподіляти роботу між CPU. Тому сучасний планувальник поєднує політику пріоритетів, облік минулої поведінки та апаратну топологію.

Цілі лекції

Після опрацювання матеріалу ви зможете:

• пояснити пріоритетне планування, starvation і aging;
• відрізнити multilevel queue від MLFQ;
• простежити переміщення CPU-bound та I/O-bound завдань у MLFQ;
• пояснити класичну модель Linux CFS через вагу і vruntime;
• коректно описати перехід нових ядер Linux від класичного вибору CFS до EEVDF;
• пояснити базові й динамічні пріоритети Windows;
• пов'язати CPU affinity, SMP, балансування навантаження та NUMA locality.

Передумови

Потрібно знати стани процесу й потоку, витискальне планування, квантування, FCFS, SJF і Round-Robin, а також різницю між часом очікування, відгуку й обороту.

1. Пріоритетне планування

Пріоритет задає відносну терміновість готового завдання. Планувальник обирає готове завдання з вищим пріоритетом; у витискальному варіанті його поява може перервати поточне виконання. Конкретна шкала залежить від ОС: більше число не завжди означає вищий пріоритет.

Нехай одночасно готові три завдання:

Сувора політика спершу вибере UI, потім compile, потім backup. Якщо завдання пріоритету 1 надходять постійно, backup може чекати невизначено довго. Це starvation, або голодування.

Aging поступово підвищує ефективний пріоритет завдання, яке довго чекає. Він не робить усі завдання однаковими, але обмежує ризик вічного очікування.

Не слід плутати пріоритет із правом на миттєве завершення. Вищий пріоритет лише впливає на вибір планувальника; потік усе одно може чекати I/O, блокування або доступного CPU.

2. Multilevel queue і MLFQ

У multilevel queue готові завдання наперед розподілено між кількома чергами, наприклад foreground і background. Кожна черга може мати власний алгоритм, але завдання зазвичай не переходять між чергами. Це проста, проте негнучка класифікація.

Multilevel Feedback Queue (MLFQ) додає зворотний зв'язок: рівень змінюється відповідно до спостережуваної поведінки. Типова навчальна політика:

1. Нове завдання потрапляє у верхню чергу.
2. Верхня черга має вищий пріоритет і коротший квант.
3. Завдання, яке повністю використало квант, переходить нижче.
4. Завдання, яке швидко заблокувалося на I/O, зберігає високий рівень.
5. Періодичний priority boost повертає завдання вище й протидіє starvation.

Приклад із квантами Q0 = 4 мс, Q1 = 8 мс, Q2 = 16 мс:

MLFQ наближено виявляє короткі інтерактивні bursts без знання їхньої майбутньої тривалості. Деталі не універсальні: кількість черг, кванти, правила обліку та boost є параметрами конкретної реалізації.

3. Класична модель Linux CFS

Completely Fair Scheduler (CFS) є важливою концептуальною моделлю планування звичайних задач Linux. Він уявляє ідеальний багатозадачний CPU, який ділить час між усіма runnable-завданнями одночасно, а реальний CPU наближує до цієї справедливості послідовним запуском.

Класичний CFS обліковує virtual runtime, або vruntime: отриманий CPU-час, нормалізований за вагою пріоритету. Завдання з меншою вагою накопичує vruntime швидше, тому раніше поступається CPU; завдання з більшою вагою отримує більшу частку.

Спрощено:

delta_vruntime ≈ delta_exec × NICE_0_LOAD / weight

Це не формула для ручного налаштування ядра, а спосіб зрозуміти облік. У класичному описі runnable-завдання зберігалися у впорядкованому red-black tree, а планувальник вибирав завдання з найменшим vruntime зліва. Після виконання його vruntime зростав, і дерево перевпорядковувалося.

У Linux користувацьке значення nice зазвичай лежить у межах від -20 до 19: менше nice означає більшу вагу, але зниження nice часто потребує додаткових прав. nice задає відносну частку для звичайного класу, а не жорсткий відсоток CPU.

Сучасна примітка: EEVDF

Починаючи з новіших гілок ядра Linux, перехід, розпочатий у районі Linux 6.6, замінив класичний вибір «лівого за vruntime» для fair-класу на підхід EEVDF (Earliest Eligible Virtual Deadline First). Він враховує придатність завдання до запуску та virtual deadline, краще виражаючи справедливість і latency request.

Тому коректне формулювання таке: CFS через ваги та віртуальний час залишається базовою навчальною концепцією, але алгоритм вибору в сучасному ядрі може бути EEVDF. Точні структури, параметри й поведінку треба звіряти з документацією та кодом конкретної версії ядра, а не переносити опис старої RB-tree реалізації на всі системи.

4. Динамічні пріоритети Windows

Windows планує потоки, а не абстрактні процеси. Для звичайних потоків базовий пріоритет утворюється з priority class процесу та relative priority потоку. Система може тимчасово підвищувати динамічний пріоритет, наприклад після завершення очікування певної події, щоб покращити інтерактивний відгук. Потім boost зменшується в напрямі базового рівня.

Це схоже на ідею feedback, але не означає, що Windows буквально реалізує показану вище навчальну MLFQ. Реальна політика залежить від версії, класу, типу очікування та системних правил.

Клас REALTIME_PRIORITY_CLASS небезпечний для звичайних програм: помилковий CPU-bound потік може завадити системним службам та інтерфейсу. Для навчальних спостережень не підвищуйте процеси до real-time.

5. SMP, affinity і балансування

SMP (Symmetric Multiprocessing) означає, що кілька логічних CPU спільно виконують завдання під керуванням однієї ОС. Планувальник має одночасно:

• не залишати CPU без роботи, коли є runnable-завдання;
• не перевантажувати один CPU;
• уникати зайвих міграцій;
• зберігати cache affinity, коли це вигідно;
• дотримуватися дозволеної CPU affinity.

CPU affinity - маска логічних CPU, на яких потоку дозволено виконуватися. Вузька маска може зробити експеримент повторюванішим, але також створити hotspot і заборонити планувальнику використовувати вільне ядро. Affinity не резервує CPU і не гарантує безперервного виконання.

Безпечні команди спостереження в Linux:

lscpu
ps -eo pid,comm,ni,pri,psr,stat --sort=pid
taskset -pc $$

PSR показує CPU, на якому завдання виконувалося останнім під час знімка; це не постійне закріплення. taskset -pc $$ читає affinity поточної оболонки без її зміни.

6. NUMA: баланс не лише за кількістю потоків

У NUMA (Non-Uniform Memory Access) CPU об'єднано у вузли з локальною пам'яттю. Доступ до локальної пам'яті зазвичай має меншу затримку, ніж до пам'яті іншого вузла. Отже, перенесення потоку на менш завантажений CPU може погіршити результат, якщо робочі сторінки лишилися віддаленими.

Планувальник і memory policy балансують суперечливі цілі:

вільний CPU  <->  теплий кеш  <->  локальна пам'ять  <->  дозволена affinity

На NUMA-системі структуру можна безпечно переглянути так:

numactl --hardware
numastat

Якщо numactl не встановлено або машина має один NUMA-вузол, це не помилка. У віртуальній машині топологія може бути спрощена й не відображати фізичний хост.

Практичні завдання

Завдання 1. Простежте MLFQ

Для Q0 = 4 мс, Q1 = 8 мс, Q2 = 16 мс простежте два завдання: A щоразу використовує весь квант, B виконується 1 мс і блокується на I/O. Запишіть рівень кожного після трьох запусків і поясніть різницю.

Завдання 2. Прочитайте знімок планувальника

Виконайте три команди спостереження з розділу про SMP. Знайдіть NI, PRI, PSR для оболонки та поясніть, чому один знімок PSR не доводить постійну affinity.

Завдання 3. Оберіть політику для сервера

Сервер має два NUMA-вузли. Потік обробки даних працює з 8 ГіБ сторінок на вузлі 0, а CPU вузла 1 менш завантажені. Опишіть, які вимірювання потрібні перед міграцією потоку та чому рішення лише за utilization може бути хибним.

Підсумок

• Пріоритет впливає на вибір, а aging протидіє starvation.
• Multilevel queue має переважно фіксовані класи; MLFQ змінює рівень за поведінкою.
• CPU-bound завдання типово спускається в MLFQ, а коротке інтерактивне зберігає швидкий відгук.
• Класична модель CFS нормалізує отриманий час через вагу та vruntime.
• Нові ядра Linux перейшли від класичного RB-tree вибору CFS до EEVDF; деталі залежать від версії.
• Windows поєднує базові пріоритети з контрольованими динамічними boosts.
• Affinity обмежує дозволені CPU, але не резервує їх.
• У SMP потрібен баланс навантаження, а в NUMA - ще й локальність пам'яті.