Введение в распределённые алгоритмы. Ж. Тель (2009) (1185665), страница 28
Текст из файла (страница 28)
Упрощения, о которых идет речь,касаются следующих четырех аспектов этого протокола.1. Однонаправленность. Рассматривается передача данных только в одном направлении, а именно от процесса р к процессу q. Иногда мы будем называть процесс р отправителем, а процесс q — получателем. При этом, однако,нужно иметь в виду, что в протоколе используются подтверждающие сообщения,которые следуют в обратном направлении от процесса q к процессу р.Но обычно приходится иметь дело с двусторонним обменом данными. Дляэтого приходится заводить второй протокол, в котором процессы р и q меняютсяролями.
И в этом случае можно ввести комбинированные сообщения, в которыхсодержатся как данные (сопровождаемые порядковым номером), так и информация, входящая в состав подтверждающего пакета.2. Окно приема шириной в одно слово. Получатель не проводит записьпакетов данных, имеющих больший порядковый номер, чем тот, который им ожидается. Поступивший пакет принимается в расчет и немедленно доставляется по3.2. Протокол с таймерами99назначению только в том случае, когда его порядковый номер совпадает с ожида емым номером. Более сложные варианты протокола позволяют проводить записьпреждевременно поступивших пакетов с большими порядковыми номерами и доставлять их по назначению, после того как будут получены и доставлены пакетыс меньшими порядковыми номерами.3. Упрощенные допущения о времени. В рассматриваемом протоколе используется минимальное количество таймеров.
Например, предполагается, чтоподтверждение может быть отправлено в любое время, до тех пор пока получатель поддерживает соединение открытым. Однако возможны ситуации, при которых подтверждение должно быть отправлено спустя небольшой период времени;учет этого обстоятельства приводит к дополнительному усложнению протокола.Кроме того, мы исключили из описания протокола специальные таймеры, которые используются для запуска повторной передачи пакетов данных, как этобыло сделано в §3.3.1.
В протокол включены лишь те таймеры, которые необходимы для обеспечения свойств безопасности протокола.4. Пакеты , состоящие из одного слова. В каждый пакет данных отправитель может поместить одно-единственное слово. Протокол можно сделать болееэффективным, если разрешить помещать в пакет целый блок последовательноидущих слов.В рассматриваемом нами протоколе используются таймеры, т. е.
процессыимеют доступ к устройствам, измеряющим физическое время. Мы будем опираться на следующие основные предположения о времени и таймерах.5. Глобальное время. Все процессы системы функционируют в рамках единой глобальной шкалы времени; это означает, что каждое событие происходитв некоторый вполне определенный момент времени. Каждое событие происходитмгновенно, т. е.
его длительность равна 0, и при этом процессы не обладаютспособностью регистрировать те моменты времени, в которые происходят события.6. Ограниченное время жизни пакета. Время жизни пакета ограниченонекоторой константой pi (максимальное время жизни пакета). Поэтому, есликакой-то пакет был отправлен в момент времени о и получен в момент временит, то верно неравенствоо < т < о + pi.Если в канале произошло дублирование пакета, то каждая копия должна бытьполучена спустя не более pi единиц времени после отправления исходного пакета(в противном случае копии будут утрачены).7. Таймеры. Сами по себе процессы не обладают способностью регистрировать абсолютное время выполнения своих действий, но они имеют доступ к таймерам.
В роли таймера выступает вещественная переменная, значение которойсо временем постоянно убывает (или присваивается этой переменной явным образом). Точнее говоря, если переменная Xt — это таймер, то мы будем использовать запись Xt® для обозначения значения этой переменной в момент времени t,и если в период времени между моментами t\ и О переменной Xt не было при-100Гл. 3. Коммуникационные протоколысвоено какое-либо другое значение, то верно равенствоXt(h) - X t {h) = t2 - t i .Следует обратить внимание на то, что таймеры отсчитывают время точно, т. е.за период времени длительности 8 их значения уменьшаются в точности на 8.В §3.2.3 мы обсудим, как поступать в том случае, когда таймеры подверженырасхождению во времени.Как и в §3.3.1, входные слова, подлежащие отправлению, моделируются бесконечным массивом inp. И точно так же предполагается, что этот массив никогда не содержится целиком в процессе-отправителе р\ в каждый момент временипроцесс р имеет доступ только к некоторой части массива.
Та часть массива inp,которая доступна процессу р, неуклонно расширяется (номера слов возрастатют),по мере того как р получает все новые и новые слова от процесса, порождающего эти слова. Мы условимся называть эту операцию поступлением слова кпроцессу-отправителю.В этом параграфе мы будем моделировать слова, доставленные процессуполучателю, совсем не так, как это было сделано в §3.3.1. Вместо того, чтобыосуществлять запись слов в (бесконечный) массив, процесс-получатель будетвручать эти слова процессу-потребителю посредством операции, которую условимся называть вручением слова.
Наш замысел состоит в том, чтобы каждоеслово из массива inp было вручено в точности один раз, и при этом порядоквручения слов должен быть правильным.Спецификация нашего протокола будет, однако, не столь требовательной,и причина этого состоит в том, что протоколу разрешается обрабатывать каждое слово из массива inp в течение ограниченного интервала времени. Никакойпротокол не может предоставить гарантии того, что слово будет доставлено поназначению за ограниченный срок времени, поскольку не исключена возможностьтого, что за это время все пакеты будут потеряны.
Поэтому в спецификации нашего протокола предусмотрена возможность зарегистрированной потери, прикоторой протокол отправителя выдает сообщение об ошибке, свидетельствующеео том, что слово могло быть потеряно. (Если в связи с этим сообщением протоколвысокого уровня предоставит процессу р это слово повторно, то это, естественно,приведет к дублированию; однако здесь мы не будем утруждать себя рассмотрением этой проблемы.) Интересующие нас свойства протокола, которые будутдоказаны в §3.2.2 таковы.1. Отсутствие потерь. Каждое слово из массива inp будет вручено процессом q или зарегистрировано процессом р (как «вероятно потерянное») спустяограниченный отрезок времени с момента поступления этого слова к процессу р.2. Соблюдение порядка.
Слова, которые вручаются процессом q, следуютв порядке строгого возрастания номеров в массиве inp.3.2.1. Описание протоколаПротокол открывает сеанс связи (соединение) всякий раз, когда соединениеотсутствует, но при этом либо к отправителю поступает некоторое слово, либо3.2.
Протокол с таймерами101Сетевая константа:р: real;(* Максимальное время жизни пакета *)Константы протокола:U: real;(* Продолжительность периода отправления сообщения *)R: real;(* Продолжительность перерыва при приеме сообщения: R К U + pi *)S:real;(* Продолжительность перерыва при передаче сообщения: S К R + 2ц *)Учетные записи отправителя:Low: integer;(* Подтвержденные слова текущего сеанса связи *)H i g h : integer;(* Поступившие слова текущегосеанса связи *)St: timer ;(* Таймер отправителя*)Учетные записи получателя:Exp: integer;(* Очередной ожидаемыйпорядковый номер *)Rt: timer ;(* Таймер получателя *)Коммуникационная подсистема:Mq: channel ; (* Пакеты данных для процесса q *)Мр: channel ; (* Пакеты подтверждений для процесса р *)Вспомогательные переменные:В: integer init 0 ;cr: bool initfalse ;cs: bool initfalse ;(* Слова из предыдущего сеанса связи *)(* Участие получателя в сеансе связи *)(* Участие отправителя в сеансе связи *)Рис.
3.3. Переменные протокола с таймерамиполучателю передается пакет, который должен быть вручен. Поэтому в нашемпротоколе, для того чтобы открыть сеанс связи, нет необходимости обмениваться контрольными сообщениями перед отправлением пакета. За счет этого достигается определенная эффективность протокола в тех случаях, когда в каждомсеансе связи совершается передача всего лишь нескольких слов (в режиме передачи информации мелкими пакетами). Предикат cs (соответственно сг) имеетзначение true, когда отправитель (или получатель) открыл сеанс связи.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
