Взаємне блокування

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

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 — це коли стани процесів постійно змінюється один відносно одного — але все одно вони «у безвихідному циклі», що не робить ніякої корисної роботи.

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

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

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

Ребро від процесу ${\displaystyle P_{i}}$ до ресурсу ${\displaystyle P_{j}}$ позначається як ${\displaystyle P_{i}\to P_{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}}$ (скорочено, ребро виділення).

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

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

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

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

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

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

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

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

witness

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

SPIN

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

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