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

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

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

 

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

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

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

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