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

Их замечания способствовали значительному улучшению качества рукописи. Я получил также полезные предложения от студентов, посещавших курслекций «Расределенные алгоритмы» в осеннем семестре в Утрехтском университете. Факультет вычислительной математики снабдил меня всем необходимымдля обработки и печати текстов. Редакторскую работу выполнила Сьюзан Паркинсон.1.1. Что такое распределенная система?151.1. Что такое распределенная система?ГЛАВА 1ВВЕДЕНИЕ: РАСПРЕДЕЛЕННЫЕ СИСТЕМЫВ этой главе объясняется, почему нужно изучать распределенные алгоритмы.Мы начнем с того, что рассмотрим вкратце основные типы электронной аппаратуры и программного обеспечения, для которых были разработаны распределенныеалгоритмы. Под распределенной системой мы понимаем всякую вычислительнуюсистему, в которой несколько компьютеров или процессоров так или иначе вступают во взаимодействие.

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

В этой книге мы не будем, однако, заниматьсявопросом о том, как выглядят такие системы и как они используются; главнаятема книги — как заставить эти системы работать. И даже в этой теме мы выделим в дальнейшем еще более узкую часть, посвященную алгоритмам, которыеиспользуются в распределенных системах.Конечно, изучение одних лишь алгоритмов не приведет нас к полному пониманию того, как устроены распределенные системы и как они функционируют.Чтобы как следует понять такую систему, нужно также полностью изучить архитектуру ее аппаратуры и программного обеспечения, разделение ее функциональной составляющей на модули.

Кроме того, есть много важных вопросов,касающихся особенностей тех языков программирования, при помощи которыхсоздается программное обеспечение распределенных систем. Эти вопросы будутявляться предметом нашего обсуждения в § 1.2.К счастью, однако, есть превосходные книги, посвященные распределеннымсистемам, в которых основное внимание уделяется архитектуре и языкам программирования. Среди них можно выделить монографии Таненбаума [182] , Сломана и Креймера [176] , Бала [21] , Колориса и Доллиморе [56] , Госцинского[101] .

Как было уже сказано, в центре внимания нашей книги будут алгоритмы для распределенных систем. В § 1.3 будет объяснено, почему проектирование распределенных алгоритмов отличается от проектирования централизованных алгоритмов. Мы очертим также области исследования распределенных алгоритмов и коротко опишем содержание этой книги.В этой главе мы будем использовать термин «распределенная система» дляобозначения взаимосвязанной совокупности автономных компьютеров или процессоров.

Компьютеры, процессы или процессоры будем называть узлами распределенной системы. (В последующих главах мы будем использовать болееформальное понятие, см. определение 2.6.) Чтобы узлы могли считаться «автономными», они должны, по меньшей мере, обладать собственным независимымуправлением. По этой причине параллельный компьютер, архитектура которогоустроена по схеме «одна команда для многих данных» (SIMD 1) ), не может считаться распределенной системой. Чтобы считаться «взаимосвязанными», узлыдолжны обладать способностью обмениваться информацией.Поскольку в качестве узлов системы могут выступать процессы программы,приведенное определение охватывает также и такие программные системы, которые представляют собой совокупность взаимосвязанных процессов, выполняемых на одном и том же вычислительном устройстве.

Однако в большинствеслучаев в распределенной системе содержится хотя бы несколько процессоров,взаимосвязанных друг с другом при помощи средств коммуникации.В научной литературе встречаются также и более ограниченные вариантыопределения распределенных систем. Например, Таненбаум в своей книге [182]называет программную систему распределенной только тогда, когда существование автономных узлов представляется «прозрачным» для пользователей этойсистемы. В этом случае система, которая считается распределенной, ведет себятак, как положено виртуальной автономной вычислительной системе, но при этомреализация такой прозрачности требует разработки изощренных распределенныхалгоритмов управления.1.1.1. МотивировкаСуществует несколько причин, по которым распределенные системы либооказываются более предпочтительными, нежели последовательные системы, либоих использование становится просто неизбежным.

Мы обсудим здесь некоторыеиз этих причин, не претендуя на то, что список их окажется исчерпывающе полным. Иногда в пользу выбора распределенной системы можно привести сразунесколько доводов из числа перечисленных ниже, а иногда их преимущества обнаруживаются в качестве побочного эффекта, после того как они были выбраныпо какой-то другой причине. Характеристики распределенной системы могут также варьироваться в зависимости от тех обстоятельств, в силу которых потребовалась эта система, но эти вопросы мы обсудим более подробно в §§ 1.1.2 –1.1.6.1.

Обмен информацией. Потребность в обмене данными между разнымикомпьютерами возникла в шестидесятых годах, когда большинство ведущих университетов и компаний начали обзаводиться своими собственными большими вычислительными машинами. Обмен данными между компьютерами, принадлежа1) Отангл. Single Instruction – Multiple Data. — Прим. перев.16Гл. 1. Введение: распределенные системыщими разным организациям, способствовал сотрудничеству между людьми, работающими в этих организациях, и это послужило толчком к развитию так называемых глобальных сетей. ARPANET, предшественник современной сети Internet,появилась в 1969 г.

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

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

Совместное использование ресурсов. Хотя удешевление компьютеровдало организациям возможность снабдить каждого работника персональнымкомпьютером, этого нельзя сказать о таких периферийных устройствах, как резервные запоминающие устройства, дисковые накопители, принтеры. В небольших организациях каждый компьютер, испытывающий потребность в компиляторах и других прикладных программах, может получить поддержку от сервера,к которому он подключен. Кроме того, представляется неэффективным размножать все прикладные программы и сопутствующие им файлы на всех компьютерах; ведь помимо расходования дисковой памяти это создает ненужные трудности, связанные с поддержкой программного обеспечения. Таким образом, компьютеры, которым требуются печатающие устройства или дисковые накопители,могут рассчитывать на поддержку от соответствующих узлов сети.

Сеть, объединяющая компьютеры на уровне одной организации, принято называть локальнойсетью.Причины, по которым организации выгоднее завести у себя сеть небольшихкомпьютеров вместо одной большой вычислительной машины, — это снижениерасходов и возможность наращивания ресурсов. Прежде всего, небольшие компьютеры имеют лучшее соотношение между ценой и производительностью, нежели большие вычислительные машины: типичная большая вычислительная машина работает в 50 раз быстрее типичного мини-компьютера, но стоит в 500 раз дороже. Кроме того, если вычислительная мощность системы становится недостаточной, то к сети можно добавить новые машины (дисковые накопители, серверы,принтеры), чтобы удовлетворить потребности организации. А вот если мощностьавтономной вычислительной системы становится недостаточной, то в этом случаеприходится менять всю систему.3.

Повышение надежности за счет дублирования. Распределенные системы имеют более высокую потенциальную надежность, чем автономные системы, поскольку они обладают свойством частичного отказа. Под этим подразумевается способность системы перераспределять выполнение задач, возло-1.1. Что такое распределенная система?17женных на вышедшие из строя компоненты системы, между теми узлами, которые продолжают исправно функционировать. А вот выход из строя автономногокомпьютера наносит непоправимый ущерб всей системе, и продолжать работув этом случае нет никакой возможности. По этой причине при проектированиивысоконадежных вычислительных систем принято обращаться к распределеннымархитектурам.Типичная высоконадежная система состоит из нескольких (двух, трех или четырех) абсолютно идентичных монопроцессоров, на которых выполняется однаи та же прикладная программа, а специальный механизм голосования обеспечивает фильтрацию тех результатов, которые вычисляются на отдельных машинах.Для правильного функционирования распределенных систем, в которых отдельные компоненты могут выходить из строя, требуется достаточно сложная алгоритмическая поддержка.4.