Реферат: Распределенные алгоритмы

Физический (1) уровень. Цель физического уровня состоит в том, чтобы передать последовательности битов по каналу связи. Поскольку имя уровня предполагает, что эта цель достигнута посредством физического подключения между двумя узлами, типа телефонной линии, волоконно-оптического подключения, или спутникового подключения. Проект уровня непосредственно - вполне вопрос для инженеров - электриков, в то время как интерфейс 1/2 определяет процедуры,  которыми следующий уровень вызывает услуги физического уровня. Обслуживание физического уровня не надежно; поток битов может быть попорчен в течение передачи.

Канальный уровень  (2). Цель канального уровня состоит в том, чтобы маскировать ненадежность физического уровня, то есть обеспечивать надежную связь с более высокими уровнями. Уровень связи данных только осуществляет надежное подключение между узлами, которые непосредственно связаны физической связью, потому что он сформирован непосредственно над физическим уровнем. (Связь между несмежными узлами выполнена в сетевом уровне.) Чтобы достигнуть цели, уровень делит поток битов на части фиксированной длины, названные кадрами. Приемник кадра может проверять(отмечать), был ли кадр получен правильно,  проверяя контрольную сумму, которая является некоторой избыточной информацией, добавленной к каждому кадру. Имеется обратная связь от приемника до отправителя, чтобы сообщить отправителю относительно правильно или неправильно полученного кадра; эта обратная связь происходит посредством сообщений подтверждения.

Отправитель пошлет кадр снова, если оказалось, что он получен неправильно или полностью потерян. Общие принципы, объясненные в предыдущем параграфе могут быть усовершенствованы к ряду различных протоколов связи данных. Например, сообщение подтверждения может быть послано для кадров, которые получены (положительные подтверждения) или для кадров, которые отсутствуют из совокупности полученных кадров (отрицательные подтверждения). Окончательная ответственность за правильную передачу всех кадров может быть на отправителе или стороне приемника. Подтверждения могут быть посланы для одиночных кадров или блоков кадров, кадры могут иметь числа последовательности или не иметь, и т.д.

Сетевой уровень (3). Цель сетевого уровня состоит в том, чтобы обеспечить средства связи между всеми парами узлов, не только связанных физическим каналом. Этот уровень должен выбрать маршруты через сеть, используемую для связи между не-смежными узлами и должен управлять загрузкой движения в каждом узле и канале. Выбор маршрутов обычно основан на информации относительно сетевой топологии, содержащейся в маршрутизации таблиц, сохраненных в каждом узле. Сетевой уровень содержит алгоритмы, чтобы модифицировать таблицы маршрутизации, если топология сети изменилась (вследствие сбоя канала или восстановления). Такой сбой или восстановление обнаруживается канальным уровнем связи. Хотя канальный уровень обеспечивает надежное обслуживание у сетевого уровня, обслуживание, предлагаемое сетевым уровнем не надежно. Сообщения (названные пакетами в этом уровне) посланные от одного узла до другого могут следовать различными путями, вызывая опасность, что одно сообщение настигнет другое. Вследствие  сбоев узла сообщения могут быть потеряны (узел может накрыться во время хранения cообщения), и вследствие лишних сообщений перепередач могут даже быть дублированы. Уровень может гарантировать ограниченному пакету срок службы; то есть, существует константа c такая, что каждый пакет или передается в узел адресата в течение с секунд, или теряется.

Транспортный уровень (4). Цель транспортного уровня состоит в том, чтобы маскировать ненадежность, представленную сетевым уровнем, то есть, обеспечивать надежную связь между любыми двумя узлами. Проблема была бы подобна той решенной канальным уровнем, но это еще усложнено возможностью дублирования и переупорядочения сообщений. Это делает невозможным использовать циклические числа последовательности, если ограничение на срок службы пакета не гарантируется сетевым уровнем.

  Алгоритмы, используемые для управления передачи в транспортном уровне используют подобные методы для алгоритмов в канальном уровне: числа последовательности, обратная связь через подтверждения, и перепередачи.

Уровень сеанса (5). Цель уровня сеанса состоит в том, чтобы обеспечить средства для поддержания подключений между процессами в различных узлах. Подключение может быть открыто и закрыто и между открытием, и закрытием подключение может использоваться для обмена данных, используя адрес сеанса скорее, чем повторение адреса удаленного процесса с каждым сообщением. Уровень сеанса использует надежную непрерывную связь, предлагаемую транспортным уровнем, но структурирует передаваемые сообщения в сеансы. Сеанс может использоваться для передачи файла или удаленного входа в систему. Уровень сеанса может обеспечивать механизмы для восстановления, если узел терпит крах в течение сеанса и для взаимного исключения, если критические операции не могут выполняться на обоих концах одновременно.

Уровень представления (6). Цель уровня представления состоит в том, чтобы выполнить преобразование данных, где представление информации в одном узле отличается от представления в другом узле или не подходящее для передачи. Ниже этого уровня (то есть, при интерфейсе 5/6) данные находятся в передавабельной и стандартизированной форме, в то время как выше этого уровня (то есть, при интерфейсе 6/7) данные находятся в пользовательско - или компьютерно - специфической форме. Уровень выполняет сжатие данных и декомпрессию, чтобы уменьшить количество данных, переданных через более низкие уровни. Уровень выполняет шифрование данных и расшифровку, чтобы гарантировать конфиденциальность и целостность в присутствии злонамеренных сторон, которые стремятся получать или разрушать переданные данные.

Уровень прикладной программы (7). Цель уровня прикладной программы состоит в том, чтобы выполнять конкретные требования пользователя типа передачи файла, электронной почты, информационных табло, или виртуальных терминалов. Широкое разнообразие возможных прикладных программ делает невозможным стандартизировать полные функциональные возможности этого уровня, но для некоторых из прикладных программ, перечисленных здесь, стандарты были предложены.

1.2.3 OSI Модель в  локальных сетях: IEEE Стандарты

На  проект ссылочной модели OSI влияют в большой степени архитектуры существующих глобальных сетей. Технология, используемая в локальных сетях налагает различные программные требования, и из-за этих требований некоторые из уровней могут почти совсем отсутствовать в локальных сетях. Если сетевая организация полагается на общую шину, общедоступную всеми узлам (см. Подраздел 1.1.4), то сетевой уровень почти пуст, потому что каждая пара узлов связана непосредственно через шину. Проект транспортного уровня очень упрощен ограниченным количеством недетерминизма представленного шиной, по сравнению с промежуточной двухточечной сетью. Напротив, канальный уровень усложнен фактом, что к  той же самой физической среде обращается потенциально большое количество узлов. В ответе на эти проблемы IEEE одобрил дополнительные стандарты, покрывая только более низкие уровни OSI иерархии, для использования в локальных сетях (или, если быть более точным, во всех сетях, которые являются структурированными шиной скорее, чем двухточечными соединениями). Потому что никакой одиночный стандарт не мог бы быть достаточно общий, чтобы охватить все сети уже широко использующиеся, IEEE одобрил три различных, несовместимых стандарта, а именно МНОЖЕСТВЕННЫЙ ДОСТУП С ОПРОСОМ НЕСУЩЕЙ И РАЗРЕШЕНИЕМ КОНФЛИКТОВ, маркерную шину , и эстафетное кольцо. Канальный уровень заменен двумя подуровнями, а именно управление доступом к среде и подуровни управления логическим соединением.

Физический (1) уровень. Цель физического уровня в стандартах IEEE подобна таковому первоначального стандарта МЕЖДУНАРОДНОЙ ОРГАНИЗАЦИИ ПО СТАНДАРТИЗАЦИИ, а именно передавать последовательности битов. Фактические стандартные описания (тип монтажа и т.д.), однако, радикально различны, вследствие того, что вся связь происходит через общедоступную среду, а не через двухточечные подключения.

Medium-access-control подуровень (2a). Цель этого подуровня состоит в том, чтобы решить конфликты, которые возникают между узлами, которые хотят использовать общедоступную среду связи. Статичный подход раз и навсегда планировал бы интервалы времени, в течение которых каждому узлу позволяют использовать среду. Этот метод теряет много пропускной способности, однако, если только несколько узлов имеют данные, чтобы передавать, и все другие узлы тихи, среда остается в простое в течение времен, планируемых для тихих узлов. В шинах маркера и эстафетных кольцах доступ к среде находится по карусельному принципу: узлы циркулируют привилегию, названную маркером, среди них, и узлу, задерживающему этот маркер, позволяют использовать среду. Если узел, задерживающий маркер, не имеет никаких данных, чтобы передать, он передает маркер к следующему узлу. В эстафетном кольце циклический порядок, в котором узлы получают их право хода,  определен физической топологией подключения (который,  действительно, кольцо), в то время как в шине маркера,  циклический порядок определен динамически основываясь на порядке адресов узлов. В стандарте МНОЖЕСТВЕННОГО ДОСТУПА С ОПРОСОМ НЕСУЩЕЙ И РАЗРЕШЕНИЕМ КОНФЛИКТОВ узлы наблюдают, когда среда неактивна, и если так, то им позволяют послать. Если два или больше узла запускают посылку (приблизительно) одновременно, имеется проверка на пересечение, которое обнаруживается, что заставляет каждый узел прерывать передачу и пытаться снова в более позднее время.

Logical-link-control подуровень (2b). Цель этого уровня сравнима с целью канального уровня в OSI модели, а именно: управлять обменом данными между узлами. Уровень обеспечивает управление ошибками и управление потоком данных, используя методы, подобные тем использованных в OSI протоколах, а именно числа последовательности и подтверждения. Видящийся с точки зрения более высоких уровней, logical-link-control подуровень появляется подобно сетевому уровню OSI модели. Действительно, связь между любой парой узлов происходит без того, чтобы использовать промежуточные узлы, и может быть обработана непосредственно logical-link-control подуровнем. Отдельный сетевой уровень не следовало бы выполнять в локальных сетях; вместо этого, транспортный уровень сформирован непосредственно на верхней части logical-link-control подуровня.

1.2.4 Поддержка Языка

Реализация одного из программных уровней сети связей или распределенной прикладной программы требует, чтобы распределенный алгоритм, используемый в том уровне или прикладной программе был кодирован на языке программирования. На  фактическое кодирование конечно высоко влияет язык и особенно примитивы, которые он предлагает. Так как в этой книге мы концентрируемся на алгоритмах и не на их кодировании как программа, наша базисная модель процессов основана на состояниях процесса и переходах состояния (см. Подраздел 2.1.2), а не на выполнении команд, принимаемых из предписанного набора. Конечно, неизбежно, чтобы там, где мы представили алгоритмы, требовалась некоторая формальная запись; запись программирования, используемая в этой книге обеспечена в Приложении A. В этом подразделе мы описываем некоторые из конструкций, которые можно наблюдать в фактических языках программирования, разработанных для распределенных систем. Мы ограничиваемся здесь кратким описанием этих конструкций; Для большего количества деталей и примеров фактических языков, которые используют различные конструкции, см., например, Bal [Bal90]. Язык для программирования распределенных прикладных программ, должен обеспечить средства, чтобы выразить параллелизм, обрабатывать взаимодействие, и недетерминизм. Параллелизм, конечно, требуется для программирования различных узлов системы таким способом, которым узлы выполнят их часть программы одновременно. Связь между узлами должна также быть поддержана в соответствии с языком программирования. Недетерминизм необходим, потому что узел должен иногда быть способен получить сообщение от различных узлов, или быть способным либо посылать, либо получать сообщение.

Параллелизм. Наиболее соответствующая степень параллелизма в распределенной прикладной программе зависит от отношения(коэффициента) между стоимостью связи и стоимостью вычисления. Меньшая степень параллелизма учитывает более быстрое выполнение, но также и требует большего количества связи, так, если связь дорога, усиление в быстродействии вычисления может быть потеряно в дополнительной стоимости связи. Параллелизм обычно выражается,  определением нескольких процессов, где каждый процесс является последовательным объектом с собственным пространством состояния. Язык может или предлагать возможность статического определения совокупности процессов или позволять динамическое создание и завершение процессов. Также возможно выразить параллелизм посредством параллельных инструкций или в функциональном языке программирования. Параллелизм не всегда явен в языке; выделение разделов кода в параллельные процессы может выполняться сложным транслятором.

Связь. Связь между процессами свойственна распределенным системам: если процессы не связываются, каждый процесс функционирует в изоляции от других процессов и должен изучаться в изоляции, a не как часть распределенной системы. Когда процессы сотрудничают в вычислении, связь необходима, если один процесс нуждается в промежуточном результате, произведенном другим процессом. Также, синхронизация необходима, потому что вышеупомянутый процесс должен быть приостановлен, пока результат не доступен. Прохождение cообщения затрагивает, и связь и синхронизацию; общедоступная память затрагивает только связь: дополнительная осторожность должна быть предусмотрена для синхронизации процессов, которые сообщаются c использованием общедоступной памяти. В языках, которые обеспечивают передачу сообщения, доступны операции "посылать" и "получать". Связь происходит выполнением посылающейся операции в одном процессе (следовательно названным процессом отправителя) и получающейся операцией в другом процессе (процесс приемника). Параметры посылающей операции - адрес приемника и дополнительные данные, формирующие содержание сообщения. Эти дополнительные данные становятся доступными приемнику, когда получающая инструкция выполнена, то есть, таким образом осуществляет связь. Получающая операция может быть завершена только после того, как посылающая операция была выполнена, что и осуществляет синхронизацию. В некоторых языках получающая операция не доступна явно; вместо этого, процедура или операция активизируется неявно, когда сообщение получено. Язык может обеспечивать синхронное прохождение сообщения, когда посылающая операция завершена только после выполнения получающей операции.

Другими словами, отправитель блокирован, пока сообщение не было получено, и имеет место двухсторонняя синхронизация между результатами приемника и отправителем. Сообщения могут быть посланы двухточечно, то есть, от одного отправителя на один приемник, или широковещательно, когда то же самое сообщение получено всеми приемниками. Термин мультиприведение также используется, чтобы обратиться к сообщениям, которые посланы совокупности (не обязательно всех) процессов. Несколько более структурированный примитив связи -  удаленный вызов процедуры (RPC). Чтобы связываться с процессом b, процедура a обращается к процедуре, представленной в процессе b,  посылая параметры процедуры в сообщении; а приостанавливается, пока результат процедуры не будет возвращен в другом сообщении. Вариант для прохождения сообщения - использование общедоступной памяти для связи; один процесс пишет значение переменной, и другой процесс читает значение. Синхронизация между процессами тяжелее, чтобы ее достигнуть, потому что чтение переменной может быть использовано прежде, чем переменная была записана. При использовании примитивов синхронизации типа семафоров [Dij68] или мониторов [Hoa78], возможно выполнить передачу сообщения, в среде общедоступных  переменных. И наоборот, также возможно выполнить (виртуальную) общедоступную память в передающей сообщения среде, но это очень неэффективно.

Недетерменизм. В многих точках в выполнении процесс может быть способен продолжиться различными способами. Получающая операция часто недетерминирована, потому что это позволяет получение сообщений от различных отправителей. Дополнительные способы выражать недетерменизм основаны на охраняемых командах. Охраняемая команда в наиболее общей форме - список инструкций, каждый предшествованный булевым выражением (его защитником). Процесс может продолжать выполнение с любой из инструкций, для которых соответствующая защита оценивается истиной. Защита может содержать получающую операцию, когда она оценивается истиной, если имеется сообщение, доступное, чтобы быть полученным.

1.3 Распределенные Алгоритмы

Предыдущие разделы дали причины для использования распределенных компьютерных систем и объяснили характер этих систем; потребность программировать эти системы возникает как следствие. Программирование распределенных систем должно быть основано на использовании правильных, гибких, и эффективных алгоритмов. В этом разделе обсуждается, что разработка распределенных алгоритмов - ремесло, совершенно различное по характеру от ремесла, используемого в разработке централизованных алгоритмов. Распределенные и централизованные системы отличаются по ряду существенных отношений, обрабатываемых в Подразделе 1.3.1 и иллюстрируемых в 1.3.2 Подразделе. Распределенное исследование алгоритмов следовательно развилось как независимое поле научного исследования; см. 1.3.3 Подраздел. Эта книга предназначена, чтобы представить читателю это поле исследования. Цели книги и выбора результатов, включенных в книгу установлены в  Подразделе 1.3.4.

1.3.1 Распределенный против Централизованных Алгоритмов

Распределенные системы отличаются от централизованных компьютерных систем по трем существенным отношениям, которые мы теперь обсуждаем.

(1) Недостаток знания  глобального состояния. В централизованных решениях управление алгоритмом может быть сделано основанным на наблюдениях состояния системы. Даже при том, что к  всему состоянию обычно нельзя обращаться в одиночной машинной операции, программа может осматривать переменные один за другим, и принимать решение, в конце концов релевантная информация будет расценена. Никакие данные не изменяются между проверкой и решением, и это гарантирует целостность решения. Узлы в распределенной системе имеют доступ только к их собственному состоянию и не к глобальному состоянию всей системы. Следовательно, не возможно делать решение управления основанным на глобальном состоянии. Это имеет место тот факт, что узел может получать информацию относительно состояния других узлов и базировать решения управления на этой информации. В отличие от централизованных систем, факт, что полученная информация является старой, может стать причиной получения недопустимой информации, потому что состояние другого узла, возможно, изменилось между посылкой информации состояния и решения, основанного на этом. Состояние подсистемы связи (то есть, какие сообщения находятся в транзите в  некоторый момент) никогда непосредственно не наблюдается узлами. Эта информация может только быть выведена косвенно,  сравнивая информацию относительно сообщений, посланных и полученных узлами. Недостаток глобального кадра времени. События, составляющие выполнение централизованного алгоритма полностью упорядочиваются естественным способом их временным появлением;  для каждой пары событий, каждое происходит ранее или позже чем другое. Временное отношение, вызванное на событиях, составляющих выполнение распределенного алгоритма - не общее количество; Для некоторых пар событий может иметься причина для решения, что каждое происходит перед другим, но для других пар имеет место, что ни одно из событий не происходит перед другим [Lam78]. Взаимное исключение может быть достигнуто в централизованной системе требующих его, если доступ процесса p к ресурсу начинается позже чем доступ процесса q, то доступ процесса p начался после того, как доступ процесса q закончился. Действительно, все такие события (старт и окончание доступа процессов p и q) полностью упорядочиваются отношением временного предшествования; в распределенной системе они - не упорядочиваются, и та же самая стратегия не достаточна. Процессы p и q могут начать обращаться к ресурсу, в то время как начало одного не предшествует началу другой.

(3) Недетерменизм. Централизованная программа может описывать вычисления, поскольку они разворачиваются из некоторого ввода недвусмысленно; имея данную программу и ввод, только одиночное вычисление возможно. Напротив, выполнение распределенной системы обычно не -детерминировано, из-за возможных различий в быстродействии выполнения компонентов системы.

Рассмотрим ситуацию, где процесс сервера может получать запросы из неизвестного числа процессов пользователя. Сервер не может приостановить обработку запросов, пока все запросы не были получены, потому что не известно, сколько сообщений прибудет. Следовательно, каждый запрос должен быть обработан немедленно, и порядок обработки - порядок, в который запросы прибывают. Порядок, в котором клиентура посылает их запросы, может быть известен, но поскольку задержки передачи не известны, запросы могут прибывать в различном порядке.

 Комбинация недостатка знания относительно глобального состояния, недостаток глобального кадра времени, и недетерменизм делает проект распределенных алгоритмов запутанным ремеслом, потому что три аспекта вмешиваются несколькими способами. Понятия времени и состояния очень связаны; в централизованных системах понятие времени может быть определено,  рассматривая последовательность состояний, принятых системой в течение выполнения. Даже при том, что в распределенной системе глобальное состояние может быть определено, и выполнение может рассматриваться как последовательность глобальных состояний (Определение 2.2), это представление имеет ограниченное использование, так как выполнение может также быть описано другими последовательностями глобальных состояний (Теорема 2.21). Те альтернативные последовательности обычно состоят из различных глобальных состояний; это придает утверждению "система, принимала это или то состояние в течение выполнения " очень сомнительное значение. Недостаток знания относительно глобального состояния мог бы компенсироваться, если было возможно предсказать это глобальное состояние из алгоритма, который выполняется. К сожалению, это не возможно из-за свойственного недетерменизма в выполнении распределенных систем.

Рис. 1.5 Упрощенная сетевая архитектура

1.3.2 Пример: Связь с  одиночным сообщением

Мы проиллюстрируем трудности, налагаемые недостатком знания относительно глобального состояния и недостатка глобального кадра, с помощью примера, обсужденного Beisnes [Bel76l, а именно надежный обмен информацией через ненадежную среду. Рассмотрим два процесса a и b, связанных сетью передачи данных, которая передает сообщения от одного процесса до другого. Сообщение может быть получено в произвольно длительное время после того, как оно послано, оно может также быть потеряно в целом в сети. Надежность связи увеличивается при использовании сетевых процедур управления (NCPs), через который a и b обращаются к сети. Процесс a инициализирует связь,  передавая информационный модуль m к NCP A. Взаимодействие между NCPs (через сеть передачи данных, DN) должно гарантировать, что информация m передана в процесс b (NCP B), после которого a уведомляется относительно доставки (через NCP A). Структура связи изображена в Рисунке 1.5. Даже если только одиночный информационный модуль должен транспортироваться от a до b, ненадежность сети вынуждает NCP A и NCP B вовлекаться в сеанс связи, состоящий из нескольких сообщений. Они поддерживают информацию состояния относительно этого сеанса связи, но потому что число возможных партнеров сеанса связи для каждого процесса большое, то требуется, чтобы информация состояния была отброшена после того, как обмен сообщениями завершен. Инициализация информации состояния называется открытие, и ее отбрасывание называется закрытием сеанса связи. Заметьте, что после закрытия сеанса связи, NGP находится в точно том же самом состоянии как и перед открытием его; это называется закрытым состоянием. Информационный модуль m.,  говорят, потерян, если a получил уведомление от b, но модуль фактически не был никогда передан к b. Модуль m,  говорят, дублирован если он был передан дважды. Надежные механизмы связи предотвращают и потери и дублирования. Принимается, что NCPs могут терпеть неудачу, после которой они перезапускаются в закрытом состоянии (действительно теряя всю информацию относительно открытого в настоящее время сеанса связи).

Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42