Реферат: Распределенные алгоритмы

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

Правило 4. Когда волна заканчивается неудачно, p0 начинает новую волну.

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

Заметьте, что процесс p, окрашивающий маркер в белый цвет, не изменяет значение  P на ложь если i > t, и P всегда принимет значение истина, когда p0 начинает волну,  посылая маркер к PN - 1. Из этого  следует, что окрашивание в белый цвет может благополучно иметь место при отправления маркера.

Правило 5. Каждый процесса становиться белым сразу после посылки маркера. Это гарантирует конечный успех волны после завершения основного вычисления. Алгоритм дается как Алгоритм 8.6.

var statep   : (active, passive) ;

     colorp   : (white, black) ;

Cpq: { statep = active }

        begin (* p посылает основное сообщение, которое получает  q *)

                   colorp := black;    (* Правило 2 *)

                  state q := active

        end

Ip:  { statep = active }

       begin statep := passive end

Начало обнаружения, исполняется один раз процессом p0:

       begin send ( tok, white ) to pN -1  end

Tp: (* Процесс p обрабатывает маркер (tok ,c) *)

      { statep == passive }   (* Правило I *)

      begin if p = p0

                   then if (c = white Ù colorp = white)

                               then Announce

                              else send ( tok, white} to pN -1   (* Правило 4 *)

                   else if (colorp = white)  (*Правило 3 *)

                              then send ( tok, c ) to Nextp

                              else send ( tok, black ) to Nextp ;

                 colorp := white  (*Правило 5 *)

       end

Алгоритм 8.6 dukstra-feuen-van gasteren алгоритм.

Теорема 8.8 Dijkstra-Feijen- Фургон Gasteren алгоритм (Алгоритм 8.6) - правильный алгоритм обнаружения завершения для основных вычислений, использующих синхронное прохождение сообщений.

Доказательство. Предикат P º (P0 Ú P1  Ú P2 ) и алгоритм были разработаны таким образом, что P является инвариантом алгоритма. Завершение считается обнаруженным когда пассивный, белый p0  обрабатывает белый маркер. Действительно, при этом из цвета маркера следует, что ØP2 ,из цвета процесса p0  и из    t = 0 следует  ØP1  , а из P0 и состояния p0 следует term. Следовательно алгоритм безопасен.

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

Теперь мы попытаемся оценить число управляющих сообщений, используемых алгоритмом. Основное вычисление, используемое в доказательстве Теоремы 8.2 заставляет алгоритм использовать по крайней мере один обход маркера для каждых двух основных сообщений; следовательно сложность алгоритма в худшем случае - ½ N.M управляющих сообщений; см. Упражнение 8.5.

Алгоритм может использовать значительно меньшее количество сообщений в "среднем" основном вычислении. Предположим, что  основное вычисление имеет сложность по времени T. Т.к. маркер всегда отправляется последовательно, не неблагоразумно предположить, что маркер отправляется  приблизительно T раз прежде, чем заканчивается основное вычисление. (Даже эта оценка может быть слишком пессимистичной, т.к. отправление маркеров приостановлено в активных процессах.) Т.к. маркер отправляется менее чем 3N раза после завершения, алгоритм в этом случае использует T + 3N управляющих сообщений. Сложность основного вычисления - по крайней мере T (а именно, сложность по времени), но если вычисление содержит достаточный параллелизм,  сложность сообщения может достигать Ω(N.T ).Если параллелизм позволяет каждому процессу посылать постоянное число сообщений в единицу времени, сложность по сообщениям основного вычисления - N.T.a, то есть Ω(N.T ) . Число управляющих сообщений, который является 0 (N + T), тогда намного лучше чем можно ожидать от сложности обнаружения завершения в худшем случае.

8.3.2 Подсчет Основных Сообщений: Алгоритм Сафра

Синхронность прохождения сообщений, принятая для основного вычисления в алгоритме Dijkstra-Feijen-Van Gasteren - серьезное ограничение для его общего применения. Несколько авторов обобщили этот алгоритм для вычислений с асинхронным прохождением сообщений (cf. Алгоритм 8.1). В данном подразделе будет обсуждено решение Сафра [Dij87]; в нем сложность в  среднем случае сопоставима с сложностью алгоритма Dijkstra-Feijen-Van Gasteren.

Определим для каждой конфигурации число сообщений находящихсы в процессе передачи как B. Тогда term эквивалентен

("p : statep = passive) Ù B = 0.

Снова инвариант P будет составлен так, что завершение можно будет определить из  P, t = 0, и другой информации из p0. Инвариант должен сохраняться, когда p0 начинает волну, то есть, когда t = N - 1.

Чтобы информация о B была доступна в процессах (распределенным способом), процесс p  снабжается счетчеком сообщений mcp , и процессы поддерживают Pm как инвариант, где

Pm  º  B= SpÎP  mcp .

Инвариант Pm  получен, когда первоначально mcp = 0 для каждого p, и процессы подчиняются следующему правилу.

Правило М. Когда процесс p посылает сообщение, счетчик сообщений увеличивается на 1; когда процесс p получает сообщение,  счетчик сообщений уменьшается на 1.

Инвариант должен позволять p0 решать,что содержит term, когда он получает маркер (t = 0). Т.к. term теперь также включает ограничение на значение B, маркер будет использоваться для передачи целого числа q для вычисления суммы счетчиков сообщений процессов, которые его отправили. Попробуем установить P = Pm Ù P0 , где

P0   º   ("i (N > i > t) : statePi = passive) Ù ( q = SN>i>t  mcPi ) .

Действительно, P0  истинен, когда t = N -1  и q = 0, и если t = 0 тогда из P следует, что

("i > 0 : statePi = passive) Ù (mcP0+ q = B),

так  что p0 может определить завершение если state P0 = passive и mcP0 + q = 0.

Утверждение P0 устанавливается, когда p0 начинает волну,  посылая маркер в pN -1 с q = 0. Отправление маркера сохраняет P0, только если отправляют маркер пассивные процессы и добавляют значение их счетчека сообщений; поэтому мы принимаем следующее правило.

Правило 1. Процесс обрабатывает маркер только когда он пассивен, и когда процесс посылает маркер он прибавляет значение своего счетчика сообщений к q.

При этом, P сохраняется при отправлении маркера и также при внутренних действиях; к сожалению, P не сохраняется при получении сообщения процессом p, с i > t. При получении сообщения P0 принимает значение ложь, то есть, это применимо только когда B> 0. Т.к. Почтовый сохраняется перед тем как принимает значение ложь,сохраняется P1, где

P1 º (Si £ t  mcPi + q )>0.

Утверждение P1 остается истинным при получении сообщения процессом  pi с i > t ; следовательно, более слабое утверждение P, определенное как Pm Ù (P0 Ú P1) сохраняется при получениисообщения процессом  pi с i > t.

var statep   : {active, passive) ;

      colorp   : (white, black) ;

      mcp      : integer init 0 ;

Sp: { statep = active }

       begin send ( mes ) ;

                 mcp := mcp + 1  (* Правило M *)

       end

Rp: { Сообщение (mes) прибывает в p }

       begin receive (mes) ; statep := active ;

                 mcp := mcp - 1;   (*Правило M *)

                 colorp := black  (*Правило 2 *)

       end

Ip: { statep = active }

      begin statep := passive end

Начало определения, выполняется один раз процессом p0:

       begin send (tok, white, 0) to pN  - 1  end

Tp: (* Процесс p обрабатывает маркер (tok,c,q ) *)

      { statep = passive }   (*Правило I *)

      begin if p = p0

                    then if (c = white) Ù (colorp = white) Ù(mcp + q = 0)

                                 then Announce

                                 else send (tok, white,0) to pN -1   (*Правило 4 *)

                    else if (colorp = white)  (*Правила I and 3 *)

                                 then send ( tok, c, q + mcp ) to Nextp

                                 else send ( tok, black, q + mcp ) to Nextp ;

                colorp := white  (*Правило 5 *)

       end

Алгоритм алгоритма 8.7 safra's.

Это измененное утверждение все еще позволяет обнаружить завершение процессу p0 при тех же самых условиях, потому что, если t = 0, P1 читает mcP0 + q > 0, таким образом если mcP0 + q = 0 (это уже требовалось для обнаружения), ØP1 сохраняется. Отправление маркера сохраняет P1, и тоже самое происходит при посылке основного сообщения. К сожалению, P1 может принималь значение ложь при получении сообщения процессом  pi с i £ t. Как и в Подразделе 8.3.1, эта ситуация исправляется  назначение цвета каждому процессу по следующему правилу:

Правило 2. Процесс получающий сообщение становится черным и P заменяется на Pm Ù (P0 Ú P1 Ú P2 ), где

P2 º  $ j (t ³ j ³ 0) : colorp = black.

При каждом получении соощения, при котором P1 принимает значение ложь, P2 принимает значение истинна, так что P не принимает значение ложь при любом основном действии. Так как (P Ù colorP0 = white Ù t = 0) Þ ØP2 , все еще возможно обнаружить завершение с новым утверждением, а именно, проверяя является ли p0 белым (и пассивным) когда он обрабатывает маркер.

Ослабление P было успешно предотвращает изменение значения Р после основных событий; но более слабое утверждение может принять значение ложь при отправлении маркера, а именно, если процесс t - единственный черный процесс и он посылает маркер. Ситуация исправляется дальнейшим ослаблением P. Маркеру также назначается цвет (белый или черный) , и P ослабляется до Pm Ù (P0 Ú P1 Ú P2 ÚP3),  где

P3   º маркер черный.

Отправление маркера сохраняет P3, если черные процессы отправляют черный маркер.

Правило 3. Когда черный процесс посылает маркер, маркер  становится черным.

Т.к. (маркер белый) Þ ØP3  завершение может все еще обнаруживаться процессом p0, а именно, проверкой получает ли он белый маркер (и белый ли он сам и пассивный).

Действительно, теперь можно быть уверенным, что внутренние действия, основные коммуникации и отправление маркеров сохраняют P. Волна заканчивается неудачно,  когда маркер возвращается в p0, если он черный, p0 черный, или mcP0 + q ¹ 0. Если волна заканчивается неудачно, должна быть начата новая волна.

Правило 4. Когда волна заканчивается неудачно, p0 начинает новую волну.

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

Заметим, что процесс p окрашивающий в белый цвет не изменяет заначение P на ложь если i > t, и что P всегда становится истинным когда p0 начинает волну,  посылая маркер в pN -1.Из этого следует, что окрашивание в белый цвет может благополучно иметь место при отправлении маркера.

Правило 5. Каждые процесс становится белым сразу после посылки маркера. При этом гарантируется конечный успех волны после завершения основного вычисления. Алгоритм дается как Алгоритм 8.7.

Теорема 8.9 Алгоритм Сафра (Алгоритм 8.7) - правильный алгоритм обнаружения завершения для вычислений с асинхронным прохождением сообщений.

Доказательство. Алгоритм был разработан так, что предикат P, определенный как Pm Ù (P0 Ú P1 Ú P2 ÚP3)  - инвариант алгоритма.

Чтобы показать безопасность, заметим, что завершение обнаружевается при t = 0, stateP0 = passive, colorP0 = white, и mcP0 + q = 0.Из  этих условий Ø P3, Ø P2, и Ø P1, следовательно Pm Ù P0, из чего  вместе с stateP0 = passive и mcP0 + q = 0 следует term.

Чтобы показать живость, заметим, что после завершения основного вычисления счетчики сообщений  не изменяют свои значения и их сумма, равняется 0. Волна, начатая в такой конфигурациизаканчивается с mcP0 +q = 0 и все процессы  окрашены в белый цвет, что гарантирует, что следующая волна будет успешной. o

В отличие от алгоритма Dijkstra-Feijen-Van Gasteren, алгоритм Сафра не имеет ограниченной сложности для худшего случая; маркер может быть пропущен неограниченное число раз, в то время как все процессы - пассивные, но некоторые основные сообщения находятся в процессе передачи в течение длительный периода времени. Что касается алгоритма Dijkstra-Feijen-Van Gasteren, для основного вычисления со сложностью времени T можно ожидать выполнения Q(T + N)  сообщений.

Векторно-расчетный алгоритм. Mattern [Mat87] предложил алгоритм, сопоставимый с алгоритмом Сафра, но который поддерживает отдельный счетчик сообщений для каждого адресата. Для процесса p счетчик сообщений - массив mcp[P]. Когда p посылает сообщение q, p изменяет счетчик mcp [q] := mcp [q]+l и когда p получает сообщение, он изменяет счетчик mcp [p] := mcp [p] - 1. Маркер также содержит массив счетчиков, и когда p обрабатывает маркер, к mcp добавляется в маркер и обнуляется (массив в начале содержит нули). Завершение обнаружено, когда маркер равняется 0.

Алгоритм векторного-подсчета имеет некоторые преимущества по сравнению с алгоритмом Сафра, но также и страдает от некоторых серьезных неудобств. Одно из преимуществ алгоритма состоит в том, что  завершение обнаруживается быстрее, а именно за один обход маркера после возникновения завершения. Второе преимущество состоит в том, что пока вычисление не закончилось, маркер приостанавливается чаще, что может уменьшить число управляющих сообщений, используемых алгоритмом. В алгоритме Сафра, каждый пассивный процесс передает маркер; в алгоритме векторного подсчета такой процесс p не будет отправлять маркер если из информации, содержащейся в маркере следует, что сообщение находиться на пути к p.

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

Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42