Планувальник завдань Linux, Linux, Операційні системи, статті

Ядро Linux продовжує розвиватися – з’являється підтримка новітніх технологій, ростуть надійність, масштабованість і продуктивність. Одним з найважливіших компонентів ядра версії 2.6 є планувальник завдань, розроблений Інго Молнаром (Ingo Molnar). Даний планувальник є динамічним, підтримує розподіл навантаження, а його алгоритм має складність O (1). Дана стаття розповість про ці та деяких інші властивості планувальника.


В даній статті наведено огляд планувальника завдань Linux 2.6 і його найбільш важливих властивостей. Але перед тим, як зануритися в деталі пристрою планувальника, пропоную розібратися з його основними завданнями.


Що таке планувальник завдань?


У загальному значенні терміна, операційна система є посередником між додатками і ресурсами. До ресурсів зазвичай відносять пам’ять і фізичні пристрої. Але центральний процесор (ЦП) можна також вважати ресурсом, який планувальник на деякий час (що вимірюється у відрізках) виділяє завданню. Планувальник забезпечує паралельне виконання декількох програм, розподіляючи ресурси ЦП між різними завданнями різних користувачів.


Важливою метою планувальника є ефективний розподіл відрізків процесорного часу за умови забезпечення користувачеві часу очікування на прийнятному рівні. Крім цього, перед планувальником можуть стояти суперечать один одному цілі, такі, як мінімізація часу очікування при виконанні критично важливих задач реального часу і максимальне використання ресурсів ЦП. Подивимося, як планувальник задач Linux 2.6 справляється з досягненням цих цілей в порівнянні зі своїми попередниками.


Проблеми попередніх версій планувальників завдань Linux


До виходу ядра версії 2.6 планувальник мав істотне обмеження, що виявлялося при великій кількості виконуються завдань. Причиною тому був алгоритм планувальника, який мав складність O (n). При його використанні час, що витрачається на планування, знаходиться у функціональній залежності від числа завдань, що виконуються в системі. Іншими словами, чим більше число завдань (n), тим більше часу потрібно на їх планування. При дуже високому навантаженні планування може зайняти майже все процесорний час, залишивши власне завданням лише малу його частку. Таким чином, алгоритму не вистачало масштабованості.


Планувальник, що застосовувався до виходу версії 2.6, також використовував єдину чергу завдань для симетричних мультипроцесорних (SMP) систем. Це означало, що завдання могла бути призначена будь-якого з процесорів, що добре для розподілу навантаження, але погано для кешування. Уявімо, наприклад, що завдання виконується на ЦП-1 і її дані знаходяться в кеші цього процесора. Якщо завдання буде перепланована на ЦП-2, її дані потрібно прибрати з кеша ЦП-1 і розмістити в кеші ЦП-2.


Крім того, попередня реалізація планувальника використовувала єдину блокування черги задач, через що на SMP-системах кілька процесорів не могли одночасно виконувати такі маніпуляції з чергою, як вибір завдання для виконання. Це призводило до простою процесорів, які очікують звільнення блокування черги завдань і, як наслідок, до падіння продуктивності.


На довершення всього, планувальник не підтримував витіснення. Це означало, що завдання, що має високий пріоритет могла очікувати завершення завдання з нижчим пріоритетом.


Знайомство з планувальником завдань Linux 2.6


Планувальник версії 2.6 спроектований і розроблений Інго Молнаром. Інго бере участь в розробці ядра Linux з 1995 р. Він задався метою створити новий планувальник виключно на основі алгоритмів складності O (1) для пробудження процесів, перемикання контекстів і обробки переривання таймера. Однією з причин виникнення потреби в новому планувальнику були віртуальні машини Java ™ (JVM). Модель програмування цієї мови активно використовує потоки, що призводить до зростання накладних витрат при використанні планувальника з алгоритмом О (n). Планувальник з алгоритмом O (1) не має даного недоліку, оскільки його продуктивність не погіршується при високому навантаженні. Це дозволяє забезпечити ефективну роботу віртуальних машин Java ™.


Крім усунення інших недоліків, в планувальнику версії 2.6 вирішені три основні проблеми, властиві його попереднику (O (n) і проблеми масштабованості на багатопроцесорних системах). Зараз ми розглянемо загальні принципи пристрою планувальника версії 2.6.


Основні структури даних


Почнемо з огляду структур даних, використовуваних планувальником. Кожен ЦП має чергу завдань, що складається з 140 списків, що обслуговуються в порядку FIFO і містять завдання, що мають відповідний пріоритет. Завдання, заплановані до виконання, додаються в кінець списку. Кожній задачі виділяється відрізок часу, що визначає тривалість її виконання. Перші 100 списків черги завдань зарезервовані для задач реального часу, а останні 40 – для користувача завдань (див. малюнок 1). Пізніше ви зрозумієте важливість цього розмежування.


Рисунок 1. Структура черги завдань планувальника версії 2.6



Крім черги завдань ЦП, званої активної чергою задач, існує ще неактивна чергу. Після того, як завдання, що знаходиться в активній черги, вичерпує відведений їй час, вона переноситься в неактивну чергу. При перенесенні відбувається перерахунок її відрізка часу (також перераховується її пріоритет, але про це пізніше). Якщо в активній черги відсутні завдання з даним пріоритетом, відповідні покажчики активної і неактивної черг міняються місцями, при цьому неактивний список стає активним.


Робота планувальника завдань не відрізняється складністю: він просто вибирає завдання для виконання зі списку з найвищим пріоритетом. Щоб підвищити ефективність цього процесу, для визначення наявності завдань в списку використовується бітовий масив. Отже, для пошуку біта, відповідного списку з найвищим пріоритетом, можна використовувати інструкцію find-first-bit-set, Яку підтримує більшість архітектур процесорів. Час, що витрачається на пошук завдання, залежить не від числа активних завдань, а від числа пріоритетів. Отже, планувальник версії 2.6 є процесом складності O (1), оскільки час, що витрачається на планування завдання постійно і детерміністичного незалежно від числа активних завдань.


Покращена підтримка симетричної багатопроцесорної обробки


Отже, що ж таке симетрична багатопроцесорна обробка? Це архітектура, яка забезпечує одночасне виконання окремих завдань на декількох ЦП, на відміну від традиційної асиметричної обробки, при якій всі завдання виконуються єдиним ЦП. Симетрична багатопроцесорна обробка може бути корисною для багатопотокових додатків.


Незважаючи на те, що попередня реалізація планувальника мала підтримку багатопроцесорних систем, архітектура її механізму блокувань мала особливість, через яку процесорам доводилося чекати звільнення черзі завдань, заблокованої іншим процесором на час вибору завдання для виконання. У планувальнику версії 2.6 ця проблема усунена – тепер черги завдань мають незалежну блокування, що дозволяє будь ЦП здійснювати планування завдань, не створюючи перешкод іншим процесорам.


Крім того, наявність у кожного ЦП окремої черги в загальному випадку забезпечує прив’язку завдання до процесора, що сприяє ефективному використанню його “гарячого” кеша.


Витіснення завдань


Ще однією перевагою планувальника версії 2.6 є підтримка витіснення. Це означає, що завдання з більш низьким пріоритетом не буде виконуватися, якщо інше завдання, що має більш високий пріоритет, буде готова до виконання. Планувальник витіснить процес з низьким пріоритетом, помістить його назад до списку і повторить планування.


Стривайте, це ще не все!


Крім реалізації алгоритмів складності O (1) і механізмів витіснення, в новому планувальнику з’явилася підтримка динамічного призначення пріоритетів завдань і розподілу навантаження між процесорами. Давайте подивимося, яка, власне, користь від цих нових можливостей.


Динамічне призначення пріоритетів завдань


Для запобігання повного завантаження процесора єдиним завданням і викликаного цим відсутності доступу інших завдань до ЦП, планувальник версії 2.6 може динамічно змінювати пріоритет завдань. Це досягається шляхом “штрафування” задач, обмежених швидкістю процесора і “нагородження” задач, обмежених швидкістю вводу / виводу. Завдання, обмежені швидкістю вводу / виводу, зазвичай створюють навантаження на ЦП при підготовці операцій введення / виводу і, потім, очікують їх завершення. Даний тип поведінки дозволяє іншим задачам отримати доступ до ЦП.


Оскільки завдання, обмежені швидкістю вводу / виводу вважаються невимогливими до обчислювальних ресурсів, їх пріоритет, в якості нагороди, знижується на величину до п’яти рівнів. Завдання, обмежені продуктивністю ЦП, “караються” підвищенням пріоритету також на величину до п’яти рівнів.


Належність завдання до класу обмежених швидкістю вводу / виводу або обмежених продуктивністю ЦП визначається за допомогою евристичної процедури обчислення інтерактивності. Метрика інтерактивності завдання обчислюється шляхом порівняння часу виконання завдання і часу, протягом якого завдання знаходиться в стані очікування. Слід зауважити, що, оскільки завдання, обмежені швидкістю вводу / виводу, планують операції введення / виводу і, потім, очікують їх завершення, більшу частину часу вони проводять в очікуванні, що підвищує їх метрику інтерактивності.


Важливо зауважити, що корекція пріоритету проводиться тільки для користувача завдань – завдання реального часу це не зачіпає.


Розподіл навантаження в симетричних багатопроцесорних системах


Завдання, запущені в SMP-системі, потрапляють в чергу завдань одного з ЦП. У загальному випадку неможливо передбачити, чи завершиться завдання майже відразу або буде виконуватися протягом тривалого часу. Отже, початкове розподіл завдань по ЦП швидше за все буде неоптимальним.


Для того щоб забезпечити збалансовану завантаження процесорів, необхідно перерозподіл завдань шляхом їх перенесення з перевантаженого ЦП на неповних. Планувальник Linux 2.6 робить це шляхом розподілу навантаження. Кожні 200 мілісекунд планувальник перевіряє, збалансована чи навантаження на процесори. Якщо ні, проводиться перенесення завдань між ними.


Даний процес має негативний аспект, що полягає в тому, що кеш процесора, на який тільки що була перенесена задача, є для неї “холодним” (вимагає заповнення даними).


Тепер згадаємо, що кеш ЦП являє собою локальну (що знаходиться безпосередньо в ЦП) пам’ять, що забезпечує більш високу, ніж системна пам’ять швидкість доступу. Локальний кеш ЦП вважається “гарячим “Якщо містить дані завдання, що виконується на цьому процесорі. Якщо ж таких даних в кеші немає, то для даної задачі він вважається” холодним “.


На жаль, забезпечення повного завантаження ЦП шляхом переносу завдань призводить до виникнення такої неприємної проблеми, як “холодний” кеш.


Тут є ще багато цікавого


Вихідний код планувальника версії 2.6 компактно розміщується у файлі / usr / src / linux / kernel / sched.c. Список найбільш цікавих функцій, які перебувають у даному файлі, наведено в таблиці 1.






























Таблиця 1. Функції, складові код планувальника версії 2.6


Ім’я функції


Опис функції

schedule  Головна функція планувальника. Планує виконання завдання з найвищим пріоритетом.
load_balance  Перевіряє, не потрібно чи перерозподіл навантаження і, в разі необхідності, робить спробу перенесення завдань.
effective_prio  Повертає ефективний пріоритет завдання (розрахований на основі статичного пріоритету задачі і всіх “нагород” і “штрафів”).
recalc_task_prio  Обчислює “нагороду” або “штраф” для зазначеного завдання на основі часу простою.
source_load  Обчислює консервативну оцінку завантаження ЦП-джерела (з якого може бути перенесена задача).
target_load  Обчислює ліберальну оцінку завантаження цільового ЦП (на який може бути потенційно перенесена задача).
migration_thread  Високопріоритетний системний потік, який здійснює міграцію завдань між ЦП.


Крім того, у файлі / usr / src / linux / kernel / sched.c можна знайти структуру черги завдань. Новий планувальник також має функцію збору статистики, яку можна активувати за допомогою параметра конфігурації ядра CONFIG_SCHEDSTATS. Зібрана статистика може бути отримана з файлу / proc / schedstat, що знаходиться в файловій системі / proc, і містить різні відомості по кожному ЦП системи, включаючи статистику розподілу навантаження і перенесення завдань.


Забігаючи вперед


Планувальник версії 2.6 значно просунувся у розвитку в порівнянні зі своїми попередниками. Були зроблені величезні кроки в галузі підвищення завантаженості ЦП при одночасному зниженні часу відгуку. Підтримка механізму витіснення і покращена підтримка багатопроцесорних архітектур наближають до реальності ідею операційної системи, однаково ефективної на робочих станціях і системах реального часу. Ядро Linux 2.8 з’явиться ще нескоро, але, судячи зі змін у версії 2.6, попереду нас чекає багато цікавого.

Схожі статті:


Сподобалася стаття? Ви можете залишити відгук або підписатися на RSS , щоб автоматично отримувати інформацію про нові статтях.

Коментарів поки що немає.

Ваш отзыв

Поділ на параграфи відбувається автоматично, адреса електронної пошти ніколи не буде опублікований, допустимий HTML: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

*

*