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

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

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

Процессы занумерованы, нумерация ведется от р о до р м - \ , и кольце­вой алгоритм инициируется процессом ро путем отправления маркера процессур л/_ 1 . Процесс p i + 1 (для i < N — 1) переправляет этот маркер процессу p i . Обходмаркером кольца завершается, как только он будет возвращен обратно процессуРо-Первое решение такого рода, которое мы обсудим, — это алгоритм Дейкстры—Фейджена—ван Гастерена (§8.3.1).

Этот алгоритм обнаруживает заверше­300Гл. 8. Обнаружение завершенияние вычислений с синхронным обменом сообщениями. Сразу нескольким авторамудалось обобщить этот алгоритм для случая вычислений с асинхронным обменомсообщениями; главная проблема здесь состоит в проверке того, что каналы свя­зи пусты. Мы обсудим решение, предложенное Сафрой (см. §8.3.2), в которомкаждый процесс проводит подсчет числа отправленных и полученных сообще­ний.

Сравнивая показания счетчиков, можно на самом деле убедиться в том, чтоканалы пусты. Для этой цели можно также воспользоваться подтверждениями(§8.3.3); но это решение вновь требует, чтобы каналы были двунаправленными,и число контрольных сообщений будет по меньшей мере равно тому количествусообщений, которое используется алгоритмом Шави—Франчеза.В § 8.3.4 указанный принцип обнаружения завершения вычислений будет обоб­щен для случая произвольного волнового алгоритма.8.3.1. Алгоритм Дейкстры—Фейджена—ван Гастеренаvar statep : (active, passive) ;Cpq\ { stateP = active )begin (* процесс p отправляет базовое сообщение,и оно сразу же принимается процессом q *)stateq := activeend\p.{ statep = active }begin statep := passive endАлгоритм 8.5. Базовый алгоритм с синхронным обменом сообщениямиАлгоритм Дейкстры, Фейджена и ван Гастерена [6 6 ] обнаруживает завершениебазового вычисления, в котором используется синхронный обмен сообщениями;действия подобного вычисления приведены на примере алгоритма 8.5.

Для такихвычислений условие их завершения имеет следующий вид:term -<=>- V/ 7 : statep = passive.Можно сравнить приведенный алгоритм и условие term с алгоритмом 8.1 и тео­ремой 8 . 1 .Построение алгоритма состоит из ряда небольших шагов. Каждый шаг можнолегко понять, а корректность алгоритма является следствием одного инварианта,который мы построим вместе с самим алгоритмом. Такой подход заимствован изстатьи [6 6 ]. В дальнейшем символом t условимся обозначать номер того процес­са, который удерживает маркер или должен получить маркер, если этот маркерпребывает на этапе пересылки. Только процесс pt может осуществить передачумаркера, и при этом t уменьшится на 1.

Волна угасает, когда t = 0, и, следова­тельно, инвариант Р должен быть выбран так, чтобы о завершении вычисленияможно было судить на основе самого Р, того факта, что t = 0, и дополнительной8.3. Решения на основе волновых алгоритмов301информации, представленной в процессе р о. Инвариантное соотношение должнособлюдаться, когда ро запускает волну, т. е. когда t = N — 1.В качестве первого приближения будем полагать, что Р = Р о , где Ро задаетсяследующим соотношением:Ро= V/ (N > i > t): statePi = passive.И в самом деле, Р о обращается в истину, когда t = N — 1, и если выполняютсяравенства t = 0 и statePo = passive, то отсюда мы заключаем, что вычислениезавершилось. При передаче маркера Р о сохраняет справедливость только тогда,когда в передаче участвуют одни лишь пассивные процессы; значит, нам прихо­дится ввести следующее правило.Правило 1.

Только пассивный процесс обладает маркером.При таком режиме работы условие Р сохраняется при передаче маркера,а также при выполнении внутренних действий; к сожалению, Р не сохраняетсяпри выполнении коммуникационных действий. Предикат P q может быть опро­вергнут, если процесс р/ активизируется таким процессом pt, что / > t и i ^ t(см. упражнение 8.4).

Так как Р о можно опровергнуть, в качестве Р выбираетсяменее жесткое утверждение (Ро V Pi), причем Pi выбирается так, чтобы в слу­чае каждого опровержения предиката Ро предикат Pi обращался в истину. Мыбудем полагать, что каждый процесс может иметь некоторый цвет, который зада­ется переменной color, эта переменная может иметь одно из двух значений whiteили black.

Положим Р = (P q V Pi), где предикат Р\ определяется соотношениемPi = 3/ (t > / > 0 ) : colorPi = black.Всякий раз, когда предикат Ро опровергается, предикат Pi либо уже выполняется,либо должен обратиться в истину, если процесс-отправитель окрашен в цветblack.Правило 2. Всякий процесс-отправитель имеет цвет black.Коль скоро имеет место соотношение (Р Л colorРо = white A t = 0) = > - P i ,мы можем обнаружить завершение вычисления и при помощи нового инварианта,а именно оценив окрашен ли процесс ро в цвет white (будучи при этом пассив­ным), когда он владеет маркером.Ослабление условия Р успешно предотвращает его опровержение при выпол­нении коммуникационных действий; но и ослабленное утверждение можно опро­вергнуть при передаче маркера, а именно в том случае, когда процесс pt являетсяединственным процессом, окрашенным в цвет black, и при этом осуществляетпередачу маркера.

Чтобы спасти ситуацию, требуется дальнейшее ослаблениеусловия Р. Будем предполагать, что маркер тоже окрашен (в один из двух цветовwhite или black), а Р имеет вид (Ро V Pi V Р2), где предикат Pi определяетсясоотношениемРг = маркер окрашен в цвет black.Предикат Р 2 сохраняется при передаче маркера, если процессы, окрашенныев цвет black, передают маркер того же цвета.Правило 3. Если процесс, окрашенный в цвет black и отличный от р о , пере­дает маркер, то маркер также приобретает окраску black.302Гл. 8. Обнаружение завершенияТак как верно соотношение (маркер окрашен в цвет white) =4- -iР2 , за­вершение вычисления может быть обнаружено процессом ро, а именно путемпроверки того, получил ли этот процесс маркер цвета white (будучи при этомпассивным и окрашенным в цвет white).И в самом деле, теперь можно убедиться в том, что внутренние действия, об­мен базовыми сообщениями и передача маркера не нарушают истинности преди­ката Р.

Но за счет окрашивания маркера в цвет black возникает эффект неудач­ных волн ; процесс ро не способен выявить завершение вычисления, если полу­ченный им маркер имел цвет black. Если одна волна оканчивается неудачно, тодолжна быть запущена новая волна.Правило 4.

Когда одна волна оканчивается неудачно, процесс ро запускаетновую волну.Конечно, и следующая волна так же завершится неудачей, как и ее предше­ственница, если процесс, окрашенный в цвет black, не будет иметь возможностивновь приобрести окраску white. Действительно, процессы, окрашенные в цветblack, придадут такой же цвет маркеру, когда будут передавать его, и поэтомуочередная волна будет неудачной.var s t a t e pc o lo r p: (a c t i v e , p a s s i v e ) ;: ( w h i t e , b la c k ) ;C pq: { s t a t e p — a c t i v e }begin (* процесс pотправляет базовое сообщение,которое получает процесс q *)c o lo r p := b la c k ;(* Правило 2 *)s t a t e q := a c t i v eendIp \{ s t a te p = a ctive )begin s t a t e p := p a s s i v e endПриступить к обнаружению завершения вычисления,выполняется один раз процессом р о :begin send (tok, w h i t e ) to p ^ - \ endT„: (* Процессp обладает маркером (tok, c) *){ s t a t e p = p a s s i v e } (* Правило 1 *)begin if p = p 0then if (c = w h i t e A colo rp = w h i t e )then A n n o u n c eelse send (tok, w h i t e ) to р ц - 1 (* Правило 4 *)else if (c o lo r p = w h i t e ) (* Правило 3 *)then send (tok, c) to N e x t pelse send (tok, b la c k ) to N e x t p ;c o lo r p \= w h i t e(* Правило 5 *)endАлгоритм 8.6.

Алгоритм Дейкстры—Фейджена—ван Гастерена8.3. Решения на основе волновых алгоритмов303Заметим, что процесс pi, обретший окраску white, не опровергает Р, еслиi > t, а также что условие Р всегда будет выполнено, когда ро запускает волну,передавая маркер процессу ры-\- Отсюда следует, что процесс можно всегдабезопасно перекрасить в цвет white после передачи маркера.Правило 5. Каждый процесс приобретает цвет white сразу после передачимаркера.Этого режима установления цвета white вполне достаточно, чтобы обеспе­чить успех одной из волн после завершения базового вычисления. Приведенныерассуждения представлены в виде алгоритма 8 .6 .Теорема 8 .8 . Алгоритм Дейкстры — Фейджена— ван Гастерена (алго­ритм 8 .6 ) является корректным алгоритмом обнаружения завершениябазовых вычислений с синхронным обменом сообщениями.Д о к а з а т е л ь с т в о .

Предикат Р определяется формулой Ро V Pi V Рг,а сам алгоритм устроен так, что Р является инвариантом этого алгоритма. З а ­вершение базового вычисления обнаруживается, когда пассивный процесс ро,окрашенный в цвет white, владеет маркером, который также окрашен в цветwhite. И действительно, когда это происходит, окраска маркера означает, чтовыполняется условие ^Рг, окраска процесса ро и тот факт, что t = 0 , означают,что выполняется условие - P i , а выполнимость условия Ро и то состояние, в ко­тором пребывает процесс ро, приводят к заключению о выполнимости предикатаterm.

Таким образом, достаточное условие корректности обеспечено.Чтобы обосновать необходимое условие корректности, предположим, что ба­зовое вычисление завершилось. Начиная с этого момента, все процессы по по­лучении маркера передают его без задержки. Когда маркер завершает полныйобход кольца в первый раз после завершения базового вычисления, все процес­сы будут иметь окраску white, а когда маркер обойдет кольцо вторично, будетобнаружено, что базовое вычисление завершилось.□Теперь мы попытаемся оценить число контрольных сообщений, используе­мых рассматриваемым алгоритмом.

Базовое вычисление, фигурирующее в до­казательстве теоремы 8 .2 , вынуждает маркер совершать по меньшей мере одинобход кольца для каждой пары базовых сообщений; значит, в худшем случаеалгоритму потребуется ^ NM контрольных сообщений (см. упражнение 8.5).Но данный алгоритм может использовать гораздо меньше сообщений в сред­нем, когда анализируется «произвольное» вычисление. Предположим, что слож­ность базового вычисления по времени равна Т.

Поскольку маркер всегда пере­дается последовательно, вполне разумно полагать, что он будет передан прибли­зительно Т раз, прежде чем базовое вычисление завершится. (И даже эта оценкаможет оказаться чрезмерно завышенной, так как только активные процессы от­кладывают передачу маркера.) Поскольку маркер передается менее ЗЛ/ раз послезавершения базового вычисления, нашему алгоритму требуется в таком случаесовершить менее Т + 3N обменов контрольными сообщениями.

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

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