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

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

Програмний код планувальника операційної системи Linux міститься у файлі kernel / schedc Алгоритм планування і відповідний програмний код були істотно перероблені в ті часи, коли почалася розробка ядер серії 25 Отже, програмний код планувальника є повністю новим і відрізняється від планувальників попередніх версій Новий планувальник розроблявся для того, щоб задовольняти зазначеним нижче вимогам

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

• Повинна забезпечуватися добра масштабованість для SMP-систем Кожен процесор повинен мати свої індивідуальні елементи блокувань і свою індивідуальну чергу виконання

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

• Повинна бути забезпечена хороша продуктивність для інтерактивних додатків Навіть при значному завантаженні система повинна мати гарну реакцію і негайно планувати виконання інтерактивних завдань

• Повинна бути забезпечена равнодоступность ресурсів (fairness) Жоден процес не повинен відчувати нестачу квантів часу за допустимий період Крім того, жоден процес не повинен отримати неприпустимо велике значення кванта часу

• Повинна бути забезпечена оптимізація для найбільш поширеного випадку, коли число готових до виконання процесів одно 1-2, але в той же час має забезпечуватися гарне масштабування і на випадок великої кількості процесорів, на яких виконується велике число процесів

Новий планувальник дозволяє задовольнити всім цим вимогам

Черги виконання

Основна структура даних планувальника – цечергу виконання (runqueue) Черга виконання визначена у файлі kernel/schedc3 у вигляді структури struc t runqueue Вона являє собою список готових до виконання процесів для даного процесора

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

struct runqueue {

spinlock_t lock / * Спін-блокування для захисту цієї черги виконання * / unsigned long nr_rinning / * Кількість завдань, готових до виконання * / unsigned long nr_switches / * Кількість перемикань контексту * / Unsigned long expired timestamp / * Час останнього обміну масивами * / unsigned long nr_uninterruptible / * Кількість завдань у стані

непреривавшуюся очікування * /

unsigned long long timestamp last tick / * Остання мітка часу планувальника * /

struct task_struct * curr / * Поточне завдання, яке виконується на даному

процесорі * /

struct task_struct * idle / * Неодружена завдання даного процесора */

struct mm_struct * prev_mm / * Поле mm_struct останнього виконуваного завдання * /

struct prio_array active / * Покажчик на активний масив пріоритетів * /

struct prio_array expired / * Покажчик на минулий масив пріоритетів * /

struct prio_array arrays[2] /* масиви пріоритетів * /

struct task_3truct * migration_thread / * Міграційний потік для даного процесора * /

struct list_head migration_queue / * Міграційна чергу для

даного процесора * /

atomic_t nr_iowait / * Кількість завдань, які очікують на введення-виведення * /

}

3 Може виникнути питання: чому використовується фай лkernel / schedс,а не заголовний файл include/linux/schedh        Тому що бажано абстрагуватися від реалізації коду планувальника і забезпечив, доступність для решти коду ядра тільки лише деяких інтерфейсів

Оскільки чергу виконання – це основна структура даних планувальника, існує група макросів, які використовуються для доступу до певних черг виконання Макрос cpu_rq (processor ) Повертає покажчик на чергу виконання, повязану з процесором, що має заданий номер Аналогічно макрос this_r q () повертає покажчик на чергу, повязану з поточним процесором І нарешті, макрос task_rq (task) повертає покажчик на чергу, в якій знаходиться відповідне завдання

Перед тим як проводити маніпуляції з чергою виконання, її необхідно заблокувати (блокування детально розглядаються в розділі 8, Введення в синхронізацію виконання коду ядра) Так як черга виконання унікальна для кожного процесора, процесору рідко необхідно блокувати чергу виконання іншого процесора (проте, як буде показано далі, таке все ж іноді трапляється) Блокування черги виконання дозволяє заборонити внесення будь-яких змін в структуру даних черзі, поки процесор, що утримує блокування, виконує операції читання або запису полів цієї структури Найбільш часто зустрічається ситуація, коли необхідно заблокувати чергу виконання, в якій виконується поточне завдання У цьому випадку використовуються функції tapk_rq_loc k () і task_rq_unlock () , Як показано нижче

struct runqueue *rq

unsigned long flags

rq = task_rq_lock(task, &ampflags)

/ * Тут можна проводити маніпуляції з чергою виконання * /

task_rq_unlock (rq, &ampflags)

Альтернативними функціями виступають функція this_rq_loc k (), яка дозволяє заблокувати поточну чергу виконання, і функція rq    unlock (struc t runqueue * rq), що дозволяє розблокувати зазначену в аргументі чергу

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

/ * Для того, щоб заблокувати .. * /

if (rql &lt rq2) ( spin_lock(s,rql-&gtlock] spin_lock(Srq2-&gtlock)

} else (

spin_lock(Srq2-&gtlock)  

spin_lock(&amprql-&gtlock)

}

/ * Тут можна маніпулювати обома чергами .. * /

/ • для того, щоб розблокувати .. * / spin_unlock (brql-> lock) spin_unlock (& ​​rq2-> lock)

За допомогою функцій double_rq_lock () і double_rq_unlock () зазначені кроки можна виконати автоматично При цьому отримуємо наступне

double_rq_lock(rql, rq2)

/ * Тут можна маніпулювати обома чергами ..*/

double_rq_unlock(rql, rq2)

Розглянемо невеликий приклад, який показує, чому важливий порядок захоплення блокувань Питання взаємних блокувань обговорюється в розділах 8, Введення в синхронізацію виконання коду ядра і 9, Засоби синхронізації в ядрі. Ця проблема стосується не тільки черг виконання: вкладені блокування повинні завжди захоплюватися в одному і тому ж порядку Спін-блокування використовуються для запобігання маніпуляцій з чергами виконання кількома завданнями одночасно Принцип роботи цих блокувань аналогічний ключу, за допомогою якого відкривають двері Перше завдання, яке підійшло до дверей, захоплює ключ, входить у двері і закриває її з іншого боку Якщо інше завдання підходить до дверей і визначає, що двері закриті (бо за дверима знаходиться перше завдання), то воно повинно зупинитися і почекати, поки перше завдання на вийде і не поверне ключ Очікування називаєтьсяспінінгом (обертанням, spinning), так як насправді завдання постійно виконує цикл, періодично перевіряючи, не повернуто чи ключ Тепер розглянемо, що буде, якщо одне завдання намагається спочатку заблокувати першу чергу виконання, а потім другу, в той час як нове завдання намагається спочатку заблокувати другу чергу, а потім – першим Припустимо, що перше завдання успішно захопило блокування першої черги, в той час як друге завдання захопило блокування другої черги Після цього перше завдання намагається заблокувати другу чергу, а друге завдання – перше Жодне із завдань ніколи не добється успіху, так як нове завдання вже захопило цю блокування Обидва завдання будуть очікувати один одного вічно Так само як у глухому куті дороги створюється блокування руху, так і неправильний порядок захоплення блокувань призводить до того, що завдання починають очікувати один одного вічно, і теж виникає тупикова ситуація, яка ще називається взаімоблокіровке Якщо обидва завдання захоплюють блокування в одному і тому ж порядку, то розглянутій ситуації відбутися не може У розділах 8 і 9 представлено повний опис блокувань

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

Кожна черга виконання містить два масиву пріоритетів (priority arrays): актину і минулий Масиви пріоритетів визначені у файлі kernel / sched c у вигляді опису struc t prio_array Масиви пріоритетів – це структури даних, які забезпечують 0 (1)-планування Кожен масив пріоритетів містить для кожного значення пріоритету одну чергу процесів, готових до виконання Масив пріоритетів також містить бітову маску пріоритетів (priority bitmap), використовувану для ефективного пошуку готового до виконання завдання, у якого значення пріоритету є найбільшим в системі

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

*

*