Структуры данных для алгоритма банкира

Пусть в системе имеется n процессов и m типов ресурсов.

Вектор Available длины m содержит информацию о доступных ресурсах. Если Avaliable[j] = k,то в системе в данный момент доступно k единиц ресурса j.

Матрица Max (n * m) отображает максимальные потребности процессов в ресурсах. Если Max [i, j] = k,то процесс i может запросить, самое большее, k единиц ресурса j.

Матрица Allocation (n * m) отображает фактическое выделение системой ресурсов. Если Allocation [i, j] = k,то процессу i в данный момент выделено системой k единиц ресурса j.

Матрица Need (n * m) отображает оставшиеся потребности процессов в ресурсах. Если Need [i, j] = k,то процессу i могут потребоваться еще k единиц ресурса j для завершения работы.

Имеет место следующее соотношение между элементами матриц:

Need [i, j] = Max [i, j] – Allocation [i, j].

Алгоритм проверки состояния системы на безопасность

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

Введем целочисленный вектор Work (длины m) и булевский вектор Finish (длины n). Вектор Work отображает пробные выделения ресурсов. Вектор Finish представляет информацию о завершаемости процессов при данном состоянии системы.

Алгоритм безопасности.

Шаг 1. Инициализация.

Work = Available

Finish [i] = false для i = 1, …, n.

Здесь и в дальнейшем все присваивания и сравнения, в которых участвуют векторы или матрицы, выполняются поэлементно.

Шаг 2. Находим i, такое, что:

Finish [i] = false

Need [i] <= Work

Если такого i нет, переходим к шагу 4.

Шаг 3.

Work = Work + Allocation [i]

Finish [i] = true

Переход к шагу 2.

Шаг 4. Если Finish[i] = true для всех i = 1, …, n, то система в безопасном состоянии.

Необходимые пояснения к алгоритму:

· Алгоритм строит безопасную последовательность номеров процессов i, если она существует. На каждом шаге, после обнаружения очередного элемента последовательности, алгоритм моделирует освобождение i - м процессом ресурсов после его завершения.

· На шаге 1 присваивание векторов выполняется поэлементно.

· На шаге 2, Need – матрица потребностей (n * m); Need[i] - строка матрицы, представляющая вектор потребностей (длины m) процесса i. Сравнение выполняется поэлементно, и его результат считается истинным, если соотношение выполнено для всех элементов векторов. Проверяемое условие означает, что потребности процесса i с найденным номером могут быть удовлетворены немедленно, и процесс может получить их и завершиться.

· На шаге 3, Allocation [i] – строка матрицы Allocation, обозначающая текущие ресурсы, выделенные процессу i. С помощью вектора Work моделируется освобождение ресурсов i – м процессом, после чего процессу присваивается признак завершаемости.

Формальное доказательство корректности алгоритма и оценку его сложности предоставляем студенту.

Алгоритм запроса ресурсов для процесса Pi – основная часть алгоритма банкира

Для основного алгоритма введем вектор Requesti (длины m) – вектор запросов для процесса P_i. Если Requesti [j] = k,то процесс P_i запрашивает k экземпляров ресурса R_j.

Шаг 1. Если Requesti <= Need[i], перейти к шагу 2.

Иначе – сгенерировать исключительную ситуацию

(процесс превысил свои максимальные потребности).

Шаг 2. Если Requesti <= Available, перейти к шагу 3.

Иначе процесс должен ждать, так как ресурс недоступен.

Шаг 3. Спланировать выделение ресурса процессу P_i, модифицируя состояние системы следующим образом:

Available = Available - Requesti

Allocation = Allocation + Requesti

Need [i] = Need [i] - Requesti

Вызвать алгоритм проверки безопасности полученного состояния.

Если состояние безопасно, выделить ресурс процессу P_i. Выход.

Если состояние небезопасно, восстановить предыдущее состояние;

процесс должен ждать.

Пример использования алгоритма банкира

Пусть имеется 5 процессов – P₀, …, P₄, и 3 типа ресурсов – ресурс A (10 экземпляров), ресурс B (5 экземпляров) и ресурс C (7 экземпляров). Пусть состояние системы в момент T0 следующее:

	Allocation	Max	Available
	A	B	C	A	B	C	A	B	C
P0
P1
P2
P3
P4

Вычислим матрицу потребностей Need = Max – Allocation:

	Need
	A	B	C
P0
P1
P2
P3
P4

Нетрудно видеть, что система – в безопасном состоянии. Последовательность процессов <P₁, P₃, P₄, P₂, P₀> удовлетворяет критерию безопасности. Проверку предоставляем студенту.

В продолжение примера, предположим, что процесс P₁ сделал запрос (1 0 2). Проверяем, что Request <= Available: <(1 0 2) <= (3 3 2) = true.

Удовлетворяем запрос.

Состояние системы принимает вид:

	Allocation	Max	Available
	A	B	C	A	B	C	A	B	C
P0
P1
P2
P3
P4

Исполнение алгоритма безопасности показывает, что последовательность процессов <P₁, P₃, P₄, P₀, P₂> удовлетворяет критерию безопасности. Предоставляем студенту проверку корректности данных преобразований и предлагаем ответить на следующие дополнительные вопросы:

· может ли быть удовлетворен запрос (3 3 0) для процесса P₄?

· может ли быть удовлетворен запрос (0 2 0) для процесса P₀?

Методы обнаружения тупиков

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

Граф wait-for

В дополнение к графу распределения ресурсов, введем более простой по струтуре граф wait-for: вершины в нем соответствуют процессам, и дуга проводится из вершины P_i в вершину P_j, если процесс P_i ожидает процесса P_j. Если каждый тип ресурса в системе существует в единственном экземпляре, то очевидно, что цикл в данном графе означает тупик. Система для обнаружения тупиков должна периодически проверять отсутствие циклов в графе wait-for. Как известно, алгоритм обнаружения цикла в графе требует O(n²) операций, где n – число вершин в графе.

На рис.3 приведен пример графа распределения ресурсов и соответствующего ему графа wait-for для системы с тупиком.

Рис. 3. Граф распределения ресурсов и граф wait-for.