скачать рефераты
  RSS    

Меню

Быстрый поиск

скачать рефераты

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

Первое решение, обсуждаемое в этом классе - алгоритм Dijkstra, Feijen, и Van Gasteren (Подраздел 8.3.1); этот алгоритм обнаруживает завершение вычислений с синхронным прохождением сообщений. Несколько авторов обобщили алгоритм для вычислений с асинхронным прохождением сообщений; главная проблема здесь состоит в том, чтобы проверить, что каналы связи пусты. Мы обсуждаем решение Safra (Подраздел 8.3.2), в котором в каждом процессе подсчитывается число сообщений, которые посланы и получены; сравнивая счетчики можно определить действительно ли каналы являются пустыми. Также возможно использовать подтверждения для этой цели (Подраздел 8.3.3); но это решение снова требует, чтобы каналы были двунаправленными и чтобы число управляющих сообщений равнялось по крайней мере числу, используемому алгоритмом Shavit-Francez.

В Подразделе 8.3.4 принцип обнаружения будет обобщен для использования произвольного волнового алгоритма.

8.3.1 Алгоритм Dijkstra-Feijen-Van Gasteren

Алгоритм Dijkstra, Feijen, и Van Gasteren [DFG83] обнаруживает завершение основного вычисления, используя синхронное прохождение сообщений; действия такого вычисления даются как Алгоритм 8.5. В этих вычислениях, завершение описано с помощью предиката

term  Û "p : statep = passive

term  Û "p : statep = passive

 

var statep   : (active, passive);,

     

C pq: { statep = active }

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

                  statep := active

         end

Ip:  { statep = active }

       begin statep := passive end

Алгоритм 8.5 основной алгоритм с синхронными сообщениями.

Сравните алгоритм и term с Алгоритмом 8.1 и Теоремой 8.1.

Алгоритм разработан как последовательность небольших шагов, каждый шаг прост для  понимания, и правильность следует из инварианта, который разработан вместе с алгоритмом. Обработка взята из [DFG83]. Обзначим номер процесса, содержащего маркер t ,или если маркер находится в процессе передачи, номер процесса, к которому направляется является маркер. Отправление маркера может быть выполнено только процессом pt, при этом t уменьшается на 1. Волна заканчивает когда t = 0; следовательно инвариант P должен быть выбран такой, что можно было сделать заклющение о наличии завершения из P, t = 0, и другой информации в p0. Инвариант должен сохранятся, когда p0 начинает волну, то есть, когда t = N - 1

Сначала положим P = P0, где

P0   º "i (N > i> t) : statep = passive.

Действительно, P0 истинен когда t = N - 1, и если t = 0 и statepp0 = passive, из этого утверждения можно сделать заключение о завершение. Отправление маркера сохраняет P0, если только маркер отправляют пассивные процессы, поэтому мы принимаем следующее правило.

Правило 1. Процесс только тогда управляет маркером, когда он пассивен.

В этом режиме, P сохраняется с помощью отправления маркера и также с помощью внутренних действи1; к сожалению, P не сохраняется действиями связи. Предикат P0 может принимать значение ложь, когда процесс pj активизируется процессом pi, где j > t и  i £ t; см. Упражнение 8.4. Так как P0 может принять значение ложь, P заменяется более слабым утверждением (P0 Ú P1), где P1 выбирается так, что каждый раз когда P0 принимает значение ложь, P1 является истинным. Каждому процессу присваивается цвет,  белый или черный, и пусть P = (P0 Ú P1) где

P1 º  $ j (t ³ j ³ 0) : colorpj = black.

Каждый раз, когда P0  принимает значение ложь , P1 является или становится истинным, если цвет посылающего процесса черный.

Правило 2. Посылающие процессы становятся черными.

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

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

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

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

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

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

Действительно, теперь можно проверить, что внутренние действия, основная соммуникации, и отправление маркера сохраняют 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 как инвариант, где

Pº  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 ) .

Страницы: 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, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62


Новости

Быстрый поиск

Группа вКонтакте: новости

Пока нет

Новости в Twitter и Facebook

  скачать рефераты              скачать рефераты

Новости

скачать рефераты

© 2010.