Від шедулера до планування

См. дві інші статті цієї групи — Робимо багатозадачність і Преемптивность: як відібрати процесор.

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

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

Як я вже говорив, шедулер — це просто функція, яка відповідає на питання: яку нитку і на скільки часу поставити на процесор.

До речі, в SMP системі шедулер нічим не відрізняється від однопроцесорного. Взагалі, щоб простіше розуміти структуру взаємодії сутностей на декількох процесорах, найпростіше представити собі наступну модель: для кожного процесора є нитка «простою» (яка працює, якщо взагалі більше нікому і просто останавливае процесор до переривання), яка постійно намагається «віддати» процесор (яким вона володіє б) іншим ниткам, вибираючи нитка з допомогою шедулера.

Говорячи про шедулере не можна не сказати про пріоритети.

Пріоритет — властивість нитки (або процесу) впливає на конкуренцію цієї нитки з іншими нитками за процесор.

Пріоритет зазвичай описується парою <клас пріоритету, значення пріоритету всередині класу>.

На сьогодні сформувалася досить чітка схема реалізації пріоритетів. Пріоритети ниток діляться на три класи:

  • Реальний час: нитки такого класу завжди витісняють з процесора нитки інших класів так швидко, як це можливо, і ніколи не знімаються з процесора крім як за наявності нитки з більш високим пріоритетом реального часу. Тобто — такі нитки самі повинні вирішувати, коли їм більше не потрібен процесор.
  • Поділ часу: нитки такого класу завжди витісняють з процесора нитки класу idle, між собою нитки поділу часу конкурують м'яко. Дві нитки такого класу з різними значеннями пріоритету будуть отримувати різний відсоток процесорного часу, але обов'язково будуть її отримувати, навіть якщо значення пріоритетів розрізняються граничним чином.
  • Idle клас: нитки такого класу отримують процесор тільки якщо немає готових до виконання ниток інших класів, «на здачу». Особисто я не бачу сенсу в значенні пріоритету всередині класу idle. Хоча так теж буває.


До речі. Кажуть, Кернигана якось запитали, що б він зробив інакше, якби писав Юнікс заново. «Написав би creat як create», — відповів метр. Я б додав до списку виправлень ще мішок недоречностей, починаючи з nice — поняття пріоритету в Юниксе чомусь первернуто. Чим nice менше, тим пріоритет вище.

Ми в цій статті будемо дотримуватися більш человеколюбивой шкали: вище чисельне значення = більше процесора.

Комусь, напевно, вже хочеться заглянути в код. Ось він:
Вихідний текст Фантомовского шедулера.

Тут ми трохи граємо у Пушкіна :)І ось вже тріщать морози
І срібляться серед полів…
(Читач чекає вже рими троянди;
На, візьми її мерщій!)


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

За сім — продовжимо.

Досить традиційна реалізація шедулера припускає наявність так званої run queue — черзі ниток, готових до виконання. Взагалі-то це не обов'язково чергу, і якщо і черга — то, звичайно, безліч черг, що належать до різних класів, а іноді і рівнів пріоритетів.

Конкретно в Фантоми це три черги, відповідно до класів:

/** Idle prio threads */
static queue_head_t runq_idle = {0,0};

/** Normal prio threads */
static queue_head_t runq_norm = {0,0};

/** Realtime prio threads */
static queue_head_t runq_rt = {0,0};


В цілому нитку по відношенню до процесора може перебувати в трьох станах:

  • Заблокована. Не перебуває на процесорі, не може бути на нього поставлена. Відсутня в якій-небудь run queue.
  • Виконується. Відсутня в якій-небудь run queue.
  • Може виконуватися. Присутній в якій-небудь run queue.


Тобто, в run queue розташовані нитки, які хотіли б потрапити на процесор.

Звідси робота планувальника зводиться до того, щоб:

  1. Визначитися з тим, нитка якого класу пріоритету зараз будемо запускати. Це просто — перевірити, не чи порожня черга realtime — якщо не порожня, то ми запускаємо нитка realtime, перевірити чергу нормальних пріоритетів — якщо не порожня, то запускаємо нормальну нитка. Інакше — запускаємо idle нитка. Якщо таких немає, відзначаємо, що процесор idle і йдемо в нитка «вічного сну.
  2. Якщо визначилися з пріоритетом — вибрати правильну нитка для виконання в даному пріоритеті.
  3. Призначити нитки часовий інтервал для виконання.


В цілому реалізація досить банальна. Почнемо з реального часу. Наївна реалізація сортує наявні нитки і запускає нитка з максимальним чисельним значенням пріоритету. Часовий інтервал не призначається, так як для ниток з пріоритетом реального часу він і не перевіряються.

// Have some realtime?
if( !queue_empty(&runq_rt) )
{
int maxprio = -1;
phantom_thread_t *best = 0;
phantom_thread_t *it = 0;
queue_iterate(&runq_rt, it, phantom_thread_t *, runq_chain)
{
if( it->thread_flags & THREAD_FLAG_NOSCHEDULE ) continue;
if( ((int)it->priority) > maxprio )
{
maxprio = it->priority;
best = it;
}
}
if( best )
{
assert(t_is_runnable(best));
return best;
}
}


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

Тепер нитки з пріоритетом класу поділу часу — тобто, звичайні нитки, м'яко конкуруючі за процесор.

Тут треба зазначити, що змінна ticks_left у структурі стану нитки визначає, скільки 10 мсек інтервалів нитка протримається на процесорі.

Спочатку розглянемо, що робить функція t_assign_time():

it->ticks_left = NORM_TICKS + it->priority;


Вона перевіряє, що всі нитки витратили свої ticks_left, і якщо так — призначає їм нові ticks_left — тим, у кого пріоритет більше — дає більше процесорного часу.

Що робить сам планувальник? Вибирає нитка з максимальним пріоритетом і з ненульовим залишком процесорного часу, і запускає її:

// Have normal one?
if( !queue_empty(&runq_norm) )
{
// If no normal thread has ticks left, reassign
// ticks and retry
do {
unsigned int maxprio = 0; // NB! not a negative number!
phantom_thread_t *best = 0;
phantom_thread_t *it = 0;
queue_iterate(&runq_norm, it, phantom_thread_t *, runq_chain)
{
if( it->thread_flags & THREAD_FLAG_NOSCHEDULE ) continue;

if( (it->priority > maxprio) && (it->ticks_left > 0) )
{
maxprio = it->priority;
best = it;
}
}
if( best )
{
return best;
}
} while(t_assign_time());
}


Коли всі залишки у всіх ниток скінчилися — просить t_assign_time() призначити ниткам нові залишки.

Взагалі-то, сортування тут відносно надлишкова. Досить просто додавати нитки в кінець черги, а вибирати з початку — fair enough. Взагалі, сортувати всі нитки — очевидно погано, не робіть так. Я теж цей шматок перепишу більш оптимальним чином, наприклад, так як вже описав вище, для realtime.

До речі, при читанні коду планувальника треба враховувати, що нитки не завжди «з'їдають» свій квант часу — нитка може заблокуватися на примітив синхронізації і частину часу простояти не по своїй волі. Цим і зумовлена сортування: якщо пріоритет нитки високий, то нитка після розблокування повернеться на процесор раніше, ніж доопрацюють всі інші нитки.

Добре, перейдемо до idle priority class. Ми потрапимо сюди тільки якщо в попередніх класах всі нитки сплять або відсутні.

// Have idle one?
ret = (phantom_thread_t *)queue_first(&runq_idle);
if( ret )
{
if( ret->thread_flags & THREAD_FLAG_NOSCHEDULE )
goto idle_retry;

// Just take first. Switched off thread will become
// last on runq, so all idle threads will run in cycle
ret->ticks_left = NORM_TICKS;
return ret;
}
else
goto idle_no;


Тут все просто — беремо першу-ліпшу, запускаємо на стандартний час. Оскільки при знятті з процесора вона потрапить в кінець черги runq_idle, всі такі нитки будуть запускатися по колу.

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

STAT_INC_CNT(STAT_CNT_THREAD_IDLE);
percpu_idle_status[GET_CPU_ID()] = 1; // idle
return GET_IDLEST_THREAD(); // No real thread is ready to run


Вона у кожного процесора своя просто тому, що одну нитку не можна запустити двічі. Проста, як мукання:

while(1)
{
hal_sti();
hal_wait_for_interrupt();
}


Майже все.

Що тут не враховано.

Interactive thread prio boost: зазвичай планувальники збільшують фактичний пріоритет ниток, які помічені у введенні-виведенні з консолі або іншої сутності, за якої, потенційно, ховається інтерактивний юзер. Це підвищує перцептивную реактивність системи — «операційка менше тупить» з точки зору людини. І навпаки — якщо нитка «доїдає свій таймслайс до кінця, і робить це стабільно, їй трохи знижують пріоритет, вважаючи її суто обчислювальної. З тією ж метою — підвищити реактивність системи.

Це, звичайно, стосується тільки ниток з звичайним класом пріоритетів — ніхто і ніколи не чіпає пріоритети реального часу.

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

Інверсія пріоритетів.

Припустимо, у нас є страшно важлива нитка R з максимальним пріоритетом реального часу, і нитку I з пріоритетом класу idle, яка займається несуттєвою нісенітницею. А так само звичайна нитка U, яка працює з юзером — читає команди з консолі. Шелл, наприклад.

Юзер спить, чекає введення-виведення і нитка U.

Нитка I отримує процесор, вирішує зробити свою нісенітницю і хоче для цього виділити собі трохи пам'яті. Функція виділення пам'яті ядра замикає глобальний м'ютекс і починає виділяти. Працюючи на idle prio, очевидно.

У цей момент прокидається від сну нитка R, якій пора скорегувати положення стрижня поглинача активної зони реактора. І теж хоче трохи пам'яті.

(Давайте не будемо коверзувати і питати, що U і R роблять на одній машині — U може бути сервером статистики по TCP, наприклад.)

Природно, R забирає процесор у I, але впирається в глобальний м'ютекс при виділенні пам'яті, і зупиняється.

Тут би I продовжити роботу, але юзер набирає команду, і U приймається за роботу, відбираючи процесор у I. Тепер, раптово, высокоприоритетная нитка реального часу R чекає закінчення роботи нитки U, і реактор вибухає до біса.

Для того, щоб цього не траплялося, роблять те, що у мене в Фантоми поки не зроблено — інверсії пріоритетів.

Вона формулюється так: якщо нитка більш високого пріоритету заблокована на ресурсі, зайнятій ниткою низького пріоритету, друга нитка отримує на час такого блокування пріоритет першої нитки.

Тобто, в нашому прикладі, нитка I на час блокування м'ютексу виділення пам'яті повинна була отримати пріоритет реального часу від нитки R, витіснити до біса нитка U і доробити те, що блокує нитка R. Після розблокування м'ютексу її пріоритет повинен знизитися назад до idle і процесор перейде до R, як і повинно бути.

Ось тепер, напевно, все. :)

Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.