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

Наиболее благоприятные условия для незаблокированного процесса Р_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.

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

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

Рассмотрим вариант с матричным представлением. Поскольку граф двудольный, он представляется m.´двумя матрицами размером n Одна матрица – матрица распределения 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|(RS= |Ri| –_i,P_k)|.

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

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

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

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

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:= {Р_iw½_i = 0}. Программа выбирает процесс Р из списка L, процесс Р сокращает граф, увеличивая число доступных единиц r_j всех ресурсов R_j, распределенных процессу Р, обновляет счётчик ожидания w_i каждого процесса Р_i который сможет удовлетворить свой запрос на частный ресурс R_j, и добавляет Р_i к L, если счётчик ожидания становится нулевым.