Багатозадачність в ядрі Linux: переривання і tasklet's

Котейко і молодші братипопередній своїй статті я торкнулася теми багатопоточності. У ній мова йшла про базові поняття: про типи багатозадачності, планування, стратегії планування, машині станів потоку та інше.

На цей раз я хочу підійти до питання планування з іншого боку. А саме, тепер я постараюся розповісти про планування не потоків, а їх «молодших братів». Так як стаття вийшла досить об'ємною, в останній момент я вирішила розбити її на кілька частин:
  1. Багатозадачність в ядрі Linux: переривання і tasklet's
  2. Багатозадачність в ядрі Linux: workqueue
  3. Protothread і кооперативна багатозадачність
У третій частині я також спробую порівняти всі ці, на перший погляд, різні сутності і отримати які-небудь корисні ідеї. А через деякий час я розповім про те, як нам вдалося втілити ці ідеї на практиці в проект Embox, і про те, як ми запускали на маленькій хустці нашу ОС з майже повноцінної багатозадачністю.

Розповідати я постараюся докладно описуючи основну API і іноді вдаючись в особливості реалізації, особливо загострюючи увагу на задачі планування.

Переривання та їх обробка
Апаратне переривання (IRQ) — це зовнішнє асинхронне подія, яка надходить від апаратури, зупиняє хід програми і передає керування процесора для обробки цієї події. Обробка апаратного переривання відбувається наступним чином:
  1. Призупиняється поточний потік управління, зберігається контекстна інформація для повернення в потік.
  2. Виконується функція-обробник (ISR) в контексті відключених апаратних переривань. Обробник повинен виконати дії, необхідні для даного переривання.
  3. Обладнання повідомляється, що переривання оброблене. Тепер воно зможе генерувати нові переривання.
  4. Відновлюється контекст для виходу з переривання.
Функція-обробник може бути досить великою, що недозволено з урахуванням того, що вона виконується в контексті відключених апаратних переривань. Тому придумали ділити обробку переривань на дві частини (в Linux вони називаються top-half і bottom-half):
  • Безпосередньо ISR, яка викликається при перериванні, виконує тільки саму мінімальну роботу, яку неможливо відкласти на потім: вона збирає інформацію про переривання, необхідну для подальшої обробки, як-то взаємодіє з апаратурою і планує другу частину.
  • Друга частина, де виконується основна обробка, запускається вже в іншому контексті процесора, де апаратні переривання дозволені. Виклик цієї частини обробника буде здійснений пізніше.
Так ми підійшли до відкладеної обробці переривань. В Linux для цих цілей використовуються tasklet і workqueue.

Tasklet
Якщо коротко, то tasklet — це щось на зразок дуже маленького потічка, у якого немає ні свого стека, ні контексту. Такі «потоки» відпрацьовують швидко і повністю. Основні особливості tasklet'ов:
  • tasklet'и атомарны, так що з них не можна використовувати sleep() і такі примітиви синхронізації, як м'ютекси, семафори та інше. Але, наприклад, spinlock (круглу блокування) використовувати можна;
  • викликаються у більш «м'якому» контексті, ніж ISR. У цьому контексті можна апаратні переривання, які витісняють tasklet'и на час виконання ISR. У ядрі Linux цей контекст зветься softirq, і крім запуску tasklet'ів, він використовується ще кількома підсистемами;
  • tasklet виконується на тому ж ядрі, що і планує його. А точніше, встигло запланувати його першим, викликавши softirq, обробник якого завжди прив'язані до зухвалому ядра;
  • різні tasklet'и можуть виконуватись паралельно, але при цьому сам з собою він одночасно не викликається, оскільки виконується лише на одному ядрі, першим запланировавшим його виконання;
  • tasklet'и виконуються за принципом невытесняющего планування, один за одним, в порядку черги. Можна планувати з двома різними пріоритетами: normal і high.
Загляньмо ж тепер «під капот» і подивимося, як вони працюють. По-перше, сама структура tasklet (визначається в <linux/interrupt.h>):
struct tasklet_struct
{
struct tasklet_struct *next; /* Наступний tasklet у черзі на планування */
unsigned long state; /* TASKLET_STATE_SCHED або TASKLET_STATE_RUN */
atomic_t count; /* Відповідає за те, активований tasklet чи ні */
void (*func)(unsigned long); /* Основна функція tasklet'а */
unsigned long data; /* Параметр, з яким запускається func */
};

Перш, ніж користуватися tasklet'ом, його спочатку потрібно ініціалізувати:
/* За замовчуванням tasklet активований */
void tasklet_init(struct tasklet_struct *t, void (*func)(unsigned long), unsigned long data);
DECLARE_TASKLET(name, func, data);
DECLARE_TASKLET_DISABLED(name, func, data); /* деактивований tasklet */

Плануються tasklet'и просто: tasklet поміщається в одну з двох черг в залежності від пріоритету. Черги організовані як односвязные списки. Причому, у кожного CPU ці черги свої. Робиться це за допомогою функцій:
void tasklet_schedule(struct tasklet_struct *t); /* з нормальним пріоритетом */
void tasklet_hi_schedule(struct tasklet_struct *t); /* з високим пріоритетом */
void tasklet_hi_schedule_first(struct tasklet_struct *t); /* позачергово */

Коли tasklet заплановано, йому виставляється стан TASKLET_STATE_SCHEDі він додається в чергу. Поки він знаходиться в цьому стані, запланувати його ще раз не вийде — в цьому випадку просто нічого не станеться. Tasklet не може перебувати в кількох місцях в черзі на планування, яка організується через поле next структури tasklet_struct. Втім, це справедливо для будь-яких списків, пов'язаних через поле об'єкта, як, наприклад, <linux/list.h>.
На час виконання tasklet'у присвоюється стан TASKLET_STATE_RUN. До речі, з черги tasklet дістається перед своїм виконанням, а стан TASKLET_STATE_SCHED знімається, тобто, його можна запланувати знову під час його виконання. Це може зробити як він сам, так і, наприклад, переривання на іншому ядрі. В останньому випадку, щоправда, викликаний він буде тільки після того, як він закінчить своє виконання на першому ядрі.

Досить цікаво, що tasklet можна активувати і деактивувати, причому рекурсивно. За це відповідають наступні функції:
void tasklet_disable_nosync(struct tasklet_struct *t); /* деактивація */
void tasklet_disable(struct tasklet_struct *t); /* з очікуванням завершення роботи tasklet'а */
void tasklet_enable(struct tasklet_struct *t); /* активація */

Якщо tasklet деактивовано, його можна додати в чергу на планування, але виконуватися на процесорі він не буде до тих пір, поки не буде знову активований. Причому, якщо tasklet був деактивовано кілька разів, то він повинен бути рівно стільки ж раз активований, поле count в структурі якраз для цього.

А ще tasklet'и можна вбивати. Ось так:
void tasklet_kill(struct tasklet_struct *t);

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

Цікавіше всього функції, які відіграють роль планувальника:
static void tasklet_action(struct softirq_action *a);
static void tasklet_hi_action(struct softirq_action *a);

Так як вони практично однакові, то немає сенсу наводити код обох функцій. Але ось на одну з них варто поглянути, щоб розібратися детальніше:
static void tasklet_action(struct softirq_action *a)
{
struct tasklet_struct *list;

local_irq_disable();
list = __this_cpu_read(tasklet_vec.head);
__this_cpu_write(tasklet_vec.head, NULL);
__this_cpu_write(tasklet_vec.tail, &__get_cpu_var(tasklet_vec).head);
local_irq_enable();

while (list) {
struct tasklet_struct *t = list;

list = list>next;

if (tasklet_trylock(t)) {
if (!atomic_read(&t->count)) {
if (!test_and_clear_bit(TASKLET_STATE_SCHED, &t->state))
BUG();
t->func(t->data);
tasklet_unlock(t);
continue;
}
tasklet_unlock(t);
}

local_irq_disable();
t->next = NULL;
*__this_cpu_read(tasklet_vec.tail) = t;
__this_cpu_write(tasklet_vec.tail, &(t->next));
__raise_softirq_irqoff(TASKLET_SOFTIRQ);
local_irq_enable();
}
}

Зверніть увагу на виклик функцій tasklet_trylock() і tasklet_lock(). tasklet_trylock() виставляє tasklet'у стан TASKLET_STATE_RUN і тим самим блокує tasklet, що запобігає виконання одного і того ж tasklet'а на різних CPU.

Ці функції планувальники, по суті, реалізують кооперативну багатозадачність, яку я детально розглядала у своїй статті. Функції реєструються як обробники softirq, який ініціюється при плануванні tasklet'ів.

Реалізацію всіх вищеописаних функцій можна подивитися в файлах include/linux/interrupt.h kernel/softirq.c.

Продовження слід

У наступній частині я розповім про набагато більш потужному механізмі — workqueue, який також часто використовується для відкладеного обробки переривань.

P. S. На правах реклами. Ще я хочу запросити всіх, кому цікавий наш проект, на зустріч, організовану codefreeze.ru анонс на хабре). На ній можна буде поспілкуватися наживо, задати питання головному лиходієві abondarev і покритикувати в обличчя, в кінці кінців :)

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

0 коментарів

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