Виявлення тупиків

Виявлення взаимоблокировки зводиться до фіксації тупикової ситуації і виявлення залучених до неї процесів. Для цього проводиться перевірка наявності циклічного очікування у випадках, коли виконані перші три умови виникнення тупика. Методи виявлення активно використовують графи розподілу ресурсів. Розглянемо модельну ситуацію.

1. Процес P1 очікує ресурс R1.

2. Процес P2 утримує ресурс R2 і очікує ресурс R1.

3. Процес P3 утримує ресурс R1 і очікує ресурс R3.

4. Процес P4 очікує ресурс R2.

5. Процес P5 утримує ресурс R3 і очікує ресурс R2.

Питання полягає в тому, чи є дана ситуація тупиковою, і якщо так, то які процеси в ній беруть участь. Для відповіді на це питання можна сконструювати граф ресурсів, як показано на рис. 9.5. З малюнка видно, що є цикл, що моделює умова кругового очікування, і що процеси P2, P3, P5, а може бути, і інші знаходяться в тупиковій ситуації.

Рис. 9.4. Граф ресурсів

Візуально легко виявити наявність глухого кута, але потрібні також формальні алгоритми, реалізовані на комп'ютері. Один з таких алгоритмів описаний в [Таненбаум, 2002], там же можна знайти посилання на інші алгоритми.

Існують і інші способи виявлення тупиків, застосовні також у ситуаціях, коли є кілька ресурсів кожного типу. Так в [Дейтл, 1987] описаний спосіб, званий редукцією графа розподілу ресурсів, а в [Таненбаум, 2002] - матричний алгоритм.

Читайте також:

<== попередня сторінка	\|	наступна сторінка ==>
Ігнорування проблеми тупиків	\|	Взаємодія процесів

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

Генерація сторінки за: 0.008 сек.