Условия возникновения тупиков

Условия возникновения тупиков были сформулированы Коффманом, Элфиком и Шошани в 1970 г.

1. Условие взаимоисключения (Mutual exclusion). Одновременно использовать ресурс может только один процесс.

2. Условие ожидания ресурсов (Hold and wait). Процессы удерживают ресурсы, уже выделенные им, и могут запрашивать другие ресурсы.

3. Условие неперераспределяемости (No preemtion). Ресурс, выделенный ранее, не может быть принудительно забран у процесса. Освобождены они могут быть только процессом, который их удерживает.

4. Условие кругового ожидания (Circular wait). Существует кольцевая цепь процессов, в которой каждый процесс ждет доступа к ресурсу, удерживаемому другим процессом цепи.

Для образования тупика необходимым и достаточным является выполнение всех четырех условий.

Основные направления борьбы с тупиками

· Игнорирование проблемы в целом

· Предотвращение тупиков

· Обнаружение тупиков

· Восстановление после тупиков

Пример тупика. Пусть двум процессам, выполняющимся в режиме мультипрограммирования, для выполнения их работы нужно два ресурса, например, принтер и диск. Пусть после того, как процесс А занял принтер (установил блокирующую переменную), он был прерван. Управление получил процесс В, который сначала занял диск, но при выполнении следующей команды был заблокирован, так как принтер оказался уже занятым процессом А. Управление снова получил процесс А, который в соответствии со своей программой сделал попытку занять диск и был заблокирован: диск уже распределен процессу В. В таком положении процессы А и В могут находиться сколь угодно долго.

Игнорирование проблемы тупиков

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

Способы предотвращения тупиков

Цель предотвращения тупиков – обеспечить условия, исключающие возможность возникновения тупиковых ситуаций. Большинство методов связано с предотвращением одного из условий возникновения взаимоблокировки. Система, предоставляя ресурс в распоряжение процесса, должна принять решение, безопасно это или нет. Алгоритм банкира который базируется на безопасных или надежных состояниях (safe state). Безопасное состояние – это такое состояние, для которого имеется по крайней мере одна последовательность событий, которая не приведет к взаимоблокировке.

Суть алгоритма состоит в следующем.

· Предположим, что у системы в наличии n устройств, например лент.

· ОС принимает запрос от пользовательского процесса, если его максимальная потребность не превышает n.

· Пользователь гарантирует, что если ОС в состоянии удовлетворить его запрос, то все устройства будут возвращены системе в течение конечного времени.

· Текущее состояние системы называется надежным, если ОС может обеспечить всем процессам их выполнение в течение конечного времени.

· В соответствии с алгоритмом банкира выделение устройств возможно, только если состояние системы остается надежным.

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

· Число пользователей и число ресурсов фиксировано.

· Число работающих пользователей должно оставаться постоянным.

· Алгоритм требует, чтобы клиенты гарантированно возвращали ресурсы.

· Должны быть заранее указаны максимальные требования процессов к ресурсам. Чаще всего данная информация отсутствует.