2017-12-14
660
Предположим, что существуют два процесса ПР1 и ПР2, разделяющих два ресурса типа SR: R1 иR2. Пусть взаимное исключение доступов к этим ресурсам реализуется с помощью семафоров S1 и S2 соответственно. Процессы ПР1 и ПР2 обращаются к ресурсам следующим образом (рис. 9.3):
Процесс ПР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);
::
Рис. 9.3. Пример последовательности операторов для двух процессов,
которая может привести к тупиковой ситуации
Здесь несущественные (с точки зрения обращения к ресурсам) детали опущены. Считаем, что оба семафора первоначально установлены в единицу. Пространство возможных вычислений приведено на рис. 9.4.
Горизонтальная ось задаёт выполнение процесса ПР1, вертикальная – ПР2. Вертикальные линии, пронумерованные от 1 до 4, соответствуют операторам 1– 4 процесса ПР1. Аналогично горизонтальные линии, пронумерованные от 5 до 8, соответствуют операторам 5 – 8 программы ПР2. Точка на плоскости определяет состояние вычислений в некоторый момент времени. Так, точка А соответствует ситуации, при которой ПР1 начал исполнение, но не достиг оператора 1, а ПР2 выполнил оператор 6, но не дошел до оператора 7. По мере выполнения точка будет двигаться горизонтально вправо, если исполняется ПР1, и вертикально вверх, если исполняется ПР2.
|
|
|
Рис. 9.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 заблокируется в точке Х при выполнении оператора 2, а процесс ПР2 заблокируется в точке Y при выполнении оператора 6. При этом процесс ПР1 ждёт, когда процесс ПР2 выполнит оператор 7, а ПР2 ждёт, когда ПР1 выполнит оператор 4. Оба процесса будут находиться в тупике, ни ПР1, ни ПР2 не могут закончить выполнение. При этом все ресурсы, которые получили ПР1 и ПР2, становятся недоступными для других процессов, что резко снижает возможности вычислительной системы по обслуживанию их. Отметим одно очень важное обстоятельство: тупик будет неизбежным, если вычисления зашли в прямоугольник D, являющийся критическим состоянием.
|
|
|
Для того чтобы возник тупик, необходимо, чтобы одновременно выполнялись четыре условия:
- взаимного исключения, при котором процессы осуществляют монопольный доступ к ресурсам;
- ожидания, при котором процесс, запросивший ресурс, ждёт до тех пор, пока запрос не будет удовлетворен, при этом удерживая ранее полученные ресурсы;
- отсутствия перераспределения, при котором ресурсы нельзя отобрать у процесса, если они ему уже выделены;
- кругового ожидания, при котором существует замкнутая цепь процессов, каждый из которых ждёт ресурс, удерживаемый его предшественником в этой цепи.
Проанализировав содержательный смысл этих четырех условий, легко убедиться, что все они выполняются в точке Y (рис. 9.4).
