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

Тупики возникают как в аппаратных, так и в программных ресурсах.

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

Рис. 12. Пример тупиковой ситуации.

 

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

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

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

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

1. Условие взаимоисключения (Mutual exclusion). Каждый ресурс выделен в точности одному процессу или доступен. Процессы требуют предоставления им монопольного управления ресурсами, которые им выделяются.

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

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

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

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

1. Игнорировать проблему в целом

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

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

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

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

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

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

1. Можно избежать взаимоблокировки, если тщательно распределять ресурсы, придерживаясь определенных правил. Алгоритм банкира. Это алгоритм базируется на безопасных и надежных состояниях.

Безопасное состояние – это такое состояние, для которых имеется хотя бы одна последовательность событий, которая не приведет к взаимоблокировке. Модель основана на действиях банкира, имея деньги, выдает кредиты.

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

2. Можно избежать взаимоблокировки, если нарушить условия возникновения тупиков