Лекция: При наличии нескольких экземпляров ресурсов каждого типа
Для обнаружения взаимных блокировок в этом случае используются матричные операции. Пусть, например, имеются n процессов, которые захватывают и требуют ресурсы P1,…, Pn. Пусть имеется m классов ресурсов, при этом внутри каждого класса имеется несколько ресурсов:
E1 класс 1
E2 класс 2
Ei класс C
……………….
Em класс m
Задача предполагает следующие понятия (рис. 4.3):
Вектор существующих ресурсов 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.Если таких процессов нет, то работа программы заканчивается, т.к. происходит взаимная блокировка.
Пример 1. Пусть имеются 4 класса ресурсов – плоттеры, сканеры, принтеры, HDD и 4 процесса — Р1, Р2, Р3, Р4. Тогда
Е = (4 4 3 1) – вектор существующих ресурсов.
А = (2 0 0 1) – вектор доступных ресурсов.
— матрица текущего распределения ресурсов.
— матрица запросов ресурсов.
Следуем алгоритму:
Находим процесс Pi для которого i-я строка матрицы R≤ A.
Из всех 4-х процессов этому условию удовлетворяет только 1-ый процесс — Р1
R1 ≤ A1 2000 < 2001
Прибавляем 1-ю строку матрицы C к вектору A.
С1 + А = (2 0 1 0) + (2 0 0 1) = 4 0 1 1 А = (4 0 1 1).
Снова ищем процесс Pi, для которого i-я строка матрицы R≤ A.
Видим, что таких процессов нет, т.е. ни один из оставшихся трех процессов Р2, Р3, Р4 стартовать не может, следовательно, обнаружена взаимная блокировка.
Пример 2. Пусть имеются 4 класса ресурсов – плоттеры, сканеры, принтеры, HDD и 4 процесса — Р1, Р2, Р3, Р4.
Е = (4 4 3 1) – вектор существующих ресурсов.
А = (2 1 0 1) – вектор доступных ресурсов.
— матрица текущего распределения ресурсов.
— матрица запросов ресурсов.
Следуем алгоритму:
Находим процесс Pi, для которого i-я строка матрицы R≤ A.
Из всех 4-х процессов этому условию удовлетворяют два процесса — Р1 и Р2.
Р1 R1 ≤ A1 2000 < 2101
Р2 R2 ≤ A2 0100 < 2101
Прибавляем 1-ю строку матрицы C к вектору A.
С1 + А = (2 0 1 0) + (2 1 0 1) = 4 1 1 1 А = (4 1 1 1)
Маркируем 1-ый процесс — Р1.
Снова ищем процесс Pi, для которого i-я строка матрицы R≤ A. Таких процессов два — Р2, Р3.
Прибавляем 2-ю строку матрицы C к вектору A.
С2 + А = (0 2 1 0) + (4 1 1 1) = 4 3 2 1 А = (4 3 2 1)
Маркируем 2-ой процесс — Р2.
Ищем процесс Pi, для которого i-я строка матрицы R≤ A. Таких процессов два – Р3, Р4.
Прибавляем 3-ю строку матрицы C к вектору A.
С3 + А = (0 1 0 0) + (4 3 2 1) = 4 4 2 1 А = (4 4 2 1)
Маркируем 3-ой процесс – Р3.
Прибавляем 4-ю строку матрицы C к вектору A.
С4 + А = (0 0 1 0) + (4 4 2 1) = 4 4 3 1
Маркируем последний 4-ый процесс — Р4.
Выполнились все 4 процесса — Р1, Р2, Р3, Р4.
Проверка: А = (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.