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

Выходные данные программы p1 поступают в буфер и становятся входными данными для программыp2; программа p1 приостанавливает свое выполнение, если буфер переполнен,а программа p2 приостанавливает свое выполнение, если буфер опустошен.4. Обмен сообщениями. В некоторых языках программирования (к их числу относятся языки программирования Occam или Ada) в качестве средств межпроцессного взаимодействия используются операторы обмена сообщениями. Припомощи обменов сообщениями сравнительно легко решаются проблемы синхронизации: поскольку сообщение нельзя получить прежде, чем оно было отправле-Обеспечение связи между компонентами распределенной системы являетсясложной задачей, и поэтому коммуникационная подсистема должна быть оченьхорошо структурирована.

Для этого сети обычно приходится строить из отдельных модулей, каждый из которых служит для выполнения очень специальнойфункции при поддержке других модулей. Сеть устроена так, что эти модули образуют строгую иерархию: каждый модуль может обращаться только к тем модулям, которые непосредственно предшествуют ему в этом иерархическом порядке.Эти модули называются уровнями или слоями (см. рис.

1.4).1.2. Архитектура и языкиПрограммное обеспечение, необходимое для создания компьютерных сетейсвязи, устроено очень сложно. В этом параграфе мы расскажем о том, какимобразом это программное обеспечение подразделяется на ациклически зависимые друг от друга модули, которые называются уровнями (§ 1.2.1). Мы рассмотрим два стандарта сетевой архитектуры: модель взаимодействия открытыхсистем ISO 9) , которая служит стандартом для глобальных сетей, и дополнительный IEEE стандарт для локальных сетей (§ 1.2.2 и § 1.2.3). Мы также обсудимособенности языков программирования распределенных систем (§ 1.2.4).1.2.1. АрхитектураУровень k Межуровневыйинтерфейс-- Уровень k Прикладные программы-Уровень 2 - Уровень 2Уровень 1 - Уровень 1Уровень 0 - Уровень 0 АппаратураРис.

1.4. Многоуровневая архитектура сети9) InternationalStandards Organization — Прим. перев.32Гл. 1. Введение: распределенные системыНа каждом уровне реализована только часть тех функций, которые необходимы для работы сети, и каждый уровень может опираться только на те функции,которые реализованы на предшествующем уровне. Те сервисные функции, которые уровень i предоставляет уровню i + 1, подробно описаны в интерфейсе взаимодействия уровня i + 1 с уровнем i (его коротко называют i / (i + 1)-интерфейс).Проектирование сети начинается с того, что определяется необходимое числоуровней и прописывается интерфейс взаимодействия соседних уровней.Все функции каждого уровня должны вычисляться распределенным алгоритмом, и при этом алгоритм на уровне i предназначен для решения тех «задач»,которые определены в i/ (i + 1)-интерфейсе на основе тех «допущений», которыеопределены в (i − 1) /i-интерфейсе.

Например, в (i − 1) /i-интерфейсе может бытьобъявлено о возможности передавать сообщения из узла p в узел q без гарантиинадежной доставки этих сообщений, а в i/ (i + 1)-интерфейсе указано, что имеются средства для надежной передачи сообщений из узла p в узел q. Таким образом,на уровне i требуется решить следующую алгоритмическую проблему: располагая средством передачи сообщений, обеспечить надежную передачу сообщений.Это обычно достигается при помощи подтверждений и повторной передачи потерянных сообщений (см.

§ 1.3.1 и гл. 3). При решении этой задачи определяетсятип сообщений, которыми обмениваются процессы на уровне i, и смысл этих сообщений, или, иными словами, то, как на эти сообщения должны реагироватьпроцессы. Правила и соглашения, которыми руководствуются процессы в «разговоре» друг с другом на уровне i, называют протоколом уровня i.Самым низким уровнем иерархии (уровнем 0 на рис. 1.4) обычно являетсяаппаратный уровень.

В 0/1-интерфейсе описаны процедуры, которые позволяютпередавать непереработанную информацию на уровне 1 по проводам связи, а вопределении самого уровня 0 приводятся описания типов используемых проводов, напряжения в цепи, служащего для представления единицы и нуля, и т. д.Очень важно заметить, что изменения, происходящие в реализации системы науровне 0 (например, замена проводов одного типа проводами другого типа илиспутниковой связью), не требуют внесения изменений в 0 /1-интерфейс. То жесамое происходит и на верхних уровнях: межуровневый интерфейс скрывает подробности реализации одного уровня от других уровней, и поэтому изменения,происходящие в этих реализациях, никак не сказываются на других уровнях.Архитектурой сети принято называть совокупность всех модулей (уровней) вместе с определениями соответствующих интерфейсов и протоколов.

Таккак в сети могут быть узлы, изготовленные разными производителями, имеющиепрограммное обеспечение от разных компаний, важно, чтобы продукты, созданные разными компаниями, были совместимы. Потребность в совместимости былаосознана во всем мире, и поэтому были разработаны стандартные сетевые архитектуры. Два таких стандарта получили «официальный» статус, поскольку онибыли утверждены авторитетными организациями (Международной организацией стандартов, ISO и Институтом инженеров по электротехнике и электронике ,IEEE 10) .

Мы рассмотрим их в последующих параграфах этой главы.10) Instituteof Electrical and Electronics Engineers. — Прим. перев.1.2. Архитектура и языки33Протокол управления передачей/Интернет-протокол (TCP/IP 11) ) представляет собой семейство протоколов, которые используются сетью Internet. Он неявляется официально учрежденным стандартом, но используется столь широко,что стал стандартом de facto.

Семейство протоколов TCP /IP (для ознакомления с ним см. работу Девидсона [59]) разбито на уровни, которые соответствуютуровням эталонной модели взаимодействия открытых систем и будут рассмотренынами в следующем параграфе. Вместе с тем, эти протоколы могут быть использованы как в глобальных, так и в локальных сетях.

На более высоких уровняхпредставлены протоколы для электронной почты (простой протокол электроннойпочты, SMTP 12) ), передачи файлов (FTP 13) ), двусторонней связи дистанционныхвходов в систему (Telnet).1.2.2. Эталонная модель OSIМеждународная организация стандартов (ISO) утвердила стандарт для техкомпьютерных сетевых продуктов, которые используются в глобальных сетях.Разработанный стандарт получил название эталонная модель взаимодействияоткрытых систем (OSI 14) ). В этом параграфе мы приведем его краткое описание.

Ввиду того что этот стандарт не очень удобен для использования применительно к локальным сетям, в следующем параграфе мы рассмотрим дополнительные стандарты IEEE, предназначенные для локальных сетей.Эталонная модель OSI имеет семь уровней: физический уровень, уровеньпередачи данных, сетевой уровень, транспортный уровень, сеансовыйуровень, представительский уровень и прикладной уровень.

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

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

На11) Transmissioncontrol protocol/Internet protocol. — Прим. перев.Mail Transfer Protocol. — Прим. перев.13) File Transfer Protocol.— Прим. перев.14) Open-Systems Interconnection.— Прим. перев.12) Simple34Гл. 1. Введение: распределенные системыуровне передачи данных надежное соединение обеспечивается только между темиузлами, которые непосредственно соединены друг с другом при помощи какогонибудь физического средства связи, потому что этот уровень опирается только нафизический уровень. Если узлы не являются смежными, то коммуникация междуними осуществляется на сетевом уровне.Чтобы выполнить поставленную задачу, битовый поток на уровне передачиданных разбивают на кусочки одинаковой длины, которые называются фреймами. При получении фрейма проводится проверка его целостности; для этогоприменяется метод контрольных сумм, предусматривающий внесение в каждыйфрейм некоторой избыточной информации.

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