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

Функція effective_pri o () повертає значення динамічного пріоритету завдання Ця функція виходить із значення параметра пicе для даної задачі і обчислює для цього значення надбавку або штраф у діапазоні від -5 до +5, в залежності від інтерактивності завдання Наприклад, завдання з високою інтерактивністю, яке має значення параметра nice, рівне 10, може мати динамічний пріоритет, рівний 5 І навпаки, програма зі значенням параметра nice, рівним 10, яка досить активно використовує процесор, може мати динамічний пріоритет, рівний 12 Завдання, які володіють помірною інтерактивністю, не отримують ні надбавки, ні штрафу, і їх динамічний пріоритет збігається зі значенням параметраnice

Звичайно, планувальник за помахом чарівної палички не може визначити, який процес є інтерактивним Для визначення необхідна деяка евристика, яка відображає, чи є процес обмеженим швидкістю введення-виведення або швидкістю процесора Найбільш виразний показник – скільки часу задача знаходиться в загальмованому стані (sleep) Якщо завдання проводить більшу частину часу в загальмованому стані, то вона обмежена введенням-висновком Якщо завдання більше часу перебуває в стані готовності до виконання, ніж у при-

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

Для реалізації такої евристики в ядрі Linux передбачений змінюваний показник того, як співвідноситься час, який процес проводить у загальмованому стані, з часом, який процес проводить в стані готовності до виконання Значення цього показника зберігається в полі sleep_av g структури task_struct Діапазон значень цього показника лежить від нуля до значення MAX_SLEEP_AVG, яке за замовчуванням дорівнює 10 мс Коли завдання стає готовою до виконання після припиненого стану, значення поля sleep_avg збільшується на значення часу, який процес провів у загальмованому стані, поки значення sleep_av g не досягне MAX_SLEEP_AVG Коли завдання виконується, то протягом кожного імпульсу таймера (timer tick) значення цієї змінної зменшується, поки воно не досягне значення 0

Такий показник є, на подив, надійним Він розраховується не тільки на підставі того, як довго завдання знаходиться в загальмованому стані, а й на підставі того, наскільки мало завдання виконується Таким чином, завдання, яка проводить багато часу в загальмованому стані і в той же час постійно використовує свій квант часу, не отримає великий прибавки до пріоритету: показник працює не тільки для заохочення інтерактивних завдань, але і для покарання завдань, обмежених швидкістю процесора Цей показник також стійкий по відношенню до зловживань Завдання, яке отримує підвищену Значення пріоритету і велике значення кванта часу, швидко втратить свою надбавку до пріоритету, якщо вона постійно виконується і сильно завантажує процесор Зрештою, такий показник забезпечує малий час реакції Щойно створений інтерактивний процес швидко досягне високого значення поля sleep_avg Незважаючи на все сказане, надбавка і штраф застосовуються до значення параметра nice, так що користувач також може впливати на роботу системного планувальника шляхом зміни значення параметра nice процесу

Розрахунок значення кванта часу, навпаки, більш простий, оскільки значення динамічного пріоритету вже базується на значенні параметра nice і на інтерактивності (ці показники планувальник враховує як найбільш важливі) Тому тривалість кванта часу може бути просто виражена через значення динамічного пріоритету Коли створюється новий процес, породжений і батьківський процеси ділять навпіл решту кванта часу батьківського процесу Такий підхід забезпечує равнодоступность ресурсів і запобігає можливість отримання нескінченного значення кванта часу шляхом постійного створення породжених процесів Однак після того, як квант часу завдання вичерпується, це значення перераховується на підставі динамічного пріоритету завдання Функція task_timeslic e () повертає нове значення кванта часу для даного завдання Розрахунок просто зводиться до масштабування значення пріоритету в діапазон значень квантів часу Чим більше значення пріоритету завдання, тим більшої тривалості квант часу отримає завдання в поточному циклі виконання Максимальне значення кванта часу одно MAX_TIMESLICE, яке за замовчуванням дорівнює 200 мс Навіть завдання з найнижчим пріоритетом отримують квант часу тривалістю MIN_TIMESLICE, що відповідає 10 мс

Завдання з пріоритетом, використовуваним за замовчуванням (значення параметра nice, одно О і відсутня надбавка та штраф за інтерактивність), отримують квантчасу тривалістю 100 мс, як показано в табл 41

Таблиця 41 Тривалості квантів часу планувальника

Тип завдання

Значення параметра nice

Тривалість кванта часу

Новостворене Те ж, що і у батьківського Половина від батьківського процесу процесу

Мінімальний пріоритет +19 5 мс (MIN_TIMESUCE) Пріоритет за замовчуванням 0100 мс (DEF_TIMESLICE) Максимальний пріоритет -20800 мс (MAX_TIMESLICE)

Для інтерактивних завдань планувальник надає додаткову послугу: якщо завдання досить інтерактивно, то при вичерпанні свого кванта часу воно буде поміщено не в минулий масив пріоритетів, а назад в активний масив пріоритетів Слід згадати, що перерахунок значень квантон часу проводиться шляхом перестановки активного і минув масивів пріоритетів: активний масив стає вичерпаним, а минулий-активним Така процедура забезпечує перерахунок значень квантів часу, який масштабується за часом як O (1) З іншого боку, це може призвести до того, що інтерактивне завдання стане готовим до виконання, але не отримає можливості виконуватися, тому що воно застрягло в минулому масиві Приміщення інтерактивних завдань знову в активний масив дозволяє уникнути такої проблеми Слід зауважити, що це завдання не виконуватиметься відразу ж, а буде заплановано на виконання по колу разом з іншими завданнями, які мають такий же пріоритет Дану логіку реалізує функція scheduler_tic k (), яка викликається обробником переривань таймера (обговорюється в главі 10, Таймери та управління часом), як показано нижче

struct task_struct *task = current

struct runqueue *rq = this_rq()

if (–task-&gttime_slice) {

if (TASK_INTERACTIVE(task) || EXPIRED_STARVING(rq))

enqueue_task(task, rq-&gtexpired)

else

}

enqueue_task(task, rq-&gtactive)

Показаний код зменшує значення кванта часу процесу і перевіряє, чи не стало це значення рівним нулю Якщо стало, то завдання є вичерпаним і його необхідно помістити в один з масивів Для цього код спочатку перевіряє інтерактивність завдання за допомогою макросу ТАSK_INTERACTIVE () Цей макрос на підставі значення параметра nice розраховує, чи є завдання досить інтерактивним. Чим менше значення nice (Чим вище пріоритет), тим менш інтерактивним має бути завдання Завдання зі значенням параметра nice,  рівним 19, ніколи не може бути достатньо інтерактивним для приміщення назад в актив-

ний масив Навпаки, завдання зі значенням nice,  рівним -20, повинно дуже сильно використовувати процесор, щоб його не помістили в активний масив Завдання зі значенням nice,  використовуваним за замовчуванням, тобто рівним нулю, повинна бути досить інтерактивною, щоб бути вміщеній назад в активний масив, але це також відпрацьовується досить чітко Наступний макрос, EXPIRED_STARVING (), перевіряє, чи немає в минулому масиві процесів, особливо нужденних у виконанні (startving),  коли масиви не перемикайтеся протягом досить довгого часу Якщо масиви давно не переключалися, то зворотне приміщення завдання в активний масив ще більше затримає перемикання, чт про призведе до того, що завдання в минулому масиві ще більше потребуватимуть виконанні Якщо це не так, то завдання може бути поміщена назад в активний масив В інших випадках задача поміщається в минулий масив, що зустрічається найчастіше

Перехід в призупинене стан і повернення до виконання

Припинене стан завдання (стан очікування, заблоковане стан, sleeping,  blocked)  являє собою спеціальне стан завдання, в якому завдання не виконується Це є дуже важливим, тому що в противному випадку планувальник вибирав би на виконання завдання, які не «хочуть виконуватися, або, гірше того, стан очікування мало б бути реалізовано у вигляді циклу, що займає час процесора Завдання можуть переходити в призупинене стан з кількох причин, але в кожному разі-в очікуванні настання деякої події Подією може бути очікування настання деякого моменту часу, очікування наступної порції даних при файловому введенні-ниводе або інша подія в апаратному забезпеченні Завдання також може переходити в призупинене стан мимовільним чином, коли вона намагається захопити семафор в режимі ядра (ця ситуація розглянута в розділі 9, Засоби синхронізації в ядрі) Звичайна причина переходу в призупинене стан – це виконання операцій файлового введення-виведення, наприклад завдання викликає функцію rea d () для файлу, який необхідно вважати з диска Ще один приклад-задача може очікувати на введення даних з клавіатури У будь-якому випадку ядро поводиться однаково: завдання позначає себе як що знаходиться в загальмованому стані, поміщає себе в чергу очікування (wail queue), видаляє себе з черги виконання і викликає функцію schedule d для вибору нового процесу на виконання Повернення до виконання (wake up) відбувається в зворотному порядку: завдання позначає себе як готову до виконання, видаляє себе з черги очікування і помепгает себе в чергу виконання

Як вказувалося в попередньому розділі, з призупиненим станом повязані два значення поля стану процесу: TASK_INTERRUPTIBLE і TASK_UNINTERRUPTIBLE Вони відрізняються тільки тим, що в стані TASK_UNINTERRUPTIBLE завдання ігнорує сигнали, в той час як завдання в стані TASK_INTERRUPTIBLE повертаються до виконання передчасно і обробляють прийшов сигнал Обидва типи завдань, знаходяться в загальмованому стані, поміщаються в чергу очікування, очікують настання деякої події і не готові до виконання

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

(Wait queue) Черга очікування-це просто список процесів, які очікують

настання деякої події Черги очікування в ядрі представляються за допомогою типу даних wait_queue_head_t Вони можуть бути створені статично за допомогою макросу DECLARE_WAIT_QUEUE_HEAD () Або виділені динамічно з подальшою ініціалізацією за допомогою функції init_waitqueue_hea d () Процеси поміщають себе в чергу очікування і встановлюють себе в призупинене стан Коли відбувається подія, повязана з чергою очікування, процеси, що знаходяться в цій черзі, повертаються до виконання Важливо реалізувати перехід в призупинене стан і повернення до виконання правильно, так щоб уникнути конкуренції за ресурси (race)

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

/* нехай q – це черга очікування (створена в іншому місці), де ми хочемо перебувати в загальмованому стані * /

DECLARE_WAITQUEUE(wait, current)

add_wait_queue(q, &ampwait)

set_current_State (TASK_INTERRUPTIBLE) / * Або TASK_UNINTERRUPTIBLE * /

/ * Змінна condition характеризує настання події, якого ми очікуємо * /

while (condition)

schedule() set_current_state(TASK_RUNNING) remove_wait queue(q, &ampwait)

Опишемо кроки, які повинна виконати завдання для того, щоб помістити себе в чергу очікування

• Створити елемент черги очікування за допомогою макросу DECLARE_WAITQUEUE ()

• Додати себе в чергу очікування за допомогою функції ad d wait_queu e ()

За допомогою цієї черги очікування процес буде повернуто в стан готовності до виконання, коли умова, на виконання якого очікує процес, буде виконано Звичайно, для цього десь в іншому місці повинен бути код, який викликає функцію wake_up () для даної черги, коли відбудеться відповідна подія

• Змінити стан процесу в значення TASK_INTERRUPTIBLE або TASK_ UNINTERRUPTIBLE

• Перевірити, чи не виконає очікуване умова Якщо виповнилося, то більше немає необхідності переходити в призупинене стан Якщо ні, то викликати функцію schedul e ()

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

з циклу Якщо ні, то знову викликається функція schedul e () і повторюється перевірка умови

• Коли умова виконана, завдання може встановити свій стан в значення TASK_RUNNING і видалити себе з черги очікування за допомогою функції remove_wait_queue ()

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

Повернення до виконання (wake up) проводиться за допомогою функції wake_up (), яка повертає всі завдання, які очікують в даній черзі, в стан готовності до виконання Спочатку викликається функція try_to_wake_u p (), яка встановлює поле стану завдання в значення TASK_RUNNING, далі викликається функція activate_tas k () для додавання завдання в чергу виконання і встановлюється прапор need_resched в ненульове значення, якщо пріоритет завдання, яка повертається до виконання, більше пріоритету поточного завдання Код, який відповідає за наступ деякої події, зазвичай викликає функцію wakeu p () після того, як ця подія відбулася Наприклад, після того як дані прочитані з жорсткого диска, підсистема VFS викликає функцію wake_up () для черги очікування, яка містить всі процеси, які очікують надходження даних

Важливим може бути зауваження про те, що перехід в призупинене стан часто супроводжується помилковими переходами до виконання Це виникає тому, що перехід завдання в стан виконання не означає, що подія, якого очікувала завдання, вже настав: тому перехід в призупинене стан повинен завжди виконуватися в циклі, який гарантує, що умова, на яке очікує завдання, дійсно виконалось (рис 43)

Балансування навантаження

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

Функція     add_wait_que-je () поміщає задачу в чергу очікування, встановлює стан завдання TASK_INTERRUPTIBLE і викликає функціюschedule () Функцияscheduledвызываетфункцию deactivate_task (), яка видаляє задачу з черги виконання

Завдання готова до виконання Завдання не готова до виконання

Отриманий сигнал,

задача встановлюється в стан

TASK_RUNNING і виконує обробник сигналу

Подія, на яке очікувала завдання, сталося, і функція try_to_wake_up () встановлює завдання в стан TASK_RUNNING, викликає функцію activate_task () і функцію schedule ()

Функція remove_wait_quaue () видаляє завдання з черги очікування

Рис 4,3 Перехід в призупиненестан (Sleeping) і повернення до виконання (wake up)

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

Система балансування навантаження реалізована у файлі kernel / sched з у вигляді функції load_balanc e () Ця функція викликається в двох випадках Вона викликається функцією schedul e (), коли поточна чергу виконання порожня Вона також викликається за таймером з періодом в 1 мс, коли система не завантажена, і кожні 200 мс в іншому випадку У однопроцессорной системі функція load_balanc e () не викликається ніколи, насправді вона навіть не компілюється у виконуваний образ ядра, пітому що в системі тільки одна черга виконання і ніякої балансування не потрібно

Функція балансування навантаження викликається при заблокованій черги виконання поточного процесора, переривання при цьому також заборонені, щоб захистити чергу виконання від конкуруючого доступу У тому випадку, коли функція loa d balance () викликається з функції schedul e (), мета її виклику цілком ясна, тому що поточна чергу виконання порожня і знаходження процесів в інших чергах з подальшим їх проштовхуванням в поточну чергу дозволяє отримати переваги Коли система балансування навантаження активізується за допомогою таймера, то її завдання може бути не так очевидна В даному випадку це необхідно для усунення будь-якого дисбалансу між чергами виконання, щоб підтримувати їх у майже однаковому стані, як показано на рис 44

Процес 1

Процес 2

ПроцессЗ Процес 4

Процес 5

Процес 6

Процес 20

  load_balancer()  

Проштовхування процесу з однієї черги до іншої для зменшення дисбалансу

Процес 1

Процес 2

Процес 3

Процес 4

Процес 5

Процес 6

Процес 15

Черга виконання процесора 1, всього

20 процесів

Черга виконання процесора 2, всього

15процессов

Рис 44 Система балансування навантаження

Функція load_balanc e () і повязані з нею функції порівняно великі і складні, хоча кроки, які вони роблять, досить ясні

• Функція load_balanc e () викликає функцію find_busiest_queu e () для визначення найбільш завантаженою черги виконання Іншими словами – черга з найбільшою кількістю процесів у ній Якщо немає черги виконання, кількість процесів в якій на 25% більше, ніж у дайной черзі, то функція f ind_busiest_queue () повертає значення NULL і відбувається повернення з функції load_balance () В іншому випадку повертається вказівник на саму завантажену чергу

• Функція load_balance () приймає рішення про те, з якого масиву пріоритетів найзавантаженішій черзі будуть проштовхуватися процеси Минулий масив є кращим, тому що містяться в ньому завдання не виконувалися досить довгий час і, швидше за все, не перебувають у кеші процесора (тобто не активні в кеші, not cache hot) Якщо минулий масив пріоритетів порожній, то нічого не залишається, як використовувати активний масив

• Функція load_balance () знаходить непорожній список завдань, відповідний самому високому пріоритету (з найменшим номером), так як важливо більш рівномірно розподіляти завдання з високим пріоритетом, ніж з низьким

• Кожне завдання з даними пріоритетом аналізується для визначення завдання, яке не виконується, не заборонено для міграції через процесорної привязки і не активно в кешеЕслі знайдена задача, яка відповідає цьому критерію, то викликається функція pull_tas k () для проштовхування цього завдання з найбільш завантаженою черги в дану чергу

• Поки черги виконання залишаються розбалансованими, попередні два кроки повторюються і необхідну кількість завдань проштовхується з найзавантаженішій черги виконання в дану чергу виконання Зрештою, коли дисбаланс усунутий, черга виконання розблокується і відбувається повернення з функції load_balance ()

Далі показана функція load_balance (), трохи спрощена, але містить всі цажние деталі

static int load_balance(int this_cpu, runqueue_t *this_rq,

struct sched_doraain *sd, enum idle_type idle)

{

struct sched_group *group runqueue_t *busiest unsigned long imbalance int nr_moved

spin_lock(&ampthis_rq-&gtlock)

group = find_busiest_group(sd,  this_cpu, &ampimbalance, idle)

if (group)

goto out_balanced

busiest = find_busiest_queue(group)

if (busiest)

goto out_balanced

nr_moved = 0

if (busiest-&gtnr_running &gt 1) {

double_lock_balance(this_rq, busiest)

nr_moved = move_tasks(this_rq, this_cpu, busiest, imbalance, sd, idle)

spin_unlock(&ampbusiest-&gtlock)

}

spin_unlock(&ampthis rq-&gtlock)

if (nr_moved) {

sd-&gtnr_balance_failed++

if (unlikely(sd-&gtnr_balance_failed &gt sd-&gtcache_nice_tries+2))  {

int wake = 0

spin_lock(abusiest-&gtlock)

if (busiest-&gtactive_balance) { busiest-&gtactive_balance = 1 busiest-&gtpush_cpu = this_cpu wake = 1

)

} else

}

spin_unlock(&ampbusiest-&gtlock)

if (wake)

wake_up_process(busiest-&gtmigration_thread)

sd-&gtnr_balance_failed = sd-&gtcache_nice_tries

sd-&gtnr_balance_failed = 0

sd-&gtbalance_interval = sd-&gtmin_interval

return nr_moved

out_balanced:

spin_unlock(&ampthis_rq-&gtlock)

if (sd-&gtbalance_interval &lt sd-&gtmax_interval)

sd-&gtbalance_interval *= 2

return 0

}

Джерело: Лав, Роберт Розробка ядра 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>

*

*