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

Когда в системе существует несколько экземпляров каких-нибудь ресурсов, для обнаружения взаимоблокировки необходим другой подход. Сейчас будет представлен алгоритм, основанный на использовании матриц и предназначенный для обнаружения взаимоблокировки при работе n процессов, от P1 до Pn.
Пусть m — это число классов ресурсов, Е1 — количество ресурсов класса 1, Е2 — количество ресурсов класса 2, а в общем

Ei — количество ресурсов класса I (где 1 < I < m). E — это вектор существующих ресурсов. Он передает общее количество имеющихся в наличии экземпляров каждого ресурса. Например, если класс 1 представляет собой накопители на магнитных лентах, то E1 = 2 означает, что в системе есть два таких накопителя.

В любой момент времени какие-то ресурсы могут быть выделены и недоступны. Пусть A будет вектором доступных ресурсов, где Ai дает количество экземпляров ресурса ¿, доступных на данный момент (то есть не выделенных). Если оба накопителя на магнитной ленте уже выделены, A1 будет равно 0.

Теперь нам нужны два массива: C — матрица текущего распределения и R — матрица

запросов. ¿-я строка в матрице C говорит о том, сколько экземпляров каждого класса ресурсов в данный момент удерживает процесс Р{. Таким образом, С — это количество экземпляров ресурса], которое удерживается процессом ¿. По аналогии с этим Rij — это количество экземпляров ресурса], которое хочет получить процесс Р. Все четыре структуры данных показаны на рис. 6.4.

Рис. 6.4. Четыре структуры данных, необходимые для работы алгоритма обнаружения взаимоблокировок


Для этих четырех структур данных сохраняется одно важное соотношение. А именно — каждый ресурс является либо выделенным, либо доступным. Это наблюдение означает, что

Иными словами, если сложить все уже выделенные экземпляры ресурса] и к ним прибавить все еще доступные экземпляры, в результате получится количество существующих экземпляров ресурса этого класса.

Алгоритм обнаружения взаимоблокировок основан на сравнении векторов. Определим, что для двух векторов А и В сооотношение А < В означает, что каждый элемент вектора А меньше или равен соответствующему элементу вектора В. Математически это можно записать так: А < В тогда и только тогда, когда А{ < В{ для 1 < I < т.

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

Теперь алгоритм обнаружения взаимного исключения можно изложить в следующей последовательности:

1. Поиск непомеченного процесса, Рг, для которого г-я строка матрицы Я меньше или равна А.

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

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

По окончании работы алгоритма все непомеченные процессы, если таковые имеются, считаются участвующими во взаимоблокировке.

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

Рассмотрим пример работы алгоритма обнаружения взаимоблокировок, показанный на рис. 6.5. Здесь изображены три процесса и четыре класса ресурсов, которые мы произвольно обозначили как накопители на магнитной ленте, плоттеры, сканер и привод Blu- гау-дисков. Процесс 1 удерживает один сканер. Процесс 2 удерживает два ленточных привода и один привод Blu-ray-дисков. Процесс 3 удерживает плоттер и два сканера. Каждый процесс нуждается в дополнительных ресурсах, что отображено в матрице Я.

Рис. 6.5. Пример, демонстрирующий работу алгоритма обнаружения взаимоблокировок


Во время работы алгоритма обнаружения взаимоблокировок осуществляется поиск процесса, чей запрос на ресурс может быть удовлетворен. Требования первого процесса удовлетворить невозможно из-за отсутствия доступного привода Blu-ray-дисков. Запрос второго процесса также нельзя удовлетворить, так как нет свободного сканера. К счастью, можно удовлетворить запрос третьего процесса, поэтому третий процесс запускается и в конечном итоге высвобождает все удерживавшиеся им ресурсы, в результате чего получается:

А = (2 2 2 0)

Теперь может быть запущен процесс 2, высвобождающий удерживающиеся им ресурсы, в результате чего получается:

А = (4 2 2 1)

и может быть запущен оставшийся процесс. При этом взаимоблокировки в системе не возникает.

Рассмотрим незначительное изменение ситуации, показанной на рис. 6.5. Предположим, что процесс 3 нуждается в приводе Blu-ray-дисков, а также в двух ленточных накопителях и плоттере. Ни один из этих запросов не может быть удовлетворен, поэтому вся система в конечном итоге войдет в состояние взаимоблокировки. Даже если мы дадим процессу 3 два его ленточных накопителя и один плоттер, система войдет в состояние взаимоблокировки при запросе привода Blu-ray-дисков.

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

6.4.3.

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

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

  1. Этичное использование типа
  2. Раздел III Использование достижений криминалистической психологии при собирании, оценке, использовании личностной информации
  3. 8.2. Государственная политика в области формирования и использования информационных ресурсов
  4. 8.1. Конституционная основа формирования и использования информационных ресурсов
  5. Прежде чем вы решите заняться поднятием своего сознания, вы, возможно, зададите себе несколько вопросов, типа нижеследующих:
  6. Часть третья Использование кодов для определения типа характера
  7. Часть третья Использование кодов для определения типа характера
  8. Назначение наказания при одновременном осуждении лица за несколько преступлений (ч. 2 иЗ ст. 69 УК РФ)
  9. 2. Назначение наказания при разновременном осуждении лица за несколько преступлений (ч. 5 спи 69 УК РФ)
  10. Статья 9. Применение Гражданского кодекса Украины к урегулированию отношений в сферах хозяйствования, использование естественных ресурсов, охраны окружающей среды, а также к трудовым и семейным отношениям
  11. 4.3.2. Информационные правоотношения, возникающие при производстве, передаче и распространении информации, информационных ресурсов, информационных продуктов, информационных услуг
  12. 4.3.1. Информационные правоотношения, возникающие при осуществлении поиска, получения и потребления информации, информационных ресурсов, информационных продуктов, информационных услуг
  13. 2. Система договоров при расчетах с использованием банковских карт
  14. Статья 540. Выполнение обязательства, в котором принимают участие несколько кредиторов или несколько должников
  15. Раздел I Использование достижений криминалистической психологии при выявлении и раскрытии серийных преступлений
  16. Использование экстраординарных психофизиологических («экстрасенсивных») способностей человека при раскрытии преступлений.
  17. Раздел II Использование достижений нетрадиционных отраслей криминалистической психологии при выявлении и раскрытии преступлений