Тупики и близкая к ним проблема бесконечного откладывания — важные факторы, которые должны учитывать разработчики ОС.
Тупик (deadlock) — это такая ситуация в мультипрограммной системе, когда процесс ожидает некоторого события, которое никогда не произойдет. Системная тупиковая ситуация, или “зависание” системы — это ситуация, когда один или более процессов оказываются в состоянии тупика.
При рассмотрении проблемы тупиков все ресурсы разделяются на два класса: повторно используемые (или системные) ресурсы (типа RR-reusable resource и SR-system resource) и потребляемые (или расходуемые) ресурсы (типа CR-consumable resource).
Повторно используемый ресурс (SR) есть конечное множество идентичных единиц со следующими свойствами:
• число единиц ресурса постоянно;
• каждая единица ресурса или доступна, или распределена одному и только одному процессу (разделение либо отсутствует, либо не принимается во внимание, т.к. не оказывает влияния на распределение ресурсов и на возникновение тупиковой ситуации);
• процесс может освободить единицу ресурса, только если он ранее получил эту единицу, т.е. никакой процесс не может оказывать какое-либо влияние ни на один ресурс, если он ему не принадлежит.
Данное определение выделяет существенные для изучения тупиков свойства системных ресурсов, к которым относятся компоненты аппаратуры: основная память, внешняя память, периферийные устройства, процессы,- а также программное и информационное обеспечение: файлы данных, таблицы, разрешение войти в критическую секцию.

Расходуемый ресурс (CR) отличается от ресурса типа SR следующим:
• число доступных единиц некоторого ресурса типа CR изменяется по мере того, как приобретаются и освобождаются отдельные их элементы выполняющимися процессами, и такое число единиц ресурса является неограниченным; процесс-производитель увеличивает число единиц ресурса, освобождая одну или более единиц, которые он создал;
• процесс-потребитель уменьшает число единиц ресурса, сначала запрашивая и затем приобретая одну или более единиц. Единицы ресурса, которые приобретены не возвращаются ресурсу, а потребляются. Эти свойства потребляемых ресурсов присущи многим синхронизирующим сигналам, сообщениям и данным, порождаемым как аппаратурой, тай и программным обеспечением, и могут рассматриваться как ресурсы типа CR при изучении тупиков. В их число входят: прерывания от таймера и устройств ввода-вывода; сигналя синхронизации процессов; сообщения, содержащие запросы на различные виды обслуживания или данные.

Для исследования параллельных процессов и тупиков было разработано несколько моделей. Одной из них является модель повторно используемых ресурсов Холта. Согласно этой модели система представляется как множество процессов и множество ресурсов, причем каждый из ресурсов состоит из фиксированного числа единиц. Любой процесс может изменять состояние системы с помощью запроса, получения или освобождения единицы ресурса.
В графической форме процессы представляются квадратами, ресурсы – кружками, каждый кружок содержит некоторое количество точек – единиц этого ресурса. Дуга, указывающая из процесса на ресурс, означает запрос одной единицы ресурса. Дуга, указывающая из ресурса на процесс, представляет выделение ресурса процессу. Число дуг, исходящих из ресурса к различным процессам, не может превышать общего числа единиц ресурса. Такая модель называется графом повторно используемых ресурсов.

Рассмотрим пример системы из двух ресурсов типа SR
Пусть процесс P1 запрашивает две единицы ресурса R1 и одну единицу ресурса R2. процессу P2 принадлежат две единицы ресурса R1 и ему нужна единица ресурса R2. Предположим, что P1 получил бы единицу R2. если принято правило, по которому процесс должен получить все запрошенные им ресурсы, прежде чем освободить хотя бы один из них, то удовлетворение запроса P1 приведет к тупиковой ситуации:
P1 не сможет продолжиться до тех пор, пока P2 не освободит единицу ресурса R1, а процесс P2 не сможет продолжиться до тех пор, пока P1 не освободит единицу R2.

Причиной данного тупика являются неупорядоченные попытки процессов войти в критический интервал, связанный с выделением соответствующей единицы ресурса.

R1 P2

P1 R2

Рисунок — Пример модели Холта для системы из двух ресурсов

Рассмотрим пример тупика при распределении ресурсов.
В ОС тупики в большинстве случаев возникают при конкуренции процессов за выделение ресурсов последовательного доступа, которые в каждый момент времени отводятся только одному пользователю.
На графе распределения ресурсов показана тупиковая ситуация, в которой каждый процесс удерживает ресурс, запрашиваемый другим процессом, причем ни один из процессов не хочет освободить принадлежащий ему ресурс.

Ресурс 1 выделен Процесс_Y запрашивает
процессу_Х Ресурс 1 ресурс 1

Процесс_Х Процесс_Y

Процесс_Х запрашивает Ресурс 2 выделен
ресурс 2 Ресурс 2 процессу_ Y

Рис. 5 Граф распределения ресурсов

Такое состояние кругового ожидания характерно для систем в тупиковом состоянии.
Системы спулинга часто оказываются подвержены тупикам.

Близкая к проблеме возникновения тупиков — проблема бесконечного откладывания, когда предоставление запрашиваемого ресурса некоторому процессу будет откладываться на неопределенный срок, в то время, как система будет уделять внимание другим процессам. Напомним, что при разработке ОС необходимо предусматривать справедливое, а также эффективное управление процессами, находящимися в состоянии ожидания. В некоторых системах бесконечное откладывание предотвращается благодаря тому, что приоритет процесса увеличивается по мере того, как он ожидает выделения нужного ему ресурса. Это называется старением процесса.

Необходимые условия возникновения тупиков

Необходимые условия наличия тупика могут быть сформулированы следующим образом .
• Условие взаимоисключения — когда процессы требуют предоставления им права монопольного управления ресурсами, которые им выделяются.
• Условие ожидания ресурсов — когда процессы удерживают за собой ресурсы, уже выделенные им, ожидая в то же время выделения дополнительных ресурсов.
• Условие неперераспределяемости — когда ресурсы нельзя отобрать у процессов, удерживающих их, пока эти ресурсы не будут использованы для завершения работы.
• Условие кругового ожидания — когда существует кольцевая цепь процессов, в которой каждый процесс удерживает за собой один или более ресурсов, требующихся следующему процессу.
Борьба с возникновением тупиков может вестись по четырем основным направлением: предотвращение тупиков; обход тупиков; обнаружение тупиков; восстановление после тупиков.