Семафори

Концепцію семафорів запропонував у 1965 році Е. Дейкстра – відомий голландський фахівець у галузі комп’ютерних наук. Семафори є найстарішими синхронізаційними примітивами з числа тих, які застосовуються на практиці.

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

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

void down (semaphore_t sem) {

if (sem>0) sem--;

else sleep();

}

· Збільшення семафора (up): значення семафора збільшують на одиницю; коли при цьому є потоки, які очікують на семафорі, один із них виходить із очікування і виконує свою операцію down. Якщо на семафорі очікують кілька потоків, то внаслідок виконання операції up його значення залишається нульовим, але один із потоків продовжує виконання (у більшості реалізацій вибір цього потоку буде випадковим). Цю операцію також називають сигналізацією – post. Ось її псевдокод:

void up (semaphore_t sem) {

sem++;

if (waiting_threads()) wakeup (some_thread));

}

Фактично значення семафора визначає кількість потоків, що може пройти через цей семафор без блокування. Коли для семафора задане нульове початкове значення, то він блокуватиме всі потоки доти, поки якийсь потік його не «відкриє», виконавши операцію up. Операції up і down можуть бути виконані будь-якими потоками, що мають доступ до семафора.

Дейкстра використовував для операції down позначення Р (від голландського probieren – перевіряти), а для операції up – позначення V (від голландського verhoren – збільшувати). Ці позначення часто використовують у літературі.

Особливості використання семафорів

Семафори можна використовувати для розв’язання двох різних задач синхронізації.

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

semaphore_t sem = 1; //на початку семафор відкритий

down(sem);

//критична секція

up(sem);

1. За їхньою допомогою можна організувати очікування виконання деякої умови. Припустимо, що треба організувати очікування одним потоком завершення виконання іншого (аналог операції приєднання). У цьому випадку можна використати семафор із початковим значенням 0 (закритий). Потік, який чекатиме повинен виконати для цього семафора операцію down, а щоб просигналізувати про завершення потоку, у його функції завершення потрібно для того самого семафора виконати up. Ось псевдокод (this_thread означає поточний потік):

void thread_init() {

this_thread.sem = 0; //на початку виконання потоку семафор закритий

}

void thread_exit() {

up(this_thread.sem); //розбудити потік, що очікує, якщо такий є

}

void thread_join(thread_t thread) {

down(thread.sem); //очікування завершення потоку thread

}

Реалізація задачі виробників-споживачів за допомогою семафорів

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

1. Помістити операції безпосередньої зміни буфера(для виробника – поміщення об’єкта у буфер, для споживача – вилучення об’єкта із буфера) у критичні секції.
2. Організувати очікування відповідно до вимоги 2 (очікування виробника у разі повного буфера). При цьому споживач повинен повідомляти виробникам, які очікують, про те, що він забрав об’єкт із буфера (тобто буфер став неповним, якщо він був певним).
3. Організувати очікування відповідно до вимоги 3 (очікування споживача у разі порожнього буфера). При цьому виробник повинен повідомляти споживачів, які очікують, про те, що він додав новий об’єкт у буфер(тобто буфер став непорожнім, якщо він був порожнім).

Тепер розглянемо синхронізаційні примітиви, які нам потрібні. Кожна синхронізаційна операція потребує окремого семафора.

1. Для організації критичної секції використаємо двійковий семафор, як це робили раніше. Назвемо його lock. Він використовуватиметься як виробником, так і споживачем, захищаючи доступ до буфера від інших потоків (знову таки, як виробників, так і споживачів).
2. Для організації очікування виробника у разі повного буфера нам знадобиться семафор, поточне значення якого дорівнює кількості вільних місць у буфері. Назвемо його empty_items. Виробник перед спробою додати новий об’єкт у буфер зменшує цей семафор, переходячи в стан очікування, якщо той дорівнював 0. Споживач після того, як забере об’єкт із буфера, збільшить семафор, повідомивши таким способом про це виробників, що очікують (і розбудивши одного із них).
3. Для організації очікування споживача у разі порожнього буфера знадобиться семафор, поточне значення якого дорівнює кількості зайнятих місць у буфері. Назвемо його full_items. Споживач перед спробою забрати об’єкт із буфера зменшує цей семафор, переходячи у стан очікування, якщо той дорівнював 0. Виробник після того, як додасть об’єкт у буфер, збільшить семафор, повідомивши таким способом про це споживачів, що очікують (і розбудивши одного з них). Ось псевдокод розв’язання цієї задачі:

semaphore_t lock = 1; //для критичної секції

semaphore_t empty_items = n; //0 – буфер повний, від початку він порожній

semaphore_t full_items = 0; //якщо 0 – буфер порожній

//виробник

void producer() {

item_t item = produce(); //створити об’єкт

down(empty_items); //чи є місце для об’єкта?

down(lock); //вхід у критичну секцію

append_to_buffer(item); //додати об’єкт item у буфер

up(lock); //вихід із критичної секції

up(full_items); //повідомити споживачів, що є новий об’єкт

}

//споживач

void consumer() {

item_t item;

down(full_items); //чи не порожній буфер?

down(lock); //вхід у критичну секцію

item = receive_from_buffer(); //забрати об’єкт item з буфера

up(lock); //вихід із критичної секції

up(empty_items); //повідомити виробників, що є місце

consume(item); //спожити об’єкт

}

Проблеми використання семафорів

Як бачимо, розв’язання задачі виробників-споживачів ілюструє обидва способи використання семафорів: для взаємного виключення і для очікування. Насправді така універсальність має свій зворотній бік: код із використанням семафорів виходить досить складним.

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

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

Ось приклад того, як легко зробити помилку в такому коді. Припустимо, що ми поміняли місцями down(empty_items) і down(lock) в producer(), тому перевірка умови з можливим очікуванням буде зроблена всередині критичної секції.У цьому разі ми можемо отримати таку послідовність дій, якщо буфер повний.

1. Виробник успішно входить у критичну секцію всередині producer(), закриваючи семафор lock.
2. Виробник перевіряє, чи не заповнений буфер даних, і блокується на семафорі empty_items. Семафор lock залишається закритим.
3. Споживач намагається ввійти у критичну секцію всередині consumer() і блокується на семафорі lock.

У цьому стані обидва потоки й залишаються – це взаємне блокування (deadlock), коли кожен із потоків очікує на блокуванні, запровадженим іншим.

Для розв’язання деяких із цих проблем було запропоновано розділити дві функції семафорів, надавши кожній із них окремий синхронізаційний примітив. Для організації взаємного виключення використовують м’ютекси, очікування виконання умові – умовні змінні.

5.3.2. М’ютекси

Поняття м’ютекса багато в чому збігається з поняттям блокування. М’ютексом називають синхронізаційний примітив, що не допускає виконання деякого фрагменту коду більш як одним потоком. Фактично м’ютекс є реалізацією блокування на рівні ОС.

М’ютекс, як і випливає з його назви, реалізує взаємне виключення. Його основне завдання – блокувати всі потоки, які намагаються отримати доступ до коду, коли цей код уже виконує деякий потік.

М’ютекс може бути у двох станах: вільному і зайнятому. Початковим станом є «вільний». Над м’ютексом є дві атомарні операції.

· Зайняти м’ютекс (mutex_lock): якщо м’ютекс був вільний, він стає зайнятим, і потік продовжує своє виконання (входячи у критичну секцію); якщо м’ютекс був зайнятий, потік переходить у стан очікування (кажуть, що потік «очікує на м’ютексі», або «заблокований на м’ютексі»), виконання продовжує інший потік. Потік, який зайняв м’ютекс, називають власником м’ютекса (mutex owner):

mutex_lock (mutex_t mutex) {

if (mutex.state == free) {

mutex.state = locked;

mutex.owner = this_thread;

}

else sleep();

}

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

mutex_unlock (mutex_t mutex) {

if (mutex.owner!= this_thread) return error;

mutex.state = free;

if (waiting_threads()) wakeup (some_thread);

}

Деякі реалізації надають ще третю операцію: спробувати зайняти м’ютекс (mutex_trylock): якщо м’ютекс вільний, діяти аналогічно до mutex_lock, якщо зайнятий – негайно повернути помилку і продовжити виконання.

Ось найпростіша реалізація критичної секції за допомогою м’ютекса.

mutex_t mutex;

mutex_lock(mutex);

//критична секція

mutex_unlock(mutex);

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

Правила спрощеного паралелізму

Правила спрощеного паралелізму (easy concurrency rules) призначені для спрощення програмування на базі м’ютексів. Вони ґрунтуються на тому очевидному факті, що м’ютекс захищає не код критичної секції, а спільно використовувані дані всередині цієї секції.

· Кожна змінна, яку спільно використовує більш як один потік, має бути захищена окремим м’ютексом (скільки змінних, стільки м’ютексів):

volatile int i, data[100];

mutex_t i_mutex, data_mutex;

· Перед кожною операцією зміни такої змінної відповідний м’ютекс має бути зайнятий, а після зміни звільнений:

mutex_lock(i_mutex);

i++;

mutex_unlock(i_mutex);

· Якщо треба працювати одночасно із кількома спільно використовуваними змінними, необхідно зайняти всі їхні м’ютекси до початку роботи і звільнити їх тільки після повного закінчення роботи. Цим роботу розділяють на три етапи:

//зайняття м’ютексів

mutex_lock(i_mutex);

mutex_lock(data_lock);

//робота зі змінними

data[i++] = 100;

//звільнення м’ютексів

mutex_unlock(i_mutex);

mutex_unlock(data_mutex);

Зазначимо, що для спільно використовуваних даних задано клас пам’яті volatile. Використання такого модифікатора сповіщає компілятор мови С, про можливе асинхронне змінення змінної поза даною програмою. Це завжди потрібно робити для спільно використовуваних даних.

Реалізація задачі виробників-споживачів за допомогою м’ютексів

З’ясуємо можливість розв’язання задачі ввиробників-споживачів за допомогою самих лише м’ютексів та розглянемо проблеми, які з цим пов’язані. Тут не наводитимемо повного коду розв’язання завдання, зупинимося тільки на ключових моментах.

Проблем із реалізацією критичних секцій не виникне, оскільки в цьому разі м’ютекси використовуватимуться за прямим призначенням.

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

mutex_t lock;

void consumer() {

item_t item;

for (;;) { //нескінчений цикл активного очікування

//вихід із нього, якщо буфер не порожній

mutex_lock(lock); //вхід у критичну секцію

if (count_items_in_buffer()!= 0) { //якщо буфер не порожній

item = receive_from_buffer(); //забрати об’єкт із буфера

mutex_unlock(lock); //вийти із критичної секції

break; //вийти з циклу

}

mutex_unlock(lock); //вихід із критичної секції

}

consume(item); //спожити об’єкт

}

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

Рекурсивні м’ютекси

Розглянемо випадок, коли потік, який займає м’ютекс, спробує зайняти той самий м’ютекс іще раз. Для звичайних м’ютексів отримаємо взаємне блокування, оскільки потік очікуватиме на м’ютексі, що його звільнити може тільки він сам.

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

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

5.3.3. Умовні змінні та концепція монітора

Поняття умовної змінної

Умовною змінною називають синхронізаційний примітив, який дає змогу організувати очікування виконання деякої умови всередині критичної секції,заданої м’ютексом. Умовна змінна завжди пов’язана із конкретним м’ютексом і даними, захищеними цим м’ютексом. Для умовної змінної визначено такі операції

· Очікування (wait). Додатковим вхідним параметром ця операція приймає м’ютекс, який повинен перебувати в закритому стані. Виклик wait відбувається в ситуації, коли не виконується деяка умова, потрібна потоку для продовження роботи. Внаслідок виконання wait потік (позначатимемо його T_W) припиняється (кажуть, що він «очікує на умовній змінній»), а м’ютекс відкривається (ці дві дії виконуються атомарно). Так інші потоки отримують можливість увійти в критичну секцію і змінити там дані, які вона захищає, можливо, виконавши умову, потрібну потоку T_W. На цьому операція wait не завершується – її завершить інший потік, викликавши операцію signal після того, як умову буде виконано.

· Сигналізація (signal). Цю операцію потік (назвемо його T_S) має виконати після того, як увійде у критичну секцію і завершить роботу з даними (виконавши умову, яку очікував потік, що викликав операцію wait). Ця операція перевіряє, чи немає потоків, які очікують на умовній змінній, і якщо такі потоки є, переводить один із них (T_W) у стан готовності (цей потік буде поновлено, коли відповідний потік T_S вийде із критичної секції). Внаслідок поновлення потік T_W завершує виконання операції wait – блокує м’ютекс знову (поновлення і блокування теж відбуваються атомарно). Якщо немає жодного потоку, який очікує на умовній змінній, операція signal не робить нічого, і інформація про її виконання в системі не зберігають.

· Широкомовна сигналізація (broadcast) відрізняється від звичайної тим, що переведення у стан готовності і, зрештою, поновлення виконують для всіх потоків, які очікують на цій умовній змінній, а не тільки для одного з них.

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

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

Особливості виконання операцій над умовною змінною

Операцію wait викликають, коли деяка умова, необхідна потоку для продовження, не виконується. Умова повинна бути пов’язана зі спільно використовуваними даними. Перед викликом wait потрібно перевірити цю умову в циклі while

while (! condition_expr) //вираз для умови

wait (condition, mutex);

Розглянемо, чому в цій перевірці використовують цикл while, а не умовний оператор if. На перший погляд, використання while зайве – нам досить перевірити умову один раз, для чого можна скористатися й if.

Пояснимо, чому це не так. Після того, як потік T_S виконає операцію signal, потік T_W не запускається негайно, а переходить у стан готовності до виконання. Виконуватися він почне тоді, коли його вибере планувальник (звичайно це відбувається швидко). Проте за проміжок часу між викликом signal і початком виконання потоку T_W ще один потік (позначимо його T_X) може ввійти у критичну секцію (згадаймо, що м’ютекс у цей час поки що відкритий) і змінити в ній дані так, що умова знову перестане виконуватися. Тепер, якби виклик wait стояв за if, після виходу з wait потік T_W заблокував би м’ютекс і продовжив своє виконання, незважаючи на те, що умова все одно не виконується. Це помилка, яка практично налагодженню не підлягає (її називають помилковим поновленням – spurious wakeup). Коли ж використати while, то після виходу з wait умова знову буде перевірена, і якщо вона далі не виконується, потік T_W розблокує м’ютекс і знову перейде у стан очікування.

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

Наведемо приклад використання операції wait для організації очікування, поки звільниться місце у буфері (це фрагмент розв’язання задачі виробників-споживачів, як розглянемо далі). Тут умовою є порожність буфера.

while (count_items_in_buffer() ==n) //поки буфер повний

wait (not_full, mutex); // not_full – умовна змінна

Операція signal повинна викликатися із критичної секції (тим паче, що параметром цієї операції теж є м’ютекс). Потік T_S має викликати signal, коли умова, якої очікував потік T_W, почне виконуватися.

//тут condition_expr == true

signal(condition, mutex);

Ось приклад використання операції signal для повідомлення про те, що буфер звільнився:

item = receive_from_buffer(); //звільнити буфер

signal(not_full, mutex); //сигналізувати, що буфер непорожній

Розглядаючи цей фрагмент у поєднанні із попереднім, зауважимо: якщо якийсь потік вставить об’єкт у буфер між викликом signal і поновленням виконання потоку, це негайно зробить умову в циклі while знову істинною, внаслідок чого операція wait буде виконана знову.

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

Відмінності умовних змінних від семафорів

Наведемо принципові відмінності умовних змінних від семафорів, які використовують для організації очікування за умовою.

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

2. Умовні змінні не зберігають стану, а семафори – зберігають. Ось що це означає.

· Якщо потік T_S виконує signal для умовної змінної і потоки, які очікують на цій умовній змінній, відсутні, нічого не відбувається і жодної інформації в системі не зберігають. Коли потім потік T_W виконає операцію wait на цій умовній змінній, то він призупиниться.

· Якщо потік T_S виконує up для семафора і потоки, які очікують на цьому семафорі, відсутні, значення семафора все одно збільшують і нове значення зберігають у системі. Коли потім потік T_W виконає операцію down для цього семафора, він замість призупинення зменшить семафор і продовжить своє виконання (незважаючи на те, що потік T_S раніше виконав свою операцію намарно).

Рекурсивні м’ютекси й умовні змінні

Рекурсивні м’ютекси не можуть бути використані у поєднанні з умовними змінними, оскільки рекурсивний м’ютекс може не звільнитися разом із початком очікування всередині wait, якщо він перед цим був зайнятий кілька разів (а це гарантує взаємне блокування).

Очікування виконання кількох умов

Можна організувати очікування виконання кількох умов, хоча це рекомендують робити тільки у разі необхідності, щоб не ускладнювати код. Для такого очікування потрібно використати одну умовну змінну й у циклі while перевіряти кількох умов:

//повинно виконуватися condition_expr1 або condition_expr2

while (! condition_expr1 &&! condition_expr2)

wait (condition, mutex);

// повинно виконуватися condition_expr1 і condition_expr2

while (! condition_expr1 ||! condition_expr2)

wait (condition, mutex);

Кожну умову треба сигналізувати окремо:

//виконують condition_expr1

signal (condition, mutex);

//…

//виконують condition_expr2

signal (condition, mutex);

Поняття монітора

Як ми бачимо, умовні змінні не використовують окремо від м’ютексів, причому є кілька правил взаємодії між цими примітивами. Ці правила є підґрунтям поняття монітора – синхронізаційної концепції вищого рівня.

Монітором називають набір функцій, які використовують один загальний м’ютекс і нуль або більше умовних змінних для керування паралельним доступом до спільно використовуваних даних відповідно до певних правил. Функції цього набору називають функціями монітора.

Ось правила, яких слід дотримуватися у разі реалізації монітора.

· Під час входу в кожну функцію монітора потрібно займати м’ютекс, під час виходу – звільняти. Отже, у кожний момент часу тільки один потік може перебувати всередині монітора (під яким розуміють сукупність усіх його функцій).

· Під час роботи з умовною змінною (і під час очікування, і під час сигналізації) необхідно завжди вказувати відповідний м’ютекс. Не можна працювати з умовними змінними, якщо м’ютекс незайнятий.

· Під час перевірки на виконання умови очікування потрібно використати цикл, а не умовний оператор.

Ідея монітора була вперше запропоновані в 1974 році відомим ученим у галузі комп’ютерних наук Ч.А. Хоаром. Монітор часто розуміють як високорівневу конструкцію мови програмування (як приклад такої мови звичайно наводять Java), а саме як набір функцій або методів класу, всередині яких автоматично зберігається неявний м’ютекс разом із операціями очікування і сигналізації. Насправді, як ми бачимо, концепція монітора може ґрунтуватися на базових примітивах – м’ютексах і умовних змінних – і не повинна бути обмежена якоюсь однією мовою.

Монітори Хоара відрізняються від тих, що були розглянуті тут (ці монітори ще називають MESA-моніторами за назвою мови, у якій вони вперше з’явилися). Головна відмінність полягає у реалізації сигналізації.

· У моніторах Хоара після сигналізації потік T_S негайно призупиняють, і керування переходить до потоку T_W, який при цьому захоплює блокування. Коли потік T_W вийде із критичної секції або знову виконає операцію очікування, потік T_S буде поновлено.

· У MESA-моніторах, як було видно, після сигналізації потік T_S продовжує своє виконання, а потік T_W просто переходить у стан готовності до виконання. Він зможе продовжити своє виконання, коли потік T_S вийде з монітора (чекати цього доведеться недовго, тому що звичайно сигналізація відбувається наприкінці функції монітора).

Результатом є те, що для моніторів Хоара не обов’язково перевіряти умову очікування в циклі, досить умовного оператора (потік негайно отримує керування після виходу з очікування і не може статися так, що за цей час інший потік увійде в монітор і змінить умову). З іншого боку, ці монітори менш ефективні (потрібно витрачати час нате, щоб припиняти і поновлювати потік T_S); потрібно мати повну гарантію того, що між виконанням сигналізації та передаванням керування потоку T_W планувальник не передасть керування іншому потокові T_X, який увійде у функцію монітора. Забезпечення такої гарантії потребує втручання в алгоритм роботи планувальника ОС.

Ці недоліки призводять до того, що на практиці використовують переважно MESA-монітори.

Ось приклад розв’язання задачі очікування завершення потоку із використанням монітора.

//всі функції перебувають у моніторі

//з кожним потоком пов’язана умовна змінна finished_cond

//і прапорець finished – спільно використовувані дані

void thread_init() {

mutex_lock(mutex);

//на початку виконання потоку умова не виконується

this_thread.finished = 0;

mutex_unlock(mutex);

}

void thread_exit() {

mutex_lock(mutex);

this_thread.finished = 1;

//розбудити потік, який очікує, якщо він є

signal(this_thread.finished_cond, mutex);

mutex_unlock(mute);

}

void thread_join(thread_t thread) {

mutex_lock(mutex);

//очікування закінчення потоку thread

while (! thread.finished)

wait(thread.finished_cond, mutex);

mutex_unlock(mutex);

}

Реалізація задачі виробників-споживачів за допомогою монітора

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

· Для того, щоб забезпечити перебування в моніторі тільки одного потоку в конкретний момент часу, використовуватимемо м’ютекс lock. Він буде спільним для всіх функцій семафора, з ним працюватимуть як виробник, так і споживач.

· Для організації очікування виробника у разі повного буфера потрібна умовна змінна, сигналізація якої означатиме, що місце у буфері звільнилося. Назвемо цю змінну not_full. Перед спробою додати новий об’єкт виробник перевіряє, чи буфер повний і, якщо це так, виконує очікування на цій змінній. Споживач, забравши об’єкт із буфера, сигналізує not_full, повідомляючи цим про наявність вільного місця виробникам, які очікують (і перевівши у стан готовності одного з них).

· Для організації очікування споживача під час порожнього буфера потрібна умовна змінна, сигналізація якої означатиме, що у буфері з’явиться об’єкт. Назвемо цю змінну not_empty. Перед спробою забрати об’єкт із буфера споживач перевіряє і, якщо це так, виконує очікування на цій змінній. Виробник, додавши об’єкт у буфер, сигналізує not_empty, повідомляючи цим про наявність об’єктів споживачам, які очікують (і перевівши у стан готовності одного з них).

Завданнями функцій монітора буде забезпечення роботи із буфером. Для кращої організації коду запишемо ці функції окремо від коду виробника і споживача.

Ось псевдокод розв’язання цієї задачі:

mutex_t lock; //для критичної секції

condition_t not_empty; //сигналізує про те, що буфер непорожній

condition_t not_full; //сигналізує про те, що буфер неповний

int n = 100; //максимально можлива кількість елементів

//виробник

void producer () {

item_t item = produce() //створити об’єкт

put_into_buffer(item);

}

//споживач

void consumer () {

item_t item = obtain_from_buffer();

consume(item); //спожити об’єкт

}

//функції монітора

void put_into_buffer(item_t item) {

mutex_lock(lock); //вхід у критичну секцію

while(count_items_in_buffer() == n)

wait (not_full, lock); //чекати, поки буфер повний

//на цей час зняти блокування

append_to_buffer(item); //додати об’єкт item у буфер

signal(not_empty, lock); //повідомити, що є новий об’єкт

mutex_unlock(lock); //вихід із критичної секції

}

item_t obtain_from_buffer () {

item_t item;

mutex_lock(lock); //вхід у критичну секцію

while (count_items_in_buffer() == 0)

wait (not_empty, lock); //чекати, поки буфер порожній

//на цей час зняти блокування

item = receive_from_buffer(); //забрати об’єкт item із буфера

signal(not_full, lock); //повідомити, що є вільне місце

mutex_unlock(lock); //вихід із критичної секції

return item;

}

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

Деякі джерела взагалі не рекомендують користуватися семафорами для синхронізації, обмежуючи себе тільки моніторами (м’ютексами й умовними змінними). Треба, однак, зазначити, що:

· у деяких системах (наприклад, у Linux до появи NPTL) семафори – це єдиний засіб синхронізації потоків різних процесів;

· в інших системах (наприклад, у Win32 API) майже не підтримуються умовні змінні (принаймні, реалізувати їх там складно)ж

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

Загальна стратегія організації паралельного виконання

Для коректної організації виконання багатопотокових програм особливо важливі два із розглянутих раніше правил.

· М’ютекс захищає не код критичної секції, а спільно використовувані дані всередині цієї секції.

· Виклик wait для умовної змінної відбувається тоді, коли не виконується умова, пов’язана зі спільно використовуваними даними всередині критичної секції, виклик signal – коли умова, пов’язана з цими даними, починає виконуватися.

Як бачимо, м’ютексами і умовними змінними керують дані, що вони захищають. Так само вся концепція монітора побудована навколо спільно використовуваних даних. У разі розробки на С++ є сенс надати самим спільно використовуваним даним право відповідати за свою синхронізацію перетворенням їх в об’єкти класів та інкапсуляцією всіх синхронізаційних примітивів у методах цих класів. Рекомендують такий базовий підхід до розробки багатопотокових програм на С++.

1. Виділити одиниці паралельного виконання. Зробити кожну з них потоком. Потоки можуть бути інкапсульовані у класи з методом go(), який виконує функція потоку.
2. Виділити спільно використовувані структури даних. Зробити кожну з таких структур класом. Виділити методів класів – дії, які потоки виконуватимуть із цими структурами даних.
3. Записати основний цикл виконання кожного потоку.

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

1. Визначити всі синхронізаційні дії, котрі необхідно виконувати з об’єктами цього класу. Визначити тип кожної дії: взаємне блокування або очікування умови.
2. Створити м’ютекси або умовні змінні для кожної дії.
3. Розробити методи класів, використовуючи для синхронізації ці м’ютекси і умовні змінні (звичайно ці методи роблять функціями монітора).

Дата добавления: 2014-01-05