Лекция №11

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

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

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

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

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

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

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

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

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

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

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

А
В
С

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

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

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

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

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

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

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

A

A

A

A

A

-

B

B

B

-

B

-

B

-

C

C

C

C

-

C

-

Свободно 3

Свободно 1

Свободно 5

Свободно 7

Свободно 10

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

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

A

2

A

A

A

B

B

B

B

-

C

C

C

C

Свободно 3

Свободно 2

Свободно 0

Свободно 7

небезопасно

небезопасно

небезопасно

Недопустимо

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

Предотвращение блокировок:

1) Атака взаимного исключения;

2) Атака условия удержания и ожидания;

Пример: Если все ресурсы запрашиваются одновременно, то тупиков не возникнет; если мы ожидаем несколько ресурсов WaitForMultipleObjects(), то тупиков тоже нет.

3) Атака условия отсутствия принудительной выгрузки;

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

Дата добавления: 2014-12-07