Пусть в системе имеется 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 — м процессом, после этого процессу присваивается признак завершенности.
