Лекция: При наличии одного экземпляра ресурсов каждого типа
Обнаружение блокировок в вычислительной системе при наличии одного экземпляра ресурсов каждого типа производится на основе анализа построенного графа ресурсов и процессов /6-8/. Наличие циклов в графе указывает на взаимную блокировку в вычислительной системе.
В графе процессы обозначаются как круг с именем процесса, а ресурсы обозначаются как квадрат с именем ресурса. Исходящее ребро от процесса к ресурсу означает, что процесс требует данный ресурс. Входящее ребро от ресурса к процессу означает, что процесс занял данный ресурс.
Один из возможных алгоритмов поиска циклов в графе следующий. Для каждого из N узлов в графе выполняется пять шагов.
1.Задаются начальные условия: L-пустой список, все ребра немаркированы.
2.Текущий узел добавляем в конец списка L и проверяем количество появления узла в списке. Если он встречается два раза, значит цикл и взаимоблокировка.
3.Для заданного узла смотрим, выходит ли из него хотя бы одно немаркированное ребро. Если да, то переходим к шагу 4, если нет, то переходим к шагу 5.
4.Выбираем новое немаркированное исходящее ребро и маркируем его. И переходим по нему к новому узлу и возвращаемся к шагу 3.
5.Зашли в тупик. Удаляем последний узел из списка и возвращаемся к предыдущему узлу. Возвращаемся к шагу 3. Если это первоначальный узел, значит, циклов нет, и алгоритм завершается.
Пример 1. Рассмотрим вычислительную систему, в которой выполняются 10 процессов (A, B, C, D, E, F, G, H, I, J) и используется 8 ресурсов (Q, K, L, N, X, V, T, R). Требуемые и занятые данными процессами ресурсы отображаются табл.4.1, а граф процессов и ресурсов построен на рис. 4.1.
Проверяем есть ли в данном графе цикл, а значит возможность блокировки.
[C] [B] [B]
[C, L, E] [B, X] [B, K]
[C, L, E, K] [B, X, J] [B, K, G]
[C, L, E, K, G] [B, X, J, R] [B, K, G, N]
[C, L, E, K, G, N] [B, K, G, N, F]
[C, L, E, K, G, N, F]
[D] [D]
[D, Q] [D, Q] [D, N]
[D, Q, H] [D, Q, A] [D, N, F]
[D, Q, H, V] [D, Q, A, N]
[D, Q, H, V, I] [D, Q, A, N, F]
[D, Q, H, V, I, T]
Вывод: в данном графе циклов нет, поэтому блокировки не обнаружено.
Пример 2. Рассмотрим вычислительную систему, в которой выполняются 10 процессов (A, B, C, D, E, F, G, H, I, J) и используется 8 ресурсов (Q, K, L, N, X, V, T, R). Требуемые и занятые данными процессами ресурсы отображаются табл. 4.2, а граф процессов и ресурсов построен на рис. 4.2. Изменим в графе направление ребра DN на противоположное.
[C]
[C, L]
[C, L, E]
[C, L, E, K]
[C, L, E, K, G]
[C, L, E, K, G, N] [C, L, E, K, G, N]
[C, L, E, K, G, N, F] [C, L, E, K, G, N, D]
[C, L, E, K, G, N, D, Q, ]
[C, L, E, K, G, N, D, Q, A]
[C, L, E, K, G, N, D, Q, A, N]
Вывод: количество появлений узла N в списке 2 раза, следовательно, в графе есть цикл и обнаружена блокировка.
Текст программы graf, реализующей этот алгоритм:
program graf;
type
PPr = ^Pr;
Pr=record
Name:string;
Pred:PPr;
Next:PPr;
end;
type
PResZan = ^ResZan;
ResZan=record
Num:string;
Pred:PResZan;
Next:PResZan;
end;
type
PResZapr = ^ResZapr;
ResZapr=record
Num1:string;
Num2:string;
end;
type
Pspisok = ^spisok;
spisok=record
pole:string;
pred:Pspisok;
next:Psipok;
end;
label s;
var
Process:array [1..10] of Pr;
ZanRes:array [1..10] of ResZan;
ZaprRes:array [1..10] of ResZapr;
Cep:array [1..10] of spisok;
list:array [1..10] of string;
n,i,j,m:integer;
Results:PPr;
begin
writeln(‘Введите число процессов’);
Readln(n);
for i:=1 to n do
begin
writeln(‘Введите название’,i,’-го процесса’);
readln(Process[i].name);
writeln(‘Введите для процесса ‘,Process[i].name,’занятый ресурс’);
readln(ZanRes[i].num);
writeln(‘Введите для процесса ‘,Process[i].name,’1-ый запрашиваемый ресурс’);
readln(ZaprRes[i].num1);
writeln(‘Введите для процесса ‘,Process[i].name,’2-ой запрашиваемый ресурс’);
writeln(‘Если второго запрашиваемого ресурса нет, введите символ *’);
readln(ZaprRes[i].num2);
end;
for i:=1 to 10 do
cep[i].pole:=’0’;
S: i:=1;
cep[i].pred:=ZanRes[i].num;
list[i]:=cep[i].pred;
cep[i].pole:=Process[i].name;
list[i+1]:=cep[i].pole;
ifZaprRes[i].num 1<> ‘*’then
begin
cep[i].next:=ZaprRes[i].num1;
cep[i+1].pred:=cep[i].next;
list[i+2]:=cep[i].next;
end
else
begin
if ZaprRes[i].num2<>’*’then
cep[i].next:ZaprRes[i].num2;
cep[i+1].pred:=cep[i].next;
list[i+2]:=cep[i].next;
else
begin
cep[i].next:=’0’;
end;
end;
end.