Deadlock

Взає́мне блокува́ння (англ. Deadlock) — ситуація, коли кожен із групи процесів очікує на подію, яку може викликати лише інший процес з цієї групи. Часто, така ситуація спостерігається в парадоксах типу («Курка чи яйце?»). Також зустрічаються назви тупикова ситуація, тупик, клінч. В англомовній літературі ця ситуація має назву англ. deadlock (вимовляється як дедлок).

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

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

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

Умови виникнення взаємного блокування

Було показано, що для виникнення ситуації взаємного блокування, необхідно виконання наступних чотирьох умов водночас:

1. Умова взаємного виключення (англ. mutual exclusion). Кожен ресурс в поточний момент або зайнятий рівно одним процесом або вільний. Тобто, ресурси знаходяться в режимі ексклюзивного користування.
2. Умова утримання та очікування (англ. hold and wait). Процеси, що в поточний момент утримують отримані раніше ресурси, можуть робити запити на отримання нових ресурсів.
3. Умова відсутності примусового звільнення ресурсів (англ. no preemption). Неможливо примусити процес звільнити раніше отримані ресурси. Процес, що володіє ресурсами, повинен сам їх звільняти.
4. Умова циклічного очікування (англ. circular wait). Має існувати кільцева послідовність із двох або більше процесів, кожен із яких очікує на звільнення ресурса, що утримується наступним членом послідовності. Іншими словами, має існувати множина процесів ${\displaystyle \{P_{0},P_{1},\dots ,P_{n}\}}$, так, що процес ${\displaystyle P_{0}}$ очікує на звільнення ресурів процесу ${\displaystyle P_{1}}$, ${\displaystyle P_{1}}$ очікує на ${\displaystyle P_{2}}$, …, ${\displaystyle P_{n-1}}$ очікує на ${\displaystyle P_{n}}$, а ${\displaystyle P_{n}}$ очікує на звільнення ресурсів процесом ${\displaystyle P_{0}}$.

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

Livelock

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

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

Моделювання тупикових ситуацій

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

Ситуації взаємного блокування можливо описати точніше з допомогою спеціального засобу — графу виділення ресурсів (англ. system resource-allocation graph). В цьому орієнтованому графі, множина вершин складається із двох підмножин — всіх активних процесів у системі (${\displaystyle P=\{P_{1},P_{2},\dots ,P_{n}\}}$) та існуючих типів ресурсів (${\displaystyle R=\{R_{1},R_{2},\dots ,R_{m}\}}$).

Ребро від процесу ${\displaystyle P_{i}}$ до ресурсу ${\displaystyle R_{j}}$ позначається як ${\displaystyle P_{i}\to R_{j}}$; означає, що процес ${\displaystyle P_{i}}$ подав запит на одну одиницю ресурсу типу ${\displaystyle R_{j}}$ та очікує на цей ресурс (скорочено, ребро запиту). Ребро від ресурсу типу ${\displaystyle R_{j}}$ до процесу ${\displaystyle P_{i}}$ позначається як ${\displaystyle R_{j}\to P_{i}}$; означає, що одиницю ресурсу типу ${\displaystyle R_{j}}$ було надано процесу ${\displaystyle P_{i}}$ (скорочено, ребро виділення).

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

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

Якщо кожен тип ресурсів має лише один екземпляр, то із наявності циклу випливає наявність тупика. Кожен процес в циклі потрапляє в тупик.

Якщо є типи ресурсів з декількома екземплярами, то із наявності циклу наявність тупика не випливає. В цьому випадку наявність циклу є необхідною, але не достатньою умовою для виникнення тупиків.

Мережі Петрі

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

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

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

Обробка тупикових ситуацій

Обробку та поводження із ситуаціями взаємного блокування можна умовно поділити на:

1. Нехтування проблемою взагалі (т. з. «страусиний алгоритм»).
2. Виявлення та відновлення. Дозволити відбутися взаємному блокуванню, виявити його, та виконати деякі дії.
3. Динамічне уникнення взаємного блокування шляхом правильного розподілу ресурсів.
4. Запобігання шляхом невиконання однієї із чотирьох умов виникнення взаємного блокування.

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

Запобігання

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

Взаємне виключення

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

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

Утримання та очікування

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

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

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

Примусове звільнення ресурсів

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

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

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

Циклічне очікування

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

Нехай ${\displaystyle R=\{R_{1},R_{2},\dots ,R_{n}\}}$ — множина типів ресурсів. Ототожнимо з кожним з них ціле число, що дозволить порівнювати ресурси та встановлювати пріоритети (див. частково впорядкована множина).

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

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

Уникнення

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

Інструменти

Відомі такі інструменти для роботи з клінчами в обчислювальних системах:

witness

програма witness, що працює на операційних системах сімейства BSD, отримує інформацію про отримані локи та перевіряє на припустимість ці запити.

SPIN

система для верифікації моделей розподілених систем.

Примітки

1. (Таненбаум 2002), глава 3 , стор. 188.
2. (Abraham 2005), глава 7, стор. 246.
3. (Bowman, Gomez) розділ 12.2
4. (Coffman et al 1971)
5. (Таненбаум 2002), стор. 188—189
6. (Abraham 2005), розділ 7.2, стор. 247—249
7. (Holt 1972)
8. (Abraham 2005) розділ 7.2.2, стор. 249.
9. (Таненбаум 2002), стор. 189—192
10. (Hack 1972)
11. (Питерсон 1984), розділ 7.4.3, стор. 202—203.
12. (Таненбаум 2002), глава 3, стор. 192.
13. (Abraham 2005), розділ 7.3, стор. 252.
14. (Havender 1968)
15. (Таненбаум 2002), стор. 206.
16. (Abraham 2005), розділ 7.4, стор. 253.
17. FreeBSD 7.0: WITNESS(4) Manual page. 24 липня 2008. Архів оригіналу за 25 червня 2013. Процитовано 24 липня 2008.
18. Архівована копія. Архів оригіналу за 25 квітня 2009. Процитовано 17 квітня 2009.{{}}: Обслуговування CS1: Сторінки з текстом «archived copy» як значення параметру title ()

• Coffman, E. G., Elphick, M. J. and Shoshani, A.: «System Deadlocks», Computing Surveys, vol. 3, pp. 67—78, червень 1971.
• Havender, J. W.: «Avoiding Deadlock in Multitasking Systems», IBM Systems Journal, vol. 7, pp. 74—84, 1968.
• Holt, R. C.: «Some Deadlock Properties of Computer Systems», Computing Surveys, vol. 4, pp. 179—196, вересень 1972.
• Hack M., Analysis of Production Schemata by Petri Nets, Master's thesis, Department of Electrical Engineering, Massachusetts Institute of Technology, лютий 1972.

Література

• Таненбаум Э. (2002). глава 3. Современные Операционные Системы (вид. 2). СПб Питер. ISBN .
• Питерсон Дж. (1984). Теория сетей Петри и моделирование систем. М. «Мир». (пер. з англ.)
• Abraham Silberschatz, Peter Baer Galvin, Greg Gagne (2005). глава 7. Operating Systems Concepts (вид. 7). Wiley. ISBN .
• Howard Bowman, Rodolfo Gomez (2006). Concurrency Theory. Springer. ISBN .
• Ajay D. Kshemkalyani, Mukesh Singhal (2008). Deadlock detection in distributed systems. Distributed Computing Principles, Algorithms, and Systems. Cambridge University Press. ISBN .

Див. також

Паралельне програмування Процес Зависання Проблема зупинки

Пі-числення Мережа Петрі Обмін повідомленнями Теорія графів