Урок № 96

(згідно навчальної робочої програми)

Тема: «Базові механізми синхронізації потоків»

Питання:

1. Поняття синхронізації.

2. Семафори.

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

4. М’ютекси.

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

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

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

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

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

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

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

12. Блокування читання-записування.

13. Типи блокувань.

14. Операції блокувань.

15. Синхронізація за принципом бар’єра.

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

Синхронізаційні механізми поділяють на такі основні категорії:

• універсальні, низького рівня, які можна використовувати різними способами (семафори);

• прості, низького рівня, кожен з яких пристосований до розв’язання тільки од­нієї задачі (м’ютекси та умовні змінні);

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

• високого рівня, пристосовані до розв’язання конкретної синхронізаційної за­дачі (блокування читання-записування і бар’єри).

Семафори

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

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

voiddown (semaphore_tsem) { if (sem> 0) sem--; elsesleep():}

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

void up (semaphore_tsem) { sem++;

if (waiting_threads()) wakeup (some_thread);

}

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

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

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

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

Насправді така універсальність має свій зворотний бік: код із використанням семафорів ви­ходить досить складним.

• Далеко не завжди просто відстежити, де і як може змінитися значення сема­фора.

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

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

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

М’ютекси

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

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

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

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

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

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

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

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

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

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

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

mutex_lock(i_mutex): і++; mutex_un1ock(i_mutex);

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

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

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

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

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

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

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

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

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

• Очікування(wait).

• Сигналізація(signal).

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

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

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

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

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

Умовні змінні не зберігають стану, а семафори — зберігають.

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

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

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

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

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

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

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

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

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

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

Блокування читання-записування

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

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

Блокування читання-записування — це синхронізаційний примітив, для яко­го визначені два режими використання: відкриття для читання і відкриття для за­писування.

Насправ­ді нам не завжди потрібен такий однозначний захист, наприклад, для певного ти­пу задач хотілося б розрізняти читання спільно використовуваних даних та їхню модифікацію. Для розв’язання такої задачі використо­вують блокування читання-записування(read-writelocks).

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

Типи блокувань

Розрізняють два типи блокувань читання-записування: з кращим читанням і з кра­щим записом. Відмінність між ними виявляється тоді, коли потік намагається від­крити таке блокування для читання за умови, що він робить це не першим і що є призупинені потоки, які очікують можливості відкрити це блокування для записування.

• У разі кращого читання потік негайно відкриває блокування для читання і про­довжує свою роботу незалежно від того, є потоки-записувачі, що очікують, чи ні. Потоки-записувачі продовжують своє очікування.

• У разі кращого записування за наявності потоків-записувачів, що очікують, потік-читач припиняється й не буде поновлений доти, поки всі записувачі не виконають свої дії і не закриють блокування.

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

Операції блокувань

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

• Відкриття для читання(rwlock_rdlock). Якщо є потік, який відкрив блокуван­ня для записування, поточний потік припиняють. Якщо такий потік відсутній:

• у разі кращого читання блокування відкривають для читання і потік про­довжує своє виконання;

• у разі кращого записування перевіряють, чи немає призупинених потоків, які очікують відкриття цього блокування для записування; якщо вони є - потік припиняють, якщо немає — блокування відкривають для читання і по­тік продовжує своє виконання.

При цьому необхідно, щоб кілька потоків могли відкрити блокування для чи­тання, тому в разі, коли блокування вже відкрите для читання, для його нового відкриття збільшують внутрішній лічильник потоків-читачів.

• Відкриття для записування(rwlock_wr1ock). Якщо є потік, який відкрив бло­кування для читання або записування, поточний потік припиняють; коли жодного такого потоку немає, блокування відкривають для записування і по­тік продовжує своє виконання.

• Закриття(rwlock_unlock). У разі наявності кількох потоків, які відкрили бло­кування для читання, воно залишається відкритим для читання, і внутрішній лічильник потоків-читачів зменшують на одиницю.

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

Синхронізація за принципом бар’єра

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

Бар’єр — це блокування, яке зберігають доти, поки кількість потоків, що очі­кують, не досягне деякого наперед заданого числа, після чого всі ці потоки про­довжують своє виконання.

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

Розглянемо дві операцій бар’єра.

• Ініціалізація бар’єра(barriеr_іnit). Параметром даної операції є п — кількість потоків, які ми синхронізуватимемо на цьому бар’єрі. Внутрішній лічильник призупинених потоків покладають рівним нулю. Значення п після виклику barrier_init міняти не можна.

• Очікування на бар’єрі(barrier_wait). Внаслідок даної операції лічильник при­зупинених потоків збільшується на одиницю. Якщо він не досягнув п, цей по­тік призупиняють. Якщо ж після збіль­шення лічильник виявляється рівним п (досягнуто максимальної кількості потоків для бар’єра), усі потоки, що очікували на бар’єрі, поновлюються (си­туація переходу бар’єра), при цьому одному з них повертають спеціальне зна­чення (зазвичай -1), а іншим - нуль. Надалі потік, що отримав це спеціальне значення, може зробити деякі підсумкові дії після переходу бар’єра. При пере­ході бар’єра його «скидають» (внутрішній лічильник призупинених потоків знову покладають рівним 0) і він починаючи із наступної операції barri er_wait блокуватиме потоки знову.

Контрольні питання:

1. В чому суть синхронізації?

2. Що таке семафори?

3. Які існують проблеми використання семафорів?

4. Що таке м’ютекси?

5. Які існують правила спрощеного паралелізму?

6. Що таке рекурсивні м’ютекси?

7. Як використовуються умовні змінні та концепція монітора?

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

9. Як співпрацюють рекурсивні м’ютекси й умовні змінні?

10. Для чого призначено очікування виконання кількох умов?

11. Що таке монітор?

12. Як реалізовано блокування читання-записуванн?

13. Які є типи блокувань?

14. Які існують операції блокуван?

15. Як здійснюється синхронізація за принципом бар’єра?

Література: Шеховцов В.А. Операційні системи. – К.: Видавнича група BHV, 2005. – 576 с.: іл., стор. 117-136.