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

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 7)

Алгоритм, применя­емый для выбора канала связи, зависит от схемы именования узлов сети, т. е. отформата того адреса, который может использовать один узел, чтобы отправитьсообщение другому узлу. Выбор канала связи в промежуточных вершинах осу­ществляется на основе указанного адреса, и этот выбор можно сделать более эф-1.1.

Что такое распределенная система?21фективно, если в адресах узлов удастся каким-нибудь образом «закодировать»топологическую информацию.3. Устранение перегрузки. Пропускная способность коммуникационнойсети может значительно понизиться, если одновременно передается большое ко­личество сообщений. Поэтому нужно уметь управлять формированием сообще­ний в различных узлах сети в зависимости от сложившейся пропускной спо­собности сети.

Некоторые методы устранения перегрузки обсуждаются в книге[182, §5.3].4. Предотвращение блокировки (тупиков ) (см. гл. 5). Сети с двухточеч­ным соединением иногда называют сетями с промежуточным хранением дан­ных., ввиду того что сообщения, которые при пересылке проходят через ряд про­межуточных узлов, должны быть вначале помещены в память каждого из этихузлов, а затем переправлены следующему по порядку узлу. Так как в промежуточ­ных узлах объем доступной для этих целей памяти ограничен, с памятью нужнообращаться аккуратно, чтобы избежать тупиковых ситуаций. Это такие ситуации,когда в сети есть некоторое множество сообщений, ни одно из которых не мо­жет быть переправлено дальше, поскольку память в следующем узле маршрутаполностью занята другими сообщениями.5.

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

Можно воспользовать­ся методами криптографии (см., например, [182, §7.1]) для шифрования данных,чтобы обезопасить их от неразрешенного прочтения, и для внесения электронныхподписей, чтобы обезопасить их от недозволенной записи.1.1.4. Локальные сетиЛокальные сети используются для того, чтобы установить соединение меж­ду компьютерами, принадлежащими одной и той же организации. Обычно такоесоединение предназначено, главным образом, для совместного использования ре­сурсов (как файлов, так и периферийной аппаратуры) и для обеспечения обменаинформацией между сотрудниками организации.

Время от времени сети приме­няются также для ускорения вычислений (путем раздельного решения задачинесколькими узлами) и для резервной замены одних узлов другими в случае воз­никновения неполадок.Примеры сетей и устройство сетей. В первой половине семидесятых годовXX в. корпорация Xerox разработала локальную сеть Ethernet3!. Названия гло­бальных сетей ARPANET, BITNET и т. п. служат для наименования отдельных3) Ethernet — это торговая марка компании Xerox Corporation.

— Прим, автора.22Гл. 1. Введение: распределенные системысетей, тогда как названия локальных сетей обычно используются в качестве тор­говых марок. Существует одна сеть ARPANET, одна сеть 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. Введение: распределенные системы5. Взаимное исключение. Проблема взаимного исключения возникает в техслучаях, когда несколько процессов претендуют на некоторый общий ресурс, ко­торый в каждый период времени может быть использован только одним процес­сом. Таким ресурсом может быть печатающее устройство или файл, в которыйнужно провести запись. Если несколько процессов одновременно обращаютсяс одним и тем же запросом, распределенному алгоритму приходится определять,какому процессу следует в первую очередь открыть доступ к ресурсу. Кроме того,необходимо сделать так, чтобы следующий процесс приступил к использованиюресурса только после того, как предыдущий процесс завершит работу с этимресурсом.6.

Обнаружение и устранение тупиков. Если процессы должны ожидатьдруг друга (а это может случиться, если они совместно используют какой-то ре­сурс, а также если вычисление каждого из них зависит от тех данных, которыедолжны вычислить другие процессы), может возникнуть циклическая блокиров­ка, которая не позволит продолжить дальнейшее вычисление. Такие тупиковыеситуации должны быть обнаружены, после чего должны быть предприняты адек­ватные действия для перезапуска или продолжения вычисления.7.

Характеристики

Список файлов книги