2014-02-17
436
Избежание взаимных блокировок
Траектория ресурсов
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) Атака условия циклического ожидания. Если все ресурсы пронумерованы и каждый процесс имеет право захватывать ресурс только с большим порядковым номером, чем номера уже захваченных ресурсов, то тупика не возникнет.
