Проблема синхронізації

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

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

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

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

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

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

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

Семафори

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

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

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

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

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

М'ютекси

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

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

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

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

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

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

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

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

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

• Сигналізація (signal). Цю операцію потік (назвемо його Ts) має виконати після того, як увійде у критичну секцію і завершить роботу з даними (виконавши умову, яку очікував потік, що викликав операцію wait). Ця операція перевіряє, чи немає потоків, які очікують на умовній змінній, і якщо такі потоки є, переводить один із них (Tw) у стан готовності (цей потік буде поновлено, коли відповідний потік Tg вийде із критичної секції). Внаслідок поновлення потік Twзавершує виконання операції wait — блокує м'ютекс знову (поновлення і блокування теж відбуваються атомарно). Якщо немає жодного потоку, який очікує на умовній змінній, операція signal не робить нічого, і інформацію про її виконання в системі не зберігають.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• Закриття (rwl ockunl оск). У разі наявності кількох потоків, які відкрили блокування для читання, воно залишається відкритим для читання, і внутрішній лічильник потоків-читачів зменшують на одиницю. Якщо блокування відкрите для читання тільки одним потоком (лічильник дорівнює одиниці) його знімають, якщо є потоки-записувачі, які очікують на цьому блокуванні, один із них поновлюють. Коли блокування відкрите для записування, його знімають, при цьому за наявності потоків-читачів, що очікують, всі вони поновлюються, а з потоків-записувачів, що очікують, поновлюють тільки один. Якщо очікують і читачі й записувачі, результат залежить від типу блокування (у разі кращого читання або якщо жодного записувача немає, поновлюють усіх читачів, а якщо читачі відсутні у разі кращого записування — поновлюють одного з записувачів.

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