Группа процессов находиться в тупике, если каждый процесс из группы ожидает события, которое может вызвать только другой процесс из этой же группы.

Условия тупика

1. Условие взаимного исключения – каждый ресурс в данный момент времени или отдан одному процессу или свободен;

2. Условие удержания и ожидания – процессы, имеющие в своем распоряжении ресурсы, могут запрашивать еще ресурсы;

3. Условие отсутствия принудительной выгрузки ресурса – процесс, который владеет ресурсом должен освободить его сам, принудительно отобрать ресурс нельзя;

4. Условие циклического ожидания – должна существовать круговая последовательность из двух или более процессов, каждый из которых ждет освобождения ресурса, принадлежащего другому процессу из этой последовательности.

R_{1 …} R₆ - ресурсы

процесс 1

R₁ R₄

процесс 2 процесс 3

R₅

R₂ R₃ R₆

Процесс 4

процесс владеет ресурсом ,

запрашивает ресурс, или ждет освобождения

Данная проблема известна с 60 – ых годов, были разработаны различные способы решения этой проблемы. Для обнаружения тупиков разработаны алгоритмы, которые основаны на методах математического моделирования и теории графов.

Рассмотрим математическую модель распределения ресурсов компьютера.

Рассмотрим систему, в которой есть n – ресурсов, причем каждый ресурс имеет номер и m – процессов. В любой момент времени в системе согласно модели определены: