Взаімоблокіровка - студопедія
У комп'ютерних системах існує велика кількість ресурсів, кожен з яких в конкретний момент часу може використовуватися тільки одним процесом. В якості таких прикладів можна привести принтери, накопичувачі на магнітній стрічці і елементи внутрішніх таблиць системи. Поява двох процесів, одночасно передають дані на принтер, призведе до друку безглуздого набору символів. Наявність двох процесів, що використовують один і той же елемент таблиці файлової системи, обов'язково стане причиною руйнування файлової системи. Тому всі операційні системи мають здатність надавати процесу ексклюзивний доступ (по крайней мере, тимчасовий) до певних ресурсів.
Часто для виконання прикладних завдань процес потребує винятковому доступі немає одному, а до кількох ресурсів.
Приклад 3.5. Взаімоблокіровка Припустимо, що кожен з двох процесів хоче записати відсканований документ на компакт-диск. Процес A запитує дозвіл на використання сканера і отримує його. Процес B запрограмований по-іншому, тому спочатку запитує устрій-ство для запису компакт-дисків і також отримує його. Потім процес A звертається до пристрою для запису компакт-дисків, але запит відхиляється до тих пір, поки це пристрій зайнятий процесом B. На жаль, замість того щоб звільнити пристрій для запису компакт-дисків, B запитує сканер. У цей момент процеси заблоковані і будуть вічно залишатися в цьому стані. Така ситуація називається тупиком, тупиковою ситуацією або взаімоблокіровка.
У складно організованій системі з великою кількістю ресурсів і одночасно виконуваних процесів взаімоблокіровка вельми вірогідна. При цьому під ресурсами (поняття ресурсу було введено в першому параграфі) можна розуміти, в тому числі, і самі процеси. Узагальнюючи, ресурсом можна назвати будь-який об'єкт, до якого може отримати доступ процес.
Ресурси можна розбити на два класи:
- Вивантажувати назвемо такий ресурс, який можна безболісно забирати у власникові процесу. До такого ресурсу можна віднести, наприклад, пам'ять. Поки процес призупинено, можна безболісно вивантажити вміст пам'яті на диск, при цьому віддавши звільнився обсяг пам'яті іншому процесу. Коли настане момент відновити процес, пам'ять якого була вивантажено, вивантажені дані з диска прочитуються і поміщаються в пам'ять, після чого процес запускається знову.
- Невивантажуваного назвемо такий ресурс, який можна забрати у процесу, не втративши результатів роботи цього процесу. Наприклад, якщо в момент запису відняти у процесу записуючий пристрій і передати його в користування іншій процесу, всі дані першого процесу будуть втрачені безповоротно.
Справедливості заради зазначимо, що взаємне блокування може виникнути лише на другому класі ресурсів, оскільки якщо в тупиковій ситуації задіяні ресурси першого класу, ситуацію можна вирішити, примусово вивантаживши ресурс, подбавши при цьому про його подальше відновлення.
Так як всі процеси перебувають у стані очікування, жоден з них не буде причиною якої-небудь події, яке могло б активувати будь-який інший процес в групі, і всі процеси продовжують чекати до нескінченності. У цій мо-діли ми припускаємо, що процеси мають тільки один потік і що немає прерива-ний, здатних активізувати заблокований процес. Умова відсутності переривань необхідно, щоб запобігти ситуації, коли той чи інший за-блокований процес активізується, скажімо, за сигналом тривоги і потім при-водить до події, яка звільнить інші процеси в групі.
У більшості випадків подією, на яку чекає кожен процес, є звільнення будь-якого ресурсу, в даний момент зайнятого іншим учасником групи. Іншими словами, кожен учасник групи процесів, які зайшли в глухий кут, чекає доступу до ресурсу, що належить заблокованого процесу. Жоден з процесів не може працювати, жоден з них не може звільнити будь-якої ресурс і жоден з них не може відновитися. Кількість процесів і кількістю-ство і вид ресурсів, наявних і потрібних, тут не важливі. Результат ос-шається тим же самим для будь-якого виду ресурсів, апаратних і програмних.
Необхідні умови виникнення взаимоблокировки - умови Коффмана (Coffman):
- Умова взаємного виключення. Кожен ресурс в даний момент або відданий рівно одному процесу, або доступний.
- Умова утримання і очікування. Процеси, в даний момент утримую-щие отримані раніше ресурси, можуть запитувати нові ресурси.
- Умова відсутності примусового вивантаження ресурсу. У процесу не можна примусовим чином забрати раніше отримані ресурси. Процес, вла-деюще ними, повинен сам звільнити ресурси.
- Умова циклічного очікування. Повинна існувати кругова послідовність з двох і більше процесів, кожен з яких чекає доступу до ресурсу, утримуваного наступним членом послідовності.
Зазначені умови є необхідними. Тобто, якщо хоч одне з них не виконується, то взаімоблокіровка ніколи не виникне. Достатність не має місця бути: якщо виконуються всі чотири умови, взаімоблокіровка може і не відбутися, наприклад, якщо в системі немає процесів, які претендують на одночасне використання одних і тих же ресурсів.
Слід зазначити, що кожна умова відноситься до правилами, встановленими в даній конкретній операційній системі. На жаль, практично неможливо спроектувати операційну систему так, щоб повністю виключити будь-одна з умов Коффмана заздалегідь. Однак існують варіанти руйнування взаімоблокіровок, засновані на примусове виключення будь-якого з цих умов.
Відстежувати виникнення взаімоблокіровок зручно на діаграмах Холта (Holt). Діаграма Холта є спрямований граф [10], що має два типи вузлів: процеси (показуються кружечками) і ресурси (показуються квадратиками). Той факт, що ресурс отриманий процесом і в даний момент зайнятий цим процесом, вказується ребром (стрілкою) від ресурсу до процесу. Ребро, спрямоване від процесу, до ресурсу, означає, що процес в даний момент блокований і знаходиться в стані очікування доступу до відповідного ресурсу.
Критерій взаимоблокировки. Взаімоблокіровка має місце бути, тоді і тільки тоді, коли діаграма Холта, що відображає стану процесів і ресурсів, містить цикл [11].
В операційних системах реалізуються наступні стратегії обробки взаімоблокіровок (можливих або сталися):
1. Ігнорування. Чи не передбачається що-небудь робити для запобігання взаимоблокировки або її руйнування, якщо вона виникла.
2. Виявлення та відновлення. Якщо взаімоблокіровка сталася, виявити її і зробити будь-які дії.
3. Динамічне уникнути. Розподіляти ресурси системи так, щоб уникнути взаімоблокіровок. Всякий раз рішення про розподіл приймається виходячи з поточного стану системи.
4. Запобігання. Передбачає структурний спростування одного з чотирьох правил Коффмана.