Керування потоками в Linux
3. 6. 1 Базова підтримка багатопотоковості
Донедавна єдиним засобом підтримки багатопотоковості в Linux був системний виклик clone(), який дає можливість створити новий процес на базі наявного. Цей виклик багато в чому схожій на виклик fork(), але має кілька особливостей.
· Для нового процесу потрібно задати спеціальний набір прапорців, що визначають, як будуть розподілятися ресурси між предком і нащадком. До ресурсів, які можна розділяти, належать алресний простір, інформація про відкриті файли, оброблювачі сигналів. Зазаначимо, що у традиційній реалізації clone() відсутнє спеціальне використання ідентифікатора процесу (pid), ідентифікатора предка та деяких інших важливих атрибутів.
· Для нового процесу порібно задати новий стек (оскільки в наслідок виклику clone() два процеси можуть спільно використовувати загальну пам'’ть, для них неприпустиме використання загального стека).
Підтримка clone() означає реалізацію багатопотоковості за схемою 1:1. Прицьому первинними в системі є процеси, а не потоки (у Linux послідовності інструкцій процесора, за якими працює ядро, називають процесами, а не потоками ядра).
Традиційна реалізація багатопотоковості в Linux визначає, що потоки користувача відображаються на процеси в ядрі. Тому недоцільно розглядати окремо структури даних потоку в Linux – він відображається такою ж самою структурою task_struct, як і процес.
Недоліки традиційної підтримки багатопоковості в Linux
Основи підтримки багатопотоковості в ядрі Linux не зазнали принципових змін від появи системного виклику clone(). За цей час Linux із експериментальної системи перетворився на систему промислового рівня, в якій виконують корпоративні застосування в цілодобовоу режимі з великим навантаженням.
Таке використання системи висунуло до реалізації багатопотоковості вимого високої надійності та масштабованості. Стало очевидно, що реалізація , заснована на системному виклику clone(), цим вимогам не відповідає. Потрібне було повне перероблення засобів реалізації багатопотоковості в ядрі.
Керування потоками є частиною стандарту POSIX з 1996 року, відповідний програмний інтерфейс дістав назву потоки POSIX.
Потоки ядра Linux
Крім процесів і потоків користувача, Linux також підтримує спеціальний вид планованих об’єктів, яки мають уже знайому назву – потоки ядра. Такі потоки планують як звичайні процеси і потоки, кожен з яких має свій ідентифікатор (pid). Відмінності потоків ядра від процесів і потоків користувача полягають у тому, що:
· функції потоку для них визначають у коді ядра;
· вони виконуються тільки в режимі ядра;
· для них недоступні ділянки пам’яті, виділені в режимі користувача.
3. 6. 2 Програмний інтерфейс керування потоками
Створення потоків
Щоб додати новий потік у поточний процес, у POSIX використовують функцію pthread_create() із таким синтаксисом:
#include<pthread.h>
int pthread_create(pthread_t *th, pthread_attr *attr,
void *(*thread_fun)(void *).void *arg);
Розглянемо параметри цієї функції:
· th – покажчик на заздалегідь визначену структуру типу pthread_t, яка далі буде передана в інші функції роботи з потоками; далі називатимемо ії дескриптором потоку(thread handle).
· Attr – покажчик на структуру з атрибутами потоку (для використання атрибутів за замовченням потрібно передавати нульовий покажчик, деякі атрибути розглянемо пізніше);
· thread_fun – покажчик на функцію потоку, що має описуватися як
void *mythread_fun(void *value)
{
//виконання коду потоку
}
· arg – дані, що передаютьсяу функцію потоку (туди вони потраплять як параметр value).
Приклад створення потоку POSIX:
#include<pthread.h>
// функція потоку
void *thread_fun(void *num)
{
printf(“потік номер %d\n”,(int)num);
}
//……………………………
pthread_t th;
// створюємо другий потік
pthread_create(&th, NULL,thread_fun,(void *)++thread_num);
// тут паралельно виконуються два потоки
Новий потік починає виконуватися паралельно із потоком, що його створив. Наприклад, якщо всередині функції main() був створений потік, то виконання продовжать два потоки: початкової програми, що виконує код main(), і новий.
Завершення потоків POSIX
Для завершення потоку достатньо дійти до кінця його функції потоку еркthread_fun() або викликати з неї pthread_exit():
#include<pthread.h>
void pthread_exit(void *retval);
Параметр retval задає код повернення. Наведемо приклад завершення потоку:
void *turead_fun(void *num)
{
printf(“потік номер %d\n”,(int)num);
pthread_exit(0);
}
Для коду початкового потоку програми є дві різні ситуації:
· виконання оператора return або виконання всіх операторів до кінця main() завершує весь процес, при цьому всі потоки теж завершують своє виконання;
· виконання функції pthread_exit() усередині функціїmain() завершує тільки початковий потік, ця дія не впливає на інші потоки у програмі – вони продовжуватимуть виконання , поки самі не завершаться.
Виклик функції pthread_exit() використовують тільки для приєднуваних потоків, оскільки він не звільняє ресурси потоку – за це відповідає той, хто приєднає потік.
Очікування завершення виконання потоків
Для очікування завершення виконання потоків використовують функцію pthread_join(). Вона має такий синтаксис:
int pthread_join(pthread_t th,,void **status);
Ця функція блокує потік, де вона була викликана, доти, поки потік, заданий дескриптором th, не завершить своє виконання. Якщо status не є нульовим покажчиком, після виклику він вказуватиме на дані, повернені потоком (аргумент функції pthread_exit()). Якщо потік уже завершився до моменту виклику функції pthread_join(), його інформація має бути зчитана негайно.
Висновки
· Процеси і потоки є активними ресурсами обчислювальних систем, які реалізують виконання програмного коду. Потоком називають набір послідовно виконуваних команд процесора. Процес є сукупністі одго або декількох потоків і захищеного адресного простору, в якому вони виконуються. Потоки одного адресного простору можуть разом використовувати спільні дані, для потоків різних процесів без використання спеціальних засобів це неможливо. У традиційних системах кожен процес міг виконувати тільки один потік, виконання програмного коду пов’язували із процесами. Сучасні ОС підтримують концепцію багатопотоковості.
· Використання потоків у застосуванні означає внесення в нього паралелізму – можливості одночасного виконання дій різними фрагментами коду. Паралелізм у програмах відображає ясинхронний характер навколишнього світу, його джералами є виконання коду на декількох процесорах, операції введення-виведення, взаємодія з користувачем, запити застосувань-клієнтів. Багатопотоковість у застосуваннях дає змогу природно реалізувати цей паралелізм і домогтися високої ефективності.
· Розрізняють потоки коритувача, які виконуються в в режимі корстувача в адресному просторі процесу, і потоки ядра, з якими працює ядро ОС. Взаємовідношення між ними визначають схему реалізації моделі потоків. На практиці найчастіше вткористовують схему 1:1, коли кожному потоку користувача відповідає один потік ядра, і саме ядро відповідає за керування потоками користувача.
· Потік може перебувати в різних станах (виконання, очікування, готовності тощо). Принципи переходу з одного стану в інший залежать від принципів планування потоків і планування процесорного часу. Перехід процесу зі стану виконання у будь-який інший стан зводиться до перемикання контексту – передачі керування від одного потоку до іншого зі сбереженням стану процесора.
· Кожному процесу і потоку в системі відповідає його керуючий блок – структура даних, що містить усю необхідну інформацію. Під час створення процесу (зазвичай за допомогою системного виклику fork()) створють його керуючий блок, виділяють пам’ять і запускають основний потік. Створення потоку простіше і виконується швидше, оскільки не потрібно виділяти пам’ять під новий адресний простір.
Розділ 4 Планування процесів і потоків
Можливість паралельного виконання потоків залежить від кількості доступних процесорів. Якщо процесор один , паралельне виконання неможливо принцопово (у кожен момент часу може виконуватися тильки один потік). Якщо кількість процесорів N>1, паралельне виконання може бути реалізоване тільки для N потоків (по одному потокові на процесор).
Якщо потоків у системі більше, ніж доступгих процесорів, ОС повинна розв’язувати задачу планування (scheduling). Головна мета планування для однопроцесорної системи полягає у такій організації виконання кількох потоків на одному процесорі, за якої у користувача системи виникало б враження, що вони виконуються одночасно.
Це означення може бути розширене на багатопроцесорні системи у разі виникнення задачі планування, коли кількість потоків перевищує кількість доступних процесорів.
Розглянемо основні види планування, їхні принципи та алгоритми.
4. 1 Загальні принципи планування
Розглянемо основні принципи, що лежать в основі планування.
4. 1. 1 Особливості виконання потоків
З погляду планування виконання потоку можна зобразити як цикл чергування періодів обчислень (використання процесора) і періодів очікування введення-виведення. Інтервал часу, у продовж якого потік виконує тільки інструкції процесора, називають інтервалом використання процесора (CPU birst), інтервал часу, коли потік очікує введення-виведення, - інтервалом введення-виведення (I/O burst). Найчастіше ці інтервали мають довжину від 2 до 8 мс.
Потоки, які більше часу витрачають на обчислення і менше – на введення-виведення, називають обмеженими можливостями процесора (CPU bound). Вони активно використовують процесор. Основною їхньою характеристикою є час, витрачений на обчислення, інтервали використання процесора для них довші. Потокі, яки більшу частину часу перебувають в очікуванні введення-виведення, називають обмеженими можливостями введення-виведення (I/O bound). Такі потоки завантажують процесор значно менше, а середня довжина інтервалу використання прцесора для них невелика. Що вище тактова частота процесора, то більше потоків можна віднести до другої категорії.
Потік, обмежений процесором (перемножування матриць)
 |
Потік, обмежений введенням-виведенням (текстовий редактор)
 | ||
 |
Інтервал введення-виведення (I/O bound)
 |
Інтервал використання процесора (CPU bound)
Рисунок 4.1 Класифікація потоків з погляду планування
4. 1.2 Механізми і політика планування
Слід ролщрізняти механізм і політику планування. До механізмів планування належать засоби перемикання контексту, засоби синхронізації потоків тощо, до політики планування – засоби визначення моменту часу, коли необхідно перемкнути контескт. Ту частину системи, яка відповідає за політику планування називають планувальником (scheduler), а алгоритм, що використовують при цьому – алгоритмом планування (scheduling algorithm).
Є різіні критерії оцінкиполітики планування, одні з ніх застосовні для всіх систем, інші – лише для пакетних систем або лище для інтерактивних.
Сьогодні найчастіше використовують три критерії оцінки досягнення мети.
· Мінімальний час відгуку. Це найважливіший крітерій для інтерактивних систем. під часом відгуку розуміють час між запуском потоку (або введенням користувачем інтерактивної команди) і отриманням першої відповіді. Для сучасних систем прийнятим часом відгуку вважають 50-150мс.
· Максимальна пропускна здатність. Це кількість задача, які система може виконувати за одиницю часу (наприклад, за секунду).Такий критерій доцільно застосовувати у пакетних системах; в інтерактивних системах він може бути використаний для фонових задач. Щоб підвищити пропускну здатність, необхідно:
· Скорочувати час даремного навантаження (наприклад, час, необхідний для перемикання контексту);
· Ефективніше використати ресурси (для того, щоб ані процесор, ані пристрої введення-виведення не простоювали).
· Третім критерієм є справедливість, яка полягає в тому, що процесорний часпотокам виділяють відповідно до їх важливості. Справедливість забезпечує такий розподіл процесорного часу, що всі потоки просуваються у своєму виконанні, і жоден не протоює. Відзначимо, що реалізація справедливої політики планування не завжди приводить до зменшення середнього часу відгуку. Іноді для цього потрібно зробити систему менш справедливою.
4. 1. 3 Застовність принципів планування
Принципи планування потоків застосовні насамперед до багатопотокових систем із реалізацією схеми 1:1(тут плануються винятково потоки ядра), а також до систем з реалізацією модулі процесів. В останньому випадку замість терміна “потік” можна вживати термін “процес”, а інформацію, необхіжну для планування, зберігати в структурах даних процесів. Складніші принципи планування використовують у багатопотокових системах, для яких кількість потоків користувача не збігається з кількістю потоків ядра (схеми 1:M і M:N). Для них потрібні два планувальники: один для роботи на рівні ядра, інший – у режимі користувача.
Види планування
Розрізняють планування довнотермінове (long-term scheduling), cередньотермінове (medium-term scheduling) і короткотермінове (short-term schediling).
4. 2. 1 Довготермінове планування
Засоби довготермінового планування визначають, яку з програм треба у пам’ять завантажити для виконання. Таке планування також називають статичним, оскільки воно не залежить від поточного стану системи. Воно відігравало важливу роль у пакетних системах, коли заздалегідь відомо, які процеси повинні бути виконані і можна скласти розклад виконання задач. В інтерактивних системах (наприклад, у системах з розподілом часу) завантаження процесів у пам’ять здійснюють переважно користувачі, і це плануванню не підлягає; тому в них зазвичай використовують спрощену стратегію довготермінового планування. Система дає можливість створювати процеси і потоки до досягнення деякої максисально можливої межі, після чого подальші спроби створити новий процес або потік спричинятимуть помилку. Така стратегія грунтується і на психології користувачів, які, почуваючи себе некомфортно в перевантаженій системі, можуть переривати роботу з нею, що призводить до зниження навантаження.
4. 2. 2 Середньотермінове планування
Засоби середньотермінового планування керують переходом потоків із призупиненого стану в стан готовності й назад. Відразу ж зазаначимо, що керуючі блоки готових до виконання потоків організуються у пам’яті в структуру, яку називають чергою готових потоків (ready queue).
Перехід потоку в призупинений стан можуть викликати такі фактори:
· очікування операції введення-виведення;
· очікування закінчення виконання іншого потоку (приєднання);
· блокування потоку через необхідність його синхронізації з іншими потоками.
Зазвичай, для коректної організації такого очікування, крім черги готових потоків, реалізують додатковий набір черг. Кожна така черга пов’язана з ресурсом, який може викликати очікування потоку (наприклад, із пристроєм введення-виведення); ці черги ще називають чергами планування (schediling queues) або чергами очікування (wait queues). Середньотерміновий плануваг\льник керує всіма цими чергами, переміщаючи потоки між ними та чергою готових потоків. На рис. 4.2 зображена структура черг планування.
4. 2. 3 Короткотермінове планування
Короткотермінове планування , або планування процесора (CPU scheduling), є найважливішим видом планування. Воно дає змогу відповісти на два базових запитання:
· Коли перервати виконання потоку?
· Якому з потоків з числа готових до виконання потрібно передати процесор у цей момент?
Короткотерміновий планувальник – це підсистема ОС, яка в разі нелбхідності перериває активний потік і вибирає з черги готових потоків той, що має виконуватися. До його продуктивності ставлять найвищі вимого, бо він отримує керування дуже часто. Виділяють також диспетчер (dispetcher), який безпосередньо предає керування вибраному потокові (перемикає контекст).
Формат черги готових потоків залежить від реалізації короткотермінового планування. Така черга може бути організована за
TCB4 TCB2
Черга готових
потоків
Пристрій 1
Пристрій 2 TCB5 TCB1
Пристрій 3
Рисунок 4. 2 Організація черг готових потоків і планування
принципом FIFO, бути чергою із приоритетами, деревом або невпорядкованим зв’язаним списком.
Усі стратегії й алгоритми планування, які ми будемо розглядати далі, належать до короткотермінового планування.
4. 3 Стратегії планування. Витісняльна і невитісняльна багатозадачність
Перед тим, як розглянути основні стратегії планування, перелічимо варіанти передачі керування від одного потоку до іншого:
· після того, як потік перейшов у стан очікування (напрклад, під час введення-виведення або приєднання);
· після закінчення виконання потоку;
· явно (потік сам віддає процесор іншим потокам на час, поки він не зайнятий корисною роботою);
· за перериванням (наприклад, переривання від таймера дає змогоу перервати потік, що виконується довше, ніж йому дозволено).
Останній варіант відрізняється від інших тим, що потік не може контролювати, коли настане час передачі керування, за це відповідає планувальник операційної системи. Залежно від такого варіанта передачі керування розрізняють дві основні стратегії планування потоків – витісняльну і невитісняльну багатозадачність.
При витісняльній багатозадачності (preemptive multitasking) потоки, що що логічно мають виконуватись, можуть бути тимчасово перервані планувальникомОС без їхньої участі для передачі керування іншим потокам. Переривання виконання потоку і передача керування іншому потокові найчастіше здійснюється в обробнику переривання від системного таймера. Така стратегія реалізована в усіх сучасних ОС.
При невитісняльній багатозадачності (non=preemptive multitasking) потоки можуть виконуватися упродовж необмеженого часу й не можуть бути перервані ОС. Для невитісняльної багатозадачності передача керування за останнім варіантом не реалізована, і потоки самі повинні віддавати керування ОС для передачі іншим потокам або, принаймні, переходити у стан очікування. Якщо якийсь поток забуде або не зможе це зробити, наприклад, займе процесор нескінченим циклом, інші потоки не зможуть продовжквати свою роботу. Таку стратегію було реалізовано у ОС Nowell Net Ware.
Природно, що реалізація невитісняльної багатозадачності в загальному випадку робить систему досить нестабільною (будь-яке некоректно написане застосування користувача може спричинити “завісання” всієї системи). Практика показує, що невитісняльна багатозадачність у системах із застосуваннями користувача не може бути реалізована. Таку стратегію, проте, можна використати в системах, де всі застосування виконуються в режимі ядра і фактично єсистемними драйверами. Для розробки таких застосувань необхідна висока кваліфікація програмістів, вимоги до надійності застосувань можна порівняти з вимогами до самої ОС. При цьоиу простота реалізації та відсутність зовнішніх переривань потоків від планувальника ОС може підвищити продуктивність системи для обмеженого кола задач (наприклад, у випадку ОС Net Ware це було використання системи як файлового серверу).
Алгоритми планування
Алгоритм планування дає змогу короткотерміновому планувальникові вибирати з готових до виконання потоків той, котрий потрібно виконувати наступним. Можна сказати, що алгоритми планування реалізують політику планування.
Залежно від стратегії планування, яку реалізують алгоритми, їх поділяють на витісняльні і невитісняльні. Витісняльні алгоритми переривають потоки під час їхнього виконання, невитісняльні – не переривають. Деякі алгоритми відповідають лише одній із цих стратегій, інші можуть мати як витісняльний, так і невитісняльний варіанти реалізації.
Планування за принципом FIFO
Розглянемр найпрстіший (“наївний”) невитісняльний алгоритм, у якому потоки ставлять на виконання у порядку їхньої появи в системі й виконують до переходу в стан очікування, явної передачі або завершення. Чергу готових потоків при цьому організовують за принципом FIFO, тому алгоритм називають алгоритмом FIFO.
Як тільки в системі створюється новий потік, його керуючий блок додається у хвіст черги, Коли процесор звільняється, його надають потоку з голови черги.
У такого алгоритму багато недоліків:
· він за визначенням є невитісняльним;
· середній час відгуку для нього може бути доволі значним (наприклад, якщо прешим надійде поток із довгим інтервалом викоритання процесора, інші потоки чекатимуть, навіть якщо вони самі використовують тільки короткі інтервали);
· він підлягає ефекту конвою (convoy effect).
Уфект конвою можна пояснити такою ситуацією. Припустимо, що в системі є один потік (назвемо його Tcpu), обмежений можливостями процесора, і багато потоків Tio, обмежених можливостями введення-виведення. Рано чи пізно потік Tcpu отримає процесор у своє розпорядження і виконуватиме інструкції з довгим інтервалом використання процесора. За цей час інші потоки Tio завершать введення-виведення, пермістяться в чергу готових потоків і там чекатимуть, при цьому пристрої введення-виведення простоюватимуть. Коли Tcpu нарешті заблокують і відбудеться передача керування, всі потоки Tio швидко виконають інструкції своїх інтервалів використання процесора (у них, як ми знаємо, такі інтервали короткі) і знову перейдуть до введення-виведення. Після цього Tcpu знову захопить процесор на тривалий час і т д.
Кругове планування
Найпростішим для розуміння і найсправедливішим витісняльним алгоритмом є алгоритм кругового планування (round-robin scheduling). У середні віки терміном “round robin” називали петиції, де підписи йдуть по колу, щоб не можна було дізнатися, хто підписався першим (ця назва свідчить, що для такого алгоритму всі потоки рівні).
Кожному потокові виділяють інтервал часу, який називають квантом часу (time quantum, time slice) і упрдовж якого цьому потокові дозволено виконуватися. Коли потік усе ще виконується після вичерпання кванту часу, його переривають і перемикають процесор на виконання йнструкцій іншого потоку. Коли він блокується або закінчує своє виконання до вичерпання кванту часу, процесор теж передають іншому потокові. Довжина кванту часу для всієї системи однакова.
Такий алгоритм реалізувати досить легко. Для цього черга готових потоків має бути циклічним списком. Коли потік вичерпав свій квант часу, його переміщують у кінець списку, туди ж надають нові потоки. (Рисунок 4. 3). Перевірку вичерпання кванту часу виконують в обробнику переривання від системного таймера.
Черга готових потоків
t
Потік, що виконується
t+q
 |
t+2*q
Рисунок 4.3. Кругове планування
Единою характеристикою, яка впливає на роботу алгоритму, є довжина кванта часу. Тут слід дотримуватися балансу між часом, що витрачається на перемикання контексту, і необхідністю відповідати на багато одночасних інтерактивних запитів.
Завдання надто короткого кванта часу приводить до того, що відбувається дуже багато перемикань контексту, і значний відсоток процесорного часу витрачається не на корисну роботу, а на ці перемикання. З іншого боку, завдання надто довгого кванта хоча й заощаджує процесорний час, але спричиняє до зниження часу відгуку на інтерактивні запити, бо якщо десять користувачів одночасно натиснуть клавішу, то десять потоків потраплять у список готових, в наслідок чого останній з них очікуватиме десять довгих квантів часу. У випадку з квантом нескінченної довжини кругове планування зводиться до алгоритму FIFO (усі потоки встигають заблокуватися або закінчитися до вичерпання кванта). На практиці рекомендують встановлювати довжину кванта в 10 – 100 мс.
Зазаначимо, що традиційне кругове планування може давати “перекіс” у бік потоків, обмежених можливостями процесора. Такі потоки переважно використовують свій квант повністю, тоді як потоки, обмежені можливостями введення-виведення,часто передають керування до вичерпання кванта, і в результаті їм достається менше процесорного часу. Для вирішення цієї проблеми можна збільшувати довжину кванта (з огляду на проблеми, описані раніше) або вводити додаткову чергу потоків, що завершили введення-виведення, яка має перевагу на виконання перед чергою готових потоків.
4. 4. 3 Планування із приоритетами
Планування за принципом кругового чергування припускає, що всі потоки однаково важливі. В іншому разі необхідно застосовувати планування із пріоритетами.
Основна ідея проста: кожному потокові надають пріоритет, при цьому на виконання ставитиметься потік із найвищим пріоритетом із черги готових потоків. Пріоритети можуть надаватися статично або динамічно.
Одним із підходів до реалізації планування із пріоритетами є алгоритм багаторівневих черг (multilevel queues). У цьому разі організують кілька черг для груп потоків із різними пріоритетами (потоки кожної групи звичайно мають різне призначення, можуть бути групи фонових потоків, інтерактивних тощо).
Рішення про вибір потоку для виконання приймають таким чином:
· якщо в черзі потоків із найвищим пріоритетом є потоки, для них слід використати простіший алгоритм планування (наприклад, кругового планування), не звертаючи уваги на потоки в інших чергах;
· якщо в черзі немає жодного потоку, переходять до черги потоків з нижчим пріоритетом іт. д.
Для різних черг можна використовувати різні алгоритми планування, крім того, кожній черзі може бути виділена певна частка процесорного часу.
Розподіл пріоритетів є складним завданням, невдале його розв’язання може призвести до того, що потоки процесів із низьким пріоритетом чекатимуть дуже довго. Наприклад, у 1973 році в Масачусетському технологічному інституті була зупинена машина, на якій знайшли процес із низьким пріоритетом – він був поставлений у чергу на виконання в 1967 році і з того часу так і не зміг запуститися. Таку ситуацію називають голодуванням (starvation).
Є різні способи розв’язання проблеми голодування. Наприклад, планувальник може поступово зменшувати пріоритет потоку, який виконують (такий процес називають старінням), і коли він стане нижче, ніж у наступного за пріоритетом потоку, перемкнути контекст на цей потік. Можна, навпаки, поступово підвищувати пріоритети потоків, які очікують.
4. 4. 4 планування на підставі характеристик подальшого виконання
Важливим класом алгоритмів планування з пріоритетами є алгоритми, в яких рішення про вибір потоку для виконання приймають на підставі знання або оцінки характеристик подальшого його виконання.
Насамперед слід відзначити алгоритм “перший – із найкоротшим часом виконання” (Shortest Time to Completition First, STCF), коли з кожним потоком пов’язують тривалість наступного інтервалу використання ним процесора і для виконання щоразу вибирають той потік, у якого цей інтервал найкоротший. У результаті потоки, що захоплюють процесор на коротший час, отримують під час планування перевагу і швидше виходять із системи.
Алгоритм STCF є теоретично оптимальним за крітерієм среднього часу відгуку, тобто можна довести, що для вибраної групи потоків середній час відгуку в разі застосування цього алгоритму буде мінімальним порівняно з будь-яким іншим алгоритмом. На жаль, для короткотермінового планування реалізувати його неможливо, тому що ця реалізація потребує передбачення очікуваних характеристик. Для довготоермінового планування його використовують досить часто (у цьому разі, ставлячи задачу на виконання, опертор повинен вказати очікуваний момент її завершення, на який система буде зважати під час вибору). Зазначимо також, що оптимальність такого алгоритму невіддільна від його “несправедливості” до потоків із довшими інтервалами використання процесора.
Для короткотермінового планування може бути реалізоване наближення до цього алгоритму, засноване на оцінці довжини чергового інтервалу використання процесора з урахуванням попередніх інтервалів того самого потоку. Для обчислення цієї оцінки можна використати рекурсивну формулу
tn+1=aTn+(1-a)tn, 0<a<1, t0=T0,
где tn+1 – оцінка довжини інтервалу;
tn – оцінка довжини попереднього інтервалу;
Tn – справжня довжина попереднього інтервалу.
Найчастіше використовують значення a=0,5, у цьому разі перерахування оцінки достатньо обчислити середнє між попередньою оцінкою і реальним значенням інтервалу.
Витісняльним аналогом STCF є алгоритм “перший – із найкоротшим часом виконання, що залишився” (Shortest Remainig time to completition first, SRTCF). Його відмінність від STCF полягає в тому, що, коли в чергу готових потоків додають новий , у якого наступний інтервал використання процесор коротший, ніж час, що залишився до завершення виконання поточного потоку, поточний потік переривається, і на його місце стає новий потік.
4. 4. 5 Багаторівневі черги зі зворотним зв’язком
Алгоритм багаторівневих черг зі зворотним зв’язком (multilevei feedback queues) є найуніверсальнішим алгоритмом планування (за допомогою налаштування параметрів його можна звести до будь-якого іншого алгоритму), але при цьому одним з найскладгіших у реалізації.
З погляду організації структур даних цей алгоритм схожій на звичайний алгоритм багаторівневих черг: є кілька черг готових потоків із різним пріоритетом, при цьому потоки черги із нижчим пріоритетом виконуються тільки коли всі черги верхнього рівня порожні.
Відмінності між двома алгоритмами полягають у тому, що:
· потокам дозволено перехолити з рівня на рівень;
· потоки в одній черзі об’єднуються не за пріоритетом, а за довжиною інтервалу використання прцесора, потоки із коротшим інтервалом перебувають у черзі з більшим пріоритетом.
Усередині всіх черг, крім найнижчої, використовують кругове планування (у найнижчій працюює FIFO-алгоритм).Різні черги відповідають різній довжині кванта часу – що вищий пріоритет, то коротший квант (звичайно довжина кванта для сусідних черг зменшується удвічі). Якщо потік вичерпав свій квант часу, він переміщається у хвіст черги із нижчим пріоритетом (і з довшим квантом).У результаті потоки з коротшими інтервалами (наприклад, оюмежені введенням-виведенням) залишаються з високим пріоритетом, а потоки з довшими інтервалами подовжують свій квант часу (Рисунок 4. 4). Можна також автоматично переміщати потоки, які давно не отримували керування, із черги нижнього рівня на рівень вище.
Потік не вичерпав кванта
Потік вичерпав квант
Потік давно не одержував керування
Черга алгоритму FIFO
Пріоритет
Рисунок 4. 4 Багаторівневі черги зі зворотним зв’язком
Лотерейне планування
Лотерейне планування (lottery scheduling) – алгоритм, простий для розуміння і легкий у реалізації, разом з тим має великі можливості.
Ідея лотерейного планування полягає в тому, що:
· потік отримує жеяку кількість лотерейних квитків, кожен з яких дає право користуватися процесором упродовж часу T;
· планувальник через проміжок часу T вибирає випадково один лотерейний квиток;
· потік, що “виграв№, дістає керування до наступного розіграшу.
Лотерейне планування дає змогу:
· емулювати кругове планування, видавши кожному потокові однакову кількість квитків;
· емулювати планування із пріоритетами, розподіляючи квитки відпдвідно до приоритетів потоків;
· емулювати SRTCF – давати коротким потокам більше квитків, ніж довгим (якщо потік отримав хочаб один квиток, він не голодуватиме);
· забезпечити розподіл процесоного часу між потоками – дати кожному потокові кількість квитків, пропорційну до частки процесорного часу, який потрібно йому виділити (наприклад, якщо є три потоки, і треба, щоб потік A займав 50% процесора, а потоки B і C – по 25%, можна дати потоку A два квитки, а потокам B і C – по одному);
· дтнамічно міняти пріоритети, відбираючи і додаючи квитки по ходу.
Хоча більшість цих задач може бути розв’язана лотерейним плануванням лише приблизно, з деякою ймовірністю, на практиці отримують цілком задовільні результати. При цьому що довше працює система, то ближчими будуть результати до теоретичних значеь (за законом великих чисел). Насправді лотерейне планування використовує той факт, що вся ідеологія планування значною мірою є евристичною, оскільки не можна точно передбачити характер поведінки потоків у системі.
4. 5 Реалізація планування в Linux
Розглянемо два варіанти реалізації планування в Linux – традиційну (належить до ядер версій до 2.4 включно) і нову, включену в ядро
версії 2.6.
Ядро Linux при плануванні не розрізняє процеси і потоки,тому для визначеності ми надалі говоритимемо про планування процесів.
Усі процеси в системі можна поділити на три групи: реального часу із плануванням за принципом FIFO, реального часу із круговим плануванням, звичайні.
4. 5. 1 Планування процесів реального часу в ядрі
Стосовно процесів реального часу, достатньо сказати, що:
· вони завжди матимуть під час планування пріоритет перед звичайними процесами;
· процес із плануванням за принципом FIFO виконують доти, поки він сам не віддасть процесор (наприклад, в наслідок призупинення або завершення) або поки він не буде витиснений процесом реального часу із вищим пріоритетом;
· те саме стосується процесу із круговим плануванням, крім того, що він додатково буде витіснений після вичерпання кванта часу.
4. 5. 2 Традиційний алгоритм планування
Розглянемо алгоритм планування звичайних процесів. В основі алгоритму лежить розподіл процесорного часу на епохи (epochs). Упродовж епохи кожен процес має квант часу, довжину якого розраховують у момент початку епохи. Здебільшого різні процеси мають кванти різної довжини. Коли процес вичерпав свій квант, його витісняють і протягом поточної епохи він більше не виконуватиметься. Керування віддають іншому процесові. Якщо ж процес був призупинений для виконання введення-виведення або внаслідок синхронізації, його квант не вважають вичерпаним і він може бути вичерпаний планувальником упродовж поточної епохи. Епоха закінчується, коли всі готові до виконання процеси вичерпали свої кванти. У цьому разі алгоритм планування перераховує кванти для всіх процесів і розпочинає нову епоху.
Квант, який задають на початку епохи, називають базовим квантом часу процесу. Його значення можуть динамічно змінюватися системними викликами nice() і setpriority(). Процес-нащадок завжди успадковує базовий квант свого предка.
Пріоритет процесау буває двох видів: фіксований, для процесів реального часу, що задають тільки під час створення процесу, та динамічний, для звичайних процесів, який залежить від базового пріоритетуі часу, що залишився до вичерпання кванта. Динамічний пріоритет будь-якого звичайного процесу завжди нижчий за будь-який пріоритет процесу реального часу.
Опишемо найважливіші поля структури даних процесу стосовно планування:
· policy – визначає, до якої групи відноситься процес (звичайні, реального часу за алгоритмом FIFO тощо);
· nice – задає величину, на якій грунтується базовий квант часу процесу (надалі для спрощення вважатимемо nice рівним базовому кванту, насправді ц не зовсім так);
· counter – містить кількість переривань таймера, що залишилися до вичерпання кванту процесу. На початку епохи counter надають значення базового кванта і зменшують його на одиницю в обробнику переривання таймера.
Умови виклику процедури планування
Розглянемо ситуації, коли відбувається виклик процедури планування (її називають scedule()).
· Коли процес повинен бути заблокований через те, що потрібний йому ресурс у цей час недоступний. У цьому разі його керуючий блок спочатку додають у відповідну чергу очікування, а потім відбувається перепланування.
· За допомогою відкладеного запуску (lazy invocation). Відкладений запуск полягає в тому, що що у певний момент часу спеціальному полю need_reschedструктури процесу надають значення 1. Це відюувається в таких випадках: коли поточний процес вичерпав свій квант; коли у стан готовності переходить процес, пріоритет якого вищий, ніж у поточного; коли процес явно поступається своїм правом виконання через відповідний системний виклик. При цьому негайно перепланування не відбувається, але пізніше, коли цей процес повинен знову отримати керування після переривання, він перевіряє, чи не дорівнює поле need_resched одиниці. Якщо рівність виконується, запускають процедуру планування.
Процедура планування
Ця процедура спочатку перевіряє, чи не переходить поточний процес у стан очікування, і якщо це так, вилучає його з черги готових процесів. Потім вибирається процес для виконання. Для цього проглядають чергу готових процесів, для кожного процесу оцінюють динамічний пріоритет і вибирають процес і з максимальним його значенням. Для процесу, що вичерпав свій квант часу, він дорівнюватиме нулю.
Якщо жоден процес не був вибраний, поточний процес продовжує виконуватися. Коли ж вибір відбувся, контекст перемикають на новий процес.
Початок нової епохи
Особлива ситуація виникає тоді, коли для всіх процесів у черзі готових процесів значення динамічного пріоритету дорівнює нулю, тобто всі вони вичерпали свій квант, і настав час починати нову епоху. Проте це не означає, що система взагалі не має процесів, для яких квант не вичерпаний, - вони можуть перебувати в чергах очікування (найчастіше, це процеси, обмежені введенням-виведенням.
Коли розпочиняється нова епоха, відбувається перерахування квантів для всіх процесів системи (не тільки для процесів у стані готовності). При цьому довжину кванта для кожного процесу задають рівною сумі його базового пріоритету і половини частини кванта, що залишилася в нього:
for each_task(p)
p.counter=(p.counter/2)+p.nice;
Оскільки до початку нової епохи ненульовий квант залишається тільки у процесів, які не перебувають у стані готовності, цей алгоритм надає певну перевагу процесам, обмеженим можливостями введення-виведення. При цьому значення кванта для процесу ніколи не зможе стати більшим, ніж подвоєне значення його базового пріоритету.
Розрахунок динамічного пріоритету
Повернемося до обчислення динамічного пріоритету. Для цього використовують функцію goodness(). Розглянемо можливі значення, які вона може повернути.
· 0 – у разі, коли процес вичерпав свій квант часу. Цей процес не буде вибраний для виконання. Крім випадку, коли він стоїть у черзі готових процесів першим, а всі інші процеси черги також вичерпали свій квант.
· Від 0 до 1000 – у разі, коли процес не вичерпав свого кванту часу. Це значення розраховують на основі значення базового кванта процесу і частини поточного кванта, що залишилася в нього. Спрощено це можна зобразити так:
c=p.counter+p.nice;
де p – покажчик на керучий блок процесу.
Звідси випливає, що більше часу залишилося процесу для виконання і що довший його базовий квант, то вищий його пріоритет. Крім того, це значення додатково збільшують на одиницю для процесів, які використовують ту саму пам’ять, що й предки (наприклад, якщо процес відображає потік, створений за допомогою функції clone()).
Перерахування кванта під час створення нового процесу
Розглянемо, що відбувається під час створення нового процесу. Найпростіше рішення (копіювати значення counter у структуру даних нащадка) може призвести до того, що процеси будуть штучно продовжувати свій квант створенням нових нащадків, виконуючих той самий код. Для того, щоб цьому перешкодити, після функції fork() значення counter розділяють навпіл: одна половина переходить нащадкові, інша залишається предкові.
Перелічимо недоліки алгоритму.
· Вибір процесу для виконання відбувається внаслідок розрахунку динамічного пріоритету для всіх процесів у черзі готових процесів. Зі збільшенням кількості готових процесів у системі переглядати цю чергу від початку до кінця під час кожного виклику процедури планування стає невигідно.
· Якщо кількість процесів буде дуже великою, перерахування всіх динамічних пріоритетів на початку нової епохи може виконуватися дуже довго. З іншого боку, епохи змінюються рідше, що більше процесів в системі.
· Алгоритм розрахований на зменшення часу відгуку для процесів, обмежених можливостями введення-виведення, навіть, якщо вони не є інтерактивними (напрклад, фоновий процес індексації пошукової системи) і не потребують малого часу відгуку.
· Зі збільшенням кількості процесорів підтримувати загальні черги, які не враховують наявність різних процесорів, стає невигідно.
4. 5. 3 Сучасні підходи до реалізації планування
Зазначені недоліки починали істотно впливати на роботи системи, коли вона фуекціонувала за умов граничного навантаження. У звичайних умовах традиційне планування в Linux працювало досить ефективно.
Робота над виправленням недоліків тривала. Як наслідок, у ядро версії 2.6 була інтегрована нова реалізація алгоритму планування. Розглянемо коротко, як вона допомагає розв’язувати названі раніше проблеми.
Насамперед, цей алгоритм підтримує окремі черги готових процесів для кожного процесора, забезпечуючи ефективну роботу за умов багатопроцерності.
Ще одна проблема, яку має розв’язати новий алгоритм, пов’язана з необхідністю розраховувати у старому алгоритмі динамічний пріоритет для всіх готових процесів під час кожного виклику процедури планування. Рішення приймають таке: кожна черга гторових процесів – це масив черг готових процесів, де елементи упорядковані за динамічним пріоритетом. У результаті під час вибору процесу для виконання достатньо продивитись чергу з найвищим пріоритетом до першого процесу, який можна запустити. Ця процедура не залежить від кількості готових процесів у системі.
Є два масиви черг готових процесів – масив черг активних процесів і масив черг процесів з вичерпаним квантом. Після того, як процес вичерпав свій квант, його переносять із першого масиву в доугий. Коли в масиві активних черг не залишається жодного процесу, обидва масиви міняються місйями, і послідовність кроків повторюється із самого початку. У підсумку з вичерпанням квантів процесами підвищується ймовірність запуску тих процесів, які до цього часу ще не одержували керування.
4. 5. 4 Програмний інтерфейс планування
Розглянемо системні виклики Linux, за допомогою яких можна працювати із базовим пріоритетом процесів (величиною nice) і цим впливати на їхнє планування.
Для зміни базового пріоритету процесу використовують виклик
setpriority():
#include<sys/resource.h>
int setpriority(int which, int who,int priority);
Зокрема, параметр which може набувати значення PRIO_PROCESS або PRIO_USER, відповідно показуючи, що параметр who буде інтерпретований як ідентифікатор процесу чи ідентифікатор користувача. У першому випадку задають пріоритет для конкретного процесу (або для поточного процесу, якщо who дорівнює нулю), у другому – для всіх процесів цього користувача.
Параметр priority задає новий пріоритет. Пріоритет може варіюватися в межах від –20 до 20, менші значення свідчать про вищий пріоритет. Значенням за замовчуванням є 0. Негативні значення priority можуть задавати лише користувачі з правами адміністратора.
Для отримання інформації про поточний базовий пріоритет використовують виклик getpriority():
Int getpriority(int which, int who);
Цей виклик повертає значення пріоритету, параметри which і who для нього мають той самий зміст, що й для функції setpriority().
Розглянемо приклад використання цих викликів:
// задати пріоритет для поточного процесу
setpriority(PRIO_PROCESS,0,10);
// довідатися про поточне значення пріоритету
printf(“поточний пріоритет: %d\n”,getpriority(PRIO_PROCESS,0));
Для відносної зміни базового пріоритету поточного процесу можна також викоритати системний виклик nice():
#include<unistd.h>
int nice(int inc); // змінює пріорите поточного процесу на inc.
Висновки
· Задача планування потоків зводиться до організації виконання кількох потоків на одному процесорі так, аби у користувачів виникало враження, що вони виконуються одночасно. Цілями планування є: мінімізація часу відгуку, максимізація пропускної здатності та справедливість. До основних стратегій планування належать витісняльна та невитісняльна багатозадачність. У сучасних ОС застосовують витісняльну багатозадачність, коли рішення про перемикання контексту потоку приймають у коді ядра системи, а не в коді потоку.
· Розрізняють довготермінове, сереньотермінове та короткотермінове планування. Найважливіший тут короткотерміновий планувальник, котрий використовують для прийняття рішення про те, який потік запустити на виконання в певний момент. До основних алгоритмів короткотермінового планування належать планування кругове і з пріоритетами.
Розділ 5 Взаємодія потоків
Розглянемо основні принципи взіємодії потоків одного процесу. Основну увагу зосередимо на синхронізації доступу до спільно використовуваних даних таких потоків.
5. 1 Основні принципи взаємодії потоків
Потоки, які виконуються в рамках процесу паралельно, можуть бути незалежними або взаємодіяти між собою.
Потік є незалежним, якщо він не впливає на виконання інших потоків процесу, не зазанає впливу з їхнього боку, та не має з ними жодних спільних даних. Його виконання однозначно залежить від вхідних даних і називається детермінованим.
Усі інші потоки є такими, що взаємодіють. Ці потоки мають дані, спільні з іншими потоками (вони перебувають в адресному просторі їхнього процесу). Їх виконання залежить не тільки від входних даних, але й від виконання інших потоків, тобто вони є недетермінованими (далі розглянемо докладно приклади такої недетермінованості).
Результати виконання незалежного потоку завжди можна повторити, чого не можна сказати про потоки, що взаємодіють.
Дані, яки є загальними для кількох потоків, називають спільно використовуваними (shared data). Це – найважливіша концепція багатопотокового програмування. Усякий потоік може в будь-який момент часу змінити такі дані. Механізми забезпечення коректного доступу до спільно використовуваних даних називають механізмами синхронізації потоків.
Працювати із незалежними потоками простіше, ніж з тими, що взаємодіють. Програміст може не враховувати того, що одночасно з такими потоками виконуються інші, а також не звертати уваги на стан спільно використовуваних даних, з якими працює потік.
Проте обійтися без реалізації взаємодії потоків неможливо з кількох причин.
· Необхідно організовувати спільне використання інформації під час роботи з потоками. Наприклад, користувачі бази даних або веб-сервера можуть захотіти одночасно виконати запити на отримання однієї й тієї інформації, і система має забезпечити її паралельне отримання потоками, що обслуговують цих користувачів.
· Коректна реалізація токої взаємодії та використання відповідних алгоритмів можуть значно прискорити обчислювальний процес на багатопроцесорних системах. При цьому задачі розділяють на підзадачі, які виконують паралельно на різних процесорах, а потім їхні результати збирають разом для отримання остаточного розв’язання. Таку технологію називають технологією паралельних обчислень.
· У задачах, що вимагають паралельного виконання обчислень та операцій введення-виведення, потоки, що виконують введення-виведення, повинні мати можливість подавати сигнали іншим потокам із завершенням своїх операцій.
· Подібна організація дає змогу розбивати задачі на окремі виконувані модулі, оформлені як окремі потоки, що при цьому вихід одного модуля може бути входом для іншого, а також підвищується гнучкість системи, оскільки окреми модулі можна міняти, не чіпаючи інші.
Необхідність організації паралельного виконання потоків, що взаємодіють, потребує наявності механізмів обміну даними між ними і забезпечення їхньої синхронізації.
5. 2 Основні проблеми взаємодії потоків
Проблема змагання
Розглянемо на простішому прикладі, що може відбутися, коли потоки, які взаємодіють, разом використовуватимуть спільні дані без додаткових заходів із забезпечення синхронізації.
Уявимо, що при банківської організації системи для обслуговування кожного користувача видяляють окремий потік (чим намагаються підвищити продуктивність системи у разі великої кількості одночасних запитів). Припустимо, що поміщення даних на вклад користувача зводиться до збільшенн глобальної змінної total_amount. У цьому разы кожен потік під час зміни вкладу виконує такий простіший оператор:
total_amount=total_amount+new_amount;
Виникає запитання: чи можна дати гарантію, що внаслідок роботи із вкладом потік, відповідає кожному користувачу, буде здатний збільшити значення total_amount на потрібну величину?
Насправді цей на перший погляд найпростіший оператор зводиться до послідовності таких дій:
· отримання поточного значення total_amount із глобальної пам’яті;
· збільшення його на new_amount і збереження результату в глобальній пам’яті.
Розглянемо випадок, коли два користувачі А і В спільно користуються одним і тим самим рахунком. На рахунку є 100 грошових одиниць. Користувач А збирається покласти на рахунок 1000, користувач В у цей самий час – 100. Потік ТА відповідає користувачу А, потік ТВ – користувачу В. Розглянемо таку послідовність подій (варіант 1).
1. Потік ТА зчитує значення total_amount, рівне 100.
2. Потік ТВ зчитує значення total_amount, теж рівне 100.
3. Потік ТА збільшує зчитане на кроці 1 значення total_amount на 1000, отримує 1100 і зберігає його у глоальній пам’яті.
4. Потік ТВ збільшує зчитане на кроці 2 значення total_amount на 100, отримує 200 і теж зберігає його у глобальній пам’яті, перезаписуючі те, що зберіг потік ТА.
У результаті внесок користувача А повністю втрачено.
Тепер розглянемо іншу послідовність подій (варіант 2).
1. Потік ТА зчитує total_amount, збільшує його на 1000 і записує значення 1100 у глобальну пам’ять.
2. Потік ТВ зчитує total_amount, рівний 1100, збільшує його на 100 і записує значення 1200 у глобальну пам”ять.
У результаті обидва внески зареєстровані успішно.
Як бачимо, результат виконання наведеного раніше найпростішого фрагменту коду залежить від послідовності виконання потоків у системі. Це спричиняє до такого: в одній систуації код може працювати, в іншій – ні, і передбачити появу помилки в загальному випадку неможливо. Таку ситуацію називають станом гонок або змаганням (race condition), що є однією з найбільш важко вловлюваних помилок, з якими зіштовхуються програмісти. Вона практично не піддається налогодженню (оскільки нереально перебрати у налогоджувачі всі можливі комбінації послідовностей виконання потоків, особливо якщо їх багато).
Спроби розв’язувати подібні проблеми викликали необхідність синхронізації потоків. Відразу ж зазаначимо, що проблеми синхронізації і організації паралельних обчислень є одними з найскладніших у практичному програмуванні. Тому розробку й особливо налагодження багатопотокових програм часто сприймають як своєрідне “мистецтво”, що доступне далеко не всім програмістам.
Насправді така розробка та налагодження - це аж ніяк не мистецтво, а строга дисципліна, що підлягає одному головному принципу: оскільки для багатопотокових програм традиційне налагодження не придатне, програміст має писати код таким чином, щоб уже на етапі розробки не залишити місця для помилок, синхронізації.
Ознайомимся із правилами, яких треба дотримуватися, аби створений код відповідав цьому принципу.
Розглянемо основні підходи до розв’язання проблеми змагань.
Іноді (але досить рідко)можна просто ігнорувати такі помилки. Це може мати сенс, коли нас цікавить не точна реєстрація тих або інших даних, а збір статистики про них, тому окремі помилки не позначатимуться на загальному результаті. Наприклад, глобальним лічильником є величина, на базі якої розраховують середню кількість запитів до системи за добу і можна проігнорувати помилки реєстрації таких запитів, що трапляються раз на кілька годин. На жаль, у більшості випадків такий підхід не прийнятий.
Іноді використання глобальних даних не диктується специфікою задачі. У цьому разі однозначним розв’язанням є створення локальних копій цих даних для кожного потоку й оперування тільки ними. На практиці це працює вельми добре й має використовуватись де тільки можливо. Наприклад, якщо специфіка задачі допускає створення окремого лічильника для кожного потоку (або глобального масиву лічильників, де кожний елемент змінюється тільки певним потоком), реалізація таких структур даних вирішує проблему. Знову ж таки, таке вирішення можна застосовувати далеко не у всіх випадках (наприклад, у ситуції з банківськими рахунками різні потоки, зрештою, повинні якимось чином модифікувати загальний для всіх рахунок).
У всіх інших випадках потрібно забезпечувати захист змін від впливу інших потоків. Це і є основним завданням синхронізації.
Розглянемо різні підходи до його розв’язання.
5. 2. 2 Критичні секції та блокування
Поняття критичної секції
Розглянемо використання простішої ідеї для вирішення проблеми змагань.
Неважко помітити, як джерелом нашої помилки є те, що зовні найпростіша операція покладання грошей на рахунок насправді розпадається на кілька операцій, при цьому завжди залишається шанс втручання між ними якогось іншого потоку. У цьому випадку кажуть, що операція не є атомарною.
Звідси випливає, що розв’язанням проблеми змагання є перетворення фрагменту коду, який спричиняє проблему, в атомарну операцію, тобто в таку, котра гарантовано виконуватиметься цілковито без втручання інших потоків. Такий фрагмент коду називають критичною секцією (critical section):
//початок критичної секції
total_amount=total_amount+new_amount;
//кінець критичної секції
Тепер, коли два потоки візьмуться виконувати код критичної секції одночасно, той з них, що почав першим, виконає весь її код цілком до того, як другий почне своє виконання (другий потоік чекатиме, поки перший не закінчить виконання коду критичної секції). У результаті підсумку гарантовано матимемо в нашій програмі послідовність подій за варіантом 2, і змагання не відбудеться ніколи.
Розглянемо властивості, які повинна мати критична секція.
· Взаємного виключення (mutual exlusion): у конкретний момент часу код критичної секції може виконувати тільки один потік.
· Прогесу: якщо кілька потоків запрсили вхід у критичну секцію, один із них повинен обов’язково у неї ввійти (вони не можуть всі заблокувати один одного).
· Обмеженості очікування: процес, що намагається ввійти у критичну секцію, рано чи пізно обов’язково в неї ввійде.
Залишається відповісти на далеко не просте запитання: “Як нам змусити ситему сприймати кілька операцій як одну атомарну операцію?”
Найпростішим розв’язанням такої задачі було б заборонити переривання на час виконання критичної секції. Такий підхід, хоча й розв’язує задачу в принципі, на практиці не може бути застосовуваний, оскільки внаслідок зациклення аьо авірії програми у критичній секції вся система може залишитися із заблокованими перериваннями, а отже, у непрацездатному стані.
Блокування
Раціональнішим розв’язанням є використання блокувань (locks). Блокування – це механізм, який не дозволяє більш як одному потокові виконувати код критичної секції. Використання блокування зводиться до двох дій: запрвадження (заблокування, функція acquire_lock()) і зняття блокування (розблокування, функція release_lock()). У разі заблокування перевіряють, чи не було воно вже зроблено іншим потоком, і якщо це так, цей потік переходить у стан очікування, інакше він запрваджує блокування і входить у критичну секцію. Після виходу із критичної секції потік знімає блокування.
acquire_lock(lock);
//критична секція
release_lock(lock);
Так реалізовують властивість взаємного виключення, звідси походить інша назва для блокування – м’ютекс (mutex, скорочення від mutual exclusion).
Проблеми із реалізацією блокувань
Розглянемо наївну реалізацію критичної секції із використанням змінних блокування. З кожною критичною секцією пов’язують цілочислову змінну, якій присвоюють одиницю під час заблокування і нуль – після разблокування. Ось який приблизно вигляд має код такої реалізації:
int lock=0;
void aquire_lock(int lock)
{
//якщо блокування не має (lock==0), запровалити його (задати lock=1)
//і вийти – ми ввійшли у критичну секцію
//інакше чекати, поки блокування не знімуть
while(lock!=0); //(1)
lock=1; //(2)
}
void release_lock(int lock)
{
//зняти блокування
lock=0;
}
Головна проблема цієї реалізації полягає в тому, що що перевірка значення змінної блокування (1) та її зміна (2) не є частинами однієї атомарної операції. Коли інший потоік перевірить значення змінної між цима двома операціями і виявить, що вона дорівнює 0, два потоки можуть опинитися у критичній секції одночасно.
5. 3 Базові механізми синхронізації потоків
Сучасні ОС надають широкий набір готових механізмів синхронізації.
Механізмами синхронізації є засоби операційної системи, які допомогають розв’язувати основне завдання синхронізації – забезпечувати координацію потоків, котрі працюють зі спільно використовуваними даними. Якщо оакі засоби – це мінімальні блоки для побудови багатопотокових програм, їх називають синхронізаційними примітивами.
Синхронізаційні примітиви поділяють на такій основні категорії:
· універсальні, низького рівня, які можна використовувати різнимииспособами (семафори);
· прості, низького рівня, кожен з яких пристосований до розв’язання тільки одеієї задачі (м’ютекси та умовні змінні);
· універсальні високого рівня, виражені через прості; до цієї групи належить концепція монітора, яка може бути виражена через м’ютекси та умовні змінні;
· високого рівня, пристосовані до розв’язання конкретної синхронізаційної задачі (блокування читання-записування і бар’єри);
Розглянемо різні механізми і дамо оцінку перевагам, які має кожен з них, а також можливі їхні недоліки.
Для подальшої ілюстрації матеріалу візьмемо класичний пример, який демонструє необхідність синхронізації – задачу виробників-споживачів (produser-consumer problem) або задачу обмеженого буфера (bounded buffer).
Формулювання задачі просте. Припустимо, що в нас є потоки-виробники і потоки-споживачі. Виробник створює об’єкти, споживач їх отримує. Завданням є так синхронізувати їхню роботу, щоб споживач не міг намагатися отримувати ще не створені об’єкти, а виробник не міг створити більше об’єктів, ніж сможе отримати споживач.
Для синхронізації потоків помістимо між виробником і споживачем буфер фіксованої довжини n. Виробник може поміщати об’єкти у буфер, споживач – забирати їх звідти.Якщо споживач забирає об’єкт, його вилучають із буфера. Необхідно забезпечити кілька вимог:
1. Коли виробник або споживач працює із буфером, решта потоків повинна чекати, поки він завершить свою роботу.
2. Коли виробник намагається помістити об’єкт у буфер, а буфер повний (у ньому n об’єктів), він має дочекатися, поки в ньому з’явиться місце.
3. Коли споживач намагається забрати об’єкт із буфера, а буфер порожній, він має дочекатися, поки в ньому з’явиться об’єкт.
Семафори
Концепцію семафорів запропонував у 1965 році Е. Дейкстра – відомий голландський фахівець у галузі комп’ютерних наук. Семафори є найстарішими синхронізаційними примітивами з числа тих, які застосовуються на практиці.
Семафор – це спільно використовуваний невід’ємний цілочисловий лічильник, для якого задано початкове значення і визначено такі атомарні операції:
· Зменшення семафора (down): якщо значення семафора більш від нуля, його зменшують на одиницю, якщо ж значення дорівнює нулю, цей потік переходить у стан очікування доти, поки воно не стане більш від нуля (кажть, що потік “очікує на семафорі” або “заблокований на семафорі”). Таку операцію називають також очікуванням – wait. Ось її псевдокод:
void down(semaphore_t sem)
{
if (sem>0)
sem--;
else sleep();
}
· Збільшення семафора (up): значення семафора збільшують на одиницю; коли прицьому є потоки, які очікують на семафорі, один із них виходить із очікуванн