19) Стратегия «обнаружение-устранение» для борьбы с взаимоблокировками. (с использованием графов Холта, матриц распределения ресурсов)

Стратегии борьбы с блокировками

1. «Страусовый алгоритм»:

Допущение, что блокировки в системе можно игнорировать. Усилия, затраченные на преодоление блокировок, могут себя не оправдать.

2. Обнаружение и устранение:

Дать возможность произойти блокировке, обнаружить ее и предпринять действия для ее исправления.

Способы восстановления:

- принудительная выгрузка ресурса;

- восстановление через откат (прежде чем захватить ресурс, процесс сохраняет свое состояние (checkpoint, контрольная точка), в случае конфликта можно вернуться к сохраненному состоянию);

- выгрузить процесс целиком (если нет побочных эффектов (процесс не влияет на состо­яние системы)).

Обнаружение тупика в случае единственности ресурса каждого типа:

1. В текущем состоянии построить граф Холта;

2. Обнаружить на нем цикл по какому-либо алгоритму:

Процесс	Захват ресурса	Ждет ресурс
A	R	S
B	-	T
C	-	S
D	V	S, T
E	T	V
F	W	S
G	V	U

Алгоритм:

Выполняется для каждой вершины графа, в начале все ребра не марки­рованы.

1. Список посещенных вершин пустой, выбираем начальную вершину M.

2. M добавляем в список. Если M в списке есть, то обнаружен цикл.

3. Если у M имеется немаркированное исходящее ребро, то идем к шагу 4, ина­че – к шагу 5.

4. Выбираем любое немаркированное ребро, маркируем его, переходим к но­вой вершине и объявляем её текущей; переходим к шагу 2.

5. Удаляем последнюю вершину из списка, выбираем ее текущей, переходим к шагу 3.

Обнаружение тупика, если имеется несколько ресурсов каждого типа:

(E₁, E₂, …, E_m)=E – вектор ресурсов;

E_j- сколько ресурсов типа j (1 j m)

(A₁, A₂, …, A_m)=A – вектор доступных ресурсов

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

, где – сколько процесс i получил ресурсов типа j.

Матрица запросов ресурсов:

Алгоритм:

Все процессы не маркированы:

1. В матрице R ищем строку, соответствующую немаркированному процессу, которая меньше либо равна А, (r_i A).

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

3. Если процессов нет, то конец.

Если находятся немаркированные процессы, то они в тупике.

Пример: Находится ли система в тупике?

E=(4, 2, 3, 1) A=(2, 1, 0, 0)

20) Стратегия избегания блокировок. Алгоритм банкира. (диаграмма траекторий ресурсов, алгоритм банкира для одного вида ресурсов)

Избежание взаимных блокировок

Траектория ресурсов

1 – захват принтера

2 – захват плоттера

3 – освобождение принтера

4 – освобождение плоттера

Точка на траектории ресурсов может двигаться только вверх и вправо.

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

Алглритм Банкира для одного вида ресурсов

Цель алгоритма: проверить, приводит ли удовлетворение запроса на ресурс к выходу из безопасного состояния системы.

Пусть имеется один ресурс некоторого типа.

А	3	9
В	2	4
С	2	7

Максимальное число ресурсов, которое процесс может запросить без учета уже запрошеных

Сколько процесс уже имеет ресурсов

Чтобы проверить, приводит ли запрос к безопасному состоянию, необходимо описать матрицу распределения ресурсов (см. выше). При этом:

A, B, C – имена банка;

2^ой столбец – выданные кредиты;

3^ий столбец – необходимо кредитов.

Свободных кредитов 3. Можем полностью обеспечить кредитами клиента В.

A	3	9		A	3	9		A	3	9		A	3	9		A	0	-
B	2	4		B	4	4		B	0	-		B	0	-		B	0	-
C	2	7		C	2	7		C	2	7		C	0	-		C	0	-
Свободно 3				Свободно 1				Свободно 5				Свободно 7				Свободно 10

Клиент, чей запрос будет полностью удовлетворен, вернет все взятые кредиты.

Рассмотрим состояние:

A	3	9	2	A	4	9		A	4	9		A	4	9
B	2	4		B	4	4		B	4	4		B	0	-
C	2	7		C	2	7		C	2	7		C	2	7
Свободно 3				Свободно 2				Свободно 0				Свободно 7
				небезопасно				небезопасно				небезопасно

Недопустимо

Т.о., запрос от А на предоставление ему 1 единицы кредита следует отклонить.