Простой пример
2.1. Простой пример
Рассмотрим два последовательных процесса: "процесс 1" и "процесс 2", которые для наших целей удобно считать циклическими. В каждом цикле выполнения процесса существует "критический интервал", критический в том смысле, что в любой момент времени только один из процессов может находиться внутри своего критического интервала. Чтобы осуществить такое "взаимное исключение", оба процесса имеют доступ к некоторому числу общих переменных. Мы постулируем, что проверка текущего значения такой общей переменной и присваивание нового значения общей переменной рассматриваются как неделимые, не допускающие вмешательства действия; то есть, если два процесса осуществляют присваивание нового значения одной и той же общей переменной "одновременно", то присваивания происходят друг за другом и окончательное значение переменной соответствует одному из присвоенных значений, но никогда не есть их "смесь".
Подобно этому, если один процесс проверяет значение переменной "одновременно" с присваиванием ей значения другим процессом, то первый обнаруживает либо старое, либо новое значение, но никогда не их смесь.
Для наших целей АЛГОЛ-60 не подходит, так как он создан для описания единственного последовательного процесса. Поэтому /мы используем некоторое его расширение, позволяющее описывать параллельное выполнение. Если последовательность операторов - как обычно разделенных точкой с запятой - заключена в специальные операторные скобки "parbegin" и "parend", то это интерпретируется как параллельное выполнение составляющих конструкцию операторов. Вся конструкция - назовем ее "параллельный блок" - может рассматриваться как оператор. Запуск параллельного блока означает одновременный запуск всех составляющих его операторов; выполнение блока завершается после завершения выполнения всех составляющих его операторов. Например,
begin S1; parbegin S2; S3; S4; parend; S5 end
(где S1, S2, S3, S4 и S5 есть операторы) означает, что после завершения S1, операторы S2, S3 и S4 будут выполняться параллельно, и только после того, как все они завершатся, начнется выполнение оператора S5.
Теперь при определенных выше соглашениях об использовании общих переменных мы можем написать первое решение проблемы взаимного исключения:
begin integer очередь; очередь := 1; parbegin
процесс 1: begin L1: if очередь = 2 then goto L1; критический интервал 1; очередь := 2; остаток цикла 1; goto L1 end; процесс 2: begin L2: if очередь = 1 then goto L2; критический интервал 2; очередь := 1; остаток цикла 2; goto L2 end; parend
end
(Сделаем замечание для читателя, недостаточно знакомого с языком АЛГОЛ-60. После "begin" в первой строке стоит так называемое описание "integer очередь", ибо, согласно правилам языка АЛГОЛ-60 в тексте программы нельзя ссылаться на переменные, не введенные с помощью описания. Так как это описание располагается после "begin", являющегося самой внешней операторной скобкой, то это означает, что на время выполнения всей программы введена переменная, которая будет принимать только целые значения, и к которой можно обратиться с помощью имени "очередь".)
Два процесса связываются друг с другом через общую целочисленную переменную "очередь", значение которой показывает, какой из двух процессов первым выполнит (точнее, закончит) свой критический интервал. Из программы ясно, что после первоначального присваивания единственными возможными значениями переменной "очередь" являются "1" и "2". Условием входа в критический интервал для процесса 2 является "очередь
1", т. е. "очередь = 2". Но единственный способ для переменной "очередь" получить это значение есть присваивание "очередь := 2" в процессе 1. Так как процесс 1 выполняет это присваивание только по завершении своего критического интервала, то процесс 2 может войти в свой критический интервал только после завершения критического интервала 1. А критический интервал 1 действительно мог быть выполнен, потому что начальное условие "очередь = 1" означает одновременно "очередь 2", и значит потенциальный цикл ожидания, помеченный в программе как L1, первоначально бездействует.После присваивания "очередь := 2" роли процессов меняются. {Замечание. Предполагается, что других ссылок на переменную "очередь", кроме тех, которые явно присутствуют в программе, не существует.)
Наше решение, хотя и правильное, имеет, однако, излишнее ограничение: после завершения критического интервала 1, переменная "очередь" становится равной "2" и должна вновь получить значение "1", чтобы разрешить следующий вход в критический интервал 1. Как результат этого, единственно допустимая последовательность критических интервалов представляет собой строгое их чередование "1, 2, 1, 2, 1, 2, 1, ... ", т. е. процессы синхронизированы. Для того, чтобы четко определить нежелательность для нас подобного решения, мы поставим дополнительное условие: "если один из процессов остановился вне своего критического интервала, то это не должно привести к блокировке другого процесса" . Поэтому предыдущее решение не приемлемо, и мы должны искать новое.
Наша вторая попытка связана с введением двух целочисленных переменных "cl" и "с2", причем cl = 0 (или 1) или c2 = 0 (или 1) соответственно будет означать, что процесс 1 или процесс 2 находятся внутри (или вне) критического интервала. Предлагается следующее решение:
begin integer cl, c2; cl := 1; c2 := 1; parbegin
процесс 1: begin L1: if c2 = 0 then goto L1; cl := 0; критический интервал 1; c1:= i; остаток цикла 1; goto L1 end; процесс 2: begin L2: if cl = 0 then goto L2; c2 := 0; критический интервал 2; c2 := 0; остаток цикла 2; goto L2 end; parend; end
Первоначальные присваивания устанавливают cl и c2 в "1" в соответствии с тем фактом, что процессы начинают выполняться вне своих критических интервалов. Во все время выполнения критического интервала 1 сохраняется соотношение "cl = 0" и потому первая строка в записи процесса 2 представляет по существу ожидание: "ждать до тех пор, пока процесс 1 находится в своем критическом интервале." Такое решение проблемы действительно отчасти предохраняет от одновременного выполнения критических интервалов, но оно, к сожалению, потому слишком просто, что неверно.
Пусть сначала процесс 1 обнаружит, что "c2 = 1".
Пусть процесс 2 немедленно вслед за этим проверяет значение cl; тогда он еще найдет, что "cl = 1". Каждый из процессов, удостоверившись, что другой не находится в критическом интервале, решит, что он может безопасно войти в свой собственный критический интервал!
Мы должны действовать более осторожно. Давайте поменяем местами в самом начале процессов проверку чужого "с" и установку собственного "с". Получаем такую программу:
begin integer cA, c2; cl := 1; c2 := 1; parbegin
процесс 1: begin Al : cl := 0; L1 : if c2 = 0 then goto L1; критический интервал 1; cl := 1; остаток цикла 1; goto Al end; процесс 2: begin A2 : c2 := 0; L2 : if cl = 0 then goto L2; критический интервал 2; c2 := 1; остаток цикла 2; goto A2 end; parend; end
Имеет смысл убедиться в том, что это решение во всяком случае совершенно безопасно. Давайте сосредоточим внимание на моменте, когда процесс 1 обнаруживает, что "c2 = 1", и поэтому решает войти в свой критический интервал. В этот момент мы можем заключить:
- соотношение "cl = 0" уже установлено и будет сохраняться, пока процесс 1 не завершит выполнение своего критического интервала;
- так как "c2 = 1", то процесс 2 находится вне критического интервала, в который он не может войти, пока сохраняется "cl = 0", т. е. пока процесс 1 еще пребывает в своем критическом интервале.
Итак, взаимное исключение действительно гарантировано.
Но, увы, это решение также должно быть отвергнуто: предпринятые в нем меры безопасности слишком сильны, так что оно содержит опасность взаимной блокировки. Если после присваивания "cl := 0", но еще до проверки c2 (и то, и другое в процессе 1), процесс 2 выполнит присваивание "c2 := 0", то это значит, что оба процесса достигли соответственно меток L1 и L2 и одновременно справедливы соотношения "cl = 0" и "c2 = 0". В итоге процессы будут безрезультатно ждать друг от друга разрешения войти в критический интервал.
Мы правильно поступили, установив собственное "с" до проверки чужого "с", но неправильно было сохранять только состояние ожидания с неизменным установленным собственным "с". Это до некоторой степени исправлено в следующей конструкции:
begin integer cl, c2; cl := 1; c2 := 1; parbegin
процесс 1: begin L1: cl := 0; if c2 = 0 then
begin cl := 1; goto L1 end; критический интервал 1; cl := 1; остаток цикла 1; goto L1 end; процесс 2: begin L2: c2 := 0; if cl = 0 then
begin c2 := 1; goto L2 end; критический интервал 2; c2 := 1; остаток цикла 2; goto L2 end; parend; end
Эта конструкция столь же безопасна, как и предыдущая, а если присваивания "cl := 0" и "с2 := 0" выполняются "одновременно", то это не приводит с неизбежностью к взаимной блокировке до бесконечности; дело в том, что оба процесса установят свои собственные "с" обратно в "1", прежде чем возобновить попытку входа в критический интервал, тем самым предоставляя другому процессу возможность поймать удобный момент. Но наши принципы заставляют отбросить также и это решение, так как отказ от каких-либо предположений относительно соотношения скоростей означает, что решение должно быть справедливым при любых скоростях, а последняя конструкция позволяет так подобрать скорости, что процессы будут проверять чужие "с" только в те моменты времени, когда значения их собственных "с" нулевые. Чтобы четко определить неприемлемость таких решений, которые работают только при некоторых удачных обстоятельствах, мы установим следующее требование: "если два процесса находятся перед входом в свои критические интервалы, то должно быть выполнено требование о невозможности подобрать для них такие конечные скорости, при которых решение о том, какому из них первому войти в свой критический интервал, откладывается до бесконечности".
Между прочим, заметим, что отброшенное решение вполне приемлемо в повседневной жизни. Например, когда два человека разговаривают по телефону и связь неожиданно разъединяется, оба, как правило, пытаются восстановить связь.
Каждый из собеседников набирает номер и, если слышит сигнал "занято", то кладет телефонную трубку. Если тут же не происходит вызов, то он делает вторую попытку, спустя несколько секунд. Конечно, эта попытка может совпасть со следующей попыткой партнера, но обычно связь восстанавливается после небольшого числа проб. В наших условиях мы не можем принять такую схему поведения: у нас партнеры могут быть совершенно идентичны.
Предлагалось довольно много решений этой задачи, и все они оказались некорректными, так что у тех, кто занимался ею, возникло в какой-то момент сомнение, имеет ли она решение вообще. Первое правильное решение принадлежит голландскому математику Деккеру. Это решение представляет в действительности некоторое объединение наших предыдущих попыток: в нем используются "переменные безопасности", подобные тем, что обеспечивали взаимное исключение в последних конструкциях, вместе с целочисленной переменной "очередь" первого решения, но только для разрешения неопределенности, когда ни один из двух процессов не продвигается немедленно в критический интервал. Отметим, что в предлагаемой ниже программе начальное значение переменной "очередь" может быть положено также и равным "2".
begin integer cl, c2, очередь; cl := 1; c2 := 1; очередь := 1; parbegin
процесс 1: begin Al: cl := 0; L1: if c2 = 0 then
begin if очередь = 1 then goto L1; cl := 1; Bl: if очередь = 2 then goto Bl; goto A1 end; критический интервал 1; очередь := 2; cl := 1; остаток цикла 1; goto Al end; процесс 2: begin A2: c2 := 0; L2: if cl = 0 then
begin if очередь = 2 then goto L2; c2 = 1; B2: if очередь = 1 then goto B2; goto A2 end; критический интервал 2; очередь := 1; c2 := 1; остаток цикла 2; goto A2 end; parend; end
Докажем теперь корректность этого решения. Во-первых, отметим, что каждый процесс оперирует только с собственным "с".
Вследствие этого процесс 1 проверяет "c2" только при "cl = 0"; он войдет в свой критический интервал только тогда, когда обнаружит, что "c2 = 1".
Для процесса 2 можно сделать аналогичное замечание.
Короче говоря, мы узнаем переменные безопасности наших последних конструкций, и поэтому решение безопасно в том смысле, что два процесса никогда не могут оказаться одновременен) в своих критических интервалах.
Во второй части доказательства необходимо показать, что в случае сомнения, какому из двух процессов первым войти в критический интервал, выяснение этого вопроса не может откладываться до бесконечности. Теперь мы обратим внимание на целочисленную переменную "очередь": замечаем, что присваивание значения этой переменной происходит только при окончании критических интервалов (или по окончании некоторых их частей), поэтому можно считать переменную "очередь" константой во время принятия решения о том, кому войти в критический интервал. Предположим, что "очередь = 1". Тогда процесс 1 может только циклиться через метку L1 (при этом "с1 = 0") и только до тех пор, пока он находит, что "с2 = 0". Но если "очередь = 1", то процесс 2 может циклиться только через В2, а это состояние процесса 2 означает, что "с2 = 1", поэтому процесс 1 не может циклиться и непременно попадает в свой критический интервал. Для случая "очередь = 2" применяется симметричное (относительно процессов и переменных) рассуждение.
В третьей и заключительной части доказательства мы отмечаем, что остановка, скажем процесса 1 в "остатке цикла 1", не препятствует продвижению процесса 2: тогда справедливо соотношение "с1 = 1", и процесс 2 может входить в свой критический интервал совершенно независимо от текущего значения переменной "очередь". Этим завершается доказательство корректности решения Деккера. Тех читателей, которые не оценили изобретательности этого решения, я прошу учесть, что для них уже была подготовлена почва из тщательно подобранных мною и затем отвергнутых, как непригодные, решений.
