Введение в распределённые алгоритмы. Ж. Тель (2009) (не распознанно) (1185664), страница 80
Текст из файла (страница 80)
Только пассивный процесс обладает маркером.При таком режиме работы условие P сохраняется при передаче маркера,а также при выполнении внутренних действий; к сожалению, P не сохраняетсяпри выполнении коммуникационных действий. Предикат P 0 может быть опровергнут, если процесс pj активизируется таким процессом pi , что j > t и i 6 t(см. упражнение 8.4). Так как P0 можно опровергнуть, в качестве P выбираетсяменее жесткое утверждение (P0 ∨ P1), причем P1 выбирается так, чтобы в случае каждого опровержения предиката P0 предикат P1 обращался в истину. Мыбудем полагать, что каждый процесс может иметь некоторый цвет, который задается переменной color; эта переменная может иметь одно из двух значений whiteили black.
Положим P = (P0 ∨ P1), где предикат P1 определяется соотношениемP1 ≡ ∃j (t > j > 0) : colorpj = black.Всякий раз, когда предикат P0 опровергается, предикат P1 либо уже выполняется,либо должен обратиться в истину, если процесс-отправитель окрашен в цветblack.Правило 2. Всякий процесс-отправитель имеет цвет black.Коль скоро имеет место соотношение (P ∧ colorp0 = white ∧ t = 0) =⇒ ¬P1 ,мы можем обнаружить завершение вычисления и при помощи нового инварианта,а именно оценив окрашен ли процесс p0 в цвет white (будучи при этом пассивным), когда он владеет маркером.Ослабление условия P успешно предотвращает его опровержение при выполнении коммуникационных действий; но и ослабленное утверждение можно опровергнуть при передаче маркера, а именно в том случае, когда процесс p t являетсяединственным процессом, окрашенным в цвет black, и при этом осуществляетпередачу маркера. Чтобы спасти ситуацию, требуется дальнейшее ослаблениеусловия P.
Будем предполагать, что маркер тоже окрашен (в один из двух цветовwhite или black), а P имеет вид (P0 ∨ P1 ∨ P2), где предикат P1 определяетсясоотношениемP2 ≡ маркер окрашен в цвет black.Предикат P2 сохраняется при передаче маркера, если процессы, окрашенныев цвет black, передают маркер того же цвета.Правило 3. Если процесс, окрашенный в цвет black и отличный от p 0 , передает маркер, то маркер также приобретает окраску black.302Гл. 8.
Обнаружение завершенияТак как верно соотношение (маркер окрашен в цвет white) =⇒ ¬P 2 , завершение вычисления может быть обнаружено процессом p 0 , а именно путемпроверки того, получил ли этот процесс маркер цвета white (будучи при этомпассивным и окрашенным в цвет white).И в самом деле, теперь можно убедиться в том, что внутренние действия, обмен базовыми сообщениями и передача маркера не нарушают истинности предиката P. Но за счет окрашивания маркера в цвет black возникает эффект неудачных волн; процесс p0 не способен выявить завершение вычисления, если полученный им маркер имел цвет black.
Если одна волна оканчивается неудачно, тодолжна быть запущена новая волна.Правило 4. Когда одна волна оканчивается неудачно, процесс p 0 запускаетновую волну.Конечно, и следующая волна так же завершится неудачей, как и ее предшественница, если процесс, окрашенный в цвет black, не будет иметь возможностивновь приобрести окраску white. Действительно, процессы, окрашенные в цветblack, придадут такой же цвет маркеру, когда будут передавать его, и поэтомуочередная волна будет неудачной.var statep : (active, passive) ;colorp: (white, black) ;Cpq : { statep = active }begin (* процесс p отправляет базовое сообщение,которое получает процесс q *)colorp := black ;(* Правило 2 *)stateq := activeendIp :{ statep = active }begin statep := passive endПриступить к обнаружению завершения вычисления,выполняется один раз процессом p0 :begin send htok, whitei to pN−1 endTp : (* Процесс p обладает маркером htok, ci *){ statep = passive } (* Правило 1 *)begin if p = p0then if (c = white ∧ colorp = white)then Announceelse send htok, whitei to pN−1 (* Правило 4 *)else if (colorp = white) (* Правило 3 *)then send htok, ci to Nextpelse send htok, blacki to Nextp ;colorp := white (* Правило 5 *)endАлгоритм 8.6.
Алгоритм Дейкстры—Фейджена—ван Гастерена8.3. Решения на основе волновых алгоритмов303Заметим, что процесс pi , обретший окраску white, не опровергает P, еслиi > t, а также что условие P всегда будет выполнено, когда p 0 запускает волну,передавая маркер процессу pN−1 . Отсюда следует, что процесс можно всегдабезопасно перекрасить в цвет white после передачи маркера.Правило 5. Каждый процесс приобретает цвет white сразу после передачимаркера.Этого режима установления цвета white вполне достаточно, чтобы обеспечить успех одной из волн после завершения базового вычисления. Приведенныерассуждения представлены в виде алгоритма 8.6.Теорема 8.8.
Алгоритм Дейкстры—Фейджена—ван Гастерена (алгоритм 8.6) является корректным алгоритмом обнаружения завершениябазовых вычислений с синхронным обменом сообщениями.Д о к а з а т е л ь с т в о. Предикат P определяется формулой P 0 ∨ P1 ∨ P2 ,а сам алгоритм устроен так, что P является инвариантом этого алгоритма. Завершение базового вычисления обнаруживается, когда пассивный процесс p 0 ,окрашенный в цвет white, владеет маркером, который также окрашен в цветwhite. И действительно, когда это происходит, окраска маркера означает, чтовыполняется условие ¬P2 , окраска процесса p0 и тот факт, что t = 0, означают,что выполняется условие ¬P1 , а выполнимость условия P0 и то состояние, в котором пребывает процесс p0 , приводят к заключению о выполнимости предикатаterm.
Таким образом, достаточное условие корректности обеспечено.Чтобы обосновать необходимое условие корректности, предположим, что базовое вычисление завершилось. Начиная с этого момента, все процессы по получении маркера передают его без задержки. Когда маркер завершает полныйобход кольца в первый раз после завершения базового вычисления, все процессы будут иметь окраску white, а когда маркер обойдет кольцо вторично, будетобнаружено, что базовое вычисление завершилось.Теперь мы попытаемся оценить число контрольных сообщений, используемых рассматриваемым алгоритмом.
Базовое вычисление, фигурирующее в доказательстве теоремы 8.2, вынуждает маркер совершать по меньшей мере одинобход кольца для каждой пары базовых сообщений; значит, в худшем случае1алгоритму потребуется NM контрольных сообщений (см. упражнение 8.5).2Но данный алгоритм может использовать гораздо меньше сообщений в среднем, когда анализируется «произвольное» вычисление. Предположим, что сложность базового вычисления по времени равна T. Поскольку маркер всегда передается последовательно, вполне разумно полагать, что он будет передан приблизительно T раз, прежде чем базовое вычисление завершится.
(И даже эта оценкаможет оказаться чрезмерно завышенной, так как только активные процессы откладывают передачу маркера.) Поскольку маркер передается менее 3N раз послезавершения базового вычисления, нашему алгоритму требуется в таком случаесовершить менее T + 3N обменов контрольными сообщениями. И хотя сложность базового вычисления равна T (речь идет о сложности по времени), но есливычисление обладает достаточным параллелизмом, то его сложность по числу304Гл.
8. Обнаружение завершениясообщений может оценена величиной Ω (NT). Если параллелизм позволяет каждому процессу отправлять некоторое постоянное число сообщений за единицувремени, сложность базового вычисления по числу сообщений может достигатьвеличины NT , т. е. Ω (NT). Таким образом, количество контрольных сообщений,оцениваемое величиной O(N + T), оказывается тогда гораздо меньшим, чем можнобыло бы ожидать исходя из сложности задачи обнаружения завершения вычисления в наихудшем случае.8.3.2. Подсчет базовых сообщений: алгоритм СафрыСинхронный обмен сообщениями, присущий базовому вычислению валгоритме Дейкстры—Фейджена—ван Гастерена, существенно ограничивает общее применение этого алгоритма.
Ряд авторов обобщили указанный алгоритм на случайвычислений с асинхронным обменом сообщениями (см., например, алгоритм 8.1).В данном параграфе мы обсудим решение Сафры (см. [63]); оно обладает темсвойством, что его сложность в среднем сравнима со сложностью алгоритмаДейкстры—Фейджена—ван Гастерена.Для каждой конфигурации обозначим символом B число сообщений, находящихся на этапе пересылки.
Тогда предикат term эквивалентен следующей формуле:(∀p : statep = passive) ∧ B = 0.Разработаем вновь инвариант P таким образом, чтобы заключение о завершениивычисления можно было вынести на основе P, равенства t = 0 и некоторойинформации, предоставленной процессом p0 . Инвариант должен соблюдаться,когда p0 запускает волну, т. е. при t = N − 1.Чтобы сделать информацию о значении B доступной процессам (хотя быв распределенном виде), снабдим процесс p счетчиком сообщений mc p так, чтобыпроцессы придерживались как инварианта условия P m следующего вида:XPm ≡ B =mcp .p∈PИнвариантность условия Pm будет соблюдена, если первоначально полагать mc p == 0 для каждого процесса p и потребовать, чтобы все процессы подчинялисьследующему правилу.Правило M.
Когда процесс p отправляет сообщение, он увеличивает значение своего счетчика; когда процесс p получает сообщение, он уменьшает значениесвоего счетчика.Такой инвариант должен предоставлять процессу p 0 возможность принятьрешение о выполнимости условия term, после того как он получит маркер (t == 0). Так как term теперь включает ограничение, налагаемое на значение B,мы будем использовать маркер для передачи целого числа q, чтобы суммироватьпоказания счетчиков сообщений всех тех процессов, в которых побывал этотмаркер.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
