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

Начнем с самого простого случая, когда используется только один ресурс каждого типа. У системы может быть один сканер, один пишущий привод Blu-ray-дисков, один плоттер и один накопитель на магнитной ленте, но только по одному экземпляру каждого класса ресурсов.
Иными словами, мы временно исключаем системы, имеющие два принтера. Они будут рассмотрены позже с использованием другого метода.

Для такой системы можно построить ресурсный граф (рис. 6.1). Если этот граф содержит один и более циклов, значит, мы имеем дело с взаимоблокировкой. Любой процесс, являющийся частью цикла, заблокирован намертво. Если циклов нет, значит, система не находится в состоянии взаимоблокировки.

В качестве примера более сложной системы по сравнению с ранее рассмотренными, возьмем систему с семью процессами от А до С и шестью ресурсами от Я до V. Каждый ресурс находится в состоянии текущей занятости, и на каждый ресурс в данный момент поступил запрос:

1. Процесс А удерживает Я и хочет получить 5.

2. Процесс В не удерживает никаких ресурсов, но хочет получить Т.

3. Процесс С не удерживает никаких ресурсов, но хочет получить 5.

4. Процесс Б удерживает и и хочет получить 5 и Т.

5. Процесс Е удерживает Т и хочет получить V.

6. Процесс Я удерживает Vи хочет получить 5.

7. Процесс С удерживает Vи хочет получить и.

Возникает следующий вопрос: «Находится ли эта система в состоянии взаимоблокировки, и если находится, то какие процессы вовлечены в это состояние?»

Чтобы ответить на этот вопрос, можно построить граф ресурсов (рис. 6.3, а). Этот граф содержит один цикл, который можно обнаружить визуально. Этот цикл показан на рис. 6.3, б. Из цикла видно, что процессы Б, Е и С вовлечены во взаимоблокировку. Процессы А, С и Е не находятся в состоянии взаимоблокировки, поскольку ресурс 5 может быть выделен любому из них, который затем закончит свою работу и вернет ресурс. Затем оставшиеся два процесса смогут взять его по очереди и также завершить свою работу. (Заметьте, чтобы сделать этот пример немного интереснее, мы позволили процессам, а именно процессу Б, запрашивать одновременно два ресурса.)

Рис. 6.3. а — граф ресурсов; б — извлеченный из него цикл


Хотя визуально выделить взаимоблокировку из простого графа относительно нетрудно, для использования в настоящих системах нужен формальный алгоритм обнаружения взаимоблокировок. Известно множество алгоритмов для обнаружения циклов в направленных графах. Далее будет приведен простой алгоритм, проверяющий граф и прекращающий свою работу либо при обнаружении цикла, либо при обнаружении отсутствия циклов. В нем используется одна динамическая структура данных, Ь, представляющая собой список узлов, а также список ребер. В процессе работы алгоритма ребра будут помечаться для обозначения того, что они уже были проверены, чтобы предотвратить повторные проверки.

Действие алгоритма основано на выполнении следующих шагов:

1. Для каждого узла N имеющегося в графе, выполняются следующие пять шагов, использующих узел N в качестве начального.

2. Инициализируется (очищается) список Ь, а со всех ребер снимаются пометки.

3.

Текущий узел добавляется к концу списка Ь, и проводится проверка, не появится ли этот узел в списке Ь дважды. Если это произойдет, значит, граф содержит цикл (отображенный в списке Ь), и алгоритм прекращает работу.

4. Для заданного узла определяется, нет ли каких-нибудь отходящих от него непомеченных ребер. Если такие ребра есть, осуществляется переход к шагу 5, если их нет, осуществляется переход к шагу 6.

5. Произвольно выбирается и помечается непомеченное отходящее от узла ребро. Затем по нему осуществляется переход к новому текущему узлу, и алгоритм возвращается к шагу 3.

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

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

Чтобы увидеть на практике работу этого алгоритма, воспользуемся графом, изображенным на рис. 6.3, а. Порядок обработки узлов произвольный, поэтому будем исследовать их слева направо и сверху вниз, выбрав при первом запуске алгоритма начальный узел R, затем последовательно выбирая узлы A, B, C, S, D, T, E, Fи т. д. Если мы обнаружим цикл, алгоритм прекратит свою работу.

Начинаем с узла R и инициализируем L как пустой список. Затем добавляем узел R в список, переходим к единственно возможному узлу A и также добавляем его к списку L, получая L = [R, А]. Из узла A следуем к узлу S, получая L = [R, A, S]. Узел S не имеет отходящих от него ребер, следовательно, это тупик, который заставляет нас вернуться к узлу A. Так как у узла A также нет немаркированных отходящих от него ребер, мы возвращаемся к узлу R, завершая таким образом его исследование.

Теперь перезапускаем алгоритм, начиная его работу с узла A и предварительно вернув список L в исходное состояние. Этот поиск также быстро остановится, поэтому начнем снова с узла B. Из узла B проследуем по отходящим ребрам до тех пор, пока не доберемся до узла D; к этому моменту список будет иметь следующий вид: L = [B, T, E, V, G, U, D]. Теперь нужно сделать произвольный выбор. Если выбрать узел S, мы попадаем в тупик и возвращаемся к узлу D. Во второй раз выбираем узел T и обновляем список L до вида [B, T, E, V, G, U, D, T], где обнаруживаем цикл и останавливаем работу алгоритма.

Этот алгоритм еще далек от оптимального. Более удачный алгоритм показан в работе Эвена (Even, 1979). Тем не менее приведенный пример доказывает само существование алгоритма для обнаружения взаимоблокировки.

6.4.2.

<< | >>
Источник: Э. ТАНЕНБАУМ Х. БОС. СОВРЕМЕННЫЕ ОПЕРАЦИОННЫЕ СИСТЕМ Ы 4-е ИЗДАНИЕ. 2015

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

  1. Этичное использование типа
  2. Раздел III Использование достижений криминалистической психологии при собирании, оценке, использовании личностной информации
  3. 8.2. Государственная политика в области формирования и использования информационных ресурсов
  4. 8.1. Конституционная основа формирования и использования информационных ресурсов
  5. Часть третья Использование кодов для определения типа характера
  6. Часть третья Использование кодов для определения типа характера
  7. Статья 9. Применение Гражданского кодекса Украины к урегулированию отношений в сферах хозяйствования, использование естественных ресурсов, охраны окружающей среды, а также к трудовым и семейным отношениям
  8. 4.3.2. Информационные правоотношения, возникающие при производстве, передаче и распространении информации, информационных ресурсов, информационных продуктов, информационных услуг
  9. 4.3.1. Информационные правоотношения, возникающие при осуществлении поиска, получения и потребления информации, информационных ресурсов, информационных продуктов, информационных услуг
  10. 2. Система договоров при расчетах с использованием банковских карт