Введение в распределённые алгоритмы. Ж. Тель (2009) (не распознанно) (1185664), страница 6
Текст из файла (страница 6)
Выбор канала связи в промежуточных вершинах осуществляется на основе указанного адреса, и этот выбор можно сделать более эф-1.1. Что такое распределенная система?21фективно, если в адресах узлов удастся каким-нибудь образом «закодировать»топологическую информацию.3. Устранение перегрузки. Пропускная способность коммуникационнойсети может значительно понизиться, если одновременно передается большое количество сообщений. Поэтому нужно уметь управлять формированием сообщений в различных узлах сети в зависимости от сложившейся пропускной способности сети.
Некоторые методы устранения перегрузки обсуждаются в книге[182, § 5.3] .4. Предотвращение блокировки (тупиков) (см. гл. 5). Сети с двухточечным соединением иногда называют сетями с промежуточным хранением данных, ввиду того что сообщения, которые при пересылке проходят через ряд промежуточных узлов, должны быть вначале помещены в память каждого из этихузлов, а затем переправлены следующему по порядку узлу. Так как в промежуточных узлах объем доступной для этих целей памяти ограничен, с памятью нужнообращаться аккуратно, чтобы избежать тупиковых ситуаций.
Это такие ситуации,когда в сети есть некоторое множество сообщений, ни одно из которых не может быть переправлено дальше, поскольку память в следующем узле маршрутаполностью занята другими сообщениями.5. Обеспечение безопасности. При помощи сетей соединяются компьютеры, принадлежащие разным владельцам; некоторые из этих владельцев могут попытаться неправомерно воспользоваться ресурсами других владельцев или дажеповредить их вычислительные устройства. Так как есть возможность запуститьвычислительное устройство из любого места земного шара, нужно иметь надежные методы аутентификации пользователей, криптографии и сканирования поступающей информации (например, для поиска вирусов).
Можно воспользоваться методами криптографии (см., например, [182, § 7.1]) для шифрования данных,чтобы обезопасить их от неразрешенного прочтения, и для внесения электронныхподписей, чтобы обезопасить их от недозволенной записи.1.1.4. Локальные сетиЛокальные сети используются для того, чтобы установить соединение между компьютерами, принадлежащими одной и той же организации. Обычно такоесоединение предназначено, главным образом, для совместного использования ресурсов (как файлов, так и периферийной аппаратуры) и для обеспечения обменаинформацией между сотрудниками организации.
Время от времени сети применяются также для ускорения вычислений (путем раздельного решения задачинесколькими узлами) и для резервной замены одних узлов другими в случае возникновения неполадок.Примеры сетей и устройство сетей. В первой половине семидесятых годовXX в. корпорация Xerox разработала локальную сеть Ethernet 3) . Названия глобальных сетей ARPANET, BITNET и т. п. служат для наименования отдельных3) Ethernet— это торговая марка компании Xerox Corporation. — Прим. автора.22Гл.
1. Введение: распределенные системысетей, тогда как названия локальных сетей обычно используются в качестве торговых марок. Существует одна сеть ARPANET, oдна сеть BITNET и одна сетьUUCP, существует единая сеть Internet, но каждая компания может установитьсвою собственную частную сеть Ethernet, Token Ring или SNA.В отличие от глобальных сетей, сеть Ethernet построена на основе шины, т. е.связь между узлами сети обеспечивает единый механизм, к которому подключенывсе узлы, как это показано на рис.
1.2. Использование шин в локальных сетяхполучило широкое распространение, хотя при этом могут быть различия в том,как устроены и как применяются эти шины.УзлыКоммуникационная системаРис. 1.2. Сеть с шинной организациейУстройство сети Ethernet позволяет в каждый момент времени передаватьтолько одно сообщение; другие виды шин (к их числу относится, например, кольцевая сеть с маркерами, разработанная в Цюрихской лаборатории фирмы IBM)допускают повторное использование коммуникационного пространства.Под этим подразумевается, что в одно и то же время по шине могут передаваться несколько сообщений. Для построения шины не требуется сложной аппаратуры, и потому этот способ связи сравнительно дешев. Но у него есть и недостаток — такая организация сети ограничивает возможность ее наращивания.Это означает, что максимальное количество узлов, которые можно подключитьк одной шине, жестко ограничено.
Большие компании, имеющие много компьютеров, должны использовать для создания сети несколько шин, соединенных другс другом при помощи мостов. В результате этого образуются сети, имеющиеиерархическую организацию.Не все локальные сети имеют шинную организацию. В компании IBM удалось спроектировать сетевой продукт под названием SNA, в котором применяется двухточечный тип соединения. Это дало возможность клиентам фирмы подключать к сети разнообразные продукты фирмы IBM. Проектирование сети SNAбыло осложнено требованием ее совместимости со всеми сетевыми продуктами,уже созданными к тому времени компанией IBM.Алгоритмические проблемы.
При реализации локальных сетей приходитсярешать некоторые (хотя и не обязательно все) из задач, перечисленных в предыдущем параграфе, посвященном глобальным сетям. Надежный обмен даннымиуже не представляется значительной проблемой, поскольку шины обычно очень1.1. Что такое распределенная система?23надежны и передают сообщения очень быстро. Проблемы маршрутизации также не возникают в сетях с шинной организацией, поскольку к каждому адресатуможно обращаться непосредственно через шину.
В кольцевых сетях все сообщения обычно перемещаются в одном и том же направлении по кольцу и изымаютсялибо получателем, либо отправителем; поэтому задача маршрутизации становится практически вырожденной. В шинах не возникает перегрузки, так как каждоесообщение может быть получено (изъято из шины) сразу после его отправления,но при этом необходимо ограничивать очередь сообщений, ожидающих в узлахдоступа в шину. Так как сообщения не накапливаются в промежуточных узлах, невозникает и блокировки, связанной с промежуточным хранением. Если все компьютеры принадлежат одной семье или одной компании, которая доверяет своимсотрудникам, то нет необходимости и в использовании механизмов безопасности,выходящих за пределы обычной защиты данных, которая обеспечивается операционной системой.Чтобы применять локальные сети для распределенного выполнения прикладных программ (совокупности процессов, приписанных узлам сети), нужно решитьследующие задачи распределенного управления (некоторые из них обсуждаютсяво второй части этой книги).1.
Широковещательное распространение информации и синхронизация (см. гл. 6). Если мы должны добиться того, чтобы информация была доступна всем процессам или чтобы все процессы пребывали в ожидании выполнениянекоторого глобального условия, то нам необходимо иметь некоторую схему передачи сообщений, которая каким-то образом будет «затрагивать» все процессы.2. Избрание лидера (см.
гл. 7). Некоторые задачи (например, выдача результата или инициализация структур данных) должны выполняться в точностиодним процессом из заданного множества. Иногда бывает так, что нам желательно или необходимо не назначать для этого заранее никаких процессов; тогдараспределенный алгоритм должен выполняться так, чтобы для решения задачибыл избран один из процессов.3. Обнаружение завершения (см. гл. 8). Процессы распределенной системы не всегда способны непосредственно убедиться в том, что распределенноевычисление, в котором они участвуют, завершилось.
Для того чтобы можно былополучить результаты вычисления, необходимо уметь обнаруживать это завершение.4. Назначение ресурсов. Узлу может потребоваться доступ к некоторомуресурсу, который размещен где-то в сети, хотя точное место его расположениянеизвестно. Содержать таблицу, в которой регистрируется расположение каждого ресурса, не всегда выгодно, поскольку количество потенциальных ресурсовможет оказаться слишком большим или сами ресурсы могут перемещаться изодного узла в другой. В таком случае заинтересованный узел может обратитьсяко всем или некоторым узлам с запросом о доступности этого ресурса, используядля этого, например, механизм широковещательной связи. В основу алгоритмоврешения этой задачи могут быть положен волновые методы, описанные в гл. 6(см.
также работу Баратца и др. [23]).24Гл. 1. Введение: распределенные системы1.1. Что такое распределенная система?255. Взаимное исключение. Проблема взаимного исключения возникает в техслучаях, когда несколько процессов претендуют на некоторый общий ресурс, который в каждый период времени может быть использован только одним процессом.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
