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. Якщо це початковий вузол, то граф не місить циклів і алгоритм закінчується.

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

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

Якщо в системі існує декілька екземплярів деяких з ресурсів, для виявлення взаємоблокувань необхідний інший метод. Розглянемо алгоритм, що базується на матрицях, який виявляє тупіки серед n процесів, від P₁ до P_n. Нехай m – це число класів ресурсів, причому в системі E₁ - ресурсів класу 1, E₂ – ресурсів класу 2 і, в загальному, E_i –ресурсів класу i (де 1≤i≤m). E – вектор існуючих ресурсів. Він передає загальну кількість наявних екземплярів кожного ресурсу.

Далі потрібно два масиви: C – матриця поточного розподілу і R – матриця запитів. I-ий рядок в матриці C показує, скільки представників кожного класу ресурсів в даний момент використовує процес P_i. Таким чином, C_ij – кількість екземплярів ресурсу j, яке займає процес i. Аналогічно R_ij – кількість екземплярів ресурсу j, які хоче отримати процес P_i. Ці чотири структури показано на рис.5.3.

Рис.5.3. Чотири структури даних, необхідних для алгоритму виявлення тупіків

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

Алгоритм виявлення взаємоблокувань базується на порівнянні векторів. Визначимо, що для двох векторів A і B відношення A≤B означає, що кожен елемент вектору A менше або дорівнює відповідному елементу вектора B. Математично запис буде таким: A≤B тоді і тільки тоді, коли A_i≤B_i для 1≤i≤m.

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

Кроки алгоритму виявлення тупіків:

1. Шукаємо немаркований процес P_i, для якого i-ий рядок матриці R менше вектора A або дорівнює йому.

2. Якщо такий процес знайдено, добавляємо i-ий рядок матриці C до вектора A, маркуємо процес і повертаємося до кроку 1.

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

Завершення алгоритму означає, що всі немарковані процеси, якщо такі є, попали в тупік.

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

Розглянемо приклад (рис.5.4)

Рис.5.4. Приклад використання алгоритму виявлення тупіків.

Тут є три процеси і чотири класи ресурсів. Працюючи з алгоритмом виявлення взаємоблокувань, ми шукаємо процес, чий запит ресурсів може бути задоволений в даній системі. Тільки третій процес може отримати все потрібне, тому він працює, закінчується і повертає всі свої ресурси, даючи A=(2 2 2 0). З цього моменту може виконуватись процес 2, по завершенні повертаючи свої ресурси в систему. Ми отримаємо А=(4 2 2 1)

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

5. Вихід із взаємоблокування.

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

- Відновлення за допомогою примусового вивантаження ресурсу

- Відновлення через відкат

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

• Відновлення шляхом знищення процесів

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

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

Існує підхід, за яким найкраще знищувати процеси, які можна легко знову запустити.