Процесс Пр 1 Процесс Пр 2

1: P(S2); (5):P(S1);

2: P(S1); (6):P(S2);

3: V(S1); (7):V(S1);

4: V(S2); (8):V(S2);

Рис. 8.З. Пример последовательности операторов для двух процессов, которые могут привести к тупиковой ситуации

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

Горизонтальная ось задает выполнение процесса Пр1, вертикальная — процесса Пр2. Вертикальные линии, пронумерованные от 1 до 4, соответствуют операторам 1-4 процесса Пр1; аналогично горизонтальные линии, пронумерованные от 5 до 8, соответствуют операторам 5-8 программы Пр2. Точка па плоскости определяет состояние вычислений в некоторый момент времени. Так, точка А соответствует ситуации, при которой процесс Пр1 начал исполнение, но не достиг оператора 1, а процесс Пр2 выполнил оператор 6, но не дошел до оператора 7. По мере выпол-

Примеры тупиковых ситуаций и причины их возникновения_____________________ 253

нения точка будет двигаться горизонтально вправо, если исполняется процесс Пр 1, и вертикально вверх, если исполняется процесс Пр2.

Рис. 8.4. Пространство состояний системы двух параллельных конкурирующих процессов

Интервалы исполнения, во время которых ресурсы R1 и R2 используются каж­дым процессом, показаны с помощью фигурных скобок. Линии 1-8 делят простран­ство вычислений на 25 областей, каждая из которых соответствует определенному состоянию в распределении ресурсов в процессе вычислений. Закрашенные се­рым цветом состояния являются недостижимыми из-за взаимного исключения процессов Пр1 и Пр2 при доступе к ресурсам R1 и R2.

Рассмотрим последовательность исполнения 1-2-5-3-6-4-7-8, представленную тра­екторией Т1. Когда процесс Пр2 запрашивает ресурс R1 (оператор 5), ресурс недо­ступен (оператор выполнен, семафор закрыт). Поэтому процесс Пр2 заблокиро­ван в точке В. Как только процесс Пр1 достигнет оператора 3, процесс Пр2 деблокируется по ресурсу R1. Аналогично в точке С процесс Пр2 будет заблоки­рован при попытке доступа к ресурсу R2 (оператор 6). Как только процесс Пр1 достигнет оператора 4, процесс Пр2 деблокируется по ресурсу R2.

Если же, например, выполняется последовательность 1-5-2-6, то процесс ПР1 за-блокируется в точке X при выполнении оператора 2, а процесс Пр2 заблокируется в точке Y при выполнении оператора 6. При этом процесс ПР1 ждет, когда процесс Пр2 выполнит оператор 7, а Пр2 ждет, когда Пр 1 выполнит оператор 4. Оба процесса бу­дут находиться в тупике, ни Пр1, ни Пр2 не смогут закончить выполнение. При этом все ресурсы, которые получили оба процесса, становятся недоступными для других

254_______________________ Глава 8. Проблема тупиков и методы борьбы с ними

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

Исследования проблемы тупиков показали, что для возникновения тупиковой ситуации необходимо одновременное выполнение следующих четырех условий [17, 54]:

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

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

- условия отсутствия перераспределения, при котором ресурсы нельзя отобрать у процесса, если они ему уже выделены;

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

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