Задание №3. Разработка программы обнаружения взаимных блокировок процессов при наличии одного ресурса каждого типа.

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

Существует четыре условия возникновения взаимных блокировок, которые сформулировал Кофман:

1)взаимное исключение – каждые ресурс в данный момент времени либо отдан, либо доступен только одному процессу (невозможно совместное использование ресурса);

2)ожидание и удержание – процессы, удерживающие в данный момент времени полученные ресурсы, могут запрашивать новые;

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

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

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

Выделяют четыре стратегии борьбы с тупиками:

1)пренебрежение тупиками или блокировками в системе;

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

3)обход тупиков с помощью специального распределения ресурсов;

4)распознавание тупика и восстановление системы.

Существуют следующие методы ликвидации взаимоблокировок:

• метод восстановления при помощи принудительной выгрузки ресурсов. Отбирается ресурс у процесса–владельца и передается другому процессу. Но отдать ресурс, а затем его получить не всегда возможно;

• метод восстановления системы через откат алгоритма. Процессы периодически создают контрольные точки, которые записываются в файл (из этого файла процесс может быть восстановлен). Когда взаимоблокировка обнаружена выполняются следующие действия: 1) определяется какой ресурс требуется дополнительно для выхода из блокировки; 2) процесс, занимающий ресурс, возвращается к точке времени, перед которой этот ресурс был получен, далее ресурс передаётся одному из процессов циклической последовательности;

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

Для обнаружения взаимных блокировок при наличии нескольких экземпляров ресурсов каждого типа используются матричные операции. Пусть, например, имеются n процессов, которые захватывают и требуют ресурсы P1,…, Pn. Пусть имеется m классов ресурсов, при этом внутри каждого класса имеется несколько ресурсов:

E1 класс 1

E2 класс 2

Ei класс C

……………….

Em класс m

Вектор существующих ресурсов E (E1,E2,…,Em);

Вектор доступных ресурсов A (A1,A2,…,Am), Ai в этом векторе равен количеству экземпляров ресурсов класса i доступных в текущий момент времени;

C – матрица текущего распределения ресурсов (какому процессу какие ресурсы принадлежат), C(ij) - количество экземпляров ресурса j, которое занимает процесс P(i).

R – матрица запросов ресурсов (какой процесс какой ресурс запросил),

R(ij) - количество экземпляров ресурса j, которое хочет получить процесс P(i).

Рис. 4.3. Векторы ресурсов вычислительной системы

Общее количество ресурсов равно сумме занятых и свободных ресурсов.

Алгоритм обнаружения взаимоблокировок основан на сравнении векторов:

1.Находится процесс Pi для которого i-я строка матрицы R≤ A.

2.Если такой процесс найден, то прибавляем i-ю строку матрицы C к вектору A и возвращаемся к шагу 1.

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

. Пусть имеются 4 класса ресурсов – плоттеры, сканеры, принтеры, HDD и 4 процесса - Р₁, Р₂, Р_3, Р₄.

Е = (4 4 3 1) – вектор существующих ресурсов.

А = (2 1 0 1) – вектор доступных ресурсов.

- матрица текущего распределения ресурсов

- матрица запросов ресурсов

Следуем алгоритму:

Находим процесс Pi, для которого i-я строка матрицы R≤ A. Из всех 4-х процессов этому условию удовлетворяют два процесса - Р_1, Р₂.

Р₁ R₁ ≤ A₁ 2000 < 2101

Р₂ R₂ ≤ A₂ 0100 < 2101

Прибавляем 1-ю строку матрицы C к вектору A.

С1 + А = (2 0 1 0) + (2 1 0 1) = 4 1 1 1 А = (4 1 1 1)

Маркируем 1-й процесс - Р₁.

Снова ищем процесс Pi, для которого i-я строка матрицы R≤ A. Таких процессов два - Р₂, Р₃.

Прибавляем 2-ю строку матрицы C к вектору A.

С2 + А = (0 2 1 0) + (4 1 1 1) = 4 3 2 1 А = (4 3 2 1)

Маркируем 2-й процесс - Р₂.

Ищем процесс Pi, для которого i-я строка матрицы R≤ A. Таких процессов два – Р₃, Р₄.

Прибавляем 3-ю строку матрицы C к вектору A.

С3 + А = (0 1 0 0) + (4 3 2 1) = 4 4 2 1 А = (4 4 2 1)

Маркируем 3-й процесс – Р₃.

Прибавляем 4-ю строку матрицы C к вектору A.

С4 + А = (0 0 1 0) + (4 4 2 1) = 4 4 3 1

Маркируем последний 4-й процесс - Р₄.

Выполнились все 4 процесса - Р₁, Р₂, Р_3, Р₄.

Проверка: А = (4 4 3 1) = Е = (4 4 3 1). После выполнения всех четырех процессов вектор доступных ресурсов равен вектору существующих ресурсов.

Вывод: взаимных блокировок не обнаружено

Текст программы blokir, реализующей этот алгоритм:

program blokir;

var

E,A: array [1..4] of integer;

C,R: array [1..3, 1..4] of integer;

i, j, k, z, s, x: integer;

Label m;

begin

for i:=1 to 4 do

begin

writeln (‘VVedite kolichestvo sushesvuyushih resursov klassa ‘,i);

readln (E [i]);

end;

for i:=1 to 4 do

begin

writeln (‘VVedite kolichestvo dostupnyh resursov klassa ‘,i);

readln (A [i]);

end;

for i:=1 to 3 do

for j:=1 to 4 do

begin

writeln (‘VVedite kolichestvo resursov klassa ‘,i,’, ispolzuemyh processom ‘,j);

readln (C [i, j]);

end;

for i:=1 to 3 do

for j:=1 to 4 do

begin

writeln (‘VVedite kolichestvo resursov klassa ‘,i,’, trebuemyh processu ‘,j);

readln (R [i, j]);

end;

//поиск процесса, для старта которого достаточно доступных на данный момент ресурсов

k:=1;

while k < = 3 do

begin

if ((R[k,l]<=A[l])and(R[k,2]<=A[2])and(R[k,3]<=A[3])and(R[k,4]<=A[4])) then

begin

writeln (‘Startoval process ‘,k);

z:=k;

end;

k:=k + 1;

end;

//вычисление вектора доступных ресурсов при условии освобождения ресурсов стартовавшим процессом

writeln (‘Vector dostupnyh resursov’);

for i:=1 to 4 do

begin

A[i]:= A[i] + C [z, i];

Writeln (A[i]);

end;

k:= 1;

while k < = 3 do

begin

if ((R[k,l]<=A[l])and(R[k,2]<=A[2])and(R[k,3]<=A[3])and(R[k,4]<=A[4])and(k<>z)) then

begin

writeln (‘Startoval process’, k);

S:= k;

end;

k:= k +1;

end;

writeln (‘Vector dostupnyh resursov’);

for i:=1 to 4 do

begin

A[i]:= A[i] + C [s, i];

Writeln (A[i]);

end;

k:= 1;

while k < = 3 do

begin

if ((R[k,l]<=A[l])and(R[k,2]<=A[2])and(R[k,3]<=A[3])and(R[k,4]<=A[4])and(k<>z)and(k<>s)) then begin

writeln (‘Startoval process’,k);

x:= k;

end;

k:= k +1;

end;

writeln (‘Vector dostupnyh resursov’);

for i:=1 to 4 do

begin

A[i]:= A[i] + C [x, i];

Writeln (A[i]);

end;

//сравнение векторов доступных и существующих ресурсов

for i:=1 to 4 do

begin

if E [i] = A[i] then goto m;

end;

m: writeln (‘Vychisleniya bez vzaimnyh blokirovok!’)

end.

Экранная формула программы.