Избегание тупиков. Алгоритм Банкира.

Распределить ресурсы таким образом, чтобы не попасть в тупик.

Алгоритм Банкира.

Условия: считаем, что максимальные требования всех процессов к ресурсам известны до начала их выполнения.

Определение: состояние называется безопасным, если для него имеется последовательность процессов {p₁,p₂,...,p_n}, такая, что для каждого Pi ресурсы, которые потребовал Pi, могут быть предоставлены за счет имеющихся не занятых ресурсов и ресурсов, выделенных всем процессам Pj, где j<i.

 

Перед выделением ресурса проверяем, является ли состояние, в которое мы перейдем после выделения, безопасным. Если новое состояние безопасно, выделяем ресурс. Если нет — ресурс не выделяется, процесс, выполнивший запрос, блокируется.

 

Алгоритм Банкира можно проиллюстрировать на графе PR. При выполнении запроса:

1. Представляем, что мы его удовлетворили.
2. Представляем, что все процессы запросили максимум ресурсов.
3. Проверяем, может ли PR-граф быть полностью редуцирован. Если да, выделяем ресурс, если нет — блокируем процесс, выполнивший запрос.

1. Я→Ч +
2. Ты→Ч +
3. Ты→Л −
4. Я→Л +