Обнаружение тупика посредством редукции графа повторно используемых ресурсов

Наиболее благоприятные условия для незаблокированного процесса Р_i могут быть представлены редукцией (сокращением) графа повторно используемых ресурсов (см. первый раздел данной главы, описание модели Холта). Редукция графа мо­жет быть описана следующим образом:

¨ Граф повторно используемых ресурсов сокращается процессом Рр который не является ни заблокированной, ни изолированной вершиной, с помощью удаления всех ребер, входящих в вершину Р_i и выходящих из Р_i. Эта процеду­ра является эквивалентной приобретению процессом Р_i неких ресурсов, на которые он ранее выдавал запросы, а затем освобождению всех его ресурсов. Тогда P_i становится изолированной вершиной.

¨ Граф повторно используемых ресурсов несокращаем (не редуцируется), если он не может быть сокращен ни одним процессом.

¨ Граф ресурсов типа RS является полностью сокращаемым, если существует последовательность сокращений, которая удаляет все дуги графа.

Приведем лемму, которая позволяет предложить алгоритмы обнаружения тупика.

Лемма. Для ресурсов типа SR порядок сокращений несуществен; все последова­тельности ведут к одному и тому же несокращаемому графу.

Доказательство. Допустим, что лемма неверна. Тогда должно существовать не­которое состояние S, которое сокращается до некоторого несокращаемого со­стояния S₁ с помощью последовательности seq₁ и до несокращаемого состояния S₂ – с помощью последовательности seq₂ так, что S₁ ¹ S₂ (то есть все процессы в состояниях S₁ и S₂ или заблокированы, или изолированы).

Если сделать такое предположение, то мы приходим к противоречию, которое устраняется только при условии, что S₁ = S₂. Действительно, предположим, что последовательность seq₁ состоит из упорядоченного списка процессов (P₁, P₂, ... , P_k). Тогда последовательность seq₁ должна содержать процесс Р, который не содержится в последовательности seq₂. В противном случае S₁ = S₂ , потому что редукция графа только удаляет дуги, уже существующие в состоянии S, а если последовательности seq₁ и seq₂ содержат одно и то же множество процес­сов (пусть и в различном порядке), то должно быть удалено одно и то же множе­ство дуг. И доказательство по индукции покажет, что Р ¹ Р_i (i = 1,2,..., k) приво­дит к указанному нами противоречию.

¨ Р ¹ P₁, так как вершина S может быть редуцирована процессом P₁, а состояние S₂ должно, следовательно, также содержать процесс P₁.

¨ Пусть Р ¹ P_i, (i = 1, 2, ... , j). Однако, поскольку после редукции процессами P_i (i = 1, 2, ... , j) возможно ещё сокращение графа процессом P_j+1, это же самое должно быть справедливо и для последовательности seq₂ независимо от по­рядка следования процессов. То же самое множество рёбер графа удаляется с помощью процесса P_i . Таким образом, Р ¹ P_j+1

Следовательно, Р ¹ P_i для i = 1, 2, ..., k и Р не может существовать, а это противо­речит нашему предположению, что S₁ ¹ S₂. Следовательно, S₁ = S₂.

Теорема о тупике. Состояние S есть состояние тупика тогда и только тогда, когда граф повторно используемых ресурсов в состоянии S не является полностью со­кращаемым.

Доказательство.

а) Предположим, что состояние S есть состояние тупика и процесс P_i находится в тупике в S. Тогда для всех S_j, таких что S S_j процесс Р_i заблокирован в S_j (по определению). Так как сокращения графа идентичны для серии опе­раций процессов, то конечное несокращаемое состояние в последовательно­сти сокращений должно оставить процесс P_i блокированным. Следовательно, граф не является полностью сокращаемым.

б) Предположим, что S не является полностью сокращаемым. Тогда существует процесс P_i, который остаётся заблокированным при всех возможных последовательностях операций редукции в соответствие с леммой. Так как любая последовательность операций редукции графа повторно используемых ресурсов, оканчивающаяся несокращаемым состоянием, гарантирует, что все ресурсы типа SR, которые могут когда-либо стать доступными, в действительности ос­вобождены, то процесс P_i навсегда заблокирован и, следовательно, находится в тупике.

Следствие 1. Процесс Р_i не находится в тупике тогда и только тогда, когда серия сокращений приводит к состоянию, в котором Р_i, не заблокирован.

Следствие 2. Если S есть состояние тупика (по ресурсам типа SR), то по крайней мере два процесса находятся в тупике в S.

Из теоремы о тупике непосредственно следует и алгоритм обнаружения тупиков. Нужно просто попытаться сократить граф по возможности эффективным способом; если граф полностью не сокращается, то начальное состояние было состоянием тупика для тех процессов, вершины которых остались в несокращен­ном графе. Рассмотренная нами лемма позволяет удобным образом упорядочи­вать сокращения.

Граф повторно используемых ресурсов может быть представлен или матрицами, или списками. В обоих случаях экономия памяти может быть достигнута использованием взвешенных ориентированных мультиграфов (слиянием определённых дуг получения или дуг запроса между конкретным ресурсом и данным процессом в одну дугу с соответствующим весом, определяющим количество единиц ресурса).

Рассмотрим вариант с матричным представлением. Поскольку граф двудольный, он представляется двумя матрицами размером n´m. Одна матрица – матрица распределения D = ||d_ij||, в которой элемент d_ij отражает количество единиц R_j ресурса, распределенного процессу Р_i то есть d_ij = |(Rj, Р;)|, где (R_j, P_i) – это дуга между вершинами R_j и P_i, ведущая из R_j в Р_i. Вторая матрица – матрица запро­сов N = ||n_ij||, где n_ij = |(Р_i , R_j)|.

В случае использования связанных списков для отображения той же структуры можно построить две группы списков. Ресурсы, распределенные некоторому процессу P_i, связаны с P_i указателями:

P_i®(R_x, d_x) ® (R_y, d_y)®... ®(R_z, d_z), где R_j – вершина, представ­ляющая ресурс, и d_j – вес дуги, то есть d_j = |(R_j, P_i)|.

Подобным образом и ресурсы, запрошенные процессом Р_i , связаны вместе.

Аналогичные списки создаются и для ресурсов (списки распределенных и запро­шенных ресурсов).

R_i®(P_u, n_u) ® (P_v, n_v)®... ®(P_w, n_w), где n_j = |(P_j, R_j)|.

Для обоих представлений удобно также иметь одномерный массив доступных единиц ресурсов (r₁, r₂, ..., r_m), где r_i указывает число доступных (нераспределён­ных единиц ресурса R_i, то есть r_i = |Ri| – S|(R_i , P_k)|.

Простой метод прямого обнаружения тупика заключается в просмотре по поряд­ку списка (или матрицы) запросов, причём, где возможно, производятся сокращения дуг графа до тех пор, пока нельзя будет сделать более ни одного сокраще­ния. При этом самая плохая ситуация возникает, когда процессы упорядочены в некоторой последовательности P₁, Р₂, ... , Р_n, а единственно возможным поряд­ком сокращений является обратная последовательность, то есть Р_n, P_n-1, ..., P₂, Р₁ , а также в случае, когда процесс запрашивает все m ресурсов. Тогда число прове­рок процессов равно

n + (n-1) + ... + 1 ⁼ n´(n+1)/2,

причём каждая проверка требует испытания m ресурсов. Таким образом, время выполнения такого алгоритма в наихудшем случае пропорционально m´n².

Более эффективный алгоритм может быть получен за счёт хранения некоторой дополнительной информации о запросах. Для каждой вершины процесса Р_i определяется так называемый счётчик ожиданий w_i , отображающий количество ресурсов (не число единиц ресурса), которые в какое-то время вызывают блоки­ровку процесса. Кроме этого, можно сохранять для каждого ресурса запросы, упорядоченные по размеру (числу единиц ресурса). Тогда следующий алгоритм сокращений, записанный на псевдокоде, имеет максимальное время выполнения, пропорциональное m´n.

For all P Î L do

Begin for all Rj ' |(R_j, P)| > 0 do

Begin r_j := r_j + |(R_j, P)|;

For all P_i ' 0 < |(P_i, R_j)| <= r_j do

Begin w_i := w_i – 1;

If w_i = 0 then L := L È {Pi}

End

End

End

Deadlock := Not (L = {P₁, P₂, ... , P_n});

Здесь L – это текущий список процессов, которые могут выполнять редукцию графа. Можно сказать, что L := {Р_i½w_i = 0}. Программа выбирает процесс Р из списка L, процесс Р сокращает граф, увеличивая число доступных единиц r_j всех ресурсов R_j, распределенных процессу Р, обновляет счётчик ожидания w_i каждо­го процесса Р_i который сможет удовлетворить свой запрос на частный ресурс R_j, и добавляет Р_i к L, если счётчик ожидания становится нулевым.