Системное программное обеспечение Лекция 8 Тупики

Тупик 2 Тупик (deadlock) – множество заблокированных процессов, каждый из которых владеет некоторым ресурсом и ожидает ресурса, которым владеет какой-либо другой процесс из этого множества. Пример тупика: Пусть P1 и P2 – процессы, а R1 и R2 – ресурсы.

Модель системы 3

Условия возникновения тупиков 4

Граф распределения ресурсов 5

6

Поиск тупиков по графу 7

Вводы 8

Направления борьбы с тупиками 9

Игнорирование проблемы тупиков 10

Способы предотвращения тупиков 11

Безопасное состояние системы 12

Стратегия безопасного выделения ресурсов 13

Утверждения о безопасных состояниях 14

Алгоритм банкира 15

Структуры данных для алгоритма банкира 16

Алгоритм безопасности 17

Алгоритм запроса ресурсов 18

Пример использования алгоритма банкира 19 AllocationMaxAvailable ABCABCABC P0P P1P P2P P3P P4P Need ABC P0P0 743 P1P1 122 P2P2 600 P3P3 011 P4P4 431

Условия к алгоритму банкира 20

Предотвращение тупиков за счет нарушения условий возникновения тупиков 21

Нарушение условия взаимоисключения 22

Нарушение условия ожидания дополнительных ресурсов 23

Нарушение принципа отсутствия перераспределения 24

Нарушение условия кругового ожидания 25

Обнаружение тупиков 26

Граф wait-for 27 граф wait-for: вершины соответствуют процессам, и дуга проводится из вершины P i в вершину P j, если процесс P i ожидает процесса P j.

Описание переменных 28

Алгоритм обнаружения тупиков 29

Пример 30 Request ABC P0P0 000 P1P1 201 P2P2 001 P3P3 100 P4P4 002 AllocationRequest ABCABC P0P P1P P2P P3P P4P

Восстановление после тупика 31

Порядок прекращаемых процессов 32

Желаемые действия при «откате» 33