Введение в распределённые алгоритмы. Ж. Тель (2009) (1185665), страница 51
Текст из файла (страница 51)
(Вспомните, как устроен протокол раздвижного окна, описанный в §3.3.1,в котором слова удаляются из массива outp только после того, как будут получены все слова с меньшим значением индекса.) Вследствие этого нарушаетсянаше предположение о том, что пакет, который достиг узла-адресата, может бытьвсегда поглощен.Блокировку сборки пакета можно предотвратить, если использовать отдельные группы буферов для продвигающихся пакетов и пакетов, которые участвуютв сборке.5.4.3. Активный тупикКак следует из определения заблокированных пакетов (определение 5.2), длякаждого пакета, находящегося под управлением беступикового контроллера, естьхотя бы одно вычисление, в котором этот пакет будет поглощен.
Но так как число различных допустимых вычислений, вообще говоря, очень велико, это отнюдьне подразумевает того, что каждый пакет рано или поздно будет доставлен поназначению даже в том случае, когда вычисление может продолжаться скольугодно долго. Достаточно взглянуть на пример, изображенный на рис. 5.6.
Предположим, что в узле и берет начало бесконечный поток пакетов, которые нужноотправить в узел v, и всякий раз, когда буфер в узле да освобождается, очередному пакету из узла и разрешается совершить продвижение. В узле s имеется пакет,адресованный узлу t, и этот пакет не заблокирован, потому что всякий раз, когда190Гл. 5. Неблокируемая коммутация пакетовбуфер в узле да освобождается, существует такое возможное продолжение вычисления, по ходу которого этому самому пакету будет разрешено продвинутьсяв узел да и затем достичь узла t. Хотя такое продолжение вычисления являетсявозможным, оно не является неизбежным, и пакет может навеки остаться в узле.Ситуацию такого рода принято называть активным тупиком.Возможности тех контроллеров, которые мы изучили в этой главе, можно такрасширить, чтобы они могли предотвращать также и активные тупики.Определение 5.23.
Пусть задана некоторая сеть, контроллер con и конфигурация у. Тогда пакет р считается оставленным без внимания , если существует бесконечная последовательность действий, применимых к конфигурацииу, при выполнении которых пакет р не будет поглощен.Конфигурация у называется активной тупиковой конфтигурацией, если в этойконфигурации есть хоть один пакет, оставленный без внимания.Говорят, что контроллер избегает активных тупиков, из конфигурации, в которой нет никаких пакетов, нельзя достичь ни одной активной тупиковой конфигурации.Далее в этом параграфе мы докажем, что контроллеры с буферным графомизбегают активных тупиков.
В самом конце мы вкратце обсудим, как поступитьс неструктурированными решениями.Контроллер с буферным графом. Можно показать, что все контроллеры,описанные в § 5.5.2, избегают активных тупиков без всякой модификации их действий, если на бесконечных вычислениях соблюдаются допущения строгой спра ведливости F1 и F2, а также допущение слабой справедливости F3.F1. Если непрерывно предпринимаются попытки сформировать пакет р, токаждое бесконечное вычисление, в котором буфер fb(p) оказывается свободнымв бесконечном множестве конфигураций, обязательно содержит пакет р.F2. Если в конфигурации у пакет р должен быть отправлен из узла и в узелда, то в каждом бесконечном вычислении, начинающемся конфигурацией у и име5.4.
Прочие вопросы191ющем пустой буфер nb(p, Ь) в бесконечном множестве конфигураций, происходитпродвижение пакета р.F3. Если пакет р в конфигурации у достиг своего узла-адресата, то в каждомбесконечном вычислении, начинающемся конфигурацией у, происходит поглощение пакета р.Лемма 5.24. Если соблюдаются допущения справедливости F2 и F3,то в любом бесконечном вычислении под управлением контроллера bgcкаждый буфер оказывается свободным бесконечно часто.Д о к а з а т е л ь с т в о . Доказательство проводится с использованием нисходящей индукции по классам буферов. Как и в доказательстве теоремы 5.7,обозначим символом R наибольший класс буферов. Напоминаем, что в конфигурациях, которые можно достичь под управлением контроллера bgc, все пакетыпомещаются в подходящие буферы.Случай г = R . Буфер класса R не имеет исходящих дуг в буферном графе,и поэтому пакет, помещенный в такой буфер, уже достиг своего узла-адресата.Следовательно, согласно допущению F3 после каждой конфигурации, в которойэтот буфер занят, рано или поздно будет достигнута конфигурация, в которойэтот буфер пуст.
Это означает, что буфер свободен бесконечно часто.Случай г < R . Рассмотрим конфигурацию у, в которой буфер b класса г << R занят пакетом р. Если р уже достиг предназначенного узла, то согласнодопущению F3 позднее будет достигнута конфигурация, в которой буфер b освободится. В противном случае пакет р должен быть переправлен в буфер nb(p, Ь),который имеет буферный класс г' > г.
По индуктивному предположению в каждом бесконечном вычислениии, которое начинается конфигурацией у, этот буферосвобождается бесконечно часто. В силу допущения F2 отсюда следует, что пакетр будет продвигаться бесконечно часто, и, значит, после конфигурации у будетдостигнута конфигурация, в которой буфер b будет пустым.□Теорема 5.25. Если соблюдаются допущения справедливости F I, F2 и F3,то в любом бесконечном вычислении под управлением контроллера bgcкаждый пакет, который может возникнуть в сети, будет поглощен всоответствующем узле-адресате.Д о к а з а т е л ь с т в о .
Flo лемме 5.24 все буферы оказываются пустымив бесконечно многих конфигурациях. Согласно допущению F1 это означает, чтокаждый пакет, который пытаются ввести в сеть бесконечно часто, рано или поздно будет сформирован. Согласно допущению F2 он будет продвигаться, до техпор пока не достигнет своего узла-адресата.
Согласно допущению F3 он будетпоглощен в узле-адресате.□Можно предполагать, что механизм недетерминированного выбора в распределенных системах просто обеспечивает выполнимость трех упомянутых допущений. В противном случае соблюдение этих допущений может быть навязанопутем встраивания в контроллер специальной процедуры, которая в случае освобождения буфера будет отдавать приоритет тем пакетам, которые имеют болеепродолжительный возраст.192Гл. 5.
Неблокируемая коммутация пакетовНеструктурированные решения. Чтобы контроллеры, описанные в §5.5.3,могли избегать активных тупиков, их нужно модифицировать. В этом можно убедиться, построив бесконечное вычисление, в котором непрерывный поток пакетовможет привести к тому, что контроллер запретит продвижение какого-то другогопакета. Туэг в работе [195] привел пример такого вычисления для контроллераFC и представил такую модификацию контроллера FS (аналогичную рассмотренной нами модификации контроллеров с буферным графом), которая позволяетизбегать активных тупиков.5.5.
Упражнения к главе 55.5.1Упражнение 5.1. Покажите, что не существует беступиковых контроллеров,которые используют только по одному буферу в каждом узле и разрешают каждому узлу отправлять пакет в какой-то другой узел.5.5.2Упражнение 5.2. Покажите, что контроллер dest не будет являться беступиковым, если маршрутизация пакетов проводится так, как показано на рис. 5.2.Упражнение 5.3.
(Схема предстоящих шагов) Опишите устройство буферного графа, а также функции fb и nb для контроллера, использующего буферba[i\ для хранения пакетов, которым предстоит совершить i продвижений, чтобыдостичь своих узлов-адресатов.Как определить буферный класс для /?„[/]? Должен ли каждый пакет вести учетсделанных шагов?Упражнение 5.4. Завершите доказательство утверждения о том, что граф5G a (определенный в доказательстве теоремы 5.13) действительно является буферным графом, т. е.
для каждого пути Р Е V существует гарантированный путь,образом которого является Р. Покажите, что функции fb и nb действительно, какутверждается в доказательстве теоремы, описывают путь в буферном графе BGa.Курсовая работа 5.5. Докажите, что существует такой беступиковый контроллер, который осуществляет коммутацию пакетов в гиперкубе, используя приэтом только два буфера в каждом узле и разрешая проводить маршрутизациюпакетов по путям с наименьшим числом звеньев.Можно ли получить совокупность используемых путей при помощи интервального алгоритма маршрутизации (см. §4.4.2)? Можно ли воспользоваться для этогосхемами разметки линейными интервалами?5.5.3Упражнение 5.6.
Докажите, что контроллеры ВС и BS являются беступиковыми.Упражнение 5.7. Докажите, что всякое действие, разрешенное контроллером ВС, будет также разрешено контроллером FC.ГЛАВА6ВОЛНОВЫЕ АЛГОРИТМЫ И АЛГОРИТМЫ ОБХОДАПри проектировании распределенных алгоритмов для разных приложений некоторые общие проблемы, относящиеся к сетевым процессам, часто становятсяпромежуточными задачами. К таким элементарным задачам относятся широковещательное распространение информация (например, сообщения о начале илизавершении вычисления), установление глобальной синхронизации между процессами, запуск выполнения некоторого действия в каждом процессе, вычисление функции при условии, что каждый из процессов содержит только часть входных данных. Эти задачи всегда решаются путем обмена сообщениями согласнонекоторой предписанной схеме, которая зависит от топологии сети и позволяетзадействовать все процессы.
И действительно, как будет видно читателю в последующих главах, эти проблемы являются настолько основополагающими, чторешения более сложных задач, таких как избрание лидера (гл. 7), определение завершения вычисления (гл. 8 ), обеспечение взаимно исключенного доступа, можнопредставить так, чтобы взаимосвязь между процессами проводилась только в соответствие с указанными схемами обмена сообщениями.Схемы обмена сообщениями, которые в дальнейшем будем называть волновыми алгоритмами, настолько важны, что мы исследуем их отдельно, независимо откакого-либо конкретного прикладного алгоритма, в который встроены эти схемы.В этой главе приводится формальное определение волновых алгоритмов (§6.1.1)и обосновываются некоторые общие результаты, относящиеся к этому понятию(§6.1.2).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
