Тупиковая ситуация (дедлок)

При параллельном исполнении процессов могут возникать такие ситуации, при которых два или более процесса все время находятся в заблокированном состоянии. Самым простым является случай, когда каждый из двух процессов ждет ресурс, занятый другим процессом. Из-за этого ожидания ни дин из процессов не может продолжить исполнение и освободить ресурс, необходимый другому. Эта тупиковая ситуация, образно называемая “смертельное объятие”, больше известна как дедлок. Хотя дедлок может быть результатом ошибок программирования, чаще всего он возникает не из-за них. Обычно процессы, находящиеся в дедлоке, не связаны друг с другом, а просто конкурируют за ресурсы системы.

Возникновение тупиковой ситуации фактически зависит в общем случае от невоспроизводимых относительных скоростей исполнения процессов. Рассмотрим, например, три процесса, претендующих на ресурс, который выделяется дискретными взаимозаменяемыми единицами, такими как магнитофон, физические страницы или буфера из множества буферов. Пусть в системе существует 10 таких единиц, из которых 8 распределены следующим образом: процесс А имеет 2 единицы, а для полного завершения ему нужно 9. Процесс В имеет 2 единицы, и ему потребуется еще 7. Процесс С имеет 4, и ему потребуется еще 6. Процессы В и С достигли точки, в которой каждому процессу требуется еще 2 единицы. Если запрос процесса С будет удовлетворен первым, то процесс сможет продолжить исполнение и в конце концов освободит все 6 единиц, которые у него были. Это позволит процессу В, а затем процессу А получить все необходимые им ресурсы и завершиться. Если же вначале будет выполнен запрос процесса и, то ни один из процессов не сможет завершиться, и в результате возникнет дедлок. Причиной этого дедлока являются неупорядоченные попытки процессов войти в критический интервал, связанный с выделением соответствующей единицы ресурса

Рис.2.22. Программы, приводящие к дедлоку.

Чтобы понять причины возникновения дедлоков, рассмотрим пример. Для простоты предполагается, что существует только два процесса ПРОЦ1 и ПРОЦ2. Они разделяют два ресурса р1 и р2. Взаимное исключение доступов к этим ресурсам реализуется с помощью семафора s1 для ресурса р1 и s2 для ресурса р2. Два процесса обращаются к ресурсам так, как показано в программах на рис. 2.22. Несущественные детали опущены и проставлены номера операторов. Оба семафора первоначально установлены в 1. Вместо P(sl) и V(s2) можно написать ЗАПРЕСр1 и ОСВОБОДИТЬр2. Пространство возможных вычислений приведено на рис. 2.23. Горизонтальная ось задает процесс выполнения ПРОЦ1; вертикальная ось-ПРОЦ2. Вертикальные линии, пронумерованные от 1 до 4, соответствуют операторам от 1 до 4 программы, исполняемой процессом ПРОЦ1. Отрезок горизонтальной оси между линиями 1 и 2 задает исполнение ПРОЦ1 между операторами 1 и 2. Аналогично горизонтальные линии, пронумерованные от 5 до 8, соответствуют операторам 5-8 в программе, исполняемой процессом ПРОЦ2.

Точка на плоскости определяет состояние вычисления в некоторый момент времени. Так, точка W соответствует ситуации, при которой процесс ПРОЦ1 начал исполнение, но не достиг еще оператора 1, а процесс ПРОЦ2 выполнил оператор 6, но не дошел до оператора 7. По мере выполнения точка движется горизонтально вправо, если исполняется процесс ПРОЦ1, и вертикально вверх, если исполняется ПРОЦ2, и стоит на месте, если не исполняется ни один из них. Таким образом, каждое возможное вычисление (только о отношению к ПРОЦ1 и ПРОЦ2) представлено пунктирной линией (траекторией), составленной из вертикальных и горизонтальных отрезков. Траектория А представляет вычисления, при которых временная последовательность запросов и освобождений ресурсов задается операторами 5, 6, 7, 8, 1, 2, 3, 4.

Интервалы исполнения, во время которых ресурсы р1 и p2 используются каждым процессом, показаны с помощью фигурных скобок. Так, процесс ПРОЦ2 использует ресурс p1 после того, как он прошел семафор оператора 6 (а не просто выполнил оператор), и до тех пор, пока ПРОЦ2 не выполнит оператор 7, т.е. операцию освобождения р1. Линии 1-8, выделяющие интервалы исполнения, делят также пространство вычислений на 25 прямоугольников, каждый из которых задает состояние вычисления. Заштрихованные состояния являются недостижимыми. Два из них недостижимы из-за взаимного исключения ПРОЦ1 и ПРОЦ2 при доступе к ресурсу р1. Шесть состояний, включая одно из предыдущих, недостижимы из-за взаимного исключения при доступе к ресурсу р2.

Временная последовательность исполнения операторов 1, 2, 5, 3, 4, 6, 7, 8 представлена траекторией В : ПРОЦ2 запрашивает р2 (оператор 5), ресурс недоступен. Хотя оператор 5 выполнен, семафор закрыт. Поэтому ПРОЦ2 заблокирован в точке X на рис. 4.23, начиная с которой исполняется процесс ПРОЦ1. Как только ПРОЦ1 достигает оператора 4, ПРОЦ2 деблокируется. Однако если выполняется последовательность 5, 1, 6, 2, тоПРОЦ2 при исполнении оператора 6 блокируется в точке траектории С, а ПРОЦ1 блокируется при исполнении оператора 2 в точке . Оба процесса находятся теперь в дедлоке; ПРОЦ1 ждет, пока ПPOЦ2 достигнет оператора 8, а ПРОЦ2 ждет, пока ПРОЦ1 достигнет оператора 3. На самом деле дедлок неизбежен, как только вычисления зашли в прямоугольник U, являющийся опасным состоянием.

Стоимость дедлока велика. Ни ПРОЦ1, ни ПРОЦ2 не могут закончить выполнение. Более того, все ресурсы, которые получили оба, по крайней мере р1 и р2, становятся недоступными, что снижает возможность системы обслуживать другие процессы.