Взаємне блокування - ситуація, коли кожен з групи процесів очікує подія, яке може викликати тільки інший процес з цієї групи. Часто, така ситуація спостерігається в парадокси типу «Курка чи яйце». Також зустрічаються назви тупикова ситуація. глухий кут. клінч. В англомовній літературі ця ситуація називається англ. deadlock (вимовляється як Дедлок).
В області інформаційних технологій, взаємним блокуванням називають ситуацію, коли два або більше процесів очікують поки інший не не звільнить певний ресурс, або якщо більше ніж два процеси чекають звільнення ресурсів в замкнутому ланцюзі.
Як приклад подібної ситуації можна навести двох чоловіків, креслять схеми, маючи лише одну лінійку і один олівець. Якщо один з чоловіків прийме лінійку, а інший олівець, між ними виникає ситуація взаємного блокування коли для того, щоб звільнити лінійку треба олівець, а для звільнення олівця треба лінійка.
Взагалі кажучи, блокуванням (або зависанням) є така ситуація, коли незалежно від того, скільки плином часу, жоден прехід з одного стану в інший відбутися не може.
Умови виникнення взаємного блокування
Було показано, що для виникнення ситуації взаємного блокування, необхідно виконання наступних чотирьох умов одночасно:
- Умова взаємного виключення (англ. Mutual exclusion). Кожен ресурс в поточний момент або зайнятий рівно одним процесом або вільний. Тобто, ресурси знаходяться в режимі ексклюзивного користування.
- Умова утримання і очікування (англ. Hold and wait). Процеси, в поточний момент утримують отримані раніше ресурси, можуть робити запити на отримання нових ресурсів.
- Умова відсутності примусового звільнення ресурсів (англ. No preemption). Неможливо змусити процес звільнити раніше отримані ресурси.Процесс, що володіє ресурсами, повинен сам їх звільняти.
- Умова циклічного очікування (англ. Circular wait). Має існувати кільцева послідовність з двох або більше процесів, кожен з яких очікує звільнення ресурсу, утримуваного наступним членом послідовності. Іншими словами, має існувати безліч процесів, так, що процес P 0 очікує звільнення ресур процесу P 1, P 1 очікує P 2. P N - 1 очікує P N. а P N очікує звільнення ресурсів процесом P 0.
Для виникнення ситуації взаємного блокування, необхідно виконання всіх чотирьох умов одночасно. Якщо хоча б одна з умов не виконується, взаємне блокування неможлива.
Моделювання тупикових ситуацій
Приклад графу виділення ресурсів. У цьому прикладі всі процеси отримають доступ до необхідних ресурсів, отже, взаємне блокування неможлива.
Ситуації взаємного блокування можливо описати точніше за допомогою спеціального засобу - графу виділення ресурсів (англ. System resource-allocation graph). У цьому орієнтованому графі, безліч вершин складається з двох підмножин - всіх активних процесів в системі (P =) і існуючих типів ресурсів (R =).Ребро від процесу P і до ресурсу P J позначається як; означає, що процес P і подав запит на одну одиницю ресурсу типу R J і очікує цей ресурс (скорочено, ребро вимогу). Ребро від ресурсу типу R J до процесу P і позначається як; означає, що одиницю ресурсу типу R J було надано процесу P і (скорочено, ребро виділення).
Оскільки може існувати кілька одиниць ресурсів одного типу, вершини з ресурсами позначаються у вигляді прямокутників з точками всередині. Кількість точок позначає кількість одиниць ресурсу цього типу.
Маючи таке визначення графу виділення ресурсів, можна довести, що за умови відсутності циклів в графі жоден з процесів не потрапляє в глухий кут. За умови наявності циклу в графі, існує можливість для виникнення тупиків.
Якщо кожен тип ресурсів має лише один екземпляр, то з наявності циклу слід наявність тупика. Кожен процес в циклі потрапляє в глухий кут.
Якщо є типи ресурсів з декількома екземплярами, то з наявності циклу наявність тупика не слід. У цьому випадку наявність циклу є необхідним, але не достатньою умовою для виникнення тупиків.
мережі Петрі
У мережах Петрі, тупиком називається така безліч позицій, що кожен перехід, який на виході має одну з позицій тупика, використовує будь-яку позицію тупика в якості входу. Тобто, якщо всі позиції тупика в певний момент спорожніють, то вся ця безліч позицій залишиться порожньою назавжди. Жоден з переходів не може пересунути фішку в глухий кут, оскільки в глухому куті відсутні фішки, що дозволяють переході, виходом якого є позиція з глухого кута.
Пасткою називається така безліч позицій, для якої кожен перехід, входом якого є одна з позицій безлічі на виході має іншу позицію безлічі. Тобто, якщо в довільній позиції пастки є фішка, то вона завжди буде знаходитися в деякому з позицій пастки.
Було доведено, що необхідною і достатньою умовою активності маркованої мережі Петрі з вільним вибором є вимога того, щоб кожен глухий кут містив пастку з фішкою.
Обробка тупикових ситуацій
Обробку і поводження з ситуаціями взаємного блокування можна умовно розділити на:
- Нехтування проблемою взагалі (т. Зв. "Страусовий алгоритм»).
- Виявлення та відновлення. Дозволити статися взаємною блокування, виявити його, і виконати деякі дії.
- Динамічне уникнути взаємного блокування шляхом правильного розподілу ресурсів.
- Запобігання шляхом невиконання одного з чотирьох умов виникнення взаємного блокування.
Перший підхід використовується в більшості сучасних операційних систем. правильна поведінка в ситуації взаємного блокування є відповідальністю розробника ПЗ.
запобігання
Як було сказано вище, для виникнення ситуації взаємного блокування необхідне одночасне виконання чотирьох умов. Якщо один з них не виконується, то ситуації взаємного блокування виникати не будуть. Тут наведені описи підходів до кожної з умов.
взаємне виключення
Умова взаємного виключення, або ексклюзивного користування повинна виконуватися для нероздільних ресурсів. Наприклад, принтер повинен використовуватися екслюзивно, одним процесом. Однак, деякі роздільні ресурси, такі, як доступ до файлів на читання, можуть лунати багатьом процесам.
У загальному випадку, умова взаємного виключення неможливо обійти, оскільки деякі з ресурсів повинні використовуватися тільки в екслюзивно режимі.
Для невиконання цієї умови, кожен раз, коли процес вимагає нові ресурси, він повинен не містити інші ресурси. Можливі такі алгоритми:
- Отримувати всі ресурси на початку роботи процесу до виконання інших операцій.
- Отримувати новий ресурс за умови вивільнення зайнятих ресурсів. Перед запитом нового ресурсу, процес звільняє зайняті їм ресурси.
Недоліком першого алгоритму є неефективне використання і простий ресурсів. Також, існує можливість «голоду»: в перевантажені системі, процес, що потребує кілька популярних ресурсів, може ніколи їх не отримати, оскільки хоча б один з них може бути зайнятий іншим процесом.
Примусове звільнення ресурсів
Для невиконання умови відсутності примусового звільнення ресурсів, можливі наступні алгоритми:
Такий алгоритм використовується для ресурсів, стан яких може бути легко збережені і відтворені, таких як регістри процесора або простору пам'яті.
циклічне очікування
Уникнення циклічного очікування досягається встановленням порядку доступу до ресурсів різних типів.
Нехай - безліч типів ресурсів. Ототожнить з кожним з них ціле число, що дозволить порівнювати ресурси і встановлювати пріоритети (див. Частково впорядкована множина).
Тепер, щоб уникнути циклічного очікування, встановимо наступне правило: процес може запитувати ресурси тільки в порядку зростання номерів. Як варіант, процес повинен звільняти ресурс з великим порядковим номером перед поданням запиту на ресурс з меншим номером.
Незважаючи на те, що встановлення і дотримання правильного порядку отримання доступу до ресурсів є відповідальністю розробника ПЗ, існують спеціалізовані інструменти для перевірки дотримання порядку і повідомлення про помилки. Одним із прикладів є програма witness, що працює на операційних системах родини BSD.
Для уникнення тупикових сутацій, програми повинні заздалегідь надавати операційній системі інформацію про ресурсах, які будуть використані процесом під час роботи. Маючи цю інформацію операційна система може вирішувати на задоволення яких запитів процес може почекати. Щоб вирішити, чи повинен процес чекати, операційна система повинна враховувати доступні ресурси, ресурси виділені процесам і майбутні запити, які можуть зробити процеси.
Інструменти
Відомі такі інструменти для роботи з клінчами в обчислювальних системах:
witness програма witness, що працює на операцінійніх системах сімейства BSD, отримує інформацію про отримані локи і перевіряє на допустимість ці запити. SPIN система для верифікації моделей розподілених систем.