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

Рассмотрим систему.

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), то два процесса окажутся в тупике.

Когда можно искать тупики:

− Когда запрашивается очередной ресурс (очень загружает систему)

− Через какой то промежуток времени (в интерактивных системах пользователь это ощутит)

− Когда загрузка процессора слишком велика