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

Когда в системе существует несколько экземпляров каких-нибудь ресурсов, для об­наружения взаимоблокировки необходим другой подход. Далее будет представлен алгоритм, основанный на использовании матриц и предназначенный для обнару­жения взаимоблокировки при работе п процессов, от Р₁ до Р_п. Пусть т — это число классов ресурсов, Е_i — количество ресурсов класса i (где 1 < i < т). Е — это вектор существующих ресурсов. Он передает общее количество имеющихся в наличии эк­земпляров каждого ресурса.

В любой момент времени какие-то ресурсы могут быть выделены и недоступны. Пусть А будет вектором доступных ресурсов,где А_i дает количество экземпляров ресурса i, доступных на данный момент (то есть не выделенных).

Теперь нам нужны два массива: С — матрица текущего распределения и R — ма­трица запросов,i-я строка в матрице С говорит о том, сколько экземпляров каждого класса ресурсов в данный момент удерживает процесс Р_i. Таким образом, С_ij— это количество экземпляров ресурса j, которое удерживается процессом i. По аналогии с этим, Rij — это количество экземпляров ресурса j, которое хочет получить процесс Р_i. Все четыре структуры данных показаны на рис/

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

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

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

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

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

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

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

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

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

взаимоблокировке. Если часть процессов никогда не сможет доработать до конца, значит, они находятся в состоянии взаимоблокировки. Хотя алгоритм не является детерминированным (поскольку он может запускать процессы в любом возможном порядке), результат всегда одинаков/