Введение в распределённые алгоритмы. Ж. Тель (2009) (1185665), страница 98
Текст из файла (страница 98)
Следовательно, все процессы р, у которых alivep = true в момент завершения работы алгоритмом разметки, являютсядействующими в у*.Осталось доказать обратное, а именно что если процесс р является действующим в конфигурации у*, то переменной aliveр будет присвоено значениеtrue. Предположим, что р является действующим процессом в конфигурации у*и (/ i, . . . , //) — это продолжение вычисления из у * , приводящее к конфигурации8 , в которой р становится активным процессом. Обратимся к последовательности конфигураций (уо, у ь . . . , у/), соответствующих данному продолжению, гдеуо = у* и у/ = 8.Воспользовавшись индукцией по г, покажем, что если у, — это первая конфигурация (в последовательности, начинающейся уо и заканчивающейся у/), в которой процесс q является активным, то переменной aliveq будет присвоено значениеtrue по ходу разметки.Случай i = 0.
Коль скоро процесс q является активным в у*, он может выполнить действие М?, присвоив тем самым переменной aliveq значение true.Случай i > 0. Процесс q оставался заблокированным во всех конфигурациях начиная с уо и оканчивая у;_ь но стал активным при осуществлении события/). Очевидно, fi — это событие приема сообщения (grant, v*), которое расширилонабор Grantq до набора G, удовлетворяющего предикату Free*(G).
Мы покажем,что для каждого г <ЕG процесс г будет рано или поздно включен в состав GrRecqалгоритмом разметки. Рассмотрим два случая.1. В конфигурации у* сообщение (grant, v*q) было на этапе пересылки отпроцесса г к процессу q. Тогда процесс г уже был включен в состав GrRecq,когда проводилась инициализация алгоритма разметки; первоначально значениеGrRecq полагалось равным Grant* U {г : (grant, v*) € sent*q \ rcvd*q}.2. Сообщение (grant, vq) было отправлено при осуществлении одного из событий последовательности f\, .
. . , /)_ i. Тогда либо (q, vq) &Pendr, либо сообщение (req, vq) находится на этапе пересылки к процессу г в конфигурации у; приэтом процесс г является активным в одной из конфигураций последовательностиТо, • • •, У;—2 - По индуктивному предположению алгоритм разметки присваиваетпеременной aliver значение true. Как только это случится, процесс г отправляетсообщение (Alive) процессу q, и после получения этого сообщения г заноситсяв GrRecq.Если сразу после инициализации выполняется включение GQGrRecq, то можно выполнять действие Mq, и в результате этого переменная aliveq примет значение true. В противном случае переменной aliveq будет присвоено значение trueпозднее, когда будет доставлено сообщение (Alive), пополняющее множество 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 проводится в томслучае, когда процесс р заблокирован в ожидании процесса q. Алгоритмы поискациклов в таком графе были предложены, в частности, в работах Ченди, Мисрыи Хааса [50], Минаска и Мюнца [146], а также Митчелла и Меритта [150].Тупиковая ситуация на уровне обмена информацией: OR-модель. Процесс, взаимодействующий с другими процессами в распределенном алгоритме,может перейти в заблокированное состояние, в котором единственно возможными событиями могут быть только события взаимосвязи с другими процессами.Осуществление всякого события взаимосвязи переводит этот процесс в другоесостояние, в котором он может продолжить свое вычисление. Следовательно,чтобы стать активным, такому процессу достаточно, чтобы был удовлетворен хотя бы один его запрос, т.
е. предикат Freep считается истинным на всяком непустом подмножестве семейства Reqsp. Ограниченная модель тупиковых ситуаций,в которой одного-единственного разрешения достаточно, чтобы процесс стал активным, называется OR-моделью.В OR-модели наличие тупиковой ситуации равносильно существованию узлав графе ожидания. Алгоритмы для этой модели были предложены, в частности,в работах Ченди, Мисры и Хааса [50] и Натараджана [153].10.5. Упражнения к главе 1010.5.1Упражнение 10.1. Будем рассматривать регистрацию моментального локального состояния процесса р как еще одно внутреннее событие ар. Докажите,чтоS* является значимым -^=^> Мр, q : ар || aq.10.5.2Упражнение 10.2. Дайте полное описание алгоритма Л ая—Янга, включивв него механизм, принуждающий завершать построение моментальных состоянийи состояний каналов.Упражнение 10.3.
Профессор Пржлвичковский пишет: «После т о г о какя ознакомился с главой 10, я сумел лучше понять алгоритмы из главы 8 . Например, в алгоритме Сафры (алгоритм 8.7) обработку маркеров процессом р нужнопонимать как вычисление моментального состояния процесса р. В построенноммоментальном состоянии системы все процессы являются пассивными, так какмаркер обрабатывается только пассивными процессами. Поэтому для вычисления зна чения Pholds требуется всего лишь проверить, пусты ли все каналы.
Д ля10.5. Упражнения к главе 10373этого в маркере указывается суммарное значение счетчиков сообщ ений. Однакомне неясна та р о л ь , которую играют окраски w h ite и b la ck , а также как удаетсяобеспечить значимость моментальных состояний системы.»Не могли бы Вы помочь профессору?ГЛАВА11ВОСПРИЯТИЕ НАПРАВЛЕНИЯ И ОРИЕНТАЦИЯВ сетях, имеющих регулярную структуру, наподобие торов или гиперкубов,в соединительных линиях обычно указывается их направление. Мы обсудим здесьрезультаты сравнительно недавних исследований, оценивающих ту пользу, которую приносит подобная разметка; эту разметку мы будем называть восприятием направления или сокращенно SoD 6 .