Введение в распределённые алгоритмы. Ж. Тель (2009) (1185665), страница 83

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 83)

Алгоритм возвращения кредитаВ начальной конфигурации активен один лишь инициатор, и он имеет положи­тельный кредит, равный 1 , причем ret = 0, а это означает, что требования S 1—S3соблюдены. По ходу вычисления нужно поддерживать инвариантность этих соот­ношений. Для этого служат следующие правила. Во-первых, каждому базовомусообщению должен быть выделен положительный кредит, когда оно отправляет­ся; к счастью, отправитель сообщения активен и поэтому имеет положительныйкредит.Правило 3. Когда активный процесс р отправляет сообщение, имеющийся вего распоряжении кредит разделяется между самим процессом р и этим сообще­нием.Гл. 8.

Обнаружение завершения316Всякому процессу должен быть выделен положительный кредит, когда он ак­тивизируется; к счастью, то сообщение, получение которого способствовало ак­тивизации, обладает положительным кредитом.Правило 4. Когда процесс активизируется, ему вручается кредит, которымобладало активизировавшее его сообщение.И лишь одну возможность не охватывают перечисленные правила — полу­чение активным процессом базового сообщения. Такой процесс уже распола­гает положительным кредитом и поэтому для выполнения требования S3 он ненуждается в том кредите, которым обладает указанное сообщение; однако этимкредитом нельзя пренебречь, ибо в таком случае было бы нарушено требованиеS 1.

Активный процесс, получивший сообщение, может распорядиться кредитомдвумя способами, и оба способа приводят к корректному алгоритму.Правило 5а. Как только активный процесс получает базовое сообщение, кре­дит, которым обладало это сообщение, возвращается инициатору.Правило 5Ь. Как только активный процесс получает базовое сообщение, кре­дит, которым обладало это сообщение, добавляется к тому кредиту которым рас­полагал сам процесс.Описанные правила приводят к алгоритму 8.9 (здесь приведен вариант, в ко­тором реализовано правило 5Ь). В этом алгоритме предполагается, что каждыйпроцесс осведомлен об имени инициатора (по крайней мере, в тот момент, когдапроцесс впервые становится пассивным).

Когда инициатор становится пассив­ным, он отправляет сообщение самому себе.Теорема 8.11. Алгоритм возвращения кредита (алгоритм 8.9) являет­ся корректным алгоритмом обнаружения завершения вычислений.Доказательство.мула Si A S 2 А S 3 , где512351 =1Алгоритм применяет правила 1—5, и поэтому фор­= ( ^^ (m es,c)С) + ( Х ^ credp j + ( ^ 2 c \+ r e t'^(ret,c)'5 2 = V (mes, с) на этапе пересылки : с > О5 3 = Ур е Р : {stateр = passive =£> credp = 0)A {stateр = active =£> credp > 0 ),является инвариантом алгоритма. Завершение вычисления обнаруживается, ко­гда ret = 1. С учетом инварианта это означает, что предикат term истинен.Чтобы обосновать необходимое условие корректности, заметим, что после за­вершения вычисления не выполняется ни одно базовое действие. Следовательно,происходит только прием сообщений (ret, с), и с каждым приемом число сооб­щений на этапе пересылки сокращается на единицу.

Поэтому алгоритм достигаетзаключительной конфигурации. В такой конфигурации базовые сообщения от­сутствуют (по определению предиката term), для всех процессов р выполняетсяравенство credp = 0 (по определению предиката term и в силу требования S 3 )и отсутствуют сообщения (ret, с) (ибо конфигурация является заключительной).8.4. Прочие решения317Это означает, что ret = 1 (в силу требования Si) и завершение вычисления будетобнаружено.□Если применяется правило 5а, то число контрольных сообщений на единицупревосходит число базовых сообщений (мы принимаем в расчет также и сооб­щения, которые процесс ро отправляет самому себе, когда становится пассив­ным). Если применяется правило 5Ь, то число контрольных сообщений на единицупревосходит число внутренних событий в базовом вычислении, которое, в своюочередь, не более чем на единицу превосходит число базовых сообщений.

Пред­ставляется, что правило 5Ь более предпочтительно с точки зрения сложностипо числу сообщений контрольного алгоритма. Совсем иначе дело обстоит, когдаречь заходит о битовой сложности. По правилу 5а каждая доля кредита в си­стеме, за исключением ret, — это некоторая отрицательная степень числа 2 (т. е.она равна 2~1 для некоторого натурального /). Представляя кредит логарифмомпо основанию 1 / 2 , мы сокращаем битовую сложность передаваемых сообщений.Алгоритм возвращения кредита — единственный алгоритм в этой главе, кото­рый предусматривает включение дополнительной информации (значение кредита)в базовые сообщения.

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

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

Это повышение кредита приводит к блокировке базового вычисления вопрекитребованию, гласящему, что алгоритм обнаружения завершения вычисления недолжен оказывать влияния на базовое вычисление. К счастью, такие операциислучаются редко.8.4.2. Решения, использующие штемпель времениВ этом параграфе рассматриваются решения задачи обнаружения завершениявычисления, использующие в своей основе штемпели времени. Предполагается,что все процессы снабжены часами (см. §2.3.3); для этой цели пригодны какаппаратные таймеры, так и логические часы Лампорта (см. раздел 2.3.3).

Сампринцип обнаружения завершения вычислений был предложен в работе Раны[161].Гл. 8. Обнаружение завершения318var statep0punackpqtp:(active, passive):integer init 0 ;: integer init 0 ;: integer init 0 ;;(* Логические часы *)(* Число неподтвержденных сообщений *)(* Время недавно случившегосяперехода в quiet *)Sp: { statep = active }begin Bp := Bp + 1 ; send (mes, Bp) ; unackp := unackp + 1 endRp: { Сообщение (mes, 6 ) из q достигло p }begin receive (mes, 6 ); Bp := max(Bp, 6 ) + 1 ;send (ack, Bp) to q ; statep := activeendIp.

{ statep = active )begin Bp := Bp + 1 ; statep := passive ;if unackp = 0 then (* p переходит в состояние quite *)begin qtp := Bp ; send (tok, Bp, qtp, p) to Nextp endendAp: { Подтверждение (ack, 6 ) достигло p }begin receive (ack, 6 ) ; Bp := max(Bp, 6 ) + 1 ;unackp := unackp —1 ;if unackp = 0 and stateP = passive then (* p переходит в quiet *)begin qtp := Bp ; send (tok, Bp, qtp, p) to Nextp endendT„: { Маркер (tok, 0, qt, q) достиг p }begin receive (tok, 0 , qt, q) ; Bp := max(0 p, 0 ) + 1 ;if quiet(p) thenif p = q then Announceelse if qt > qtp then send (tok, Bp, qt, q) to NextpendАлгоритм 8.10. Алгоритм РаныКак и для решений из раздела 8.3.3, в основу решения Раны положен ло­кальный предикат quiet{p), определенный для каждого процесса р так, чтоquiet {р) = >stateр = passive AА никакое базовое сообщение, отправленное р,не пребывает на этапе пересылки,откуда следует импликация (Vp quiet(p )) =t> term.

Как и ранее, условие quietопределяется следующим соотношениемquiet{p) = (statep = passive A unackp = 0).Цель алгоритма— проверить, верно ли, что в определенный момент времени t всепроцессы удовлетворяют условию quiet. Отсюда следует, что в момент времениt вычисление завершилось. Это осуществляется при помощи волны, по ходу ко­торой каждому процессу задается вопрос о том, достиг ли этот процесс в данныймомент состояния quiet и будет ли он оставаться в этом состоянии в дальнейшем.8.4. Прочие решения319Всякий процесс, не пребывающий в состоянии quiet, не реагирует на сообщенияволны, тем самым эффективно гася саму волну.В отличие от решений, предложенных в разделе 8.5.3, взаимодействие волныс процессом р не оказывает влияния на переменные процесса р, используемыедля обнаружения завершения вычисления.

(Взаимодействие с волной может по­влиять на переменные самого волнового алгоритма, а также, в случае исполь­зования логических часов Лампорта, на часы процесса.) Вследствие этого пра­вильность работы нашего алгоритма не нарушается при параллельном распро­странении нескольких волн.Алгоритм Раны — это децентрализованный алгоритм; каждый процесс выпол­няет один и тот же алгоритм обнаружения завершения вычисления. Децентра­лизованный алгоритм может быть также получен и в том случае, если снабдитьпроцедуру из раздела 8.3.4 децентрализованным волновым алгоритмом.

То ре­шение, которое было предложено Раной, позволяет процессам инициировать ихсобственные волны, распространяемые параллельно.Процесс р, перейдя в состояние quiet, сохраняет в памяти тот момент вре­мени qtp, когда произошло это событие, и запускает волну, чтобы проверить, всели процессы уже перешли в состояние quiet к моменту времени qtp. Если этотак, то завершение вычисления считается обнаруженным. В противном случаесуществует процесс, который перейдет в состояние quiet позже, и он запуститновую волну. Именно по такому принципу устроен алгоритм 8.10, в котором ис­пользуются логические часы Лампорта, а в качестве волнового алгоритма выбранкольцевой алгоритм.Теорема 8.12.

Алгоритм Раны (алгоритм 8.10) является корректнымалгоритмом обнаружения завершения вычислений.Д о к а з а т е л ь с т в о . Чтобы обосновать необходимое условие коррект­ности, предположим, что для конфигурации у выполняется условие term , где аподтверждений все еще пребывают на этапе пересылки. Начиная с этого моментавыполняются только действия Ар и Тр. Коль скоро выполнение каждого действияАр приводит к сокращению на единицу числа сообщений (ack, 0), пребывающихна этапе пересылки, может быть совершено лишь конечное число таких шагов.Каждый процесс переходит в состояние quiet самое большее один раз; следова­тельно, маркеры порождаются не более N раз, и каждый маркер передается неболее N раз. Таким образом, спустя а + N2 шагов алгоритм обнаружения завер­шения вычисления достигает заключительной конфигурации 8 , в которой все ещевыполняется условие term.Обозначим символом ро процесс, у которого показатель времени qt в кон­фигурации 8 является максимальным, т.

Характеристики

Список файлов книги