Тема 7. Тупики: условия возникновения тупиков, предотвращения тупиков

Первая проблема, которую мы рассмотрели, возникающая для асинхронных параллельных процессов, работающих с общим ресурсом - это проблема синхронизации процессов.

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

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

1.Взаимоисключение, когда процессы требуют монопольного предоставления ресурса.

2.Ожидание дополнительного ресурса, когда процессы удерживают ресурсы и требуют дополнительных ресурсов.

3.Неперераспределяемости ресурсов, когда ресурсы нельзя отобрать у процессов до завершения их работы.

4.Кругового ожидания, когда существует кольцо процессов, удерживающих ресурсы друг друга.

Для решения проблемы тупиков должны решаться следующие задачи:

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

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

• Условие ожидания дополнительных ресурсов можно нарушить, если потребовать, чтобы процессы запрашивали сразу все ресурсы. (Недостаток - снижение уровня мультипрограммирования и нерациональное использование ресурсов).

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

• Условие кругового ожидания можно предотвратить, если процессы запрашивают ресурсы в заранее определенном порядке, то есть ресурсы имеют уникальные упорядоченные номера, которые распределяются в соответствии с некоторым планом (планирование распределения ресурсов).

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

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

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

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

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

В настоящее время проблема тупика является критическим фактором по следующим причинам:

• широкое распространение получают мультипроцессорные и параллельные вычисления;

• в системах выполняется преимущественно динамическое распределение ресурсов;

• тенденция рассмотрения данных как ресурса приводит к возрастанию числа управляемых ресурсов.