Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
SRS_IPOVS_OS.doc
Скачиваний:
2
Добавлен:
01.07.2025
Размер:
1 Мб
Скачать
☆

7.3. Обнаружение взаимоблокировок Обнаружение взаимоблокировок при наличии одного ресурса каждого типа

Необходимым и достаточным условием взаимоблокировки в такой ситуации является наличие цикла в графе ресурсов.

Обнаружение взаимоблокировок при наличии нескольких ресурсов каждого типа

Пусть n – число процессов P1, P2, …, Pn; m – число классов ресурсов R1, R2, …, Rm; Ei – количество единиц ресурса класса i; E – вектор существующих ресурсов, содержащий общее количество имеющихся в системе единиц каждого ресурса; A – вектор доступных ресурсов, элемент этого вектора Ai – количество единиц ресурса Ri, доступных в данный момент; C – матрица текущего распределения, элемент этой матрицы Cij – количество единиц ресурса Rj, используемое процессом Ri; R – матрица запросов, элемент этой матрицы Rij – количество единиц ресурса Rj, которое запрашивает процесс Pi.

Эти четыре структуры показаны на рис. 7.3.

Будем считать, что для двух векторов A и B: AB тогда и только тогда, когда AiBi, 1im.

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

  1. Ищем немаркированный процесс Pi, для которого i-ая строка матрицы A.

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

  3. Если таких процессов не существует, работа алгоритма заканчивается.

На первом шаге алгоритм ищет процесс, который может доработать до конца, т.е. все требуемые для него ресурсы должны быть доступны. Возвращаем занятые процессом ресурсы в общий фонд ресурсов. Процесс маркируем как завершенный. Если окажется, что все процессы могут работать, тогда ни один из них в данный момент не заблокирован.

Для иллюстрации работы алгоритма рассмотрим рис. 7.4. Здесь есть три процесса и четыре класса ресурсов, например, накопители на магнитной ленте (НМЛ), плоттеры, сканеры и устройство для чтения компакт-дисков. Процесс 1 использует один сканер. Процесс 2 занял два НМЛ и устройство для чтения компакт-дисков. Процесс 3 занимает плоттер и два сканера. Каждый процесс нуждается в дополнительном устройстве, как показывает матрица R.

Работая с алгоритмом обнаружения взаимоблокировок, мы ищем процесс, чей запрос ресурсов может быть удовлетворен. Требования первого процесса нельзя выполнить, потому что в системе нет доступного устройство для чтения компакт-дисков. Запросы второго процесса также нельзя удовлетворить, т.к. нет свободных сканеров. Но третий процесс может получить все желаемое, следовательно, он работает, завершается и возвращает все свои ресурсы, давая

A = (2 2 2 0 ).

С этого момента может выполняться процесс 2, по окончании возвращая свои ресурсы в систему. Мы получим:

A = (4 2 2 1 ).

Теперь может работать оставшийся процесс. В этой системе не возникает взаимоблокировки.

Теперь немного изменим вариант, изображенный на рис. 7.3. Пусть процесс 3, кроме двух НМЛ и плоттера, нуждается также и в устройстве для чтения компакт-дисков. Тогда ни один из запросов не может быть удовлетворен, значит, вся система находится в тупике.

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]