3.Виявлення та усунення взаємоблокувань.

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

Побудуємо для системи граф ресурсів виду (рис.5.2).

Рис.5.2. Граф ресурсів (а); цикл, взятий з а (б).

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

Виникає запитання: „Чи є заблокованою ця система, і якщо так, то які процеси в цьому приймають участь?”. Граф ресурсів на рис.5.2.(а). Він містить один цикл (рис.5.2.(б)). З нього видно, що процеси D, E і G – заблоковані.

Процеси A, C і F не попали в тупік, тому що будь-якому з них можна надати ресурс S, після чого процес, який отримав ресурс, закінчить свою роботу і поверне ресурс. Потім два інших процеси по черзі можуть отримати ресурс і також успішно виконати свою роботу.

Алгоритм:

1. для кожного вузла N в графі виконуються наступні п’ять кроків, де N – є початковим вузлом.

2. задамо початкові умови: L – порожній список, всі ребра невідмічені.

3. поточний вузол доповнюємо в кінець списку L і перевіряємо кількість появ вузла в списку. Якщо вузол наявний в двох місцях, то граф містить цикл (записаний в список L) і робота алгоритму закінчується.

4. Для заданого вузла перевіряємо, чи виходить з нього хоча б одне немарковане ребро.

5. На даному кроці відбувається попадання в тупік. Видаляємо останній вузол з списку і повертаємося до попереднього вузла, тобто до того, який був поточним перед тупіковим вузлом. Позначаємо його поточним вузлом. Повертаємося до кроку 3. Якщо це початковий вузол, то граф не місить циклів і алгоритм закінчується.

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