Dijkstra-Scholten Алгоритм

Алгоритм Dijkstra и Scholten [DS80] обнаруживает завершение централизованного основного вычисления (называемого диффузийным вычислением в [DS80]). Инициатор основного вычисления (называемого окружением в [DS80]), также играет специальную роль в алгоритме обнаружения и обозначается p₀.

Алгоритм обнаружения динамически поддерживает дерево вычислений T = (V_T, E_T) со следующими двумя свойствами.

(1) T пусто или T - направленное дерево с корнем p₀.

(2) Множество V_T  включает все активные процессы и все основные сообщения, находящиеся в процессе передачи.

Инициатор p₀ вызывает алгоритм объявления когда p ₀ Ï V_T согласно первому свойству, T пусто в этом случае, и согласно второму свойству, предикат term принимает значение истина.

Для сохранения свойств дерева вычислений во время выполнения основного вычисления, T должно расширятся при отправке основного сообщения или при переходе процесса, не принадлежащего дереву, в активное состояние. Когда p посылает основное сообщение (mes), (mes) вставляется в дерево, и отцом (mes) является p. Когда процесс p, не принадлежащий дереву, становится активным получая сообщения от q, q становится отцом p. Для того, чтобы представить отправителя сообщения явно, основное сообщение (mes) послаемой q будем обозначать (mes, q).

Удаление узлов из T также необходимо по двум причинам. Во первых, основное сообщение удаляется после его получения. Во вторых, для того чтобы гарантировать продвижение алгоритма обнаружения дерево должно быть опустошено за конечное число шагов после завершения.

 

var state_p: (active, passive) init if p = p₀ then active else passive;

 sс_p : integer           init 0;

 father_p: P                    init if p == p₀ then p else udef;

 

S _p: { state_p = active }

  begin send (mes, p); sc_p:= sc_p + 1 end

 

R _p: { сообщение (mes, q) прибывает в p }

  begin receive (mes, q);, state_p:= active;,

            if father_p = udef then father_p:= q else send (sig, q) to q

  end

I _p: { state_p = active }

begin state_p:= passive;

           if sc_p = 0 then (* Удаляем p из T *)

                begin if father_p = p then Announce else send (sig, father_p) to father_p;

                           father_p:= udef

                end

  end

A _p: { Сигнал (sig,p) прибывает в p }

begin receive (sig,p); sc_p:= sc_p -1;

            if sc_p = 0 and state_p = passive then

                 begin if father_p = p then Announce else send (sig, father_p) to father_p;

                            father_p:= udef

                 end

end

Алгоритм 8.3 dijkstra-scholten алгоритм.

 

Сообщения - листья T; процессы поддерживают переменную, которая считает число их сыновей в T. Удаление сына процесса p происходит в другом процессе q; это происходит при получении сообщения сына или удалении сына процесса q. Для того, чтобы предотвратить искажение данных счетчика сына p, процессу p посылается сигнальное сообщение (sig, p) об удалении его сына. Это сообщение заменяет удаленного сына p, и его удаление, т.е. получение, происходит в процессе p и p при получении сигнала уменьшает на единицу счетчик сыновей.

Алгоритм описан как Алгоритм 8.3. Каждый процесс p имеет переменную father_p, которая не определена если pÏV _{T ,} равна p если p является корнем, и является отцом p, если p - не корень в T. Переменная sc _p содержит число сыновей p в T.

Доказательство правильности строго устанавливает, что граф T, как определено, является деревом и что он становится пустым только после завершения основного вычисления. Для любой конфигурации g Алгоритма 8.3, определено

V _T = {p: father_p ¹ udef} È {передается (mes, p) } È {передается (sig ,p) }

И

E_T = {(p, father_p): father_p ¹ udef Ù father_p ¹ p }

            È { ((mes, p), p): (mes, p) передается }È{((sig,p), p): (sig, p) передается }.

Безопасность алгоритма следует из утверждения P, определенного следующим образом

P º state_p = active Þ p Î V _p                                            (1)

           Ù (u, v) Î E_T Þ u ÎV _T Ù v Î V_T  Ç P      (2)

           Ù sc _p = # { v: (v, p) ÎE _T }                         (3)

           Ù V _T ¹ Æ Þ T дерево с корнем p ₀        (4)

           Ù (state _p = passive Ù s c_p = 0) Þ p Ï V _T (5)

 

Значение этого инварианта следующие. По определению, множество узлов T включает все сообщения (основные и управляющие), и согласно пункту (1) оно также включает все активные процессы. Пункт (2) скорее технический; он заявляет, что T - действительно граф, и все ребра направлены к процессам. Пункт (3) выражает правильность счетчика сыновей каждого процесса, и пункт (4) заявляет, что T - дерево, и p₀ - корень. Пункт (5) используется, чтобы показать, что дерево действительно разрушается, если основное вычисление заканчивается. Для доказательства правильности, обратите внимание, что из P следует, что father_p = p только для p = p₀.

Lemma 8.4 P - инвариант Dijkstra-Scholten алгоритма.

Доказательство. Первоначально state_p = passive для всех p ¹ p₀ и father_p0 ¹ udef, который доказывает пункт (1). Также, E _T = Æ, что доказывает (2). Так как sc _p = 0 для каждого p, удовлетворяется (3). V _T = {po} и E _T = Æ, таким образом T - дерево с корнем p₀, что доказывает (4). Единственный процесс в V _T - p ₀, и p ₀ активен.

S _p: Никакой процесс не становится активным в S _p, и никакой процесс не удаляется из V_T, так что (1) сохраняется.

Применимость действия означает, что p, отец нового узла (mes, p), находится в V_T, что доказывает, что (2) сохраняется. В результате действия, V_T  дополняется узлом (mes, p) и E_T  дугой ((mes, p), p), что означает, что T остается деревом, и sc _p правильно увеличивается, чтобы представить нового сына p, следовательно (3) и (4) сохраняются.

Никакой процесс не становится пассивным листом, и никакой процесс не вставлен в V_T, таким образом (5) сохраняется.

 

R _p: Или p уже был в V_T (father_p ¹ udef) или p вставлен в V_T  после действия, таким образом (1) сохраняется.

Если значение father_p определено, его новое значение - q, и если сигнал послан процессом p, его отец - также q, и q находится в V_T, таким образом (2) сохраняется. Число сыновей q не изменяется, потому что сын (mes, q) процесса q заменяется сыном p или сыном (sig, q), так что s c_q остается правильным, который сохраняет (3).

Структура графа не изменяется, таким образом (4) сохраняется. Процесс p находится в V_T после действия в любом случае, таким образом (5) сохраняется.

I _p: Переход p в пассивное состояние сохраняют (1), (2), (3) и (4). Из того, что p был прежде активен следует, что p был в V_T. Если sc _p = 0, p удаляется из V_T, таким образом (5) сохраняется.

Затем мы рассматриваем что случится при удалении p из T, то есть, если p окажется пассивным листом T.

Если сигнал посылается процессом p, отец сигнала - последний отец p, который находится в V_T, следовательно (2) сохраняется. В этом случае, сигнал заменяет p как сын процесса father_p, следовательно father _{father p}остается правильным, и (3) сохраняется. Структура графа не изменилась, следовательно (4) сохраняется.

Иначе, то есть, если father_p = p, p = p₀ и p, являющийся листом, означает, что p был единственным узелом T, так что удаление опустошает T, что сохраняет (4).

A _p: Получение сигнала уменьшает число сыновей p на единицу, и присваивание значения на sc _p гарантируетсохранение (3). То, что p был отецом сигнала, означает, что p был в V_T. Если state_p = passive и после получения sc _p присваивается 0, p удаляется, таким образом сохраняется (5). Если p удаляется из V_T, инвариант сохраняется по тем же причинам, что и для действия I _p. o

 

Теорема 8. 5 Dijkstra-Scholten алгоритм (Алгоритм 8.3) - правильный алгоритм обнаружения завершения и использует М управляющих сообщений.

Доказательство. Пусть S сумма всех счетчиков сыновей, то есть, S = S_{pÎ P} sc _p . Первоначально S = 0, S увеличивается на единицу при посылке основного сообщения (в S _p), S - уменьшается на единицу, когда получается управляющее сообщение (в A _p), и S никогда не становится отрицательным (из (3)). Это означает, что число управляющих сообщений никогда не превышает число основных сообщений в любом вычислении.

Чтобы доказать живость алгоритма, предположим, что основное вычисление закончилось. После завершения только действия A _p может иметь место и т.к. S уменьшается на единицу при каждом таком переходе, алгоритм достигает конечной конфигурации. Заметьте, что в этой конфигурации, V_T не содержит никакие сообщения. Также, из (5), V_T не содержит никаких пассивных листьев. Следовательно, T не имеет никаких листьев, что означает, что T пусто. Дерево стало пустым, когда p ₀ удалил себя, и программа такова, что p ₀ на этом шаге вызывает алгоритм объявления.

Чтобы доказать безопасность, обратите внимание, что только p ₀ вызывает алгоритм объявления, и делает это после того, как удаляет себя из V_T. Из (4), T пусто, когда это случается,что заключает в себе term. o                                                                                       

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

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

 

8.2.2 Алгоритм Shavit-Francez

Dijkstra-Scholten алгоритм был обобщен для децентрализованных основных вычислений Shavit и Francez [SF86]. В их алгоритме, граф вычисления - лес, каждое дерево которого имеет в качестве корня инициатора основного вычисления. Дерево с корнем p обозначается T_p.

Алгоритм поддерживает граф F = (V_p , E_p), такой что (1) F является пустым или F - лес, каждое дерево которого имеет в качестве корня инициатора; (2) V_p включает все активные процессы и все основные сообщения. Как в алгоритме Dijkstra-Scholten завершении обнаруживается, когда граф становится пустым. К сожалению, в случае леса не так просто выяснить,является ли граф пустым. Действительно, свойство дерева вычислений иметь в качестве корня инициатора означает, что пустота дерева замечается корнем, который и вызывает алгоритм объявления. В случае леса, каждый инициатор замечает пустоту только собственного дерева, но это не означает, что весь леса пуст.

Проверка пустоты всех деревьев выполняется отдельной волной. Лес поддерживает дополнительное свойство, что если дерево T_p стало пустым, оно остается пустым и после этого. Обратите внимание, что это не мешает p стать активным; если p становится активным после разрушения дерева, p вставляется в дерево другого инициатора. Каждый процесс участвует в волне только, если его дерево разрушилось; когда волна принимает решение, вызывается алгоритм объявления. (вызов объявления не нужен, если выбранный волновой алгоритм генерирует решение в каждом процессе; в этом случае, процесс просто останавливается после принятия решения и завершения волнового алгоритма.)

Алгоритм дается как Алгоритм 8.4, в котором волновой алгоритм не показан явно. Каждый процесс p имеет переменную f ather_p , которая не определена, если PÏV _T, и равна p если p является корнем или равна отцу p, если p не-корень в F. Переменная sс _p содержит число сыновей p в F. Логическая переменная empty истинна, тогда и только тогда, когда дерево p пусто.

Доказательство правильности алгоритма подобно доказательству Dijkstra-Scholten алгоритма. Для любой конфигурации g Алгоритма 8.4, определим

V_F = {p: father_p ¹ udef} U {передается (mes, p) } U {передается (sig,p) }

И 

Ep = {(P, father_p): father_p ¹ udef Ù father_p ¹ p}

          U {((mes, p), p): (mes, p) передается } U {((sig,p}, p): (sig,p} передается }.

Безопасность алгоритма будет следовать от утверждения Q, определенный ниже. Это инвариант алгоритма, и доказательство инвариантности подобно доказательству Lemma 8.4. Значение пунктов (1)-(5) из Q такие же как для инварианта алгоритма Dijkstra-Scholten и пункт (6) выражает тот факт, что каждый процесс правильно отслеживает,является ли он все еще корнем дерева в лесе. Конечно, лес пуст, если никакой процесс не является корнем.

 

 

Q Û state_p = active Þ p Î V _F                    (1)

Ù (u, v) Î E _F Þ u Î V_F Ù   v ÎV _F  Ç  P         (2)

Ù sc _p = # { v: (v, p) Î Ep }                     (3)

Ù  V _F ¹ Æ Þ F is a forest                      (4)

Ù   (state _p = passive A s c_p = 0) Þ p Ï Vp (5)

Ù empty_p Û Tp is empty                       (6)

 

Lemma 8.6 Q - инвариант Shavit-Francez алгоритма.

Доказательство. Первоначально state_p = passive для каждого не-инициатора p, и father_p = p для каждого инициатора p, что доказывает (1). Также, Ep = Æ, что доказывает (2). Так как sc _p = 0 для каждого p, (3) удовлетворяется. V _F = {p: p -инициатор} и E _F = Æ, так что F - лес, состоящий из деревьев, содержащих один узел для каждого инициатора, что доказывает (4). Процессы в V_F - инициаторы, которые являются активными; это доказывает (5). Первоначально empty_p равны (p - не-инициатор) и T_p действительно пуст, тогда и только тогда, когда p - не инициатор, что доказывает (6).

S _p: Никакой процесс не становится активным в S _p, и никакой процесс не удаляется из V_F, таким образом (1) сохраняется.

Применимость действия означает, что p, отец нового узла, находится в V_F, таким образом (2) сохраняется.

В результате действия, V_F пополняется вершиной (mes, p) и E _F ребром ((mes, p), p), что означает, что F остается лесом, и s c_p правильно увеличивается на единицу, чтобы представить наличие нового сына процесса p, таким образом (3) и (4) сохраняются.

Никакой процесс не становится пассивным листом, и никакой процесс не вставляется в V_F, таким образом (5) сохраняется.

Поскольку новый лист добавлен в не-пустое дерево, никакое дерево не становится непустым, и поскольку ни одна переменная empty не изменяется, (6) сохраняется.

R _p: p уже был в V _F (father_p ¹ udef) или p вставлен после действия, таким образом (1) сохраняется.

Если значение father_p определено, его новое значение - q, и если послан сигнал, его отец также q, и q находится в V _T , таким образом (2) сохраняется.

Число сыновей процесса q не изменяется, потому что сын (mes, q) процесса q заменяется сыном p или сыном (sig, q), таким образом sc _q оставляет правильным (3).

Структура графа не изменяется, таким образом (4) сохраняется. Никакой процесс не становится пассивным листом, и никакой процесс не вставляется в V_F, таким образом (5) сохраняется.

Никакое дерево не становится пустым, следовательно (6) сохраняется.

I _p: Перевод p в пассивное состояние сохраняет (1), (2), (3), и (4). То, что p прежде был активен означает, что p был в V_F. Если sc _p = 0, p удаляется из V_F, таким образом (5) сохраняется.

Затем мы рассмотрим что случится, если p удалить из F, то есть если p окажется, пассивным листом F. Если послан сигнал, отец сигнала - последний отец процесса p, который находится в V_F, следовательно (2) сохраняется. В этом случае, сигнал заменяет p на сына процесса father_p, следовательно sc _{father p} остается правильным, и (3) сохраняется. Структура графа не изменилась, следовательно (4) сохраняется. Никакое дерево не становится пустым, таким образом (6) сохраняется. Иначе, то есть, если father_p = p, p был корнем и то, что  p является листом означает, что p единственная иуршина в T_p , таким образом ее удаление делает T _p пустым и присваивание empty_p сохраняет (6).

 

 

var state_p: (active, passive)   init if p is initiator then active else passive;

sc _p  : integer                   init 0;

father_p  : P                           init if p is initiator then p else udef;

empty_p: boolean                init if p is initiator then false else true;

   

S _p: { state_p = active }

begin send (mes, p); sc _p:= sc_p + 1 end

R _p: { Сообщение (mes, q) пришло в p }

  begin receive (mes, q); state_p:= active;

            if father_p = udef then father_p:= q else send (sig, q) to q

  end

 

I _p: { state_p = active }

begin state_p:= passive;

          if sc _p = 0 then (* Delete p from F *)

             begin if father_p = p then empty_p:= true else send (sig, father_p } to father_p;

                        father_p:= udef

            end

End

A _p: { Сигнал (sig,p) пришел в p }

  begin receive (sig,p); sc _p:= sc_p - 1;

            i f sc _p = 0 and state_p = passive then

               begin if father_p = p then empty_p:= true else send (sig, father_p) to father_p;

                          father_p:= udef

               end

   end

 

Процессы одновременно выполняют волновой алгоритм, в котором посылка или принятие решения процессом p разрешается только, если empty_p истина и тогда decide вызывает алгоритм объявления.

Алгоритм 8.4 shavit-francez алгоритм.

 

A _p: получение сигнала уменьшает число сыновей процесса p на единицу, и присваивание sc_p гарантирует, что (3) сохраняется. То, что p был отцом сигнала означает, что p был в V_F. Если state_p=passive и после получение сигнала sc_p = 0, p удаляется, таким образом (5) сохраняется.

Если p удаляется из V_F, инвариант сохраняется по тем же причинам, что и при действии I _p.

 

Теорема 8.7 Алгоритм Shavit-Francez (Алгоритм 8.4) - правильный алгоритм обнаружения завершения и использует М + W управляющих сообщени.

Доказательство. Также как в Теореме 8.5 можно показано, что число сигналов не превышает число основных сообщений. Помимо сигналов, управляющий алгоритм только посылает сообщения для одной волны. Из этого следует, что послано не более М + W управляющих сообщений.

Чтобы доказать живость алгоритма предположим, что основное вычисление закончилось. За конечное число шагов алгоритм обнаружения завершения достигает конечной конфигурации, и можно показать, как это было сделано в Теореме 8.5, что в этой конфигурации F пуст. Следовательно, все события волны возможны в каждом процессе, и то, что конфигурация является конечной теперь означает, что все события волны были выполнены, включая по крайней мере одно принятие решения, при котором был вызван алгоритм объявления.

Чтобы доказывать безопасность, обратим внимание на то, что алгоритм объявления вызывается после принятия решения в волновом алгоритме. Это означает, что каждый процесс p послал сообщение волны или принял решение, и из алгоритма следует, что empty _p истина, когда p сделает это. Никакое действие не присваивает переменной empty значение ложь повторно, так что (для каждого p) empty_p  истина, когда вызывается алгоритм объявления. Из (6), V _F пусто, что имеет следствием term. o

Число управляющих сообщений, используемых алгоритмом Shavit-Francez имеет тот же порядок, что и нижнии границы, выведенные в Теоремах 8.2 и 8.3. Алгоритм является оптимальным алгоритмом для обнаружения завершения децентрализованных вычислений для худшего случая (если используется оптимальный волновой алгоритм).

Применение алгоритмов, рассматриваемых в этом разделе требует, чтобы каналы связи были двунаправленными; для каждого основного сообщения, посланного от p в q сигнал должен быть послан от q в p. Сложность с средним случаем равняется сложности в худшем случае; каждое выполнение требует одного сигнального сообщения на одно основное сообщение и, в случае Shavit-Francez алгоритма, точно одного выполнение волны. 

 

 

8.3 Решения, основанные на волнах

По двум причинам полезно рассмотреть некоторые другие алгоритмы для обнаружения завершения кроме двух алгоритмов, данных в Разделе 8.2. Во первых,

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

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

Сначала мы рассмотрим конкретные примеры алгоритмов, в которых во всех случаях волновой алгоритм является кольцевым алгоритмом. Для этого предположим, что кольцо вложено как подтопология сети; но обмен основными сообщениями не ограничен каналам, принадлежащими к кольцу. Процессы перенумерованы с p_o до p_{N -1} и кольцевой алгоритм начинается процессом p_o, посылая маркер процессу p_{N -1}. Процесс p _{i + 1} (для i < N -1) передает маркер процессу p _i. Передвижение маркера заканчивается, когда маркер получает процесс p ₀.

Первое решение, обсуждаемое в этом классе - алгоритм 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: state _p = passive

term Û "p: state_p = passive

 

var state_p: (active, passive);,

     

C _pq: { state_p = active }

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

             state_p:= active

    end

I _p: { state_p = active }

  begin state_p:= passive end

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

 

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

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

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

 

P ₀ º " i (N > i> t): state_p = passive.

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

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

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

P₁ º$ j (t ³ j ³ 0): color _pj = black.

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

 

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

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

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

P ₂º маркер черный.

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

 

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

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

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

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

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

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

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

 

 

var state_p: (active, passive);

color_p: (white, black);

 

C _pq: { statep = active }

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

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

             state _q := active

   end

 

I _p: { state_p = active }

  begin state_p:= passive end

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

  begin send (tok, white) to p_N - ₁ end

 

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

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

begin if p = p ₀

              then if (c = white Ù color_p = white)

                          then Announce

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

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

                         then send (tok, c ) to Next_p

                         else send (tok, black) to Next_p;

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

  end

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

 

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

Доказательство. Предикат P º (P ₀ Ú P ₁ Ú P ₂ ) и алгоритм были разработаны таким образом, что P является инвариантом алгоритма. Завершение считается обнаруженным когда пассивный, белый p ₀ обрабатывает белый маркер. Действительно, при этом из цвета маркера следует, что Ø P₂ , из цвета процесса p ₀  и из t = 0 следует ØP₁ , а из P ₀ и состояния p ₀ следует 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: state_p = passive) Ù B = 0.

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

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

P _m º B= S _{p Î P}  m c_p.

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

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

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

Предыдущая6789101112131415161718192021Следующая

Поделиться:

Воспользуйтесь поиском по сайту: