2. СЛАБО СВЯЗАННЫЕ ПРОЦЕССЫ

Предметом главы в целом является изучение слабо связанных последовательных процессов. Данный раздел посвящен тщательному рассмотрению простой, но характерной задачи, на примере которой читатель познакомится с возникающими в этой области проблемами.

В предыдущем разделе мы описали природу изолированного последовательного процесса, в котором последовательность действий выполняется автономно, т.е. независимо от окружающей обстановки.

Если двум или более последовательным процессам необходимо взаимодействовать друг с другом, то они должны быть связаны, т. е. иметь средства для обмена информацией. Как мы увидим ниже, свойства таких средств связи играют важную роль.

Кроме того, мы предполагаем, что процессы связаны слабо. Под этим подразумевается, что кроме (достаточно редких) моментов явной связи, эти отдельные процессы рассматриваются как совершенно независимые друг от друга. В частности, не допускаются какие-либо предположения об относительных скоростях различных процессов. (Скажем, такое предположение, как "процессы синхронизированы относительно некоторого общего времени", может рассматриваться как неявная связь.) Независимость от соотношения скоростей полностью соответствует нашему определению последовательного процесса, единственным существенным свойством которого является то, что элементарные шаги процесса выполняются последовательно. Если нужно, мы можем следить по часам за выполнением процесса, но сам он от этого совершенно не зависит.

Отказ от каких-либо предположений о соотношении скоростей на первый взгляд покажется читателю неоправданной попыткой представить вещи в более сложном виде, чем они есть на самом деле. Однако это полностью обосновано. Во-первых, нам, возможно, придется иметь дело с ситуациями, в которых действительно мало что известно о скоростях. Например, одной частью системы может быть управляемая вручную станция, а другая часть системы характеризуется тем, что она может останавливаться по внешнему воздействию на неопределенное время, тем самым уменьшая скорость "выполнения" процесса до нуля. Во-вторых, - и это значительно более важно, - когда мы думаем, что можем полагаться на некоторое соотношение скоростей, то оказывается в конце концов, что мы погнались за пенни, а упустили фунт. Конечно, отдельные устройства можно сделать проще в предположении ограничений на их скорости. Однако задача создания надежной работоспособной системы из многих связанных элементов значительно усложняется, если необходимо учитывать их взаимное влияние друг на друга и согласовывать скорости. (Прежде всего это создает весьма неустойчивое равновесие в работе, чувствительное к любым изменениям скоростей, которые легко возникают при замене элементов системы, скажем, при установке более быстрой модели построчного печатающего устройства или при перепрограммировании какой-либо части программного обеспечения.)

    begin S1; parbegin S2; S3; S4; parend; S5 end

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

Наше решение, хотя и правильное, имеет, однако, излишнее ограничение: после завершения критического интервала 1, переменная "очередь" становится равной "2" и должна вновь получить значение "1", чтобы разрешить следующий вход в критический интервал 1. Как результат этого, единственно допустимая последовательность критических интервалов представляет собой строгое их чередование "1, 2, 1, 2, 1, 2, 1, ... ", т. е. процессы синхронизированы. Для того, чтобы четко определить нежелательность для нас подобного решения, мы поставим дополнительное условие: "если один из процессов остановился вне своего критического интервала, то это не должно привести к блокировке другого процесса" 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", и поэтому решает войти в свой критический интервал. В этот момент мы можем заключить:

1. соотношение "cl = 0" уже установлено и будет сохраняться, пока процесс 1 не завершит выполнение своего критического интервала;
2. так как "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 может входить в свой критический интервал совершенно независимо от текущего значения переменной "очередь". Этим завершается доказательство корректности решения Деккера. Тех читателей, которые не оценили изобретательности этого решения, я прошу учесть, что для них уже была подготовлена почва из тщательно подобранных мною и затем отвергнутых, как непригодные, решений.

    integer cl, с2

    integer array с[1 : N]

    с[индекс],

    for j:=l step 1 until N do оператор S;

    if условие then оператор

if условие 1 and условие 2 then оператор

begin integer array b, с[0 : N],
      integer очередь;
      for очередь := 0 step 1 until N do
          begin b[очередь] := 1; с[очередь] :=1 end;
      очередь := 0;
      parbegin
      процесс 1: begin ............... end;
      процесс 2: begin ............... end;
          .
          .
          .
      процесс N: begin ............... end;
      parend
end

Все N процессов подобны. Структура i-го процесса такова (1 i N) 2):

процесс i: begin integer 3;
           Ai: b[i] := 0;
           Li: if очередь  i then
               begin с[i] := 1;
                     if b[очередь] = 1 then очередь := i;
                     goto Li
               end;
               c[i] :=0;
               for j:= 1 step 1 until N do
                     begin if j=/=1 and с[j] = 0 then goto Li end;
                     критический интервал i;
                     очередь :=0; с[i]:=1; b[i]:=l;
                     остаток цикла i; goto Ai
               end

Замечание. Программа для отдельного процесса начинается с описания "integer j". В соответствии с правилами АЛГОЛа это означает, что каждый процесс вводит свою индивидуальную целочисленную переменную "j" (так называемую локальную величину).

Доказательство мы предоставляем читателю. Снова необходимо показать:

1. в любой момент самое большее один процесс находится в своем критическом интервале;
2. решение о том, какому из процессов первым войти в свои критический интервал, не может откладываться до бесконечности;
3. остановка процесса в "остатке цикла" не влияет на другие процессы.

Доказательство второго утверждения наиболее трудно. {Краткое указание. Как только один из процессов выполнил присваивание "очередь := i", никакой другой процесс не может принять решение о присваивании своего номера переменной "очередь", прежде чем завершится критический интервал. Помните, что два процесса могут "одновременно" решить присвоить значение своего номера переменной "очередь"!)

(Замечание, которое может быть пропущено при первом чтении.) Только что приведенная программа проверяет значение "b[очередь]" в условиях, когда массив "b" и переменная "очередь" размещаются в общей памяти. Мы договорились, что проверка значения одной переменной есть неделимое действие, и поэтому проверка переменной с индексами "b[очередь]" может означать единственно следующее: проверяется значение переменной "очередь", и если оно оказывается равным "5", то проверяется "b[5]". Или более точно в алгольной записи:

процесс i: begin integer j, k;
                    .
                    .
                    .
                 k := очередь; if b[k] = 1 then. . .

begin integer a, b;
      procedure квадрат(u, v); integer u, v;
           begin u := v  v end;
   L: квадрат(а, 3); квадрат(b, а); квадрат(а, b);
end

begin integer a, b;
    L: а := 3  3; b := а  а; а := b  b
end

begin integer a;
      procedure ОНД (u, v, w); value v, w; integer u, v, w;
      if v = w then u := v
               else
         begin if v < w then ОНД (u, v, w - v)
                                  else ОНД (u, v - w, w)
         end;
      ОНД (a, 12, 33)
end

        if условие then оператор 1 else оператор 2

begin real array матрица[1 : N, 1 : M];
     real array вектор[1 : M];
     real array произведение[1 : N];
     procedure умножстроки(k); value k; integer k;
         begin if k > 0 then
               parbegin
                   begin real s; integer j;
                         s := 0;
                         for j := 1 step 1 until M do
                         s := s + матрица[k, 3]  вектор[jl;
                         произведение[k] := s
                   end;
                   умножстроки(k - 1)
               parend
         end;
     .
     .
     .
     .
     умножстроки(N);
     .
     .
end