Главная » Просмотр файлов » Введение в распределённые алгоритмы. Ж. Тель (2009)

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

Файл №1185665 Введение в распределённые алгоритмы. Ж. Тель (2009) (Введение в распределённые алгоритмы. Ж. Тель (2009).pdf) 98 страницаВведение в распределённые алгоритмы. Ж. Тель (2009) (1185665) страница 982020-08-25СтудИзба
Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 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 .

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

Тип файла
PDF-файл
Размер
18,19 Mb
Тип материала
Высшее учебное заведение

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

Свежие статьи
Популярно сейчас
А знаете ли Вы, что из года в год задания практически не меняются? Математика, преподаваемая в учебных заведениях, никак не менялась минимум 30 лет. Найдите нужный учебный материал на СтудИзбе!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
6521
Авторов
на СтудИзбе
302
Средний доход
с одного платного файла
Обучение Подробнее