Щоб розпізнати тупиковий стан, необхідно для кожного процесу визна-ділити, чи зможе він коли-небудь знову розвиватися, тобто змінювати свої статки. Так як нас цікавить можливість розвитку процесу, а не сам процес зміни стану, то досить розглянути тільки найсприятливіші зміни стану.
Очевидно, що незаблокований процес (він тільки що отримав ресурс і по-цьому не заблокований) через деякий час звільняє всі свої ресурси і потім благополучно завершується. Звільнення раніше зайнятих ресурсів може «розбудити» деякі раніше заблоковані процеси, які, в свою чергу, розвиваючись, зможуть звільнити інші раніше зайняті ресурси. Це може тривати до тих пір, поки або не залишиться незаблокованих процесів, або якусь кількість процесів все ж залишиться заблокованими. В останньому випадку (якщо існують заблоковані процеси при завершенні зазначеної послідовності дій) початковий стан Sявляется перебуваючи-ням тупика, а що залишилися процеси зайшли в глухий кут в стані S. В про-тивно випадку S не є стан безвиході.
Виявлення тупика за допомогою редукції графа повторно використовуваних ресурсів
Найбільш сприятливі умови для Незаблокована процесу Рi можуть бути представлениредукціей (скороченням) графа повторно використовуваних ресурсів (див. Перший розділ даної глави, опис моделі Холта). Редукція графа мо-же бути описана наступним чином:
Граф повторно використовуваних ресурсів скорочується процесом Рр який не є ні заблокованою, ні ізольованою вершиною, за допомогою видалення всіх ребер, що входять в вершину Рi і виходять з Рi. Ця процеду-ра є еквівалентною придбання процесом Рi деяких ресурсів, на які він раніше видавав запити, а потім звільнення всіх його ресурсів. ТогдаPi стає ізольованою вершиною.
Граф повторно використовуваних ресурсів непріводімие (НЕ редукується), якщо він не може бути скорочений жодним процесом.
Граф ресурсів типу RSявляется повністю скорочуваним, якщо існує послідовність скорочень, яка видаляє всі дуги графа.
Наведемо лемму, яка дозволяє запропонувати алгоритми виявлення тупика.
Лемма. Для ресурсів тіпаSRпорядок скорочень несуттєвий; все послідовно-ності ведуть до одного і того ж непріводімие графу.
Доведення. Припустимо, що лема невірна. Тоді має існувати не-яке стан S, яке скорочується до деякого непріводімие со-стояння S1 за допомогою послідовності seq1 і до непріводімие состояніяS2 - за допомогою последовательностіseq2 так, чтоS1 S2 (тобто всі процеси в состояніяхS1 іS2 або заблоковані, або ізольовані).
Якщо зробити таке припущення, то ми приходимо до протиріччя, яке усувається тільки за умови, що S1 = S2. Дійсно, припустимо, що послідовність seq1 складається з упорядкованого списку процесів (P1, P2. Pk). Тоді послідовність seq1 повинна містити процес Р, який не міститься в последовательностіseq2. В іншому случаеS1 = S2. тому що редукція графа тільки видаляє дуги, вже існуючі в стані S, а якщо послідовності seq1 іseq2 містять один і той же безліч процес-сов (нехай і в різному порядку), то повинно бути видалено одне і те ж безліч дуг. І доказ по індукції покаже, що РРi (i = 1,2. K) приво-дит до зазначеного нами протиріччя.
Р P1. так як вершина S може бути скорочена процессомP1. а состояніеS2 має, отже, також містити процессP1.
Нехай Р Pi. (I = 1, 2. j). Однак, оскільки після редукції процессаміPi (i = 1, 2. j) можливо ще скорочення графа процессомPj + 1. це ж саме повинно бути справедливо і для последовательностіseq2 незалежно від по-рядка проходження процесів. Те ж саме безліч ребер графа видаляється за допомогою процессаPi. Таким чином, РPj + 1
Отже, Р Pi для i = 1, 2. kи Р не може існувати, а це протидії речіт нашим припущенням, чтоS1 S2. Отже, S1 = S2.
Теорема про глухий кут. СостояніеSесть стан безвиході тоді і тільки тоді, коли граф повторно використовуваних ресурсів в стані S не є повністю со-припиняється.
а) Припустимо, що стан S є стан безвиході і процес Pi знаходиться в глухому куті в S. Тоді для всехSj. таких що S
б) Припустимо, що S не є повністю скорочуваним. Тоді існує процес Pi. який залишається заблокованим при всіх можливих послідовностях операцій редукції у відповідність до леми. Так як будь-яка послідовність операцій редукції графа повторно використовуваних ресурсів, що закінчується непріводімие станом, гарантує, що всі ресурси тіпаSR, які можуть коли-небудь стати доступними, в дійсності ос-вобождени, то процессPi назавжди заблокований і, отже, знаходиться в глухому куті.
Слідство 1. Процес Рi не перебуває у глухому куті тоді і тільки тоді, коли серія скорочень призводить до стану, в якому Рi. не заблокований.
Наслідок 2. Якщо S є стан безвиході (по ресурсах типу SR), то принаймні два процеси зайшли в глухий кут у S.
З теореми про тупику безпосередньо слід і алгоритм виявлення тупиків. Потрібно просто спробувати скоротити граф по можливості ефективним способом; якщо граф повністю не скорочується, то початковий стан було станом тупика для тих процесів, вершини яких залишилися в несокращен-ном графі. Розглянута нами лема дозволяє зручним чином впорядкувати-вать скорочення.
Граф повторно використовуваних ресурсів може бути представлений або матрицями, або списками. В обох випадках економія пам'яті може бути досягнута використанням зважених орієнтованих мультиграфом (злиттям певних дуг отримання або дуг запиту між конкретним ресурсом і даним процесом в одну дугу з відповідним вагою, визначальним кількість одиниць ресурсу).
Розглянемо варіант з матричним представленням. Оскільки граф двочастковий, він представляється двома матрицями розміром nm. Одна матриця матриця розподілу D = || dij ||, в якій елемент dij відображає кількість едініцRj ресурсу, розподіленого процесу Рi то естьdij = | (Rj, Р;) |, де (Rj, Pi) - це дуга між вершинами Rj іPi . провідна з Rj в Рi. Друга матриця матриця запро-сов N = || nij ||, гдеnij = | (Рi, Rj) |.
У разі використання пов'язаних списків для відображення тієї ж структури можна побудувати дві групи списків. Ресурси, розподілені деякого процесу Pi. пов'язані СPI покажчиками:
Подібним чином і ресурси, запитані процесом Рi. пов'язані разом.
Аналогічні списки створюються і для ресурсів (списки розподілених і запро-шенних ресурсів).
Для обох уявлень зручно також мати одновимірний масив доступних одиниць ресурсів (r1, r2. Rm), гдеri вказує число доступних (нерозподілений-них одиниць ресурсаRi. То естьri = | Ri | - | (Ri, Pk) |.
причому кожна перевірка вимагає випробування m ресурсів. Таким чином, час виконання такого алгоритму в найгіршому випадку пропорційно mn 2.
Більш ефективний алгоритм може бути отриманий за рахунок зберігання деякої додаткової інформації про запити. Для кожної вершини процесу Рi визначається так званий счётчікожіданій wi. відображає кількість ресурсів (не числом одиниць ресурсу), які в якийсь час викликають блоки-ження процесу. Крім цього, можна зберігати для кожного ресурсу запити, впорядковані за розміром (кількістю одиниць ресурсу). Тоді наступний алгоритм скорочень, записаний на псевдокоді, має максимальний час виконання, пропорційне mn.
For all P L do
Begin for all Rj | (Rj. P) |> 0 do
Тут L- це поточний список процесів, які можуть виконувати редукцію графа. Можна сказати, чтоL: = i wi = 0>. Програма вибирає процес Р зі списку L, процес Р скорочує граф, збільшуючи число доступних едініцrj всіх ресурсовRj. розподілених процесу Р, оновлює лічильник ожіданіяwi каждо-го процесу Рi який зможе задовольнити свій запит на приватний ресурс Rj. і додає Рi до L, якщо лічильник очікування стає нульовим.