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

Алгоритм глобальной разметки10.4.2. Алгоритм глобальной разметкиТеорема 10.14. Алгоритм глобальной разметки всегда завершает своюработу, и после завершения переменная alivep имеет значение true в томи только том случае, когда процесс p является действующим в конфигурации ∗ .В этом параграфе мы предлагаем алгоритм, который называется алгоритмом глобальной разметки, для обнаружения тупиков и выявления всех мертвыхпроцессов. Этот алгоритм постоянно вычисляет моментальные состояния системы и применяет к соответствующим им конфигурациям процедуру 10.8.

В этойпроцедуре значения state∗p , v∗p , Reqs∗p , Grant∗p , Pend∗p , Free∗p и (sent∗qp \ rcvd∗qp)считаются заданными константами (они вычисляются алгоритмом построения моментального состояния). В алгоритме 10.8 для выявления действующих процессов моделируется обмен разрешениями и освобождения процессов в продолжении вычисления из конфигурации ∗ .Д о к а з а т е л ь с т в о. Процесс p присваивает значение true переменнойalivep (и отправляет сопутствующие этому сообщения hAlivei) не более одногораза, и поэтому проводится обмен лишь конечным числом сообщений.Алгоритм разметки моделирует возможные продолжения вычислений базового алгоритма, начинающиеся из конфигурации ∗ , причем активными становятсялишь те процессы, у которых переменной alive присваивается значение true,а сообщениями-разрешениями служат сообщения hAlivei.

В моделируемом продолжении вычисления всякий процесс немедленно отправляет разрешение всемотложенным запросам, как только становится активным. Процесс p, выполняю-370Гл. 10. Моментальные состояния системыщий действие Mp , является активным в конфигурации ∗ . Этот процесс можеттакже стать активным в результате получения одного из тех сообщений, которыев конфигурации ∗ пребывают на этапе пересылки, и поэтому в этих случаях онсчитается действующим в ∗ . Процесс p, присвоивший переменной alivep значение true в результате выполнения действия Pp , также становится активнымв моделируемом продолжении вычисления, так как он получил разрешающее сообщение, которое было отправлено в этом продолжении; и это также означает,что процесс является действующим в ∗ .

Следовательно, все процессы p, у которых alivep = true в момент завершения работы алгоритмом разметки, являютсядействующими в ∗ .Осталось доказать обратное, а именно что если процесс p является действующим в конфигурации ∗ , то переменной alivep будет присвоено значениеtrue. Предположим, что p является действующим процессом в конфигурации ∗и (f1 , . . . , fl) — это продолжение вычисления из ∗ , приводящее к конфигурации, в которой p становится активным процессом.

Обратимся к последовательности конфигураций ( 0 , 1 , . . . , l), соответствующих данному продолжению, где∗и l= .0 =Воспользовавшись индукцией по i, покажем, что если i — это первая конфигурация (в последовательности, начинающейся 0 и заканчивающейся l), в которой процесс q является активным, то переменной alive q будет присвоено значениеtrue по ходу разметки.Случай i = 0. Коль скоро процесс q является активным в ∗ , он может выполнить действие Mq , присвоив тем самым переменной aliveq значение true.Случай i > 0. Процесс q оставался заблокированным во всех конфигурациях начиная с 0 и оканчивая i−1 , но стал активным при осуществлении событияfi . Очевидно, fi — это событие приема сообщения hgrant, v∗q i, которое расширилонабор Grantq до набора G, удовлетворяющего предикату Free ∗q (G).

Мы покажем,что для каждого r ∈ G процесс r будет рано или поздно включен в состав GrRec qалгоритмом разметки. Рассмотрим два случая.1. В конфигурации ∗ сообщение hgrant, v∗q i было на этапе пересылки отпроцесса r к процессу q. Тогда процесс r уже был включен в состав GrRec q ,когда проводилась инициализация алгоритма разметки; первоначально значениеGrRecq полагалось равным Grant∗q ∪ {r : hgrant, v∗q i ∈ sent∗rq \ rcvd∗rq }.2. Сообщение hgrant, vq i было отправлено при осуществлении одного из событий последовательности f1 , . . . , fi−1 .

Тогда либо (q, vq) ∈ Pendr , либо сообщение hreq, vq i находится на этапе пересылки к процессу r в конфигурации ; приэтом процесс r является активным в одной из конфигураций последовательности0 , . . . , i−2 . По индуктивному предположению алгоритм разметки присваиваетпеременной aliver значение true. Как только это случится, процесс r отправляетсообщение hAlivei процессу q, и после получения этого сообщения r заноситсяв GrRecq .Если сразу после инициализации выполняется включение G ⊆ GrRec q , то можно выполнять действие Mq , и в результате этого переменная aliveq примет значение true. В противном случае переменной aliveq будет присвоено значение trueпозднее, когда будет доставлено сообщение hAlivei, пополняющее множество G.10.4.

Приложения: обнаружение тупиков371В любом случае переменной alivep будет присвоено значение true.Завершение работы алгоритма 10.8 явно не обозначено, но его можно выявить при помощи какого-нибудь алгоритма обнаружения завершения вычисления (см. гл. 8). Как только завершение работы алгоритма глобальной разметки будет зафиксировано, мертвыми в конфигурации ∗ будут объявлены все теи только те процессы, у которых alivep = false.10.4.3.

Обнаружение тупиков в ограниченных моделяхМодель базового вычисления, которая использовалась в этом параграфе, является наиболее общей моделью при изучении проблемы обнаружения тупиков,и для этой модели известно совсем немного алгоритмов решения указанной задачи.Один из алгоритмов, также осуществляющий моделирование продолжениявычисления базового алгоритма, был предложен Бржезинским, Хелари, Рейнелом в работе [37] . В этом алгортитме все контрольные сообщения сосредоточеныв кольце, которое встраивается в коммуникационную сеть; по этому кольцу циркулирует маркер, и в нем указано множество процессов, о которых еще не сталоизвестно, являются ли они действующими.

Поскольку вся информация сконцентрирована в маркере, обнаружить завершение работы такого алгоритма разметкизначительно легче: стоит маркеру пройти полный круг, не совершив измененияприписанного ему множества, и завершение работы алгоритма будет зафиксировано.Задачу обнаружения тупиков часто изучают при наличии более строгих допущений, касающихся активизации процессов и допускающих описание тупиковыхситуаций в теоретико-графовых терминах. Обзор некоторых моделей и алгоритмов можно найти в статье Кнаппа [117] . Наиболее часто рассматриваются модели, в которых процессу, чтобы стать активным, необходимо получить разрешениеот всех процессов системы (AND-модель) или хотя бы от одного процесса системы (OR-модель).Тупиковая ситуация на уровне распределения ресурсов: AND-модель.Распределенная база данных состоит из совокупности файлов, рассредоточенных по большому числу сайтов (компьютеров).

Система управления базой данныхразрешает пользователям доступ к этим данным для чтения или для модификации. Доступ к данным открывается структурным методом посредством транзакций в базе данных, которые обычно направляют данные на разных сайтах.Ввиду разбросанности элементов данных нужно проследить за тем, чтобы избежать определенного чередования шагов, предпринимаемых различными транзакциями. Поэтому корректность операций над данными обычно обеспечиваетсяпосредством блокирования тех элементов данных, с которыми оперирует транзакция. И конечно же, если запрашиваемые данные уже заблокированы другойтранзакцией, то нашей транзакции приходится ожидать.Чтобы стать активной, транзакция должна получить доступ ко всем заблокированным элементам, которые ей требуются, т.

е. условие освобождения имеет372Гл. 10. Моментальные состояния системывид Freep (G) ≡ (G = Reqsp). Ограниченную модель тупиковых ситуаций, в которойвсе запросы должны быть удовлетворены, прежде чем процесс станет активным,называют AND-моделью.Можно показать, что в AND-модели наличие тупиковой ситуации равносильно существованию цикла в графе ожидания. Графом ожидания называется граф,вершинами которого являются процессы и при этом дуга pq проводится в томслучае, когда процесс p заблокирован в ожидании процесса q.

Алгоритмы поискациклов в таком графе были предложены, в частности, в работах Ченди, Мисрыи Хааса [50] , Минаска и Мюнца [146] , а также Митчелла и Меритта [150] .Тупиковая ситуация на уровне обмена информацией: OR-модель. Процесс, взаимодействующий с другими процессами в распределенном алгоритме,может перейти в заблокированное состояние, в котором единственно возможными событиями могут быть только события взаимосвязи с другими процессами.Осуществление всякого события взаимосвязи переводит этот процесс в другоесостояние, в котором он может продолжить свое вычисление. Следовательно,чтобы стать активным, такому процессу достаточно, чтобы был удовлетворен хотя бы один его запрос, т.

е. предикат Freep считается истинным на всяком непустом подмножестве семейства Reqsp . Ограниченная модель тупиковых ситуаций,в которой одного-единственного разрешения достаточно, чтобы процесс стал активным, называется OR-моделью.В OR-модели наличие тупиковой ситуации равносильно существованию узлав графе ожидания. Алгоритмы для этой модели были предложены, в частности,в работах Ченди, Мисры и Хааса [50] и Натараджана [153] .10.5.

Упражнения к главе 1010.5.1Упражнение 10.1. Будем рассматривать регистрацию моментального локального состояния процесса p как еще одно внутреннее событие a p . Докажите,чтоS∗ является значимым ⇐⇒ ∀p, q : ap k aq .10.5.2Упражнение 10.2. Дайте полное описание алгоритма Лая —Янга, включивв него механизм, принуждающий завершать построение моментальных состоянийи состояний каналов.Упражнение 10.3. Профессор Пржлвичковский пишет: «После того какя ознакомился с главой 10, я сумел лучше понять алгоритмы из главы 8. Например , в алгоритме Сафры (алгоритм 8.7) обработку маркеров процессом p нужнопонимать как вычисление моментального состояния процесса p.