1. Що таке планувальник завдань?
2. Проблеми попередніх версій планувальників завдань Linux
3. Знайомство з планувальником завдань Linux 2.6
4. Основні структури даних
5. Малюнок 1. Структура черзі завдань планувальника версії 2.6
6. Покращена підтримка симетричній багатопроцесорної обробки
7. витіснення завдань
8. Стривайте, це ще не все!
9. Динамічне призначення пріоритетів завдань
10. Зниження часу відгуку
11. Розподіл навантаження в симетричних багатопроцесорних системах
12. Тут є ще багато цікавого
13. Забігаючи наперед
14. Ресурси для скачування

Остання версія найважливішого компонента ядра підвищує масштабованість

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

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

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

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

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

Про важливість O-нотації

O-нотація дозволяє оцінити кількість часу, що витрачається на виконання алгоритму. Час, що витрачається алгоритмом O (n) лінійно залежить від обсягу вхідних даних n, тоді як алгоритм O (n ^ 2) витратить час, що дорівнює квадрату цього обсягу. Алгоритм О (1) не залежить від обсягу вхідних даних і виконується за постійне час.

До виходу ядра версії 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, попереду нас чекає багато цікавого.

Ресурси для скачування

Схожі теми

• оригінал статті Inside the Linux scheduler (EN).
• На сайті Linux Kernel Archives можна знайти останню версію ядра Linux.
• У статті " Improving Linux kernel performance and scalability "(EN) (developerWorks, січень 2003) розповідається про те, як заміряти продуктивність ядра Linux для подальшої настройки системи (включаючи настройку планувальника).
• огляд Linux Process Scheduler Improvements in Version 2.6.0 (EN), підготовлений Open Source Development Labs, містить достовірні дані по поліпшень в планувальнику версії 2.6 в порівнянні з версією 2.4 на прикладі різних багатопроцесорних конфігурацій.
• Стаття " Linux Kernel 2.6: the Future of Embedded Computing "(EN) (Linux Journal, березень 2004 року) розповідає про частину найважливіших можливостей ядра версії 2.6, включаючи планування завдань і його вплив на вбудовані системи.
• Стаття " Kernel comparison: Improvements in kernel development from 2.4 to 2.6 "(EN) (developerWorks, лютий 2004 року) дозволить поглянути на інструменти, тести і методи за лаштунками процесу створення ядра 2,6.
• IBM Redbook An Application Centric Performance Evaluation of the Linux 2.6 Operating System (EN) (липень 2004 року) містить докладні відомості про масштабованості і різних аспектах продуктивності реальних додатків в середовищі Linux 2.6.
• Стаття " Migrating from Linux 2.4 to 2.6 on iSeries and pSeries "(EN) (developerWorks, липень 2004 року) містить огляд відмінностей між версіями 2.4 і 2.6 ядра Linux на платформі POWER.
• У статті " Linux 2.6 for Embedded Systems - Closing in on Real Time "(EN) (RTC Magazine, листопад 2003 р г.) обговорюється думка, згідно з яким для вбудованих систем реального часу кращою реалізацією планувальника є 2.6.
• Доктор Ульріх Вейганд (Dr. Ulrich Weigand) розповідає в своїй презентації What's New in Linux 2.6 (EN) про те, як Linux 2.6 допомагає в розвитку платформи IBM zSeries.
• В розділі Linux сайту developerWorks можна знайти інші матеріали для Linux-розробників.
• Почніть ваш наступний проект для Linux з ознайомчими версіями ПЗ IBM , Завантажити які можна безпосередньо з сайту developerWorks. (EN)

Підпишіть мене на повідомлення до коментарів