Теорія операційної системи

:: Меню ::

Головна
Представлення даних в обчислювальних системах
Машинні мови
Завантаження програм
Управління оперативною пам'яттю
Сегментна і сторінкова віртуальна пам'ять
Комп'ютер і зовнішні події
Паралелізм з точки зору програміста
Реалізація багатозадачності на однопроцесорних комп'ютерах  
Зовнішні пристрої
Драйвери зовнішніх пристроїв
Файлові системи
Безпека
Огляд архітектури сучасних ОС

:: Друзі ::

Карта сайту
 

:: Статистика ::

 

 

 

 

 

Витісняюча багатозадачність

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

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

Цей механізм, званий time slicing або розділення часу реалізований в мікрокоді трансп'ютера і практично у всіх сучасних ОС. Спільною назвою для всіх методів перемикання ниток за ініціативою системи є термін витісняюча (preemptive) багатозадачність. Таким чином, що витісняє багатозадачність протиставляється кооперативною, в якій перемикання відбувається лише за ініціативою самого завдання. Розділення часу є окремим випадком витісняючої багатозадачності. У системах з пріоритетами, витіснення поточного завдання відбувається не лише по сигналах таймера, але і у разі, коли по якихось причинах (чаші всього із-за зовнішньої події) активізується процес, з пріоритетом вище, ніж в поточного.
При цьому питання вибору кванта часу є нетривіальною проблемою. З одного боку, надмірно короткий квант приведе до того, що велику частину часу система займатиметься перемиканням потоків. З іншого боку, в інтерактивних системах або системах реального часу дуже великий квант приведе до неприпустимо великого часу реакції.
У системі реального часу ми можемо оголосити нитки, яким треба швидко реагувати, високопріоритетними і на цьому заспокоїтися. Проте не можна так вчинити з інтерактивними програмами в розрахованій на багато користувачів або потенційно розрахованій на багато користувачів ОС, як UNIX на настільній машині х86 або Sun.
З психології сприйняття відомо, що людина починає відчувати затримку відповіді при величині цієї затримки близько 100 мс. Тому в системах розділеного часу, розрахованих на інтерактивну роботу, квант зазвичай вибирають рівним десяткам мілісекунд. У старих системах, орієнтованих на пакетну обробку обчислювальних завдань, таких як ОС ДІСПАК на БЕСМ-6, квант міг досягати десятих доль секунди або навіть секунд. Це підвищує ефективність системи, але робить неможливою або, принаймні, незручною — інтерактивну роботу. Багато сучасних систем підбирають квант часу динамічно для різних класів планерування і пріоритетів процесу.
Системи реального часу зазвичай мають два класу планерування — реального і розділеного часу. Клас планерування, як правило, дається не окремим ниткам, а цілком процесам. Процеси реального часу не уриваються по сигналах таймера і можуть бути витиснені лише активізацією пріоритетнішої нитки реального часу. Нитки реального часу високого пріоритету фактично працюють в режимі кооперативної багатозадачності. Зате нитки процесів розділеного часу витісняються і один одним по сигналах таймера, і процесами реального часу у міру їх активізації.
Витісняюча багатозадачність має багато переваг, але якщо ми про сто викликатимемо описаний в попередньому розділі Threadswitchпо перериваннях від таймера або іншого зовнішнього пристрою, то таке перемикання непоправно порушуватиме роботу ниток, що перериваються.
Дійсно, призначена для користувача програма може використовувати какой-тл з регістрів, який не зберігається при звичайних викликах. Тому, наприклад, обробники апаратних переривань зберігають в стеку всі використовувані ними регістри. До речі, якщо наша функція Threadswitch зберігатиме в стеку всі регістри, то станеться саме те, чого ми хочемо. Threadswitch викликається по перериванню, зберігає регістри поточної нитки в поточному стеку, перемикається на стек нової нитки, відновлює з її стека її регістри, і нова нитка отримує управління так, ніби і не втрачала його.
Повний набір регістрів, які потрібно зберегти, щоб нитка не відмітила перемикання, називається контекстом нитки або, залежно від прийнятої в конкретній ОС термінології, контекстом процесу. До таких регістрів, як мінімум, відносяться всі регістри спільного призначення, покажчик стека, лічильник команд і слово достатку процесора. Якщо система використовує віртуальну пам'ять, то в контекст входять також регістри диспетчера пам'яті, керівники трансляцією віртуальної адреси (приклад 8.3).

Приклад 8.3. Функція перемикання контексту в ядрі Linux/x86

/* Фрагмент файлу \arch\i386\kernel\process.c.
* Збереження і відновлення регістрів спільного призначення
* і сегментних регістрів CS, DS і S3 здійснюється при вході в ядрі *и при виході з нього відповідно. */
/*
* switch_to(х,у) повинна перемикати завдання з х на в *
* Ми використовуємо fsave/fwait, тому виключення [співпроцесора]
* скидаються в потрібний момент часу (поки виклик з боку
* fsave або fwait обробляється), і не можуть бути послані
* іншому процесу. Відкладене збереження FP більш не має
* сенсу на сучасних ЦПУ і це багато що спрощує (SMP і UP
* [uniprocessor, однопроцесорна конфігурація] тепер
* обробляються однаково).
Раніше ми використовували апаратне перемикання
* контексту. Причина, по якій ми більше так не робимо
* стає очевидна, коли ми намагаємося акуратно відновитися
* із збереженого достатку, який став неприпустимим
* (зокрема, заслання, що висять, в сегментних регістрах).
* При використанні апаратного перемикання контексту немає способу
* розумним чином вийти з поганого достатку [контексту]. *
* Те, що Intel документує апаратне перемикання контексту як
* повільне — відверта нісенітниця, цей код не дає помітного прискорення.
* Проте тут є деякий простір для поліпшення, тому
* питання продуктивності можуть рано чи пізно опинитися актуальні.
* [В даному випадку], проте, нам важливіше, що наша реалізація * забезпечує велику гнучкість.
*/ void __switch_to(struct task_struct *prev_p, struct task_struct *next_p)
(
struct thread_struct *prev = &prev_p->thread, Д *next = &next_p->thread;
struct tss_struct *tss = init_tss + smp_processor_id();
unlazy_fpu (prev__p) ;
/*
* Перезавантажити espo, LOT і покажчик на таблицю сторінок: */
tss->espo = next->espo;
/*
* Зберегти %fs і %gs. He потрібно зберігати %ез і %ds,
* бо при виконання в контексті ядра це
* завжди сегменти ядра. */
asm volatile("movl %%fs,%0":"=m" (* (int *)&prev->fs)); asm volatile("movl %%gs,%0":"=m" (*(int *)&prev->gs));
* Відновити Its і Ч
loadsegment(fs, next->fs); loadsegment(gs, next->gs);
/*
* Якщо це необхідно, перезавантажити налагоджувальні регістри */ if (next->debugreg[7]){
loaddebug(next, 0};
loaddebug(next, 1);
loaddebug(next, 2);
loaddebug(next, 3);
/* не 4 і 5 */
loaddebug(next, 6);
loaddebug(next, 7);
if (prev->ioperm || next->iopenn) { if (next->ioperm) {
*
/*
* Копіювання чотирьох ліній кеша .... не добре, але
* і не так вже погано. У кого-небудь є ідея краще?
* Воно впливає лише на процеси, використовуючі iopermo.
* [Розміщення цих TSS в області 4k-tlb і ігри з віртуальною
* пам'яттю для перемикання бітової маски ввода/вивода на
* самій справі неприйнятні.] */
memcpy(tss->io_bitmap, next->io_bitmap
Io_bitmap_size*sizeof(unsigned long)); tss~>bitmap = Io_bitmap_offset; } else /*
* Зсув бітової маски, вказуючий за межі обмежувача, "- - >
* породжує контрольоване SIGSEGV, якщо процес намагається
* використовувати команди звернення до портів. Перший виклик
* sys_ioperm() встановлює бітову маску коректно. */
tss->bitmap = INVALID 10 BITMAP OFFSET;

Примітка
Планувальник повинен повністю зберігати контекст процесу. Це значно ускладнює життя розробникам процесорів: додавши процесору зайвий регістр (як службовий, так і спільного призначення), ми ризикуємо втратити сумісність зі всіма ОС для нашого процесора, що реалізовують витісняючу багатозадачність. Наявність команд збереження контексту не вирішує цієї проблеми — адже ОС повинна виділяти пам'ять під контекст, що зберігається, а для цього необхідно знати його розмір.
Саме тому, зокрема, процесори SPARC і х86 реалізують "мультимедійні" розширення систем команд (групові операції над 8-бітовими цілими числами) з використанням вже існуючих регістрів арифметичного співпроцесора, а не додаткових регістрів.

Як правило, виявляється незручним зберігати контекст саме в стеку. Тоді його зберігають в якійсь іншій області пам'яті, найчастіше в дескрипторі процесу. Багато процесорів мають спеціальні команди збереження і завантаження контексту. Для реалізації витіснення досить зберегти контекст поточної нитки і завантажити контекст наступної активної нитки з черги. Необхідно надати також і функцію перемикання ниток за їх власною ініціативою, аналогічну Threadswitch або, точніше Deactivatethread.
Зазвичай замість Deactivatethread система надає високорівневі примітиви синхронізації, наприклад семафори або примітиви гармонійної взаємодії. Виклик Deactivatethread виявляється прихованим усередині таких високорівневих функцій.
Витісняючий планувальник з розділенням часу ненамного складніше за кооперативного планувальника — і той, і іншою реалізуються декількома десятками рядків на асемблері. У роботі (Прохоров 1990| приводиться повний асемблерний текст пріоритетного планувальника системи Vax/vms, що займає одну сторінку (авторові невідомо, чи не порушує авторські права фірми DEC публікація цього тексту). Втім, планувальники, розраховані на багатопроцесорні машини, часто бувають дещо складніше (приклад 8.4).

Приклад 8.4. Планувальник Linux 2.5

/*
* 'schedule!)' — функція планувальника. Це дуже простий і
* приємний планувальник: він не досконалий, але поза сумнівом працює
* в більшості випадків.
* The goto is "interesting".
*
* ЗАУВАЖЕННЯ!! Завдання 0 є 'порожнім' завданням, яке викликається
* коли жодна інше завдання не може виконуватися. Вона не може бути
* "убита" і не може "спати". Інформація про полягання в task[0] ніколи
* не використовується.
*/
asmlinkage void schedule(void)
{
struct schedule_data * sched_data;
struct task_struct *prev, *next, *p;
struct list_head *tmp;
int this__cpu, з;
if (!current->active_mm) BUG(); need_resched_back: prev = current; this_cpu = prev~>processor;
if (in_interrupt())
goto scheduling_in_interrupt;
release_kernel_lock(prev, this_cpu);
/* Виконати адміністративну роботу тут, поки ми не тримаємо
* жодного блокування.
*/
if (softirq_active(this_cpu)& softirq_mask(this_cpu))
goto handle_softirq; handle_softirq_back:
/*
* 'shed data" захищена неявно, тим фактом, що ми можемо виконувати
* лише один процес на одному ЦПУ. */
sched__data = & aligned_data[this_cpu].schedule_data;
spin_lock_irq (&runqueue__lock) ;
/* Перемістити вичерпаний процес RR в кінець [черги] */ if (prev->policy == Sched_rr)
goto move_rr_last; pove_rr_back:
switch (prev->state) { case TASKJLNTERRUPTIBLE:
if (signal_pending (prev) ) { prev->state = Task_running; break; } default:
dei_f rom_runqueue (prev) ; case Task_running: ;
}
prev->need_resched = 0;
/*
* це власне планувальник: */
repeat_schedule : /*
* Вибрати процес за умовчанням. . . */
next = idle_task(this_cpu); з = -1000;
if (prev->state == Task_running) goto still_running;
still_running_back :
list_for_each (tmp, srunqueue_head) {
p = list_entry (tmp, struct task_struct, run_list) ; if (can_schedule (p, this_cpu) ) {
int weight = goodness (p, this_cpu, prev->active_mm) ; if (weight > з)
з = weight, next = p;
/* Чи слідує перевичисліть лічильники? */
if (!c)
goto recalculate; /*
* з цієї миті ніщо ке може перешкодити нам
* перемкнутися на наступне завдання, відзначити цей
* факт в sched_data. */
sched_data->curr = next; tifdef Config_smp
riext->has_cpu = I;
next->processor = this_cpu; lendif
spin_unlock__irq (&runqueue_lock) ;
if (prev == next) goto same_process;
ttifdef Config_smp /*
* Підтримувати значення 'Last schedule' для кожного процесу
* (його необхідно перерахувати лажі якщо ми плануємо той же
* процес). Зараз це значення використовується лише в SMP, і воно
* приблизно, тому ми не зобов'язані підтримувати його
* поки захоплено блокування runqueue. */
sched_data->last_schedule = get_cycles();
/*
* Ми знімаємо блокування планувальника рано (це глобальна
* блокування), тому ми повинні захистити попередній процес
* від повторного планерування під час switch_to(). */
ttendif /* Config_smp */
kstat.context_swtch++; /*
* Перемикання контексту впливає на три процеси:
prev
.. ==> (last => next)
* Це 'prev', 'далеко передуючий' розміщеному в стеку 'next1
* але функція switch_to() встановлює prev на (тільки що
* що працював) процес 'last'.
* Опис декілька заплутано, але не позбавлено глибокого сенсу
*/
prepare_to_switch ( ) ;
{
struct mm struct *mm = next->mm;
struct mm_struct *oldmm = prev->active_mm;
if ( !mmi (
if (next->active_mm) BUG ( ) ;
next->active_mm = oldmm;
atomic_inc (&oldmm->mra_count) ;
enter_lazy_tlb (oldmm, next, this_cpu) ; } else {
if (next->active_mm != mm) BUG ( ) ;
switch_mm(ol<±nm, mm, next, this__cpu);
if ( !prev->irin) (
prev->active_mm = NULL; mmdrop (oldmm) ;
/*
* Цей оператор лише перемикає достаток регістрів
* і стека. */
switch_to(prev, next, prev); __schedule_tail(prev);
same_process:
teacquire_kernel__lock (current) ; if (current->need_resched) goto need reached back;
recalculate: {
struct task_struct *p;
spin_unlock_irq (&runqueue_lock) ;
read_lock (&tasklist_lock) ;
for_each_task (p)
p->counter = (p->counter » 1) + Nice_to_ticks (p->nice)
read_unlock (&tasklist__lock) ;
spin_lock_irq (&runqueue_lock) ; } goto repeat_schedule;
still_running:
з = goodness (prev, this_cpu, prev->active_mm) ; next = prev;
goto still_running_back;

handle_sof tirq: do_softirq ( ) ; goto handle_softirq_back;
move_rr_last :
if ( !prev->counter) (
prev->counter = Nice_to_ticks (prev->nice) ; move_last_runqueue (prev) ; } goto move_rr_back;
scheduling_in_interrupt :
printk ("Scheduling in interrupt\n") ;
BUG ( ) ;
return;

Контексти сучасних процесорів
В сучасних процесорів, що мають десятки регістрів спільного призначення і віртуальну пам'ять, розмір контексту процесу вимірюється сотнями байтів. Наприклад, в процесора VAX контекст процесора складається з 64 32-розрядних слів, тобто 256 байт. При цьому VAX має лише 16 регістрів спільного призначення, а велика частина останніх регістрів так чи інакше відноситься до системи управління віртуальною пам'яттю.
В мікропроцесорів SPARC, що мають регістровий файл об'ємом до декількох кілобайт, контекст, на перший погляд, має бути жахливого розміру. Проте програмі одночасно доступні лише 32 регістри спільного призначення, 24 з яких утворюють вікно, що ковзає по регістровому файлу. Завдяки цьому факту, контекст процесора SPARC складається лише з перших восьми регістрів спільного призначення і службових регістрів. Регістрове вікно нової нитки виділяється у вільній області регістрового файлу, а його пересування обробляється за допомогою виключень заповнення і очищення вікна.
Якщо в системі всього декілька активних процесів, може опинитися так, що їх регістрові вікна постійно "живуть" в регістровому файлі, тому об'єм даних, реально копійованих при перемиканні ниток, в SPARC не більше, ніж в CISC-процессоров з невеликою кількістю регістрів спільного призначення. Втім, і в SPARC, і в CISC-процессоров основну за об'ємом частину контексту процесу складають регістри диспетчера пам'яті.
На цьому заснована перевага трансп'ютера перед процесорами традиційних і RISC-архитектур. Річ у тому, що трансп'ютер не має диспетчера пам'яті, і у нього взагалі дуже мало регістрів. У гіршому разі, при перемиканні процесів (у трансп'ютері, як і в старих ОС, нитки називаються процесами) повинно зберігатися 7 32-розрядних регістрів. В кращому разі зберігаються лише два регістри — лічильник команд і статусний регістр. Крім того, перенастроюється регістр wptr, який виконує за сумісництвом функції покажчика стека, базового регістра сегменту статичних даних процесу і покажчика на дескриптор процесу.
Трансп'ютер має три арифметичні регістри, створюючих регістровий стек. При цьому звичайне перемикання процесів може відбуватися лише, коли цей стек порожній. Така ситуація виникає досить часто; наприклад, цей стек зобов'язаний бути порожнім при викликах процедур і навіть при умовних і безумовних переходах, тому циклічна програма не може не мати крапок, в яких вона може бути перервана. Згадані в попередньому розділі команди звернення до лінкам також виконуються при порожньому регістровому стеку. Тому, виявляється досить перезавантажити три керівників регістра, і ми передамо управління наступному активному процесу.
Операція перемикання процесів, а також установка процесів в чергу при їх активізації повністю реалізовані на мікропрограмному рівні.
Деактівізация процесу відбувається лише за його ініціативою, коли він починає чекати сигналу від таймера або готовності лінка. При цьому процес виконує спеціальну команду, яка встановлює його в чергу чекаючих відповідної події, і завантажує контекст чергового активного процесу. Коли приходить сигнал таймера або дані по лінку, то також викликається мікропрограма, яка встановлює активізований процес в кінець черги активних.
В трансп'ютера також існує мікропрограмний реалізований режим розділення часу, коли по сигналах внутрішнього таймера активні про цесси циклічно переставляються усередині черги. Такі перемикання но вже говорилося, можуть відбуватися лише, коли регістровий стек текущег процесу порожній, але подібні ситуації виникають досить часто.
Окрім звичайних процесів в системі існують так звані високопрі орітетниє процеси. Якщо такий процес отримує управління в результаті зовнішньої події, то поточний низькопріоритетний процес буде перерваний незалежно від того, порожній його регістровий стек чи ні. Для того, щоб при цьому не зруйнувати перерваний процес, його стек і весь останній контекст записуються в швидку пам'ять, розташовану на кристалі процесора. Це і є той самий гірший випадок, про який говорилося раніше. Весь цикл перемикання займає 640нс в порівнянні з десятками і, деколи, сотнями мікросекунд в традиційних процесорів [INMOS 72 TRN 203 02, Харп 1993].
Завдяки такій організації трансп'ютер не має рівних собі за часом реакції на зовнішню подію. На перший погляд, мікропрограмна реалізація такої досить складної конструкції, як планувальник, знижує гнучкість системи. Насправді, в сучасних системах планувальники мають досить стандартну структуру, і реалізація, виконана в трансп'ютері, дуже близька до цього стандарту, відомого як мікроядро (microkernel) (див. разд. Монолітні системи або системи з мікроядром).

 

:: Реклама ::

 

:: Посилання ::


 

 

 


Copyright © Kivik, 2017