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

вычисления полагаются на данные, обеспечиваемые другими процессами),

может возникнуть циклическое ожидание, при котором не будет возможно

дальнейших вычислений. Эти тупиковые ситуации должны определяться и

правильные действия должны предприниматься для того, чтобы

перезапустить или продолжить вычисления.

7) Распределенная поддержка файлов. Когда узлы помещают запросы на

чтение и запись удаленного файла, эти запросы, могут обрабатываться

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

уверенности в том, что каждый узел наблюдает целостный вид файла или

файлов. Обычно это производится временным штампованием запросов,

также как и информации в файлах и упорядочивание входящих запросов

по их временным отметкам; см., например, [LL86].

1.1.5 Многопроцессорные компьютеры

Многопроцессорный компьютер это вычислительная система, состоящая из

нескольких процессоров в маленьком масштабе, обычно внутри одной большой

коробки. Этот тип компьютерной системы отличается от локальных сетей по

следующему критерию. Его процессоры гомогенны, т.е. они идентичны по

аппаратуре. Географический масштаб машины очень маленький, обычно порядка

метра или менее. Процессоры предназначены для совместного использования в

одном вычислении (либо чтобы повысить скорость, либо для повышения

надежности). Если основное назначение многопроцессорного компьютера это

повышение скорости вычислений, то он часто называется параллельным

компьютером. Если его основное назначение – повышение надежности, то он

часто называется система репликации.

Параллельные компьютеры подразделяются на одно-командные много-поточные

по данным (или SIMD) и много-командные много-поточные по данным (или MIMD)

машины.

Рис. 1.3 Транспьютер и микросхема маршрутизатора

SIMD машины имеют один интерпретатор инструкций, но команды выполняются

большим числом арифметических блоков. Ясно, что эти блоки имеют недостаток

автономности, которая требуется в нашем определении распределенных систем,

и поэтому SIMD компьютеры не будут рассматриваться в этой книге. MIMD

машины состоят из нескольких независимых процессоров и они классифицируются

как распределенные системы.

Процессоры обычно оборудуются специальной аппаратурой для коммуникации

с другими процессорами. Коммуникация между процессорами может иметь место

либо через шину, либо через соединения точка-точка. Если выбрана шинная

организация, то архитектура масштабируема только до определенного уровня.

Очень популярным процессором для разработки многопроцессорных

компьютеров является транспьютер, разработанный Inmos; см. рис. 1.3.

Транспьютер состоит из центрального процессора (CPU), специального блока с

плавающей точкой (FPU), локальной памяти, и четырех специальных

процессоров. Чипы очень хорошо подходят для построения сетей степени 4

(т.е. каждый узел соединен с четырьмя другими узлами). Inmos также

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

Каждый маршрутизатор может одновременно обрабатывать трафик 32

транспьютерных соединений. Каждое входящее сообщение просматривается на

предмет того, по какой связи оно может быть перенаправлено; затем оно

направляется по это связи.

Другой пример параллельного компьютера это система Connection Machine

CM-5, разработанная Thinking Machines Corporation [LAD92]. Каждый узел

машины состоит из быстрого процессора и обрабатывающих блоков, таким

образом, предлагая внутренний параллелизм в добавление параллелизму,

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

потенциальную производительность 128 миллионов операций в секунду, и одна

машина может содержать 16384 узлов, полная машина может выполнять свыше

1012 операций в секунду. (Максимальная машина из 16384 процессоров занимает

комнату 900 м2 и скорее всего очень дорогая.) Узлы СМ-5 соединены тремя

точка-точка коммуникационными сетями. Сеть данных, с топологией толстого

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

процессорами. Сеть управления, с технологией бинарного дерева, осуществляет

специальные операции, такие как глобальная синхронизация и комбинирование

ввода. Диагностическая сеть невидима для программиста и используется для

распространения информации о вышедших из строя компонентах.. Компьютер

может быть запрограммирован как в режиме SIMD, так и в (синхронном) MIMD

режиме.

В параллельном компьютере вычисления поделены на подвычисления, каждое

осуществляется одноим из узлов. В репликационной системе каждый узел

проводит вычисление целиком, после чего результаты сравниваются для того,

чтобы обнаружить и скорректировать ошибки.

Построение многопроцессорных компьютеров требует решения нескольких

алгоритмических проблем, некоторые из которых подобны проблемам в

компьютерных сетях. Некоторые из этих проблем обсуждаются в этой книге.

1) Разработка системы передачи сообщений. Если многопроцессорный

компьютер организован как сеть точка-точка, то должна быть

разработана коммуникационная система. Это обладает проблемами

подобными тем, которые возникают в разработке компьютерных сетей,

таким как управление передачей, маршрутизация, и предотвращение

тупиков и перегрузок. Решения этих проблем часто проще, чем в общем

случае компьютерных сетей. Проблема маршрутизации, например, очень

упрощена регулярностью сетевой топологии (например, кольцо или

сетка) и надежностью узлов.

Inmos С104 маршрутизаторы используют очень простой алгоритм

маршрутизации, называемый внутренней маршрутизацией, которая

обсуждается в подразделе 4.4.2, он не может быть использован в сетях

с произвольной топологией. Это поднимает вопрос могут ли

использоваться решения для проблем, например, предотвращение

тупиков, в комбинации с механизмом маршрутизации (см. проект 5.5).

2) Разработка виртуальной разделяемой памяти. Многие параллельные

алгоритмы разработаны для так называемой модели параллельной памяти

с произвольным доступом (PRAM), в которой каждый процессор имеет

доступ к разделяемой памяти. Архитектуры с памятью, которая

разделяется физически, не масштабируются; здесь имеет место жесткий

предел числа процессоров, которые могут быть обслужены одним чипом

памяти.

Поэтому исследования направлены на архитектуры, которые имеют

несколько узлов памяти, подсоединенных к процессорам через

интерсеть. Такая интерсеть может быть построена, например, из

траспьютеров.

3) Балансировка загрузки. Вычислительная мощь параллельного компьютера

эксплуатируется только, если рабочая нагрузка вычислений

распределена равномерно по процессорам; концентрация работы на

одном узле понижает производительность до производительности одного

узла. Если все шаги вычислений могут быть определены во время

компиляции, то возможно распределить их статически. Более трудный

случай возникает, когда блоки работы создаются динамически во время

вычисления; в этом случае требуются сложные методы. Очереди задач

процессоров должны регулярно сравниваться, после чего задачи должны

мигрировать от одной к другой. Для обзора некоторых методов и

алгоритмов для балансировки загрузки см. Гочинский [Gos91, глава 9]

или Харгет и Джонсон [HJ90].

4) Робастость против необнаруживаемых сбоев (часть 3). В репликационной

системе должен быть механизм для преодоления сбоев в одном или

нескольких процессорах. Конечно, компьютерные сети должны также

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

предполагается, что такой сбой может быть обнаружен другими узлами

(см., например, алгоритм сетевого обмена в разделе 4.3).

Предположения, при которых репликационные системы должны оставаться

правильными, более строгие, т.к. процессор может производить

ошибочный ответ, и то же время кооперироваться с другими при помощи

протоколов как правильно работающий процессор. Должен быть внедрен

механизм голосования, чтобы отфильтровывать результаты процессоров,

так, что только правильные ответы передаются во все время, пока

большинство процессоров работает правильно.

1.1.6 Взаимодействующие процессы

Разработка сложных программных систем может быть зачастую упрощена

организацией программы как набора (последовательных) процессов, каждый с

хорошо определенной, простой задачей.

Классический пример для иллюстрации этого упрощения это преобразование

записей Конвея. Проблема состоит в том, чтобы читать 80 символьные записи и

записывать ту же информацию в 125 символьные записи. После каждой входной

записи должен вставляться дополнительный пробел, и каждая пара звездочек

(«**») должна заменяться на восклицательный знак («!»). Каждая выходная

запись должна завершаться символов конца записи (EOR). Преобразование может

быть проведено одной программой, но написание этой программы очень сложно.

Все функции, т.е. замена «**» на «!», вставка пробелов, и вставка символов

EOR, должны осуществляться за один цикл.

Программу лучше структурировать как два взаимодействующих процесса.

Первый процесс, скажем р1, читает входные карты и конвертирует входной

поток в поток печатных символов, не разбивая на записи. Второй процесс,

скажем р2, получает поток символов и вставляет EOR после 125 символов.

Структура программы как набор двух процессов обычно предполагается для

операционных систем, телефонных переключающих центров, и, как мы увидим в

подразделе 1.2.1, для коммуникационных программ в компьютерных сетях.

Набор кооперирующих процессов становится причиной того, что приложение

становится локально распределенным, но абсолютно возможно выполнять

процессы на одном компьютере, в этом случае приложение не является

физически распределенным. Конечно, в этом случае достигнуть физической

распределенности легче именно для систем, которые логически распределены.

Операционная система компьютерной системы должна управлять конкурентным

выполнением процессов и обеспечить средства коммуникации и синхронизации

между процессами.

Процессы, которые выполняются на одном компьютере, имеют доступ к одной

физической памяти, отсюда – естественно использование этой памяти для

коммуникации. Один процесс пишет в определенное место памяти, и другой

процесс читает из этого места. Эта модель конкурирующих процессов была

использована Дейкстрой [Dij68] и Овицким и Грайсом [OG76]. Проблемы,

которые рассматривались в этом контексте, включают следующие.

1) Атомичность операций с памятью. Часто предполагается, что чтение и

запись одного слова памяти атомичны, т.е. чтение и запись

выполняемые процессом завершается перед тем как другая операция

чтения или записи начнется. Если структуры большие, больше чем одно

слово обновляется, операции должны быть аккуратно синхронизированы,

чтобы избежать чтения частично обновленной структуры. Это может быть

осуществлено, например, применением взаимного исключения [Dij68] в

структуре: пока один процесс имеет доступ к структуре, ни один

другой процесс не может начать чтение или запись. Применение

взаимного исключения с использованием разделяемых переменных

усложнено из-за возможности нескольких процессов искать поле в этой

структуре в это же время.

Условия ожидания, налагаемые доступом со взаимным исключением

к разделяемым данным, могут понизить производительность процессов,

например, если «быстрый» процесс должен ждать данные, в настоящее

время используемые «медленным» процессом. В недавние годы внимание

концентрировалось на применении разделяемых переменных, которые

являются wait-free, что значит, что процесс может читать или писать

данные без ожидания любых других процессов. Чтение и запись могут

перекрываться, но только при тщательной проработке алгоритмов чтения

и записи, которые должны обеспечить атомичность. Для обзора

алгоритмов для wait-free атомичных разделяемых переменных см.

Киросис и Кранакис [KK89].

2) Проблема производитель-потребитель. Два процесса, один из которых

пишет в разделяемый буфер и другой и которых читает из буфера,

должны быть скоординированы, чтобы предупредить первый процесс от

записи, когда буфер полон и второй процесс от чтения, когда буфер

пуст. Проблема производитель-потребитель возникает, когда решение

проблемы преобразования Конвея выработано; р1 производит

промежуточный поток символов, и р2 потребляет его.

3) Сборка мусора. Приложение, которое запрограммировано с

использованием динамических структур данных может производить

недоступные ячейки памяти, называемые мусором. Формально, приложение

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

место, для того чтобы позволить специальной программе, называемой

сборщиком мусора, идентифицировать и вернуть недоступную память.

Дейкстра и другие [DLM78] предложили сборщик мусора на-лету, который

может работать как отдельный процесс, параллельно с приложением.

Требуется сложное взаимодействие между приложением и сборщиком,

т.к. приложение может модифицировать структуры указателей в памяти,

в то время как сборщик решает какие ячейки являются недоступными.

Алгоритм должен быть тщательно проанализирован, чтобы показать, что

модификации не обусловят ошибочный возврат доступным ячеек. Алгоритм

для сбора мусора на-лету с упрощенным доказательством правильности

был предложен Бен-Ари [BA84].

Решения проблем, перечисленных здесь, демонстрируют, что могут быть

решены очень трудные проблемы взаимодействия процессов для процессов,

которые сообщаются посредством разделяемой памяти. Однако, решения часто

исключительно усложнены и иногда очень незначительное перемешивание шагов

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

правильными на первый и даже на второй взгляд. Поэтому, операционные

системы и языки программирования предлагают примитивы для более структурной

организации межпроцессовых коммуникаций.

1) Семафоры. Семафор [Dij68] это неотрицательная переменная, чье

значение может быть прочитано и записано за одну атомичную операцию.

V операция приращает ее значение, а Р операция уменьшает ее

значение, когда оно положительно ( и подвешивает выполнение процесса

на этой операции, пока значение переменной нулевое).

Семафоры – подходящее средство для применения взаимного

исключения над разделяемой структурой данных: семафор

инициализируется в 1, и доступ к структуре предваряется операцией Р

и завершается операцией V. Семафоры накладывают большую

ответственность на каждый процесс за правильное использование;

целостность разделяемых данных нарушается, если процесс манипулирует

данными неправильно или не выполняет требуемых Р и V операций.

2) Мониторы. Монитор [Hoa74] состоит из структуры данных и набора

процедур, которые могут выполняться над этими данными, с помощью их

вызова процессами способом, использующим взаимное исключение. Т.к. к

данным доступ осуществляется полностью через процедуры, объявленные

в мониторе, гарантируется правильное использование данных, если

монитор объявлен корректно. Монитор, таким образом, предотвращает не

позволенный доступ к данным и синхронизирует доступ различных

процессов.

3) Каналы. Канал [Bou83] это механизм, который передает поток данных от

одного процесса к другому и синхронизирует два коммутирующих

процесса; это заранее запрограммированное решение проблемы

производитель-потребитель.

Канал это основной механизм коммуникаций в операционной системе

UNIX. Если программа р1 выполняет процесс р1 преобразования Конвея и

р2 выполняет р2 , команда UNIX р1 | р2 вызывает две программы и

соединяет их каналом. Вывод р1 буферизируется и становится вводом р2

; р1 подвешивается, когда буфер полон, и р2 подвешивается, когда

буфер пуст.

4) Передача сообщений. Некоторые языки программирования, такие как

OCCAM и ADA, обеспечивают передачу сообщений, как механизм для

межпроцессовой коммуникации. Проблемы синхронизации относительно

легко решаются с использованием передачи сообщений; т.к. сообщение

не может быть получено до его передачи, возникает временное

отношение между событиями благодаря обмену сообщениями.

Передача сообщений может быть выполнена с использованием

мониторов или каналов, и это естественные средства для систем

коммуникации, которые используются в аппаратуре распределенных

систем (без разделяемой памяти). В самом деле, языки OCCAM и ADA

были разработаны с идеей использования их для физически

распределенных приложений.

[pic]

Рис 1.4 Слоеная сетевая архитектура

1.2 Архитектура и Языки

Программное обеспечение для выполнения компьютерных сетей связей очень

усложнено. В этом разделе объяснено, как это программное обеспечение обычно

структурируется в ациклически зависимых модулях названных уровнями

(Подраздел 1.2.1). Мы обсуждаем два стандарта с сетевой архитектурой, а

именно, модель МЕЖДУНАРОДНОЙ ОРГАНИЗАЦИИ ПО СТАНДАРТИЗАЦИИ Соединения

Открытых систем, стандарт для глобальных сетей, и дополнительного стандарта

IEEE для локальных сетей (Подразделы, 1.2.2 и 1.2.3). Также языки,

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

(Подраздел 1.2.4).

1.2.1 Архитектура

Сложность задач, выполняемых подсистемой связи распределенной системы

требует, чтобы эта подсистема была разработана высоко структурированным

способом. К этому моменту, сети всегда организовываются как совокупность

модулей, каждое выполнение очень специфическая функция и основывающаяся на

услугах, предлагаемых другими модулями. В сетевых организациях имеется

всегда строгая иерархия между этими модулями, потому что каждый модуль

исключительно использует услуги, предлагаемые предыдущим модулем. Модули

названы уровнями или уровнями в контексте сетевой реализации; см. 1.4

Рисунок. Каждый уровень осуществляет часть функциональных возможностей,

требуемых для реализации сети и полагается на уровень только ниже этого.

Услуги, предлагаемые i уровнем i + 1 уровню точно описаны в интерфейсе i

уровня и i + 1 уровня (кратко, i / (i + 1) интерфейс). При проектировании

сети, в первую очередь, нужно определить число уровней и интерфейсов между

последующими уровнями.

Функциональные возможности каждого уровня должны быть выполнены

распределенным алгоритмом, таким, что алгоритм для i уровня решает

"проблему", определенную i / (i + 1) интерфейсом, согласно

"предположениям", определенным в (i — l) /i интерфейсе. Например, (i — 1)

/i интерфейс может определять, что сообщения транспортируются из узла p к

узлу q, но некоторые сообщения могут быть потеряны, в то время как i / (i +

1) интерфейс определяет, что сообщения передаются от p до q надежно.

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

прохождение сообщения, используя ненадежное прохождение сообщения, что

обычно делается с использованием подтверждения и перепередачи потерянных

сообщений (см. Подраздел, 1.3.1 и Главу 3). Решение этой проблемы

определяет тип сообщений, обменянных процессами i уровня и значение этих

сообщений, т.е., как процессы должны реагировать на эти сообщения. Правила

и соглашения, используемые в "сеансе связи" между процессами i уровня

упоминаются как layer-i протокол. Самый низкий уровень иерархии (уровень 0

на Рисунке 1.4) - всегда аппаратный уровень. Интерфейс 0/1 описывает

процедуры, которыми уровень i может передать необработанную информацию

через соединяющие провода, и описание уровня непосредственно определяет то,

какие типы провода используются, сколько вольт представляют единицу или

ноль, и т.д. Важное наблюдение - то, что изменение в реализации уровня 0

(замена проводов другими проводами или спутниковыми подключениями) не

требует, чтобы интерфейс 0/1 был изменен. Те же самые условия в более

высоких уровнях: интерфейсы уровня служат экраном от реализация уровня для

других уровней, и реализация может быть изменена без того, чтобы

воздействовать на другие уровни. Под сетевой архитектурой мы понимаем

совокупность уровней и сопровождающих описаний всех интерфейсов и

протоколов. Поскольку сеть может содержать узлы, произведенные различными

изготовителями, программируемые программным обеспечением, написанным

различными компаниями, важно, чтобы изделия различных компаний являлись

совместимыми. Важность совместимости была признана во всем мире и

следовательно стандартные сетевые архитектуры были разработаны. В следующем

подразделе два стандарта обсуждаются, что получило "официальное" статус,

потому что они приняты влиятельными организациями (МЕЖДУНАРОДНАЯ

ОРГАНИЗАЦИЯ ПО СТАНДАРТИЗАЦИИ, и Институт Электрических и Электронных

Инженеров, IEEE). Протокол управления передачей / internet протокол

(TCP/IP) - совокупность протоколов, используемых в Internet. TCP/IP - не

официальный стандарт, но используется настолько широко, что стал

фактическим стандартом. Семейство протоколов TCP/IP (см. Davidson [Dav88]

для введения) структурирован согласно уровням OSI модели, обсужденной в

следующем подразделе, но протоколы могут использоваться в глобальных сетях

также как в локальных сетях.

Более высокие уровни содержат протоколы для электронной почты (простой

протокол передачи почты - SMTP), передача файлов (протокол передачи

файлов, FTP), и двунаправленная связь для удаленного входа в систему

(Telnet).

1.2.2 Ссылочная Модель OSI

МЕЖДУНАРОДНАЯ ОРГАНИЗАЦИЯ ПО СТАНДАРТИЗАЦИИ установила стандарт для

компьютерных изделий(программ) для работы с сетями типа тех, которые

используются (главным образом) в глобальных сетях. Их стандарт для сетевой

архитектуры назван Соединением открытых систем (OSI) ссылочной моделью, и

будет описан кратко в этом подразделе. Потому что стандарт не полностью

соответствующий для использования в локальных сетях, дополнительные

стандарты IEEE для локальных сетей обсуждены в следующем подразделе. Модель

ссылки OSI состоит из семи уровней, а именно физического, связи данных,

сети, транспорта, сеанса, представления, и уровней прикладной программы.

Ссылочная модель определяет интерфейсы между уровнями и обеспечивает, для

каждого уровня, один или большее количество стандартных протоколов

(распределенные алгоритмы, чтобы выполнить уровень).

Физический (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 Поддержка Языка

Реализация одного из программных уровней сети связей или распределенной

прикладной программы требует, чтобы распределенный алгоритм, используемый в

том уровне или прикладной программе был кодирован на языке

программирования. На фактическое кодирование конечно высоко влияет язык и

особенно примитивы, которые он предлагает. Так как в этой книге мы

концентрируемся на алгоритмах и не на их кодировании как программа, наша

базисная модель процессов основана на состояниях процесса и переходах

Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18