Лекция: При наличии одного экземпляра ресурсов каждого типа

 

Обнаружение блокировок в вычислительной системе при наличии одного экземпляра ресурсов каждого типа производится на основе анализа построенного графа ресурсов и процессов /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.

 

еще рефераты
Еще работы по информатике