Введение в распределённые алгоритмы. Ж. Тель (2009) (1185665), страница 12
Текст из файла (страница 12)
Поэтому в локальных сетях сетевой уровень не реализуется, и транспортный уровень надстраивается прямо над уровнемуправления логической связью.1.2.4. Языковая поддержкаДля реализации программного обеспечения на любом уровне коммуникационной сети, равно как и для создания прикладных распределенных программ, нужнозапрограммировать соответствующие распределенные алгоритмы на каком-либоязыке программирования.
Построение программного кода в значительной мереопределяется особенностями языка программирования и, в первую очередь, теми базовыми конструкциями, которые представлены в этом языке. В этой книгенас будут интересовать алгоритмы, а не их программные реализации, поэтомупри описании базовой модели мы будем говорить о состояниях процессов и опереходах из одних состояний в другие (см. §2.1.2), а не о выполнении операторов из некоторого заданного множества. Конечно, для описания алгоритмовнужна строгая формальная система обозначений.
В гл. А рассказывается о томпрограммном псевдокоде, который используется в этой книге.В этом параграфе мы обсудим некоторые из основных конструкций, которые присутствуют в реальных языках программирования, предназначенных для15)Carrier sense multiple access with collision detection. — Прим, nepee.38Гл. 1. Введение: распределенные системыпроектирования распределенных систем.
Мы ограничимся лишь кратким описанием этих конструкций; их подробное описание, а также примеры реальныхязыков программирования, в которых задействованы эти конструкции, можнонайти, например, в книге Бала [21]. В любом языке, предназначенном для создания распределенных прикладных программ, должны быть средства для представления параллельного выполнения, взаимодействия процессов и недетерминизма. Средства представления параллельных вычислений, безусловно, нужныдля того, чтобы программа для различных узлов позволяла работать этим узламодновременно.
В языке программирования должны быть также средства для организации взаимосвязи между узлами. Недетерминизм также необходим, потомучто в некоторые узлы могут поступать сообщения сразу из нескольких различных узлов; иногда бывает нужно сделать так, чтобы узел имел альтернативнуювозможность принять сообщение или отправить сообщение.Параллелизм. Наиболее подходящая степень параллелизма в распределенных прикладных программах зависит от того, как соотносятся друг с другом расходы на коммуникацию и расходы на вычисление.
Высокая степень параллелизмапозволяет ускорить выполнение программы, но при этом возрастают коммуникационные издержки, и в том случае, когда связь обходится слишком дорого,выигрыш, достигнутый за счет повышения быстродействия системы, не сможеткомпенсировать дополнительные расходы на поддержание связи.Как правило, для того чтобы выразить параллелизм, достаточно определитьнесколько процессов, каждый из которых является последовательной процедурой со своим собственным пространством состояний. В языке могут быть заложены возможности как для статического определения процессов, так и для динамического создания процессов и завершения их работы. Параллелизм также можновыразить посредством специальных параллельных операторов или при помощиязыка функционального программирования.
Параллелизм не всегда присутствует в языке в явном виде: изощренные компиляторы способны сами разделятьпрограмму на параллельные процессы.Коммуникация. Неотъемлемой чертой распределенных систем является взаимосвязь между процессами: если процессы не взаимодействуют, то каждыйпроцесс работает изолированно от других процессов, и поэтому его нужно рассматривать отдельно от всей распределенной системы. Если процессы в своихвычислениях взаимодействуют друг с другом, то необходимость в связи междуними возникает всякий раз, когда один из процессов испытывает потребностьв промежуточных результатах, которые вычисляют другие процессы. Столь женеобходима и синхронизация, потому что выполнение такого процесса должнобыть приостановлено, до тех пор пока не будут получены ожидаемые результаты.
Коммуникация посредством обмена сообщениями позволяет обеспечитькак коммуникацию, так и синхронизацию. А вот совместно используемая память годится только для коммуникации: чтобы синхронизовать работу процессов, которые связаны посредством совместно используемой памяти, требуетсяаккуратно применять дополнительные средства.1.2. Архитектура и языки39В тех языках, в которых коммуникация обеспечивается путем обмена сообщениями, имеются операторы отправления сообщений send и приема сообщений receive. Связь происходит при выполнении оператора отправления сообщения в одном из процессов (этот процесс называется отправителем) и оператора приемасообщения в другом процессе (этот процесс называется получателем). Аргументами операции отправления являются адрес получателя, а также дополнительныеданные, составляющие содержание сообщения.
Эти дополнительные данные становятся доступны получателю, когда выполнится оператор приема сообщения.Таким образом осуществляется взаимосвязь процессов. Операция приема сообщений может завершиться только после того, как будет выполнена операцияотправления сообщения. Таким образом достигается синхронизация. В некоторыхязыках нет операции приема сообщения в явном виде; вместо этого в результатеприема сообщения происходит автоматическая неявная активизация некоторойоперации или процедуры.В языке может поддерживаться синхронный обмен сообщениями; в этомслучае оператор отправления сообщения завершает свое выполнение только после того, как начнется выполнение оператора приема сообщения. Иначе говоря,отправитель остается заблокированным, до тех пор пока не будет принято сообщение, и благодаря этому достигается двухсторонняя синхронизация.Сообщения могут отправляться по двухточечной связи, т.
е. одному получателю от одного отправителя, или широковещательно, и в этом случае одно и то жесообщение будет доставлено всем получателям. В последнем случае для сообщения, которое отправляется целому множеству получателей (хотя и не обязательно всем процессам), используется термин «широковещательное сообщение».Несколько более структурированным базовым средством связи является вызовудаленной процедуры (RPC 16^). Чтобы установить соединение с процессом Ь,процесс а вызывает процедуру, входящую в состав процесса Ь, путем отправления сообщения, содержащего параметры этой процедуры; при этом процесс априостанавливает свое выполнение, до тех пор пока результат вычисления этойпроцедуры не будет возвращен ему с другим сообщением.Альтернативу обмену сообщениями как средству связи составляет совместноиспользуемая память ; один из процессов присваивает значение некоторой переменной, а другой процесс считывает это значение.
В этом случае труднее добитьсясинхронизации процессов, потому что считывание нужного значения может произойти до того, как оно будет присвоено переменной. Применяя такие средствасинхронизации, как семафоры [60] или мониторы [107], можно реализоватьпередачу сообщений через совместно используемое окружение. И наоборот, припомощи механизма обмена сообщениями можно реализовать виртуальную модельсовместно используемой памяти, хотя это крайне неэффективный способ.Недетерминизм. При выполнении процесса есть много точек, в которых этовыполнение может быть продолжено по разным направлениям. Операция приема сообщения часто оказывается недетерминированной, потому что сообщение16iRemote Procedure Call. — Прим, перев.40Гл.
1. Введение: распределенные системыможет быть получено от многих разных отправителей. Недетерминизм можно выразить, например, при помощи охраняемых команд, или команд с предохранителями. В самом общем виде охраняемая команда представляет собой списокоператоров, каждому из которых предшествует булево выражение (его предохранитель). Процесс может продолжить свое выполнение, выбрав любой из техоператоров, предохранитель которого принимает значение true.
В состав предохранителя может входить операция приема сообщения; в этом случае предохранитель принимает истинное значение, если имеется сообщение, которое можетбыть получено.1.3. Распределенные алгоритмыВ предшествующих пара параграфах этой главы мы уже говорили о том, зачемнужны распределенные вычислительные системы и каковы их характерные особенности. Понятно, что для этих систем нужно создавать программы. Программыдля распределенных систем должны основываться на правильных, гибких и эффективных алгоритмах.
В этом параграфе мы покажем, что искусство разрабатывать распределенные алгоритмы очень сильно отличается от умения создаватьцентрализованные алгоритмы. Распределенные и централизованные системы отличаются в целом ряде аспектов, которые мы обсудим в § 1.3.1; в качестве иллюстрации в § 1.3.2 мы приведем несколько примеров. Поэтому изучение распределенных алгоритмов — это отдельная область научных исследований (см. § 1.3.3),введением в которую может служить эта книга. В §1.4 говорится о том, какиецели ставил перед собой автор книги, и приводится перечень результатов, включенных в эту книгу.1.3.1.
Сравнение распределенных и централизованныхалгоритмовРаспределенные системы отличаются от централизованных (однопроцессорных) вычислительных систем тремя наиболее существенными качествами, которые мы здесь обсудим.1. Отсутствие сведений о глобальном состоянии. В централизованномалгоритме управление вычислением осуществляется путем отслеживания состояния всей системы. И хотя состояние всей системы обычно нельзя оценить, выполнив одну-единственную машинную операцию, программа может проверить однуза другой все переменные и выработать решение, как только будет собрана всянеобходимая информация.
Пока проводится проверка и принимается решение,никакие данные не изменяются, и этим обеспечивается целостность принятогорешения.Узлам распределенной системы открыт доступ только к их собственным состояниям, а не к состоянию всей системы. Поэтому нельзя управлять вычислением, основываясь на информации о глобальном состоянии системы. Конечно,узел может получить информацию о состоянии других узлов и принять решение,учитывая эту информацию. Но, в отличие от централизованных систем, за время,1.3.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
