Обнаружение взаимоблокировки при наличии одного ресурса каждого типа
Взаимоблокировка процессов
Взаимоблокировка процессов может происходить, когда несколько процессов борются за один ресурс.
Ресурсы бывают выгружаемые и невыгружаемые, аппаратные и программные.
Выгружаемый ресурс - этот ресурс безболезненно можно забрать у процесса (например: память).
Невыгружаемый ресурс - этот ресурс нельзя забрать у процесса без потери данных (например: принтер).
Проблема взаимоблокировок процессов возникает при борьбе за невыгружаемый ресурсы.
Условия необходимые для взаимоблокировки:
1. Условие взаимного исключения - в какой-то момент времени, ресурс занят только одним процессом или свободен.
2. Условие удержания и ожидания - процесс, удерживающий ресурс может запрашивать новые ресурсы.
3. Условие отсутствия принудительной выгрузки ресурса.
4. Условие циклического ожидания - должна существовать круговая последовательность из процессов, каждый, из которого ждет доступа к ресурсу, удерживаемому следующим членом последовательности.
Моделирование взаимоблокировок
Моделирование тупиков с помощью графов.
Условные обозначения
На такой модели очень хорошо проверить возникает ли взаимоблокировка. Если есть цикл, значит, есть и взаимоблокировка.
Рассмотрим простой пример:
три процесса A, B, C
три ресурса R, S, T
Последовательное выполнение процессов, взаимоблокировка не возникает
Рассмотрим циклический алгоритм:
|
|
|
три процесса A, B, C
три ресурса R, S, T
Возникает взаимоблокировка
Рассмотрим тот же самый случай, но допустим, что система, зная о предстоящей взаимоблокировке, заблокирует процесс B.
Взаимоблокировка не возникает.
Методы борьбы с взаимоблокировками
Четыре стратегии избегания взаимоблокировок:
1. Пренебрежением проблемой в целом (вдруг пронесет).
2. Обнаружение и устранение (взаимоблокировка происходит, но оперативно ликвидируется).
3. Динамическое избежание тупиков.
4. Предотвращение четырех условий, необходимых для взаимоблокировок.
Пренебрежением проблемой в целом (страусовый алгоритм)
Если вероятность взаимоблокировки очень мала, то ею легче пренебречь, т.к. код исключения может очень усложнить ОС и привести к большим ошибкам. Также многие взаимоблокировки тяжело обнаружить.
Этот алгоритм используется как в UNIX, так и в Windows.
Поэтому (и не только) на серверах часто устанавливают автоматическую перезагрузку (раз в сутки, как правило ночью), если возникнет взаимоблокировка, то после перезагрузки ее не будет.
Обнаружение и устранение взаимоблокировок
Система не пытается предотвратить взаимоблокировку, а пытается обнаружить ее и устранить.
|
|
|
Обнаружение взаимоблокировки при наличии одного ресурса каждого типа
Под одним ресурсом каждого типа, подразумевается один принтер, один сканер и один плоттер и т.д.
Рассмотрим систему из 7-ми процессов и 6-ти ресурсов.
Обнаружение взаимоблокировки при наличии одного ресурса каждого типа
Визуально хорошо видна взаимоблокировка, но нам нужно чтобы ОС сама определяла взаимоблокировку.
Для этого нужен алгоритм.
Рассмотрим один из алгоритмов.
Для каждого узла N в графе выполняется пять шагов.
1. Задаются начальные условия: L-пустой список, все ребра не маркированы.
2. Текущий узел добавляем вконец списка L и проверяем количество появления узла в списке. Если он встречается два раза, значит цикл и взаимоблокировка.
3. Для заданного узла смотрим, выходит ли из него хотя бы одно немаркированное ребро. Если да, то переходим к шагу 4, если нет, то переходим к шагу 5.
4. Выбираем новое немаркированное исходящее ребро и маркируем его. И переходим по нему к новому узлу и возвращаемся к шагу 3.
5. Зашли в тупик. Удаляем последний узел из списка и возвращаемся к предыдущему узлу. Возвращаемся к шагу 3. Если это первоначальный узел, значит, циклов нет, и алгоритм завершается.
|
|
|
Алгоритм обнаружения взаимоблокировок
Для нашего случая тупик обнаруживается в списке L=[B,T,E,V,G,U,D,T]
Дата добавления: 2018-08-06; просмотров: 326; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!