Методы распознавания тупика

Чтобы распознать состояние тупика в системе необходимо для каждого существующего в ней процесса определить сможет ли он выполняться сейчас или когда-либо. При этом по определению процесс находится в тупике только в том случае, когда он не сможет развиваться ни при каких условиях.

Общая стратегия распознавания тупика состоит в моделировании наиболее благоприятного развития для каждого процесса. Если окажется, что даже при самых благоприятных условиях процесс не сможет выполняться дальше, то в менее благоприятных условиях он тем более окажется заблокированным.

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

Наиболее общий способ распознавания тупика (моделирования благоприятного развития системы) основан на редукции (сокращении) графов ресурсов, представляющих исследуемое состояние системы. Алгоритм выполнения редукции несколько отличается для графов ПИР и ПР (различия определяются свойствами ресурсов типа SR и CR и, соответственно, правилами выполнения операций, изменяющих состояние системы, процессами, а алгоритм редукции основан на этих правилах).

Граф ресурсов, представляющий состояние системы, сокращается процессом p_i, который не является заблокированным и в графе ему соответствует неизолированная вершина, с помощью удаления всех ребер, выходящих из этой вершины и входящих в нее.

Эта процедура моделирует приобретение процессом p_i запрошенных им ресурсов, а затем освобождение всех распределенных ему повторно используемых ресурсов и производство всех потребляемых ресурсов, для которых он является производителем, в объеме, достаточном для выделения всем процессам, запрашивающим эти ресурсы. В результате сокращения вершина, соответствующая процессу p_i, становится изолированной.

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

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

Порядок действий при редукции графа ПИР процессом p_i выглядит следующим образом:

1) удалить все ребра запросов (p_i, R_j), исходящие из вершины, представляющей p_i;

2) удалить все ребра (R_j, p_i), показывающие распределение ресурсов процессу p_i, причем для каждого ресурса R_j Î r, для которого удаляется ребро (R_j, p_i), изменить пометку соответствующей ему вершины: t_i:= t_i + r, где r = |(R_j, p_i)| - вес удаляемого ребра.

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

Пример редукции графа ПИР приведен на рис.2.13.

Для графов ПИР порядок сокращений несущественен. Что доказывается следующей леммой:

Все последовательности сокращений данного графа ПИР приводят к одному и тому же несокращаемому графу.

(Доказательство леммы выполняется от противного с помощью индукции)

(3, 0) (3, 2) (3, 3)

R1 R1 R1

2 1 1 1 1

P1 P2

P1 P2 Þ P1 P2 Þ P1 P2

1 1 1 1 1

R2 R2 R2

(2, 1) (2, 1) (2, 2)

Рис.2.13. Последовательность сокращений графа ПИР

С помощью этой леммы можно доказать простое необходимое и достаточное условие тупика (теорему о тупике):

Состояние системы S есть состояние тупика тогда и только тогда, когда граф ПИР для состояния S не является полностью сокращаемым.

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

Сформулированная теорема имеет два следствия:

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

2) Если S - состояние тупика в системе с ПИР, то по крайней мере два процесса находятся в тупике в этом состоянии.

Первое следствие позволяет проверить состояние (возможность развиваться) для одного конкретного процесса, а не для системы в целом.

Алгоритм редукции для распознавания тупика может быть выполнен простым перебором всех вершин, соответствующих процессам, с выполнением редукции по незаблокированным процессам, имеющим запросы и/или владеющим ресурсами.

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

Приведенный алгоритм позволяет распознать тупик в системе с повторно используемыми ресурсами, но он требует моделировать выполнение операций по изменению состояния системы. При этом исходное реальное состояние системы не должно измениться, поэтому выполнение этого алгоритма предполагает использование копии информации о системе (для каждого процесса необходимо дублировать информацию о дугах запросов и распределений, так как они могут быть “удалены” в процессе редукции, для каждой вершины, представляющей ресурс, - пометку). Таким образом, алгоритм редукции увеличивает накладные расходы системы.

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

Один из алгоритмов применим для распознавания тупика в системе, находящейся в выгодном состоянии.

Введем определение.

Узел в ориентированном графе (N, E) есть подмножество вершин M Í N таких, что для всех вершин v Î M: P(v) = M (здесь P(v) - множество всех вершин, достижимых из вершины v).

Следующая теорема дает достаточное условие тупика для системы в выгодном состоянии.

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

Приведенный ниже алгоритм дает возможность обнаружить узел в графе. Он основан на том, что узел по определению не может содержать вершину сток (сток - это вершина v, из которой не выходит ни одной дуги, то есть полустепень исхода такой вершины равна 0: od(v) = 0), а также вершины, из которых можно попасть в вершину-сток.

Sink := { v Î N | od ( v ) = 0 }

for all v Î Sink do

for all u: ( u, v ) Î E do

if u Ï Sink then Sink := Sink È { u };

if N ¹ Sink then write ( ‘В графе есть узел!’ )

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

Если в системе существуют только ресурсы только единичной емкости, то для распознавания тупика можно использовать алгоритм, основанный на следующей теореме:

Граф повторно используемых ресурсов с единичной емкостью указывает на состояние тупика тогда и только тогда, когда он содержит цикл.

Алгоритм распознавания цикла в графе, время выполнения которого пропорционально числу дуг в графе (m ´ n в худшем случае), основан на последовательном исключении дуг, направленных в стоки, его можно записать следующим образом (через w(v) обозначено число ребер, выходящих из вершины v):

Sink := { v Î N | od ( v ) = 0 }

for all v Î Sink do

Begin

for all u: ( u, v ) Î E do

Begin

w(u) := w(u) - 1;

if w(u) = 0 then Sink := Sink È { u };

end

End

if Sink ¹ N then write ( ‘В графе есть цикл!’ )

Для систем с потребляемыми ресурсами алгоритм редукции выполняется иначе - сокращение графа процессом p_i состоит из следующих операций:

1) удовлетворить все запросы процесса p_i и удалить все ребра запросов (p_i, R_j), исходящие из вершины, представляющей p_i, уменьшив соответствующие пометки вершин (счетчики доступных единиц), представляющих выделенные ресурсы, на величины выполненных запросов;

2) для всех потребляемых ресурсов R_j таких, что процесс p_i является их производителем, удалить все ребра (R_j, p_i) производителей, освободив при этом достаточное количество ресурсов для удовлетворения всех имеющихся на них запросов от всех процессов в системе (для того чтобы не усложнять работы вычислением этого числа, введем специальное число w такое, что для любого целого k выполняются условия: w > k, w + k = w - k = w), пометку вершин, для которых данный процесс был производителем, заменяем на w.

Для системы с потребляемыми ресурсами не выполняется приведенная выше лемма, то есть порядок сокращений при редукции графа потребляемых ресурсов в общем случае влияет на результат редукции (полученные после всех возможных сокращений несокращаемые графы потребляемых ресурсов могут быть различными). Пример результатов выполнения различных цепочек сокращений приведен на рис.2.14.

Так как теорема о тупике, сформулированная для систем с повторно используемыми ресурсами, основывалась на лемме, то для систем с потребляемыми ресурсами она также не будет верной. На рис.2.15 показан граф, который показывает состояние системы, которое не является тупиковым, но и граф не является полностью сокращаемым.

1

1 2

P1 1 R1 P2 R2 P3

1 1

(а)