Алгоритм планування – ЧАСТИНА 2

struct prio_array (

int nr_active / * Кількість завдань * / unsigned long bitmap [BITMAP_SIZE] / * Бітова маска пріоритетів * / struct list head queue [MAX_PRIO] / * черги пріоритетів * /

}

Константа MAX_PRIO – це кількість рівнів пріоритету в системі За замовчуванням значення цієї константи одно 140 Таким чином, для кожного значення пріоритету виділена одна структура struc t list_head Константа BITMAP_SIZE – це розмір масиву змінних, кожен елемент якого має тип unsigne d long Кожен біт цього масиву відповідає одному дійсному значенню пріоритету У разі 140 рівнів пріоритетів і при використанні 32-розрядних машинних слів, значення константи BITMAP_SIZE дорівнює 5 Таким чином, поле bitma p – це масив з пяти елементів, який має довжину 160 біт

Всі масиви пріоритетів містять поле bitmap, кожен біт цього поля відповідає одному значенню пріоритету в системі На самому початку значення всіх бітів рівні 0 Коли завдання з певним пріоритетом стає готовою до виконання (тобто значення статусу цього завдання стає рівним TASK_RUNNING), відповідний цьому пріоритету біт поля bitma p встановлюється в значення 1 Наприклад, якщо завдання з пріоритетом, рівним 7, готова до виконання, то встановлюється біт номер 7 Знаходження завдання з найвищим пріоритетом в системі зводиться тільки лише до знаходженню самого першого встановленого біта в бітовій масці Так як кількість пріоритетів незмінно, то час, який необхідно витратити на цю операцію пошуку, постійно і не залежить від кількості процесів, що виконуються в системі Більше того, для кожної підтримуваної апаратної платформи в ОС Linux повинен бути реалізований швидкий алгоритм пошуку першого встановленого біта (find first set) для проведення швидкого пошуку в бітовій масці Ця функція називається sched_find_first_bi t () Для багатьох апаратних платформ існує машинна інструкція знаходження першого встановленого біта в заданому машинному слове4 Для таких систем знаходження першого встановленого біта є тривіальною операцій і зводиться до виконання цієї інструкції кілька разів

Кожен масив пріоритетів також містить масив черг, представлених структурами struc t list_head Цей масив називається queue Кожному значенню пріоритету відповідає своя черга Черги реалізовані у вигляді повязаних списків, і кожному значенню пріоритету відповідає список всіх процесів системи, готових до виконання, що мають це значення пріоритету і знаходяться в черзі виконання даного процесора Знаходження завдання, яке буде виконуватися наступним, є простим завданням і зводиться до вибору наступного елемента зі списку Всі завдання з однаковим пріоритетом плануються на виконання циклічно

Масив пріоритетів також містить лічильник nr_active, значення якого відповідає кількості готових до виконання завдань у даному масиві пріоритетів

Перерахунок квантів часу

У багатьох операційних системах (включаючи і більш старі версії ОС Linux) використовується прямий метод для перерахування значення кванта часу кожного завдання, коли всі ці значення досягають нуля

4 Для апаратної платформи х86 використовується інструкціяbsfl,  а для платформ и РРС – Інструкція яcntlzw

Зазвичай це реалізується за допомогою циклу по всіх завдань в системі, наприклад, наступним чином

for (кожного завдання в системі) (

перерахувати значення пріоритету

перерахувати значення кванта часу

}

Значення пріоритету та інші атрибути завдання використовуються для визначення нового значення кванта часу Такий підхід має деякі проблеми

• Перерахунок потенційно може зайняти багато часу Гірше того, час такого розрахунку масштабується як О (n), де n – кількість завдань в системі

• Під час перерахунку повинен бути використаний який-небудь тип блокування для захисту списку завдань і окремих дескрипторів процесів У результаті виходить високий рівень конфліктів при захопленні блокувань

• Відсутність визначеності в випадково виникають перерахунках значень квантів часу є проблемою для програм реального часу

• Відверто кажучи, це просто негарно (що є цілком виправданою причиною для яких удосконалень ядра Linux)

Новий планувальник ОС Linux дозволяє уникнути використання циклу перерахунку пріоритетів Замість цього в ньому застосовується два масиву пріоритетів для кожного процесора: активний (active) і минулий (expired) Активний масив пріоритетів містить чергу, в яку включені всі завдання відповідної черги виконання, для яких ще не вичерпався квант часу Минулий масив пріоритетів містить всі завдання відповідної черги, які витратили свій квант часу Коли значення кванта часу для будь-якого завдання стає рівним нулю, то перед тим, як помістити це завдання в минулий масив пріоритетів, для нього обчислюється нове значення кванта часу Перерахунок значень кванта часу для всіх процесів проводиться за допомогою перестановки активного і минув масивів місцями Так як на масиви посилаються за допомогою покажчиків, то перемикання між ними буде виконуватися так само швидко, як і перестановка двох покажчиків місцями Показаний нижче код виконується в функції schedule ()

struct prio_array array = rq-&gtactive

if (array-&gtnr_active) {

rq-&gtactive = rq-&gtexpired

rq-&gtexpired = array

}

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

Функція schedule ()

Всі дії з вибору наступного завдання на виконання і перемикання на виконання цього завдання реалізовані у вигляді функції schedul e () Ця функція викликається явно кодом ядра при переході в призупинене стан (sleep), a також у разі коли якесь завдання витісняється Функція schedule () виконується незалежно кожним процесором Отже, кожен процесор самостійно приймає рішення про те, який процес виконувати наступним

Функція schedule () досить проста, враховуючи характер тих дій, які вона виконує Наступний код дозволяє визначити завдання з найвищим пріоритетом

struct task_struct *prev, *next

struct list_head *queue struct prio_array *array int idx

prev = current

array = rq-&gtactive

idx = sched_find_first_bit(array-&gtbitmap)

queue = array-&gtqueue + idx

next = list entry(queue-&gtnext, struct task struct, run_ist)

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

schedule()

Біт 0 пріоритет 0

sched_find_first_set()

Біт 7 пріоритет 7

Список всіх готових до виконання завдань а відповідно

з їх пріоритетами

Масив пріоритетів

довжиною 140 біт Біт 139 пріоритет 139

Запуск першого процесу в списку

Список готових

до виконання завдань, що мають пріоритет 7

Рис 42 Алгоритм роботи О (1)-планіровщка операційної системи Linux

Якщо отримані значення змінних pre v і next не рівні один одному, то для виконання вибирається нове завдання (next) При цьому для перемикання з завдання, на яке вказує змінна prev, на завдання, відповідне змінної next, викликається функція context_switc h (), що залежить від апаратної платформи Перемикання контексту буде розглянуто в одному з наступних розділів

У розглянутому коді слід звернути увагу на два важливі моменти Поперше, він дуже простий і, отже, дуже швидкий По-друге, кількість процесів у системі не впливає на час виконання цього коду Для знаходження найбільш відповідного для виконання процесу не використовуються цикли Насправді ніякі чинники не впливають на час, за який функція schedul e () здійснює пошук найбільш підходящого для виконання завдання Час виконання цієї операції завжди постійно

Обчислення пріоритетів і квантів часу

На початку цієї глави було розглянуто, як пріоритет і квант часу використовуються для того, щоб впливати на ті рішення, які приймає планувальник Крім того, були розглянуті процеси, обмежені швидкістю введення-виведення і швидкістю процесора, а також було описано, чому бажано піднімати пріоритет інтерактивних завдань Тепер давайте розглянемо код, який реалізує ці міркування

Процеси мають початкове значення пріоритету, яке називається nice Це значення може лежати в діапазоні від -20 до +19, за умовчанням використовується значення 0 Значення 19 відповідає найбільш низькому пріоритету, а значення -20 – найбільш високого Значення параметра nice зберігається в полі static_pri o структури task_struc t процесу Це значення називається статичним пріоритетом, тому що воно не змінюється планувальником і залишається таким, яким його вказав користувач Планувальник свої рішення засновує на динамічному пріоритеті, яке зберігається в полі prio Динамічний пріоритет обчислюється як функція статичної пріоритету та інтерактивності завдання

Джерело: Лав, Роберт Розробка ядра Linux, 2-е видання : Пер з англ – М: ТОВ «ІД Вільямс »2006 – 448 с : Ил – Парал тит англ

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


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

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

Ваш отзыв

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

*

*