Перегляд вихідного коду сторінки Взаємне блокування

[[Файл:Process deadlock.svg|thumb|right|200px]]

'''Взає́мне блокува́ння''' ({{lang-en|Deadlock}})&nbsp;— ситуація, коли кожен із групи [[процес (програмування)|процесів]] очікує на подію, яку може викликати лише інший процес з цієї групи.<ref>(Таненбаум 2002), глава 3 , стор. 188.</ref><ref>(Abraham 2005), глава 7, стор. 246.</ref> Часто, така ситуація спостерігається в [[парадокс]]ах типу «[[Курка чи яйце?]]». Також зустрічаються назви ''тупикова ситуація'', ''тупик'', ''[[клінч]]''. В англомовній літературі ця ситуація має назву {{lang-en|deadlock}} (вимовляється як ''дедлок'').

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

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

Взагалі кажучи, блокуванням (або [[зависання]]м) є така ситуація, коли не залежно від того, скільки сплине часу, жоден прехід із одного стану в інший відбутись не може.<ref>(Bowman, Gomez) розділ 12.2</ref>

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

Було показано, що для виникнення ситуації взаємного блокування, необхідно виконання наступних чотирьох умов водночас:<ref>(Coffman et al 1971)</ref><ref>(Таненбаум 2002), стор. 188—189</ref><ref>(Abraham 2005), розділ 7.2, стор. 247—249</ref>
# '''Умова [[взаємне виключення|взаємного виключення]]''' ({{lang-en|mutual exclusion}}). Кожен ресурс в поточний момент або зайнятий рівно одним процесом або вільний. Тобто, ресурси знаходяться в режимі ексклюзивного користування.
# '''Умова утримання та очікування''' ({{lang-en|hold and wait}}). Процеси, що в поточний момент утримують отримані раніше ресурси, можуть робити запити на отримання нових ресурсів.
# '''Умова відсутності примусового звільнення ресурсів''' ({{lang-en|no preemption}}). Неможливо примусити процес звільнити раніше отримані ресурси. Процес, що володіє ресурсами, повинен сам їх звільняти.
# '''Умова циклічного очікування''' ({{lang-en|circular wait}}). Має існувати кільцева послідовність із двох або більше процесів, кожен із яких очікує на звільнення ресурса, що утримується наступним членом послідовності. Іншими словами, має існувати множина процесів <math>\{P_0, P_1, \dots, P_n\}</math>, так, що процес <math>P_0</math> очікує на звільнення ресурів процесу <math>P_1</math>, <math>P_1</math> очікує на <math>P_2</math>, …, <math>P_{n-1}</math> очікує на <math>P_n</math>, а <math>P_n</math> очікує на звільнення ресурсів процесом <math>P_0</math>.
Для виникнення ситуації взаємного блокування, необхідно виконання всіх чотирьох умов водночас. Якщо хоча б одна з умов не виконується, взаємне блокування неможливе.

== Livelock ==

'''Динамічне взаємне блокування''' чи '''livelock'''&nbsp;— це коли стани процесів постійно змінюється один відносно одного&nbsp;— але все одно вони «[[зациклення|у безвихідному циклі]]», що не робить ніякої корисної роботи.

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

== Моделювання тупикових ситуацій ==
[[Файл:Sample-resource-allocation-graph.svg|thumb|250px|right|Приклад графу виділення ресурсів. В цьому прикладі всі процеси отримають доступ до необхідних ресурсів, отже, взаємне блокування неможливе.]]

Ситуації взаємного блокування можливо описати точніше з допомогою спеціального засобу&nbsp;— ''графу виділення ресурсів'' ({{lang-en|system resource-allocation graph}}). В цьому орієнтованому [[Граф (математика)|графі]], множина вершин складається із двох підмножин&nbsp;— всіх активних процесів у системі (<math>P = \{P_1, P_2, \dots, P_n\}</math>) та існуючих типів ресурсів (<math>R = \{R_1, R_2, \dots, R_m\}</math>).<ref>(Holt 1972)</ref><ref name="a">(Abraham 2005) розділ 7.2.2, стор. 249.</ref><ref>(Таненбаум 2002), стор. 189—192</ref>

Ребро від процесу <math>P_i</math> до ресурсу <math>R_j</math> позначається як <math>P_i \to R_j</math>; означає, що процес <math>P_i</math> подав запит на одну одиницю ресурсу типу <math>R_j</math> та очікує на цей ресурс (скорочено, ребро запиту). Ребро від ресурсу типу <math>R_j</math> до процесу <math>P_i</math> позначається як <math>R_j \to P_i</math>; означає, що одиницю ресурсу типу <math>R_j</math> було надано процесу <math>P_i</math> (скорочено, ребро виділення).

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

Маючи таке визначення графу виділення ресурсів, можна довести, що за умови відсутності [[Цикл (теорія графів)|циклів]] в графі жоден із процесів не потрапляє в тупик. За умови наявності циклу в графі, існує можливість для виникнення тупиків.<ref name="a"/>

Якщо кожен тип ресурсів має лише один екземпляр, то із наявності циклу випливає наявність тупика. Кожен процес в циклі потрапляє в тупик.<ref name="a"/>

Якщо є типи ресурсів з декількома екземплярами, то із наявності циклу наявність тупика не випливає. В цьому випадку наявність циклу є необхідною, але не достатньою умовою для виникнення тупиків.<ref name="a"/>

=== Мережі Петрі ===

В [[Мережа Петрі|мережах Петрі]], ''тупиком'' називається така множина позицій, що кожен перехід, який на виході має одну із позицій тупика, використовує будь-яку позицію тупика як вхід. Тобто, якщо всі позиції тупика в деякий момент спорожніють, то вся ця множина позицій залишиться порожньою назавжди. Жоден із переходів не може пересунути фішку в тупик, оскільки в тупику відсутні фішки, які б дозволили перехід, виходом якого є позиція з тупика.<ref name="hack">(Hack 1972)</ref><ref>(Питерсон 1984), розділ 7.4.3, стор. 202—203.</ref>

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

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

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

Обробку та поводження із ситуаціями взаємного блокування можна умовно поділити на:<ref>(Таненбаум 2002), глава 3, стор. 192.</ref>
# Нехтування проблемою взагалі (т. з. «[[Алгоритм страуса|страусиний алгоритм]]»).
# Виявлення та відновлення. Дозволити відбутися взаємному блокуванню, виявити його, та виконати деякі дії.
# Динамічне уникнення взаємного блокування шляхом правильного розподілу ресурсів.
# Запобігання шляхом невиконання однієї із чотирьох умов виникнення взаємного блокування.

Перший підхід використовується в більшості сучасних [[операційна система|операційних систем]]: правильне поводження у ситуації взаємного блокування є відповідальністю розробника ПЗ.<ref>(Abraham 2005), розділ 7.3, стор. 252.</ref>

=== Запобігання ===

Як було вказано вище, для виникнення ситуації взаємного блокування необхідне одночасне виконання чотирьох умов. Якщо хоча б одна з них не виконується, то ситуації взаємного блокування виникати не будуть.<ref>(Havender 1968)</ref><ref>(Таненбаум 2002), стор. 206.</ref><ref>(Abraham 2005), розділ 7.4, стор. 253.</ref> Нижче наведено описання підходів до кожної з умов.

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

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

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

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

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

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

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

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

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

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

Нехай <math>R = \{ R_1, R_2, \dots, R_n \}</math>&nbsp;— [[множина]] типів ресурсів. Ототожнимо з кожним з них [[цілі числа|ціле число]], що дозволить порівнювати ресурси та встановлювати пріоритети (див. [[частково впорядкована множина]]).

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

Попри те, що встановлення та дотримання правильного порядку отримання доступу до ресурсів є відповідальністю розробника ПЗ, існють спеціалізовані інструменти для перевірки дотримання порядку та повідомлення про помилки. Одним з прикладів є програма witness, що працює на операційних системах сім'ї [[Berkeley Software Distribution|BSD]].<ref name=witness>{{cite web|url=http://www.freebsd.org/cgi/man.cgi?query=witness&apropos=0&sektion=0&manpath=FreeBSD+7.0-RELEASE&format=html|title=FreeBSD 7.0: WITNESS(4) Manual page|date=2008-07-24|archiveurl=https://www.webcitation.org/6HeQl80wy?url=http://www.freebsd.org/cgi/man.cgi?query=witness|archivedate=2013-06-25|accessdate=2008-07-24|deadurl=no}}</ref>

=== Уникнення ===

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

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

; witness: програма witness, що працює на операційних системах сімейства BSD, отримує інформацію про отримані локи та перевіряє на припустимість ці запити.<ref name=witness/>
; SPIN: система для [[верифікація формальна|верифікації]] моделей [[Розподілені обчислення|розподілених систем]].<ref>{{Cite web |url=http://www.spinroot.com/ |title=Архівована копія |accessdate=17 квітня 2009 |archive-date=25 квітня 2009 |archive-url=https://web.archive.org/web/20090425030501/http://spinroot.com/ }}</ref>

== Примітки ==
{{reflist|2}}
{{refbegin}}
* 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.
{{refend}}

== Література ==
* {{cite book|author=Таненбаум Э.|title=Современные Операционные Системы|chapter=глава 3|year=2002|publisher=СПб Питер|edition=2|isbn=5-318-00299-4}}
* {{cite book|title=Теория сетей Петри и моделирование систем|author=Питерсон Дж.|publisher=М. «Мир»|date=1984}} (пер. з англ.)
* {{cite book|author=Abraham Silberschatz, Peter Baer Galvin, Greg Gagne|title=Operating Systems Concepts|chapter=глава 7|year=2005|edition=7|publisher=Wiley|isbn=0-471-69466-5}}
* {{cite book|title=Concurrency Theory|url=https://archive.org/details/concurrencytheor0000bowm|author=Howard Bowman, Rodolfo Gomez|publisher=Springer|year=2006|isbn=978-1-85233-895-4}}
* {{cite book|title=Distributed Computing Principles, Algorithms, and Systems| розділ=Deadlock detection in distributed systems|author=Ajay D. Kshemkalyani, Mukesh Singhal|publisher=Cambridge University Press|year=2008|isbn=978-0-511-39341-9}}

== Див. також ==

{{multicol}}
* [[Паралельне програмування]]
* [[Процес]]
* [[Зависання]]
* [[Проблема зупинки]]
{{multicol-break}}
* [[Пі-числення]]
* [[Мережа Петрі]]
* [[Обмін повідомленнями]]
* [[Теорія графів]]
{{multicol-end}}


{{Compu-stub}}
{{Паралельні обчислення}}
{{ВП-портали|Програмування|}}
[[Категорія:Програмування]]
[[Категорія:Паралельні обчислення]]
[[Категорія:Помилки програмування]]
[[Категорія:Едсгер Дейкстра]]