Робимо мультизадачність

Я намагаюся чергувати статті про розробку ОС взагалі і специфічні для ОС Фантом статті. Ця стаття — загального плану. Хоча, звичайно, я буду давати приклади саме з коду Фантома.

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

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

Шедулер — це функція, яка відповідає на питання «який нитки віддати процесор прямо зараз». Всі. Найпростіший шедулер просто перебирає всі нитки (але, звичайно, готові до виконання, не зупинені) по колу (RR алгоритм). Реальний шедулер враховує пріоритети, поведінка нитки (інтерактивні отримують більше, ніж обчислювальні), еффініті (на якому процесорі нитка працювала в минулий раз) тощо, при цьому вміє поєднувати кілька класів пріоритетів. Типово це клас реального часу (якщо є хоча б одна нитка цього класу — працює вона), клас поділу часу й клас idle (процесор отримує тільки якщо два попередніх класу порожні, тобто в них немає ниток, готових до виконання).

На цьому поки про шедулер закінчимо.

Перейдемо до власне підсистемі, яка вміє відібрати процесор в однієї нитки і віддати його іншій.

Знову ж, почнемо з простого. Багатозадачність буває кооперативна та преемптивная.

Кооперативна вкрай проста — кожна нитка час від часу чесно і свідомо «віддає» процесор, викликаючи функцію yield().

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

Сама ж кооперативна багатозадачність базується на всього однієї функції. Функції, яку викликали всі нитки одночасно.

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

Трохи пізніше ми розглянемо весь код перемикання контексту, але зараз — сама серцевина, власне перемикання між нитками.

Посилання на реалізацію для Intel 32 bit

Я трохи почистив код для простоти:

// called and returns with interrupts disabled
 
/* void phantom_switch_context(
 
phantom_thread_t *from,
 
phantom_thread_t *to,
 
int *unlock );
 
*/
 
ENTRY(phantom_switch_context)
 

 
movl 4(%esp),%eax // sw from (to store)
 

 
movl (%esp),%ecx // IP
 
movl %ecx, CSTATE_EIP(%eax)
 
movl %ebp, CSTATE_EBP(%eax)
 

 
// we saved ebp, can use it. 
 
movl %esp, %ebp
 
// params are on bp now
 

 
pushl %ebx
 
pushl %edi
 
pushl %esi
 
movl %cr2, %esi
 
pushl %esi
 

 
movl %esp, CSTATE_ESP(%eax)
 

 
// saved ok, now load 
 

 
movl 8(%ebp),%eax // sw to (load)
 

 
movl CSTATE_ESP(%eax), %esp
 

 
popl %esi
 
movl %esi, %cr2
 
popl %esi
 
popl %edi
 
popl %ebx
 

 
movl CSTATE_EIP(%eax), %ecx
 
movl %ecx, (%esp) // IP
 

 
// now move original params ptr to ecx, as we will use and restore ebp
 
movl %ebp, %ecx
 

 
movl CSTATE_EBP(%eax), %ebp
 

 
// Done, unlock the spinlock given
 

 
movl 12(%ecx),%ecx // Lock ptr
 
pushl %ecx
 
call EXT(hal_spin_unlock)
 
popl %ecx
 

 
// now we have in eax (which is int ret val) old lock value
 

 
ret
 


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

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

Перед цим ми отопрем спинлок, який нам передала минула нитка — як видно, отопрем ми його суворо після перемикання, тобто коли стара нитка зупинена — це важливо для реалізації примітивів синхронізації і для підтримки багатопроцесорності. (Якщо ми отопрем спинлок до перемикання, інший процесор може спробувати активувати нитка, яку ми ще не до кінця деактивували.)

Те, що ми розглянули — саме серце реалізації. Але безпосередньо ця функція не викликається (вона взагалі реалізує тільки архітектурно-залежну частину коду), а викликається вона з обгортки phantom_thread_switch().

См. код phantom_thread_switch().

Що відбувається в обгортці. Підемо по кроках.

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

assert_not_interrupt();
assert(threads_inited);
int ie = hal_save_cli();


Замкнемо загальний спинлок перемикання контекстів. Взагалі-то його можна б робити per CPU, але для спокою — тільки одне перемикання контексту в момент часу. Виймемо з опису структури нитки посилання на спинлок, який треба відімкнути після перемикання — її нам передав примітив синхронізації. Обнулим посилання всередині структури, щоб спинлок не отперли повторно.

hal_spin_lock(&schedlock);
toUnlock = GET_CURRENT_THREAD()->sw_unlock;
GET_CURRENT_THREAD()->sw_unlock = 0;


Заберемо у нинішньої нитки останній «тік» — запланований для неї інтервал роботи на процесорі. Це для шедулера, так що зараз в деталі вдаватися не буду. Запитаємо шедулер, кому віддати процесор. Запам'ятаємо хто була нинішня нитка. Переконаємося для порядку, що шедулер не зійшов з розуму і не запропонував нам запустити нитка, яка не має права працювати (ненульові sleep_flags).

// Eat rest of tick
GET_CURRENT_THREAD()->ticks_left--;

phantom_thread_t *next = phantom_scheduler_select_thread_to_run();
phantom_thread_t *old = GET_CURRENT_THREAD();

assert( !next->sleep_flags );


Щоб не займатися фігньою, перевіримо, чи не ту ж саму нитку треба буде запустити, якщо ту ж — просто закінчимо вправа, зазначивши в статистиці це подія.

if(next == old)
{
STAT_INC_CNT(STAT_CNT_THREAD_SAME);
goto exit;
}


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

Якщо стара нитка не заблокована, то, навпаки, поставимо її в чергу (ось тут-то нам і корисний глобальний schedlock), щоб вона могла претендувати на постановку на процесор надалі. (Якщо заблокована, то в чергу її поверне той, хто розблокує.)

t_dequeue_runq(next);

if(!old->sleep_flags)
t_enqueue_runq(old);


Далі все жорстко. Треба чітко розуміти, що після виклику phantom_switch_context ми працюємо в іншій нитки, у нас ІНШІ ЗНАЧЕННЯ ЛОКАЛЬНИХ ЗМІННИХ. Зокрема, мінлива next, в якій зберігається покажчик на дескриптор тієї нитки, яку ми запускаємо, після запуску нитки буде містити невірне значення. Тому глобальну змінну, яка зберігає знання про те, яка нитка зараз працює, ми виправимо перемикання, а не після. (Взагалі-то, після теж можна, але з іншої змінної.:)

Далі ми дозволяємо програмні переривання перед власне перемиканням, і забороняємо їх після. Це потрібно тому, що саме преемптивное перемикання контексту відбувається саме з софтверних переривань, і потрібно гарантувати певний протокол роботи з ними. Це я розповім окремо, момент реально тонкий.

// do it before - after we will have stack switched and can't access
// correct 'next'
SET_CURRENT_THREAD(next);

hal_enable_softirq();
phantom_switch_context(old, next, toUnlock );
hal_disable_softirq();


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

phantom_thread_t *t = GET_CURRENT_THREAD();

t->cpu_id = GET_CPU_ID();
arch_adjust_after_thread_switch(t);


Для Интела ця специфічна функція відновлює налаштування верхівки стека при перемиканні в ядерний режим:

cpu_tss[ncpu].esp0 = (addr_t)t->kstack_top;


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

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

Тепер про запуск нитки. Щоб створити нову нитку, потрібно, щоб вона могла… повернутися з phantom_switch_context()!

Це означає, що потрібно «зібрати» на стеку нової нитки таку картину, яка виникає коли вона знаходиться всередині phantom_switch_context() в точці, де ми переключили покажчик стека на нову нитку. При цьому адресу повернення з phantom_switch_context() повинен бути адресою функції, яка, по-перше, зробить те, що робить після перемикання нитки phantom_thread_switch(), по-друге, закінчить ініціалізацію нитки, і, нарешті, викличе функцію, яка повинна бути виконана в рамках нової нитки.

Ми не розглянули у цій статті власне преемптивность — як саме реалізується «відбирання» процесора у старої нитки, і хто і коли викликає phantom_thread_switch(). Але це вже окрема стаття.

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

0 коментарів

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