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

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

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

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

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

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

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

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

Семафори

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

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

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

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

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

Для семафора визначені дві атомарні операції

V(S) {   
  S++;    
  if (waiting_threads()) POST(S);
} 
P(S) {
  if (S > 0) S--;    
  else WAIT(S);
}

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

Семафор – універсальний засіб, що забезпечує як взаємне виключення, так і очікування події

М'ютекси

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

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

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

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 оск). У разі наявності кількох потоків, які відкрили блокування для читання, воно залишається відкритим для читання, і внутрішній лічильник потоків-читачів зменшують на одиницю. Якщо блокування відкрите для читання тільки одним потоком (лічильник дорівнює одиниці) його знімають, якщо є потоки-записувачі, які очікують на цьому блокуванні, один із них поновлюють. Коли блокування відкрите для записування, його знімають, при цьому за наявності потоків-читачів, що очікують, всі вони поновлюються, а з потоків-записувачів, що очікують, поновлюють тільки один. Якщо очікують і читачі й записувачі, результат залежить від типу блокування (у разі кращого читання або якщо жодного записувача немає, поновлюють усіх читачів, а якщо читачі відсутні у разі кращого записування — поновлюють одного з записувачів.

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

Механізми синхронізації ядра Linux

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

Аналогом потоків у ядрі виступають шляхи передачі керування ядра (kernel control paths). Таким шляхом є послідовність інструкцій, виконуваних ядром для реалізації реакції на системний виклик або обробку переривання. Така послідовність звичайно зводиться до виконання кількох функцій ядра. Наприклад, для обробки системного виклику шлях передачі керування починають з виклику функції system_cal 1 () і завершують викликом ret_systefli_call (). Надалі іноді говоритимемо не про шляхи керування, а про процеси в режимі ядра, маючи на увазі шляхи передачі керування, що відповідають системним викликам, виконаним процесами.

• Витісняльність ядра

До останнього часу ядро Linux належало до категорії невитісняльних (nonpre-emptive). Це означало, що процес, виконуваний в режимі ядра, не міг бути призупинений (витиснений іншим процесом), поки він сам не вирішить віддати керування. У разі переривання керування після виклику обробника мало бути повернуте в той самий процес.

У ядрі версії 2.6 ситуація змінилася. Це перше ядро, що є витісняльним (preemptive). Тепер процес, виконуваний в режимі ядра, може бути призупинений, коли минув квант часу або почав виконуватися процес із вищим пріоритетом. Після обробки переривання керування теж може бути передане іншому процесові. У результаті скоротився час відгуку системи. Тепер процеси, які проводять занадто багато часу в режимі ядра, не затримуватимуть виконання інших процесів. Природно, що у ядрі все одно залишаються місця, де його не можна витісняти, але тепер їх потрібно виділяти явно.

• Необхідність синхронізації у ядрі

Спільно використовувані дані у ядрі можуть бути змінені:

- у коді, викликаному асинхронно внаслідок переривання (до такого коду належать і сам обробник, і код відкладеної реакції на переривання (softirq), який пов'язують із обробником, але виконують трохи пізніше);

- у коді, виконуваному на іншому процесорі;

- у коді, що витиснув розглядуваний (у разі витісняльного ядра).

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

• Заборона переривань

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

• Атомарні операції

Як елементарну альтернативу блокуванням ядро Linux пропонує набір атомарних операцій. До них належить набір найпростіших операцій (збільшення і зменшення на одиницю, побітові операції), що їх атомарне виконання гарантує ядро. Зазначимо, що саме на базі цих операцій реалізовані складніші примітиви синхронізації, такі як семафори ядра або блокування читання-записування, а також ф'ютекси, на яких ґрунтується реалізація синхронізаційних примітивів режиму користувача.

• Спін-блокування

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

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

• Семафори ядра

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

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

Ядро Linux пропонує також блокування читання-записування, подібні до описаних у розділі 5.3.4. Основна їхня відмінність від традиційної реалізації — режими доступу для читання і для записування повністю розділені (відкриттю для читання відповідає закриття для читання, а відкриттю для записування - закриття для записування). Є також варіант семафора, що розрізняє доступ для читання і для записування.

Синхронізація процесів користувача у Linux. Ф'ютекси

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

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

• Використання для операції очікування аналогів системного виклику sleep() і реалізація операції поновлення потоків на основі сигналів. Цей підхід було прийнято у бібліотеці LinuxThreads. Застосування сигналів знову передбачало використання системних викликів, а виконання sleep() призводило до втрат часу на перемикання контексту.

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

Розглянемо реалізацію такого блокування для двох випадків.

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

• Є потік, що вже зайняв це блокування. У цьому разі можна виконати системний виклик, щоб призупинити поточний потік. Така ситуація виникає рідше, і втрати продуктивності будуть менші.

Щоб потоки не зверталися до ядра в разі успішного зайняття блокування, вони мають спільно використовувати дані в пам'яті, доступній у режимі користувача. Для потоків одного процесу забезпечити спільне використання нескладно, оскільки в них загальний адресний простір. Для потоків різних процесів потрібно організовувати розподілювану або відображувану пам'ять, докладніше про це буде сказано в розділі 6. Ці спільно використовувані дані називають блокуванням користувача (user lock). Вони визначають, закрите чи відкрите блокування і чи є потоки, що очікують на ньому. Потоки атомарно змінюють ці дані у разі спроби заблокування, якщо при цьому виникає необхідність заблокувати або поновити потік, виконують системний виклик, коли такої необхідності немає — потік продовжує виконання в режимі користувача.

Реалізація такого блокування була інтегрована у ядро Linux версії 2.6. Вона дістала назву ф'ютекс (futex, від fast user-level mutex — швидкий м'ютекс користувача).

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

Зазначимо, що лічильник ф'ютекса може розміщатися у спільній пам'яті де завгодно. Потоки можуть перетворити будь-яке місце пам'яті у ф'ютекс без попередньої підготовки (поки не виникне суперництво за ф'ютекс, потоки лише збільшують і зменшують цілочислове значення у спільній пам'яті). Ф'ютексів можна створювати безліч.

Розглянемо ситуації, коли використання ф'ютекса потребує виконання системного виклику.

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

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

Легко побачити, що ф'ютекси автоматично роблять можливою синхронізацію потоків різних процесів через розподілювану пам'ять.

Інтерфейс ф'ютексів не призначений для безпосереднього використання у прикладних програмах. Замість цього на основі ф'ютексів бібліотеки підтримки потоків можуть бути реалізовані примітиви синхронізації більш високого рівня (саме це й зроблено у NPTL).

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

Механізми синхронізації потоків у Windows ХР реалізовані на трьох рівнях: синхронізація в ядрі (на рівні потоків ядра), виконавчій системі та в режимі користувача у підсистемі Win32.

• Синхронізація в ядрі

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

• Синхронізація у виконавчій системі

Код виконавчої системи теж може користуватися спін-блокуваннями, але вони пов'язані з активним очікуванням і їхнє застосування обмежується лише організацією взаємного виключення впродовж короткого часу. Складніші задачі синхронізації розв'язують за допомогою диспетчерських об'єктів (dispatcher objects) і ресурсів виконавчої системи (executive resources).

Диспетчерські об'єкти — це об'єкти виконавчої системи, що можуть бути використані разом із сервісами очікування менеджера об'єктів.

Ресурси виконавчої системи можуть бути використані тільки в коді ВС, коду користувача вони недоступні. Вони не є об'єктами виконавчої системи, а реалізовані як структури даних зі спеціальними операціями, які можна виконувати над ними. Такий ресурс допускає різні режими доступу — взаємне виключення (як м'ютекс) і доступ за принципом блокування читання-записування.

• Об'єкти синхронізації режиму користувача

На основі диспетчерських об'єктів підсистема Win32 реалізує набір об'єктів синхронізації режиму користувача. До них належать, зокрема, м'ютекси, семафори і події.

• Очікування на диспетчерських об'єктах

Потік може синхронізуватися з диспетчерським об'єктом через виконання очікування на його дескрипторі. Для цього менеджер об'єктів надає спеціальні сервіси очікування: очікування одного об'єкта і очікування кількох об'єктів (на базі цих сервісів у Win32 АРІ реалізовані функції WaitForSingleObjectO і WaitForMultipie-Objects О).

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

Диспетчерський об'єкт може перебувати в одному з двох станів: сигналізованому (signaled) і несигналізованому (nonsignaled). Потік поновлює своє виконання, коли об'єкт, на якому він очікує, переходить у сигналізований стан (відбувається його сигналізація). При цьому виконавча підсистема перевіряє чергу очікування цього об'єкта і поновлює виконання одного або кількох потоків з неї (виконуючи перепланування і, можливо, тимчасово підвингуючи їхній пріоритет).

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

• Структури даних синхронізації

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

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

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

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

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

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

Зневага питаннями синхронізації процесів, що виконуються в режимі мультипрограмування, може привести до їх неправильної роботи або навіть до краху системи. Розглянемо, наприклад (малюнок), програму друку файлів (принт-сервер). Ця програма друкує по черзі всі файли, імена яких послідовно в порядку надходження записують в спеціальний загальнодоступний файл "замовлень" інші програми. Особлива змінна NEXT, також доступна всім процесам-клієнтам, містить номер першою вільною для запису імені файлу позиції файлу "замовлень". Процеси-клієнти читають цю змінну, записують у відповідну позицію файлу "замовлень" ім'я свого файлу і нарощують значення NEXT на одиницю. Припустимо, що в деякий момент процес R вирішив роздрукувати свій файл, для цього він прочитав значення змінної NEXT, значення якої для визначеності припустимо рівним 4. Процес запам'ятав це значення, але помістити ім'я файлу не встиг, оскільки його виконання було перерване (наприклад, в наслідок вичерпання кванта). Черговий процес S, охочий роздрукувати файл, прочитав те ж саме значення змінної NEXT, помістив в четвертую позицію ім'я свого файлу і наростив значення змінної на одиницю. Коли в черговий раз управління буде передано процесу R, то він, продовжуючи своє виконання, в повній відповідності із значенням поточної вільної позиції, отриманим під час попередньої ітерації, запише ім'я файлу також в позицію 4, поверх імені файлу процесу S.

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

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

* Нехай 2 потоки Tа і Tb (різних користувачів) отримують доступ до деякого спільного ресурсу (банківський рахунок) з метою внесення змін

На рахунку 100 у.о.
Користувач А намагається зняти 50 у.о.
Користувач В намагається покласти ще 100 у.о.

* Алгоритм роботи потоків: total_amount = total_amount + new_amount;

1.Зчитати значення total_amount	        ( var1 = total_amount )
2.Обчислити нове значення total_amount	( var1 = var1 + new_amount )
3.Записати нове значення total_amount	( total_amount = var1 )

* Послідовність подій:

1. Тa зчитав total_amount 	var1A = 100 
2. Тa обчислив total_amount 	var1A = 100 – 50
3. Тa записав total_amount 	total_amount = 50 
4. Тb зчитав total_amount 	var1B = 50
5. Тb обчислив total_amount 	var1B = 50 + 100
6. Тb записав total_amount 	total_amount = 150

Все вірно

Але результат може бути іншим!

* Послідовність подій 2:

1.Тa зчитав total_amount 	var1A = 100
2.Тa обчислив total_amount 	var1A = 100 – 50
3.Тb зчитав total_amount 	var1B = 100
4.Тb обчислив total_amount 	var1B = 100 + 100
5.Тb записав total_amount 	total_amount = 200
6.Тa записав total_amount 	total_amount = 50

В результаті total_amount == 50 (втрачена покладена сума)

* Послідовність подій 3:

1.Тa зчитав total_amount 	var1A = 100
2.Тb зчитав total_amount 	var1B = 100
3.Тb обчислив total_amount 	var1B = 100 + 100
4.Тa обчислив total_amount 	var1A = 100 – 50
5.Тa записав total_amount 	total_amount = 50
6.Тb записав total_amount 	total_amount = 200

В результаті total_amount == 200 (сума не знята)