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

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

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

Вычислением распределенного алгоритма называетсякласс эквивалентности выполнений алгоритма по отношению эквивалентностиНет смысла говорить о конфигурациях вычисления, потому что различныевыполнения одного и того же вычисления могут иметь разные конфигурации. Нопри этом имеет смысл говорить о совокупности событий вычисления, так как вовсех выполнениях одного и того вычисления происходят одни и те же события.Причинно-следственный порядок на множестве событий также однозначно опре­2.3. Причинно-следственный порядок событий и логические часы73деляется вычислением.

Мы будем называть вычисление конечным, если конечныего выполнения. Все выполнения одного и того же вычисления начинаются изодной и той же конфигурации и завершаются, если вычисление конечно, в однойи той же конфигурации (см. теорему 2.21); эти конфигурации называются началь­ной и заключительной конфигурациями вычисления. Мы будем отождествлятьвычисление с частично упорядоченным множеством событий, которые происхо­дят в нем.Как следует из теории частично упорядоченных множеств, два параллельныхсобытия одного и того же вычисления могут происходить в произвольном поряд­ке.Утверждение 2.23.П уст ь(.X , <) —част ично уп о р я д о чен н о е м нож е­с т в о и д л я д в у х э л е м е н т о в а , Ь е Х в ы п о л н я е т с я с о о т н о ш е н и е b </t а .

Т о г д асущ ест вует т а ка я ли н еа р и за ц и я < \ ча ст ичного п о р я д к а <, д ля кот о р о йв ы п о л н я е т с я с о о т н о ш е н и е а < \Ь .Это означает, что если а и b — параллельные события вычисления С , то су­ществуют два таких выполнения Е а и £), этого вычисления, в одном из которыхсобытие а происходит раньше события Ь, а в другом, наоборот, событие b про­исходит раньше события а . Процессам же по ходу выполнения неведомо, какоеиз этих двух событий происходит первым.Синхронный обмен сообщениями.

Модифицированный вариант теоремы 2.19можно сформулировать и для систем с синхронным обменом сообщениями. Какутверждается в этой теореме, в таких системах два последовательно произошед­ших события будут независимыми, если они затрагивают разные процессы.Теорема 2.24.

П р е д п о л о ж и м , ч т о у — к о н ф и г у р а ц и я р а с п р е д е л е н н о йс и с т е м ы с с и н х р о н н ы м о б м е н о м с о о б щ е н и я м и , и п у с т ь е\ — с и н х р о н н ы йп е р е х о д в п р о ц е с с а х р и q, а в 2 — с и н х р о н н ы й п е р е х о д в п р о ц е с с а х г и s,о т л и ч н ы х о т р и q, и п р и э т о м о б а с о б ы т и я е \ и е2 д о п у с т и м ы в к о н ­ф и гур а ц и иу.^(у).еДе 2 (у)) = £2(^1 (у))-Т о г д а п е р е х о д е\ д о п у с т и м в к о н ф и г у р а ц и идопуст им в конф игурацииеДу)и при эт омп е р е х о д е2Доказательство этой теоремы, в котором можно использовать те же рас­суждения, что в доказательстве теоремы 2.19, оставлено читателям в качествеупражнения (см.

упражнение 2.9). Понятие причинно-следственной зависимостив синхронных системах можно определить подобно тому, как это было сделанов определении 2.20; заинтересованные читатели могут обратиться к работе [48].Теорема, аналогичная теореме 2.21, будет также справедлива для синхронныхсистем.Выполнения и вычисления.

По ходу изложения мы вначале ввели поня­тие выполнения как пути в системе переходов и лишь затем ввели понятие вы­числения как класса эквивалентности на множестве выполнений. Такой поря­док расположения материала соответствует операционной точке зрения на функ­ционирование распределенных систем. Во многих других работах предпочтениеотдается более формальному подходу, при котором вначале определяется поня­74Гл.

2. Модельтие вычисления как частично упорядоченного множества событий и лишь затемвводится понятие выполнения как линеаризации этого частично упорядоченно­го множества. Такому подходу следуют, например, Чаррон-Бост и др. в работе[48], а также разработчики стандартного языка спецификаций Message SequenceCharts в работе [164]. Эти два подхода совершенно равноправны.2.3.3. Логические часыМы можем снабдить распределенные системы часами, при помощи которыхможно «отсчитывать» причинно-следственную зависимость, подобно тому какфизические часы отсчитывают реальное время. В этом параграфе букву 0 бу­дем использовать для обозначения функции, отображающей множество событийв некоторое упорядоченное множество (X , <).Определение 2.25.

Ч а с а м и назовем всякую функцию 0 , отображающуюмножество событий в некоторое упорядоченное множество так, что при этом вы­полняется соотношениеа -< b = >0(a) <0 (b ).Далее мы рассмотрим и обсудим некоторые примеры таких часов.1. П о с л е д о в а т е л ь н о е у п о р я д о ч е н и е . Для выполнения Е , представленногов виде последовательности событий (ео, в\, в2 , •••), положим 0§(е,-) = /. Такимобразом, каждое событие помечается порядковым номером, которое оно имеетв этой последовательности.Такой функцией может воспользоваться сторонний наблюдатель системы, ко­торый может наблюдать последовательность происходящих событий. Однако этупоследовательность нельзя наблюдать, пребывая в н у т р и системы; иначе гово­ря, распределенный алгоритм не способен вычислять функцию 0^.

Это следуетиз теоремы 2.19. Предположим, что какой-то распределенный алгоритм запи­сывает значение 0g(e,) = i для одного из тех событий е*, которые фигурируютв предпосылке теоремы. Рассмотрим теперь эквивалентное выполнение, в кото­ром изменен порядок осуществления двух событий; хотя значение функции Ogизменилось, процесс будет записывать то же самое значение г. Иными словами,функция Og определена на множестве выполнений, а не вычислений.2. Ч асы р е а л ь н о г о в р е м е н и .

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

Оказывается,эти «глобальные переходы» решительным образом изменяют всю модель: еслипредполагать наличие часов реального времени, то теорема 2.19 перестает быть2.3. Причинно-следственный порядок событий и логические часы75справедливой. Однако распределенные системы с часами реального времени име­ют практическое применение, и мы исследуем их в нашей книге в § 3.3.2 и в гл. 12и 15.3.Логические часы Лампорта. Лампорт в работе [124] предложил исполь­зовать часовую функцию, которая приписывает событию а число k, равное длинесамой протяженной последовательности событий (в\, .

. . , еД, удовлетворяющейусловиюе\ -<е 2 -<■■■-< е/г = а.Действительно, если а -< Ь, то эту последовательность можно продолжить так,чтобы выполнялось соотношение ©Да) < ©Д6). Значение ©ь для каждого собы­тия может быть вычислено распределенным алгоритмом по следующим правилам:а) если а — это внутреннее событие процесса или событие отправления со­общения, и а' — это предшествующее событие в том же самом процессе,то ©Да) = ©Да') + 1;б) если а — событие приема сообщения, а' — предшествующее событие в томже самом процессе, и b — событие отправления сообщения, соответству­ющее а, то ©Да) = т а х (0 Д а '), © Д Д ) + 1.Значение ©Да') полагается равным 0, если а — первое событие в процессе.Чтобы распределенный алгоритм мог вычислять показания часов, часовая от­метка последнего события, произошедшего в процессе р, записывается в пере­менную 0^ (ее начальное значение равно 0).

Чтобы вычислить часовую отметкусобытия приема, каждое сообщение т снабжается часовой отметкой 0Шсобытияотправления этого сообщения е. Показания логических часов Лампорта вычисля­ются алгоритмом 2.3. Для события е в процессе р значение © ДД равно величиневр сразу после осуществления события е, т. е. в тот момент, когда происходит из­менение состояния в процессе. В качестве упражнения читателям предлагаетсядоказать, что введенная таким образом функция Ор удовлетворяет определениючасов.var вр:integerinit 0 ;(* Внутреннее событие *)вр : = в р+ 1;Изменение состояния(* Событие отправления сообщения *)вр '.= вр + 1 ;send (messg, 0Д ; Изменение состояния(* Событие приема сообщения *)receive (messg, 0) ; вр := тах(вр, 0) + 1 ;Изменение состоянияАлгоритм 2.3.

Логические часы Лампорта76Гл. 2. МодельВ алгоритме не оговорены условия отправления сообщения или изменения со­стояния процесса. Эти часы играют роль вспомогательного механизма, которымможет быть снабжен любой распределенный алгоритм, для того чтобы оцениватьпорядок осуществления событий.4.В е к т о р н ы е ч а с ы . Иногда бывает удобно иметь часы, при помощи кото­рых можно отмечать не только причинно-следственный порядок (как того требуетопределение 2.25), но также и параллелизм. Параллелизм можно зафиксировать,если часовые пометки параллельных событий оказываются несравнимыми; этопроисходит, если в определении 2.25 место импликации занимает эквивалент­ность и возникает соотношениеa ~<b-*=^> 0 (a) <0 (b ).(2 . 1)Существование параллельных событий возможно только тогда, когда областьюзначений X функции часов является множество, которое упорядоченно частично,но не линейно.В в е к т о р н ы х ч а с а х Маттерна [144] X = Nw, т.

е. 0 „ (а )— это в е к т о р дли­ны 6) N . Векторы длины п можно естественным образом упорядочить, восполь­зовавшись следующим отношением покомпонентного сравнения:Введенный таким образом векторный порядок отличен от лексикографическогопорядка, который определен в упражнении 2.5 и является линейным порядком.Значением функции часов является вектор 0„(а) = (аь . .

. , ад/), в котором а,- —это число событий е, п р о и з о ш е д ш и х в п р о ц е с с е p i и удовлетворяющих соот­ношению е -< а. Подобно часам Лампорта, эта функция может быть вычисленараспределенным алгоритмом.Чаррон-Бост в своей работе [47] показал, что векторами меньшей длины дляэтой цели обойтись невозможно (если порядок на векторах определен соотноше­нием (2.2)).

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

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