8.3.4 Обнаружение завершения с помощью волн
Все алгоритмы обнаружения завершения, обсужденные пока в этом разделе используют кольцевую подтопологию для управляющих коммуникаций; все алгоритмы основаны на алгоритме волны для колец. Подобные решения были предложены для другой топологии; например, Francez и Rodeh [FR82] и Topor [Top84] предложили алгоритм, использующий корневое дерево охватов управляющих соммуникаций. Tan и Van Leeuwen [TL86] предложили децентрализованные решения к кольцевым сетям, для сетей деревьев, и для произвольных сетей. Изучение этих решений показывает, что они очень похожи друг на друга, за исклющением алгоритма волны, на который они опираются.
В этом подразделе делается набросок для вывода алгоритма обнаружения завершения (и инварианта), основанного на произвольном алгоритме волны, а не на специально определенном алгоритме (кольцевом алгоритме). Для каждой волны, первое событие, в котором процесс посылает сообщение для волны или принимает решение, называется посещением того процесса. Предполагается, что, если необходимо, процесс может отложить посещение, пока не удовлетворено локальное условие процесса. Последующие события той же самой волны больше не приостанавливаются.
Этот подраздел представляет вывод только для случая синхронного прохождения сообщений основного вычисления (как для вывода в Подразделе 8.3.1). Этот вывод можно обобщить для асинхронного случая, подобно тому как это сделано в Подразделе 8.3.2 и 8.3.3.
Инвариант алгоритма должен позволить обнаружить завершение, когда волна принимает решение; поэтому, сначала мы устанавливаем P = P0, где
P0 º все посещенные процессы пассивны.
Действительно, поскольку все процессы были посещены, когда произошло принятие решения, это утверждение позволяет обнаружение завершения, когда волна принимает решение. Кроме того, P0 устанавливается когда волна начинается (нет еще посещенных процессов). При работе алгоритма волны P0 сохраняется по правилу 1, представленному ниже.
Правило 1. Только пассивные процессы посещаются волной. К сожалению, P0 принимает значение ложь, когда посещенный процесс активизируется непосещенным процессом. Поэтому, каждый процесс обеспечивается цветом, и P ослаблляется до (P0 Ú P1), где
P1 º имеется непосещенный черный процесс.
Более слабый инвариант сохраняется согласно правилу 2.
Правило 2. Процесс посылающий сообщение становится черным.
Волна может изменить значение более слабого утверждение, если посещен единственный непосещенной черный процесс. Ситуация исправляется дальнейшим ослаблением P. Каждый процесс представляет цвет, белый или черный, как входное данное для волну. Волна измененяется так, чтобы вычислить самый темный из представленных цветов; вспомним, что волны могут вычислять infirna, и " самый темный " является infirnum. Когда волна принимает решение, будет вычислен самый темный из всех представленных цветов; это будет белый цвет, если все процессы представляют белый и черный, если по крайней мере один процесс представляет черный. В время волны, волна будет называться белой, если ни один процесс еще не представляет черный цвет; и черной, если по крайней мере один процесс уже представляет черный цвет. Таким образом процесс, когда он посещается, либо представляет белый цвет, что не изменяет цвет волны, либо представляет черный цвет,что окрашивает волну в черный цвет. P ослабляется до (P0 Ú P1 Ú P2), где
P2 º волна черная.
Это утверждение сохраняется по следующему правилу.
Правило 3. Посещенный процесс представляет волне свой текущий цвет.
Действительно, все основные коммуникации также как деятельность волны сохраняют это утверждение, которое является поэтому инвариантом. Волна заканчивается неудачно, если процессы принимают решение для черной волны, но в этом случае просто начинается новая волна. Новая волна может быть успешной, только если процессы могут стать белыми, и это случается немедленно после посещения волны.
Правило 4. Решающий узел в черной волне начинает новую волну.
Правило 5. Процессы немедленно становятся белыми после каждого посещения волны.
Эти правила гарантируют возможный успех волны после завершения основного вычисления. Действительно, если основное вычисление закончилось, первая волна, начатая после завершение, окрашивает все процессы в белый цвет, и следующая волна заканчивается успешно.
В этом алгоритме только одна волна может бежать в любой время. Если две волны, скажем А и B, бегут одновременно, окрашивание процесса в белый цвет после посещения волной B может нарушить инвариант для волны A. Поэтому, если алгоритм обнаружения должен быть децентрализован, должен также использоваться децентрализованный алгоритм волны, чтобы все инициаторы алгоритма обнаружения сотрудничали в той же самой волне. Также возможно использовать другой принцип обнаружения, в котором различные волны могут вычислять одновременно без того, чтобы нарушить правильное действие алгоритма обнаружения; см. Подраздел 8.4.2.
Еще два решения проблемы обнаружения завершения будут обсуждены в этом разделе: алгоритм восстановления кредита и алгоритм временных пометок.
8.4.1 Алгоритм восстановления кредита
Mattern [Mat89a] предложил алгоритм, который обнаруживает завершение очень быстро, а именно, за одну единицу времени после возникновения (при принятии предположений идеализации времени из Определения 6.31). Алгоритм обнаруживает завершение централизованного вычисления и предполагает, что каждый процесс может послать сообщение инициатору вычисления непосредственно (то есть, сеть содержит звезду с инициатором в центре).
В алгоритме каждому сообщению и каждому процессу назначается значение кредита, которое всегда находится между 0 и 1 (включая границы), и алгоритм поддерживает следующие утверждения как инварианты.
S1. Сумма всех кредитов (в сообщениях и процессах) равняется 1.
S2. Основное сообщение имеет положительный кредит.
S3. Активный процесс имеет положительный кредит.
Процессы имеют положительный кредит, когда правилами не предписано (то есть, пассивным процессам) посылать их кредиты инициатору. Инициатор действует как банк, собирая все кредиты, посланные ему, в переменной ret .
Когда инициатор имеет все кредиты, требование для активных процессов и основных сообщений иметь положительный кредит означает, что не имеется никаких таких процессов и никаких таких сообщений; следовательно term сохраняется.
Правило 1. Когда ret = 1, инициатор вызывает алгоритм объявления.
Для выполнения требования живости, все кредиты в конечном счете должны быть переданы инициатору при возникновении завершения. Если основное вычисление закончилось, больше нет основных сообщений, и нас интересуют только кредиты, поддерживаемые процессами.
var statep : (active, passive) init if p = p0 then active else passive ;
credp : fraction init if p = p0 then I else 0 ;
ret : fraction init 0 ; for p0 only
Sp: { statep = active } (* Праволо 3 *)
begin send (mes,credp / 2) : credp := credp / 2 end
Rp: { Сообщение (mes,c) прибыло в p }
begin receive (mes,c) ; statep := active;
credp := credp + c (* Правила 4 and 5b *)
end
Ip: { statep = active }
begin statep := passive ;
send ( ret, credp ) to p0 ; credp :== 0 (* Правило 2 *)
end
AP0: { Сообщение (ret, c) прибыло в p0 }
begin receive ( ret, c ) ; ret := ret + c ;
if ret = 1 then Announce (* Правило I *)
end
Алгоритм 8.9 Алгоритм восстановления кредита.
Правило 2. Когда процесс становится пассивным, он посылает свой кредит инициатору.
В начальной конфигурации только инициатор активен и имеет положительный кредит, а именно 1, и ret = 0, что означает, что S1- S3 удовлетворz.ncz. Инвариант должен поддержаться в течение вычисления; об этом заботятся следующие правила. Сначала, каждому основному сообщению при посылке нужно дать положительный кредит; к счастью, отправитель активен, и следовательно имеет положительный кредит.
Правило 3. Когда активный процесс p посылает сообщение, кредит разделяется между p и сообщением.
Процессу при его активизации нужно дать положительный кредит; к счастью, сообщение, которое он получает при этом, содержит положительный кредит.
Правило 4. При активизации процесса ему дается кредит активизирующего сообщения.
Единственная ситуация, не охваченная этими правилами - получение основного сообщения уже активным процессом. Процесс уже имеет положительный кредит, следовательно не нуждается в кредите сообщения, чтобы удовлетворить S3; однако, кредит не может быть разрушен, поскольку это привело бы вело бы к нарушению S1 . Процесс получающий сообщение может обращаться с кредитом двумя различными способами, оба порождают правильные алгоритмы.
Правило 5a. Когда активный процесс получает основное сообщение, кредит этого
сообщения посылается инициатору.
Правило 5b. Когда активный процесс получает основное сообщение, кредит того сообщения добавляется к кредиту процесса.
Алгоритм дается как Алгоритм 8.9. В этом алгоритме, принимается, что каждый процесс знает имя инициатора (по крайней мере, когда он сначала становится пассивным) и алгоритм использует правило 5b. Когда инициатор становится пассивным, он посылает сообщение самому себе.