Графы распределения ресурсов

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

На рис. 6.3 показаны отношения, которые могут быть представлены на графе запросов и распределения ресурсов. На рис. б. З(а) показано/что процесс Р1 запрашивает ресурс типа R1. Стрелка от квадрата Р1 доходит только до большого кружка — это говорит о том, что в текущий момент запрос от процесса на выделение данного ресурса находится в стадии рассмотрения.


Рис. 6.3 Граф запросов и распределения ресурсов: .а) процесс Р1 запрашивает ресурс типа R1;

б) ресурс типа R2 выделен процессу Р2;

в) процесс РЗ запрашивает ресурс R3, который выделен процессу Р4;

г) процессу Р5 выделен ресурс R5, необходимый процессу Р6, которому выделен ресурс R4, необходимый процессу Р5 («круговое ожидание»).

На рис. 6.3(г) показана небольшая система в тупиковой ситуации, когда процесс Р5 запрашивает ресурс R4, который выделен процессу Р6, который запрашивает ресурс R5, который выделен процессу Р5, который в свою очередь запрашивает ресурс R4 — это пример «кругового ожидания», типичного для системы в состоянии тупика.

Редукция графа

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

Рассмотрим вариант с матричным представлением.(Это Антоша просил разобрать самостоятельно.)

Поскольку граф двудольный, он

представляется двумя матрицами размером n´m.

Одна матрица — матрица распределения , в которой элемент dij отражает

количество единиц R j ресурса, выделенного процессу P i, то есть , где

— это дуга между вершинами Rj и Pi, ведущая из Rj в Pi.

Вторая матрица — матрица запросов , где .

В случае использования связанных списков для отображения той же структуры можно

построить две группы списков. Ресурсы, выделенные некоторому процессу Pi, связаны

с Pi указателями:

Здесь R j — вершина, представляющая ресурс, d j — вес дуги, то есть .

Подобным образом и ресурсы, запрошенные процессом P i, связаны вместе.

Аналогичные списки создаются и для ресурсов (списки распределенных и запро-

шенных ресурсов):

Здесь .

Для обоих представлений удобно также иметь одномерный массив доступных единиц

ресурсов , где r i обозначает число доступных (нераспределенных единиц)

ресурса R i, то есть .

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

списка (или матрицы) запросов, причем, где возможно, производятся сокращения дуг

графа до тех пор, пока нельзя будет сделать более ни одного сокращения. При этом самая

плохая ситуация возникает, когда процессы упорядочены в некоторой

последовательности а единственно возможным порядком сокращений

является обратная последовательность, то есть, а также в случае, когда

процесс запрашивает все m ресурсов. Тогда число проверок процессов равно:

n+(n-1)+...+1=n×(n+1)/2.

Таким образом, время выполнения такого алгоритма в наихудшем случае

пропорционально m´n2 , поскольку каждая проверка требует испытания m ресурсов.