Преемптивность: як відібрати процесор

Ця стаття не має сенсу без попередній, в якій описувалися основні механізми перемикання контекстів у багатозадачної ОС.

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

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

Але, як завжди є нюанси. См. код для интела.

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

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

Тому спочатку обслужимо власне переривання. Потім переконаємося, що воно не було вкладеним — що ми не перервали обслуговування іншого переривання, яке теж мало б завершитися.

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

Тут треба розуміти, що в старших бітах змінної irq_nest лежить прапор заборони обслуговування софверных переривань і прапор відсутність запиту софтверного переривання. Тобто якщо вона дорівнює нулю, то, одночасно, дорівнює нулю вкладеність запитів хардверных переривань, немає заборони на софтверное переривання і запит на софтверное переривання.

if(irq_nest)
return;

// Now for soft IRQs
irq_nest = SOFT_IRQ_DISABLED|SOFT_IRQ_NOT_PENDING;
hal_softirq_dispatcher(ts);
ENABLE_SOFT_IRQ();


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

При ініціалізації ниток ядро реєструє хендлер софтверного переривання

hal_set_softirq_handler( SOFT_IRQ_THREADS, (void *)phantom_scheduler_soft_interrupt, 0 );


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

Залишилися два моменту. Перший — як явно «віддати» процесор. Наприклад, коли ми намагаємося захопити вже замкнений м'ютекс — нитка треба зупинити.

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

void
phantom_scheduler_request_soft_irq()
{
hal_request_softirq(SOFT_IRQ_THREADS);
__asm __volatile("int $15");
}


Як сказано вище, це призведе до того, що функція phantom_thread_switch буде викликана з контексту софтверного переривання.

Другий: а хто запросить софтверное переривання, щоб завершити працюючу зараз нитка після закінчення виділеного їй слоти часу процесора?

Для цього є ось такий запит:

void
phantom_scheduler_schedule_soft_irq()
{
hal_request_softirq(SOFT_IRQ_THREADS);
}


Він виконується ось коли. Всередині таймерного переривання викликається спеціальна функція:

// Called from timer interrupt 100 times per sec.
void phantom_scheduler_time_interrupt(void)
{
if(GET_CURRENT_THREAD()->priority & THREAD_PRIO_MOD_REALTIME)
return; // Realtime thread will run until it blocks or reschedule requested

if( (GET_CURRENT_THREAD()->ticks_left--) <= 0 )
phantom_scheduler_request_reschedule();
}


Як неважко бачити, вона декрементирует змінну нитки ticks_left, і якщо порахувала до нуля — запитує перемикання нитки.

Саму змінну ticks_left виставляє шедулер, коли вибирає нитка для запуску — він прописує в цю змінну число 10 мсек інтервалів, які нитку відпрацює (якщо до того не захоче зупинитися сама).

Час роботи шедулер може виставляти фіксоване (обслуговуючи пріоритети через частоту постановки нитки на процесор) або враховувати пріоритет (даючи більш високопріоритетних ниткам довші інтервали).

До цього треба додати, що викликати phantom_scheduler_request_reschedule() може кожен, хто вважав, що настала пора визначитися, кому зараз встати на процесор.

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

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

Для повноти картини розглянемо структуру опису нитки (struct phantom_thread) в деталях.

Поле cpu містить специфічні для даної архітектури поля, в які зберігається стан процесора при зупинці нитки. cpu_id — номер процесора, на якому нитка запускалася в останній раз або працює зараз. tid — просто ідентифікатор нитки. owner застосовується об'єктної середовищем фантома, щоб прив'язати сюди об'єкт, що описує нитка на прикладному рівні. Якщо нитка обслуговує підсистему сумісності з Юнікс — pid зберігає номер процесу Юникса, до якого нитка належить. Ім'я — виключно для налагодження.

/** NB! Exactly first! Accessed from asm. */
cpu_state_save_t cpu;

//! on which CPU this thread is now dispatched
int cpu_id; 

int tid;

//! phantom thread ref, etc
void * owner;

//! if this thread runs Unix simulation process - here is it
pid_t pid;

const char * name;


ctty — буфер stdin для нитки, застосовується для зв'язку з графічною підсистемою. stack/kstack — віртуальний і фізичний адресу сегмента стека, відповідно user і kernel mode. start_func і start_func_arg — точка входу в функцію («main») нитки і аргумент цієї функції.

wtty_t * ctty; 

void * stack;
physaddr_t stack_pa;
size_t stack_size;

void * kstack;
physaddr_t kstack_pa;
size_t kstack_size;
void * kstack_top; // What to load to ESP

void * start_func_arg;
void (*start_func)(void *);


sleep_flags — ознаки засипання нитки з тієї чи іншої причини. Якщо не нуль — нитка запускати не можна (чекає м'ютексу, таймера, не народилася, померла тощо). thread_flags — різні ознаки нитки: нитка обслуговує віртуальну машину Фантом, у нитки стався таймаут примітиву синхронізації і т. п.

waitcond/mutex/sem — нитка спить на цьому примітив, чекає його звільнення. ownmutex — ця нитка замкнула цей mutex, якщо помре — треба звільнити. (Для семафора все, на жаль, неочевидно.)

sleep_event — застосовується якщо примітив синхронізації замкнений з таймаутом — таймерна підсистема ядра зберігає тут стан таймерного запиту.

chain — застосовується при постановці нитки в чергу якщо одного примітиву синхронізації чекає кілька ниток.

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

u_int32_t thread_flags; // THREAD_FLAG_xxx

/** if this field is zero, thread is ok to run. */
u_int32_t sleep_flags; //THREAD_SLEEP_xxx

hal_cond_t * waitcond;
hal_mutex_t * waitmutex;
hal_mutex_t * ownmutex;
hal_sem_t * waitsem;

queue_chain_t chain; // used by mutex/cond code to chain waiting threads
queue_chain_t kill_chain; // used code to kill chain threads to kill

//* Used to wake with timer, see hal_sleep_msec
timedcall_t sleep_event; 


snap_lock — нитка знаходиться в стані, в якому не можна робити snapshot.

preemption_disabled — нитка не можна знімати з процесора. Взагалі-то сенсу в цій штуці майже немає, особливо в SMP середовищі.

death_handler — буде викликаний, якщо нитка померла. atexit.

trap_handler — це аналог того, що в user mode називається сигнали — функція викликається, якщо нитка призвела до эксепшну процесора.

int snap_lock; // nonzero = can't begin a snapshot
int preemption_disabled;

//! void (*handler)( phantom_thread_t * )
void * death_handler; // func to call if thread is killed

//! Func to call on trap (a la unix signals), returns nonzero if can't handle
int (*trap_handler)( int sig_no, struct trap_state *ts );


Решта — машинерія шедулера. Тут все просто:

priority містить пріоритет нитки (разом з класом — realtime, normal, idle)

ticks_left — скільки «твк» (10 мсек інтервалів) нитка відпрацює на процесорі

runq_chain — якщо нитка готова до виконання, але не виконується, то вона присутня у черги на виконання.

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

u_int32_t priority;

/**
* How many (100HZ) ticks this thread can be on CPU before resched.
* NB! Signed, so that underrun is not a problem.
**/
int32_t ticks_left;

/** Used by runq only. Is not 0 if on runq. */
queue_chain_t runq_chain;

/** Will be unlocked just after this thread is switched off CPU */
hal_spinlock_t *sw_unlock;


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

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

Уф. Напевно, на сьогодні — все.

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

0 коментарів

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