Реферат: Распределенные алгоритмы
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
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. Когда инициатор становится пассивным, он посылает сообщение самому себе.
Теорема 8.11 Алгоритм восстановления кредита (Алгоритм 8.9) - правильный алгоритм обнаружения завершения.
Доказательство. Алгоритм осуществляет правила 1-5, из чего следует, что S1 Ù S2 Ù S3 инвариант, где
S1 º 1 = ( S(mes, c) c )+ (SpÎP credp )+ ( S(ret, c) c )+ret
S2 º"( mes, c ) в процессе передачи : c > 0
S3 º"p Î P : (statep = passive Þ credp = 0) Ù (statep = active Þ credp > 0).
Завершение обнаружено, когда ret = 1, который вместе с инвариантом означает, что term выполняется.
Чтобы показать живучесть, заметим что после завершения не происходят никакие основные действия, следовательно происходят только получения сообщений (ret, c), и каждое получение уменьшает на 1 число сообщений находящихся в процессе передачи. Следовательно, алгоритм достигает конечной конфигурации. В такой конфигурации не имеется никаких основных сообщений (соглачно term), credp = 0 для всех p (согласно term и S3), и не имеется никакого сообщения (ret, c) (конфигурация конечная). Следовательно, ret = 1(из S1), и завершение обнаружено. o
Если осуществляется правило 5a, число управляющих сообщений равняется числу основных сообщений плюс один. (Здесь мы также считаем сообщение, посланное p0 самому себе после того, как он стал пассивным.) Если осуществляется правило 5b, число управляющих сообщений равняется числу внутренних событий в основном вычислении плюс один, не больше числа основных сообщений плюс один. Казалось бы, что правило 5b более предпочтительно с точки зрения сложности по сообщениям управляющего алгоритма. Иная ситуация возникает при рассмотрении битовой сложности. Согласно правилу 5a, каждое значение кредита в системе кроме ret - отрицательная степень 2 (i.e .., 2-i для некоторого целого числа i). Представление кредита отрицательным логарифмом уменьшает число передаваемых бит.
Алгоритм восстановления кредита - единственный алгоритм в этой главе, который требует включения дополнительной информации (а именно, кредита) в основные сообщения. Добавление информации к основным сообщениям называется piggybacking. Если piggybacking не желателен, кредит сообщения может быть передан в управляющем сообщении, посланном сразу после основного сообщения. (Алгоритм следующего подраздела также требует piggybacking, если это осуществлено, используя логические часы Лампорта.)
Проблема может возникнуть, если кредиты (сообщений и процессов) хранятся в установленном числе бит. В этом случае существует самый маленький положительный кредит, и не возможно разделить это количество кредита на два. Когда кредит с наименьшим возможным значением нужно разделить, основное вычисление приостанавливается на время пока процесс не приобретет дополнительный кредит от инициатора. Инициатор вычитает этот кредит из ret (ret, может получиься в результате отрицательным) и передает его процессу, который возобновляет основное вычисление после получения. Это увеличение кредита вызывает блокирование основного вычисления, что противоречит требованию невмешательства алгоритма обнаружения завершения в основное вычисление. К счастью, эти действия редки.
8.4.2 Решения, использующие временные пометки
Этот подраздел обсуждает решения проблемы обнаружения завершения, основанной на использовании временных пометок. Предполагается, чтопроцессы оборудованы для этой цели часами (Подраздел 2.3.3); могут использоваться часы аппаратных средств ЭВМ также как логические часы Лампорта (Подраздел 2.3.3). Принцип обнаружения был предложен Rana [Ran83].
Подобно решениям Подраздела 8.3.3, решение Рана основано на локальном предикате quiet(p) для каждого процесса p, где
quiet(p) Þ statep = passive Ù в не передаются соощения посланные процессом p, что означаетс, что("p quiet(p)) Þ term. Как и прежде, quiet определяется как
quiet(p) º (statep = passive Ù unackp = 0).
Алгоритм стремится проверить для некоторого момента времени t, все ли процессы quiet ; при положительном ответе следует заключение о завершении. Реализуется это волной, которая опрашивает каждый процесс был ли он quiet в тот момент или позже; процесс, который не был quiet, не отвечает на сообщения волны, эффективно гася волну.
var statep : (active, passive) ;
θp : integer init 0 ; (* Логические часы *)
unackp : integer init 0 ; (* Число сообщений оставшихся без ответа*)
qtp : integer init 0 ; (* Время последнего перехода на quiet *)
begin θp := θp + 1 ; send (mes, θp) ', unack p := unack p + 1 end
Rp: { Сообщение (mes, θ) из q прибыло в p }
begin receive (mes, θ) ; θp := max(θp, θ) + 1 ;
send ( ack, θp ) to q ; statep := active
end
begin θp := θp + 1 ; statep := passive ;
if unackp = 0 then (* p становится quiet *)
begin qtp := θp ; send (tok, θp , qtp , p) to Nextp end
end
Ap: { Подтверждение ( ack, θ) прибыло в p }
begin receive ( ack, θ ) ; θp :== max(θp, θ) + 1 ;
if unackp = 0 and statep = passive then (* p сиановится quiet *)
begin qtp := θp ; send (tok, θp, qtp ,p) to Nextp end
end
Tp: { Маркер ( tok, θ, qt, q ) прибывает в p }
begin receive ( tok, θ, qt, q} ; θp := max(θp, θ) + 1 ;
if quiet(p) then
if p = q then Announce
else if qt ³ qtp then send (tok , θp , qt, q) to Nextp
end
Алгоритм 8.10 алгоритм rana.
В отличие от решений в Разделе 8.3 посещение волной процесса р не затрагивает переменные процесса p, используемые для обнаружения завершения. (Посещение волны может затрагивать переменные алгоритма волны и, если используются логические часы Лампорта, часы процесса.) В следствии этого правильное действие алгоритма не нарушается параллельным выполнением нескольких волн.
Алгоритм Рана децентрализован; все процессы выполняют один и тот же алгоритм обнаружения. Децентрализованный алгоритм также можно получить
обеспечив алгоритм Подраздела 8.3.4 децентрализованным алгоритмом волны. В решении Рана процессы могут начинать частные волны, которые бегут одновременно.
Страницы: 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
