Обнаружение взаимоблокировки при наличии нескольких ресурсов каждого типа
Рассмотрим систему.
m - число классов ресурсов (например: принтеры это один класс)
n - количество процессов
P(n) - процессы
E- вектор существующих ресурсов
E(i)- количество ресурсов класса i
A- вектор доступных (свободных) ресурсов
A(i) - количество доступных ресурсов класса i
С- матрица текущего распределения (какому процессу, какие ресурсы принадлежат)
R- матрица запросов (какой процесс, какой ресурс запросил)
C(ij) - количество экземпляров ресурса j, которое занимает процесс i.
Общее количество ресурсов равно сумме занятых и свободных ресурсов
Рассмотрим алгоритм поиска тупиков.
Если остаются не маркированные процессы, значит есть тупик.
Рассмотрим работу алгоритма на реальном примере.
Используем алгоритм:
1. Третий процесс может получить желаемые ресурсы, т.к. R (2 1 0 0) = A (2 1 0 0)
2. Третий процесс освобождает ресурсы. Прибавляем их к A. А = (2 1 0 0) + (0 1 2 0) =(2 2 2 0). Маркируем процесс.
3. Может выполнятся процесс 2. По окончании А=(4 2 2 1).
4. Теперь может работать первый процесс.
Тупиков не обнаружено.
Если рассмотреть пример, когда второму процессу требуются ресурсы (1 0 3 0), то два процесса окажутся в тупике.
Когда можно искать тупики:
− Когда запрашивается очередной ресурс (очень загружает систему)
− Через какой то промежуток времени (в интерактивных системах пользователь это ощутит)
− Когда загрузка процессора слишком велика