Каждый из собеседников набирает номер
Каждый из собеседников набирает номер и, если слышит сигнал "занято", то кладет телефонную трубку. Если тут же не происходит вызов, то он делает вторую попытку, спустя несколько секунд. Конечно, эта попытка может совпасть со следующей попыткой партнера, но обычно связь восстанавливается после небольшого числа проб. В наших условиях мы не можем принять такую схему поведения: у нас партнеры могут быть совершенно идентичны.
Предлагалось довольно много решений этой задачи, и все они оказались некорректными, так что у тех, кто занимался ею, возникло в какой-то момент сомнение, имеет ли она решение вообще. Первое правильное решение принадлежит голландскому математику Деккеру. Это решение представляет в действительности некоторое объединение наших предыдущих попыток: в нем используются "переменные безопасности", подобные тем, что обеспечивали взаимное исключение в последних конструкциях, вместе с целочисленной переменной "очередь" первого решения, но только для разрешения неопределенности, когда ни один из двух процессов не продвигается немедленно в критический интервал. Отметим, что в предлагаемой ниже программе начальное значение переменной "очередь" может быть положено также и равным "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".
Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий