57 Условие взаимоблокировки
Взаимоблокировки или тупиковые ситуации формально можно определить так: группа процессов находится в тупиковой ситуации, если каждый из группы ожидает события, которое может вызвать только другой процесс из той же группы.
Для возникновения взаимоблокировки должны выполняться следующие условия:
Условие взаимного исключения. Каждый ресурс в данный момент времени отдан одному процессу или доступен.
Условие удержания и ожидания. Процессы, удерживающие в данный момент полученные ранее ресурсы, могут запрашивать новые ресурсы.
Условие отсутствия принудительной выгрузки ресурса. У процесса нельзя принудительным образом забрать ранее полученные ресурсы. Процесс, владеющий ими, должен сам освободить ресурсы.
Условие циклического ожидания. Должна быть замкнутая последовательность из двух или нескольких процессов, каждый из которых ждет доступа к ресурсу, удерживаемому следующим членом последовательности.
Причем для возникновения взаимоблокировки необходимо выполнение всех четырех условий. Если хоть одно из них отсутствует, тупиковая ситуация невозможна.
58 Моделирование взаимоблокировок
Холт показал, что можно смоделировать четыре условия возникновения тупиков, используя направленные графы. Графы имеют два вида узлов: процессы (показанные кружками) и ресурсы (квадратами). Ребро, направленное от узла ресурса к узлу процесса, означает, что ресурс ранее был запрошен процессом, получен и в данный момент используется этим процессом. На рис. 3.1а ресурс R в настоящее время отдан процессу А.
Ребро, направленное от процесса к ресурсу, означает, что процесс в данный момент блокирован и находится в состоянии ожидания доступа к этому ресурсу (рис. 3.1б). Цикл в графе означает наличия взаимоблокировки и показан на рис. 3.1в.
Таким образом, графы ресурсов представляет собой инструмент, позволяющий обнаружить взаимоблокировку в заданной последовательности запросов/возврат ресурсов.
Моделирование состоит в графическом отображении последовательности запросов и возвратов ресурсов с дальнейшей проверкой связей на зацикливание. Если зацикливания нет, то взаимоблокировки нет, в противном случае взаимоблокировка имеет место быть.
Для решения проблемы взаимоблокировки существуют четыре стратегии:
Пренебрежение проблемой в целом (если проигнорировать проблему, возможно, затем она проигнорирует Вас)
Обнаружение и восстановление. Позволяет взаимоблокировке произойти, обнаружить ее и предпринять какие-либо действия.
Динамическое избежание тупиковых ситуаций с помощью аккуратного распределения ресурсов.
Предотвращение с помощью структурного опровержения одного из четырех условий, необходимых для взаимоблокировки.
59. Страусовский алгоритм
Большинство операционных систем потенциально страдают от взаимоблокировок, которые даже не обнаруживаются, не говоря уже об автоматическом выходе из тупика. Суммарное количество процессов в системе определяется количеством записей в таблице процесса. Таким образом, ячейки таблицы процесса являются ограниченным ресурсом. Если системный вызов fork получает отказ, потому что таблица целиком заполнена, разумно будет, что программа, вызывающая fork, подождет какое-то время и повторит попытку. Теперь предположим, что система UNIX имеет 100 ячеек процессов. Работают 10 программ, каждой необходимо создать 12 (под)процессов. После образования каждым процессом девяти процессов 10 исходных и 90 новых процессов заполнят таблицу целиком. Теперь каждый из десяти исходных процессов попадает в бесконечный цикл, состоящий из попыток разветвления и отказов, то есть возникает взаимоблокировка. Таким образом, если вероятность взаимоблокировки очень мала, как в данном примере, то ею легче пренебречь, т.к. код исключения может оень усложнить ОС и привести к большим ошибкам. Этот алгоритм используется как в UNIX, так и в Windows. Поэтому (и не только) на серверах часто устанавливают автоматическую перезагрузку (раз в сутки, как правило ночью), если возникнет взаимоблокировка, то после перезагрузки ее не будет.