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

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

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

· ожидания, при котором процесс, запрашивающий ресурс, ждет до тех пор, пока запрос не будет удовлетворен, удерживая ранее полученные ресурсы;

· отсутствия перераспределения ресурсов – выделенные ресурсы нельзя отобрать у процесса;

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

Методы борьбы с тупиками

Имеются 3 метода:

· предотвращение тупика (самый дорогой);

· обход тупика;

· распознавание тупика с последующим восстановлением.

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

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

1 условие – условие взаимного исключения – можно устранить путем разрешения неограниченного разделения ресурсов. Это удобно для повторно-входимых программ и ряда драйверов, но совершенно неприемлемо к совместно используемым переменным в критических интервалах.

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

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

4 условие – условие кругового ожидания – исключить можно, предотвращая образование цепи запросов. Это можно сделать, если ресурсам приписать определенные номера. Все запросы на ресурсы должны выполняться в порядке возрастания номеров ресурсов. Если запросы следуют в порядке возрастания номеров, - 1,2,3,4 – то они удовлетворяются по мере того, как ресурсы становятся доступными.

Процесс, имеющий ресурс i-го уровня, в дальнейшем может потребовать только ресурсы i+1-го уровня. После того, как процесс получил, а потом освободил ресурсы данного уровня, он может запросить ресурсы на том же самом уровне. Освободить процесс i-го уровня можно только после освобождения всех ресурсов на более высоких уровнях.

Например, имеются процессы P1, P2, ресурсы R1, R2; уровни R1 – 1, R2 – 2. Если P1 получил R1, он может получить R2. Но P2 не может получить R2, пока не получит R1. Т.о. создание замкнутой цепи невозможно. Иерархическое выделение ресурсов часто не дает никакого выигрыша, если порядок использования ресурсов, определенный в описании процессов, отличается от порядка уровней иерархии. В этом случае ресурсы будут использоваться крайне неэффективно.

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

2. Обход тупиков.

Обход тупика – это запрет входа в опасное состояние (такое состояние, которое может привести к тупику).

Для обхода тупика перед выделением ресурса необходимо проверить, не приводит ли выделение ресурсов к опасному состоянию, и если да – ресурс выделять нельзя.

Необходимо иметь информацию о максимальных потребностях процессов в ресурсах.

Ресурсы должны быть одного типа.

Например, имеем 6 единиц ресурса и 2 процесса

	Имеет	Требует	Максимальная потребность	“Остаток” потребностей
Р1
Р2
		Резерв-3	9>6

возможны тупики!

1. Удовлетворение запроса Р1 – приведет к продолжению его выполнения – но состояние будет опасным – если он запросит еще – то ни Р1, ни Р2 не будут выполняться.

2. Удовлетворение запроса Р2 – он завершится.

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

Его ограничения:

· количество ресурсов в системе должно быть постоянным;

· необходимо заранее указывать потребности в ресурсах;

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

3. Распознавание с последующим восстановлением.

Данный метод основан на распознавании тупика и принудительном освобождении всех ресурсов попавших в тупик процессов. Обнаружение тупика возможно с помощью графа повторно используемых ресурсов (модель Холта).

Дата добавления: 2015-07-07