Введение в распределённые алгоритмы. Ж. Тель (2009) (1185665), страница 5
Текст из файла (страница 5)
Среди них можно выделить монографии Таненбаума [182], Сломана и Креймера [176], Бала [21], Колориса и Доллиморе [56], Госцинского[101]. Как было уже сказано, в центре внимания нашей книги будут алгоритмы для распределенных систем. В § 1.3 будет объяснено, почему проектирование распределенных алгоритмов отличается от проектирования централизованных алгоритмов. Мы очертим также области исследования распределенных алгоритмов и коротко опишем содержание этой книги.1.1. Что такое распределенная система?151.1. Что такое распределенная система?В этой главе мы будем использовать термин «распределенная система» дляобозначения взаимосвязанной совокупности автономных компьютеров или процессоров. Компьютеры, процессы или процессоры будем называть узлами распределенной системы.
(В последующих главах мы будем использовать болееформальное понятие, см. определение 2.6.) Чтобы узлы могли считаться «автономными», они должны, по меньшей мере, обладать собственным независимымуправлением. По этой причине параллельный компьютер, архитектура которогоустроена по схеме «одна команда для многих данных» (SIMD 6)>не может считаться распределенной системой.
Чтобы считаться «взаимосвязанными», узлыдолжны обладать способностью обмениваться информацией.Поскольку в качестве узлов системы могут выступать процессы программы,приведенное определение охватывает также и такие программные системы, которые представляют собой совокупность взаимосвязанных процессов, выполняемых на одном и том же вычислительном устройстве.
Однако в большинствеслучаев в распределенной системе содержится хотя бы несколько процессоров,взаимосвязанных друг с другом при помощи средств коммуникации.В научной литературе встречаются также и более ограниченные вариантыопределения распределенных систем. Например, Таненбаум в своей книге [182]называет программную систему распределенной только тогда, когда существование автономных узлов представляется «прозрачным » для пользователей этойсистемы. В этом случае система, которая считается распределенной, ведет себятак, как положено виртуальной автономной вычислительной системе, но при этомреализация такой прозрачности требует разработки изощренных распределенныхалгоритмов управления.1.1.1. МотивировкаСуществует несколько причин, по которым распределенные системы либооказываются более предпочтительными, нежели последовательные системы, либоих использование становится просто неизбежным.
Мы обсудим здесь некоторыеиз этих причин, не претендуя на то, что список их окажется исчерпывающе полным. Иногда в пользу выбора распределенной системы можно привести сразунесколько доводов из числа перечисленных ниже, а иногда их преимущества обнаруживаются в качестве побочного эффекта, после того как они были выбраныпо какой-то другой причине. Характеристики распределенной системы могут также варьироваться в зависимости от тех обстоятельств, в силу которых потребовалась эта система, но эти вопросы мы обсудим более подробно в §§ 1.1.2—1.1.6.1.Обмен информацией.
Потребность в обмене данными между разнымикомпьютерами возникла в шестидесятых годах, когда большинство ведущих университетов и компаний начали обзаводиться своими собственными большими вычислительными машинами. Обмен данными между компьютерами, принадлежа»От англ. Single Instruction — Multiple Data. — Прим, перев.16Гл. 1. Введение: распределенные системыщими разным организациям, способствовал сотрудничеству между людьми, работающими в этих организациях, и это послужило толчком к развитию так называемых глобальных сетей. ARPANET, предшественник современной сети Internet,появилась в 1969 г.
Вычислительные установки, подключенные к глобальной сети (их иногда называют сетями дальней связи), как правило, снабжены всем,что необходимо для пользователя, включая резервное запоминающее устройство,дисковую память, принтеры, разнообразные прикладные программы.Позднее компьютеры стали более дешевыми и компактными, и вскоре буквально в каждой организации появилось много вычислительной техники (сейчасобычно каждому работнику выделяется персональный компьютер или рабочаястанция). Тогда для электронного обмена информацией между сотрудниками одной и той же организации потребовалось соединить друг с другом автономныекомпьютеры. Теперь уже нет ничего необычного в том, что в доме, в которомживет одна семья или даже один человек, имеется несколько компьютеров, соединенных друг с другом и образующих небольшую персональную домашнююсеть.2. Совместное использование ресурсов.
Хотя удешевление компьютеровдало организациям возможность снабдить каждого работника персональнымкомпьютером, этого нельзя сказать о таких периферийных устройствах, как резервные запоминающие устройства, дисковые накопители, принтеры. В небольших организациях каждый компьютер, испытывающий потребность в компиляторах и других прикладных программах, может получить поддержку от сервера,к которому он подключен. Кроме того, представляется неэффективным размножать все прикладные программы и сопутствующие им файлы на всех компьютерах; ведь помимо расходования дисковой памяти это создает ненужные трудности, связанные с поддержкой программного обеспечения. Таким образом, компьютеры, которым требуются печатающие устройства или дисковые накопители,могут рассчитывать на поддержку от соответствующих узлов сети. Сеть, объединяющая компьютеры на уровне одной организации, принято называть локальнойсетью.Причины, по которым организации выгоднее завести у себя сеть небольшихкомпьютеров вместо одной большой вычислительной машины, — это снижениерасходов и возможность наращивания ресурсов.
Прежде всего, небольшие компьютеры имеют лучшее соотношение между ценой и производительностью, нежели большие вычислительные машины: типичная большая вычислительная машина работает в 50 раз быстрее типичного мини-компьютера, но стоит в 500 раз дороже. Кроме того, если вычислительная мощность системы становится недостаточной, то к сети можно добавить новые машины (дисковые накопители, серверы,принтеры), чтобы удовлетворить потребности организации.
А вот если мощностьавтономной вычислительной системы становится недостаточной, то в этом случаеприходится менять всю систему.3. Повышение надежности за счет дублирования. Распределенные системы имеют более высокую потенциальную надежность, чем автономные системы, поскольку они обладают свойством частичного отказа. Под этим подразумевается способность системы перераспределять выполнение задач, возло1.1. Что такое распределенная система?17женных на вышедшие из строя компоненты системы, между теми узлами, которые продолжают исправно функционировать.
А вот выход из строя автономногокомпьютера наносит непоправимый ущерб всей системе, и продолжать работув этом случае нет никакой возможности. По этой причине при проектированиивысоконадежных вычислительных систем принято обращаться к распределеннымархитектурам.Типичная высоконадежная система состоит из нескольких (двух, трех или четырех) абсолютно идентичных монопроцессоров, на которых выполняется однаи та же прикладная программа, а специальный механизм голосования обеспечивает фильтрацию тех результатов, которые вычисляются на отдельных машинах.Для правильного функционирования распределенных систем, в которых отдельные компоненты могут выходить из строя, требуется достаточно сложная алгоритмическая поддержка.4.
Повышение производительности за счет параллельного выполнения. При наличии в распределенных системах большого числа процессоров открывается возможность сокращения общего времени выполнения задач большойвычислительной сложности за счет разделения работы между несколькими процессорами.Для этой цели создаются специальные параллельные компьютеры, но дажепользователи локальной сети могут получить выгоду от параллельного выполнения, если им удастся возложить решение задач на несколько рабочих станций,функционирующих параллельно.5.
Упрощение проектирования за счет специализации. Проектированиекомпьютерных систем может оказаться очень сложным делом, особенно в техслучаях, когда от них требуются широкие функциональные возможности. И оченьчасто это проектирование можно упростить, разделив всю систему на отдельныемодули так, чтобы каждый модуль мог выполнять только часть функциональнойнагрузки, но при этом был соединен с другими модулями.На уровне одной-единственной программы модулярность достигается путемвведения абстрактных типов данных и выделения отдельных процедур для решения разных задач.
Системы большего размера представляются в виде семействвзаимодействующих процессов. В обоих случаях эти модули могут выполняться и на однопроцессорном компьютере. Но можно создать и локальную сеть,объединяющую компьютеры разных типов, одни из которых предназначены дляпроведения численных расчетов, другие — для графических построений, третьи —для работы с файлами и т. д.1.1.2.