виявлення взаімоблокіровок
При використанні цього методу система не намагається запобігти потраплянню в тупикові ситуації. Замість цього вона дозволяє взаімоблокіровке статися. намагається визначити, коли це сталося, і потім робить якісь дії до повернення сі-стеми до стану, що мав місце до того, як система потрапила в глухий кут.
Виявлення взаимоблокировки при наявності одного ресурсу кожного типу
Алгоритм виявлення взаимоблокировки в системах, в яких існує тільки один ресурс кожного типу. Складемо граф, де ресурси - вузли. Цикл в такому графі буде взаімоблокіровка.
Цей алгоритм по черзі бере кожен вузол в якості кореня того, що, як він сподівається, виявиться деревом, і виконує в дереві пошук в глибину. Якщо в процесі обходу алгоритм повертається до вже зустрічалися вузлу, то він знайшов цик л. Якщо алгоритм обходить всі ребра з якого-небудь заданого вузла, то він повертається до попереднього вузла. Якщо він повертається до кореня і не може йти далі, то підграф поточного вузла не містить циклів. Якщо ця властивість зберігається для всіх вузлів, значить, повний граф не містить циклів, а система не заблокована.
Виявлення взаімоблокіровок при наявності декількох ресурсів кожного типу
Аналогічний алгоритм виявлення взаімоблокіровок, але при наявності декількох ресурсів кожного типу. Нехай у вихідному положенні всі процеси не марковані. У міру просування алгоритму на процеси буде ставитися оцінка, яка служить ознакою того, що вони можуть закінчити свою роботу і, отже, не перебувають у глухому куті. Після завершення алгоритму відомо, що будь-який немаркований процес знаходиться в тупиковій ситуації.
На першому кроці алгоритм шукає процес, який може допрацювати до кінця. Такий процес характеризується тим, що всі необхідні для нього ресурси повинні перебувати серед доступних в даний момент ресурсів. Тоді обраний процес пропрацює до свого завершення і після цього поверне ресурси, які він займав, до загального фонду доступних ресурсів. Потім процес маркується як за-кінчений. Якщо виявиться, що всі процеси можуть працювати, тоді жоден з них в даний момент не заблокований. Якщо деякі з них ніколи не зможуть за-пуститися, значить, вони потрапили в глухий кут. Незважаючи на те що алгоритм не є детермінованим (оскільки він може переглядати процеси в будь-якому допустимому порядку), результат завжди однаковий.
Вихід з взаимоблокировки
Припустимо, що наш алгоритм виявлення взаімоблокіровок закінчився успішно і знайшов тупик. Що далі? Необхідні методи для відновлення і отримання в результаті знову працюючої системи.
Відновлення за допомогою примусового вивантаження ресурсу
Іноді можна тимчасово відібрати ресурс у його поточного власника і віддати його іншому процесу. У багатьох випадках потрібне ручне втручання, особливо в операційних системах пакетної обробки, які працюють на мейнфреймах.
Здатність забирати ресурс у процесу, віддавати його іншому процесу і потім повертати назад так, що вихідний процес цього не помічає, в значній мірі залежить від властивостей ресурсу. Вийти з глухого кута таким чином часто важко або неможливо. Вибір призупиняють процес головним чином залежить від того, який процес володіє ресурсами, які легко можуть бути у нього відняли.
Поновлення за рішенням відкат
Іноді можна організувати роботу таким чином, щоб процеси періодично створювали контрольні точки. Створення процесом контрольної точки означає, що стан процесу записується в файл, в результаті чого згодом процес може бути відновлений з цього файлу. Контрольні точки містять не тільки образ пам'яті, а й стан ресурсів, тобто інформацію про те, які ресурси в даний момент надані процесу. Для більшої ефективності нова контрольна точка повинна записуватися не поверх старої, а в новий файл, так що під час виконання процесу утворюється ціла послідовність контрольних точок.
Коли взаімоблокіровка виявлена, досить просто зрозуміти, які ресурси потрібні процесам. Щоб вийти з глухого кута, процес, який займає необхідний ресурс, відкочується до того моменту часу, перед яким він отримав даний ресурс. для чого запускається одна з його контрольних точок. Вся робота, виконана після цієї контрольної копії, втрачається. В результаті процес знову запускається з більш раннього моменту, коли він не займав той ресурс, який тепер надається одному з процесів, по-полеглих в глухий кут. Якщо відновлений процес знову намагається отримати даний ресурс, йому доведеться чекати того моменту, коли ресурс знову стане доступний.
Відновлення шляхом знищення процесів
Грубий, але одночасно і найпростіший спосіб виходу з ситуації взаимоблокировки полягає в знищенні одного або декількох процесів. Можна знищити процес, що знаходиться в циклі взаимоблокировки. При невеликому везінні інші процеси зможуть продовжити роботу. Якщо перше вилучення не допомагає, процедуру можна повторювати до тих пір, поки цикл врешті не буде розор-ван.
уникнення взаімоблокіровок
Розглядаючи виявлення взаімоблокіровок, ми неявно припускали, що коли процес запитує ресурси, він вимагає їх все відразу. Однак в більшості систем ресурси запитуються по черзі, по одному. Система повинна вміти вирішувати, чи є надання ресурсу безпечним чи ні. і надавати його процесу тільки в першому випадку. Таким чином, виникає нове запитання: чи існує алгоритм, який завжди може уникнути ситуації взаимоблокировки, весь час роблячи правильний вибір? Відповіддю є умовне «так» - ми можемо уникнути тупиків, але тільки якщо заздалегідь буде доступна певна інформація.