МЕНЮ


Фестивали и конкурсы
Семинары
Издания
О МОДНТ
Приглашения
Поздравляем

НАУЧНЫЕ РАБОТЫ


  • Инновационный менеджмент
  • Инвестиции
  • ИГП
  • Земельное право
  • Журналистика
  • Жилищное право
  • Радиоэлектроника
  • Психология
  • Программирование и комп-ры
  • Предпринимательство
  • Право
  • Политология
  • Полиграфия
  • Педагогика
  • Оккультизм и уфология
  • Начертательная геометрия
  • Бухучет управленчучет
  • Биология
  • Бизнес-план
  • Безопасность жизнедеятельности
  • Банковское дело
  • АХД экпред финансы предприятий
  • Аудит
  • Ветеринария
  • Валютные отношения
  • Бухгалтерский учет и аудит
  • Ботаника и сельское хозяйство
  • Биржевое дело
  • Банковское дело
  • Астрономия
  • Архитектура
  • Арбитражный процесс
  • Безопасность жизнедеятельности
  • Административное право
  • Авиация и космонавтика
  • Кулинария
  • Наука и техника
  • Криминология
  • Криминалистика
  • Косметология
  • Коммуникации и связь
  • Кибернетика
  • Исторические личности
  • Информатика
  • Инвестиции
  • по Зоология
  • Журналистика
  • Карта сайта
  • Распределенные алгоритмы

    программу и поддерживаются механизмом голосования, чтобы

    отфильтровывать результаты машин. Правильное функционирование

    распределенной системы при наличии поврежденных компонент требует

    довольно сложной алгоритмической поддержки.

    4) Большая производительность благодаря распараллеливанию. Наличие

    многих процессоров в распределенной системе открывает возможность

    снижения дополнительного времени для интенсивной работы с помощью

    разделения работы среди нескольких процессоров.

    Параллельные компьютеры разработаны специально для этой

    цели, но пользователи локальных сетей также могут получить пользу от

    параллелизма, перекладывая задачи на другие рабочие станции.

    5) Упрощение разработки благодаря специализации. Разработка

    компьютерной системы может быть сложной, особенно если требуется

    значительная функциональность. Разработка может быть зачастую

    упрощена разбитием системы на модули, каждый из которых отвечает за

    часть функциональности и коммутируется с другими модулями.

    На уровне одной программы модульность достигается

    определением абстрактных типов данных и процедур для различных

    задач. Большая система может быть определена как набор кооперирующих

    процессов. В обоих случаях, модули могут быть исполнены в рамках

    одного компьютера. Но также возможно иметь локальную сеть с

    различными типами компьютеров: один снабжен специальным

    оборудованием для вычислений, другой – графическим оборудованием,

    третий – дисками и т.д.

    1.1.2 Компьютерные сети

    Под компьютерной сетью мы понимаем набор компьютеров, соединенных

    коммуникационными средствами, с помощью которых компьютеры могут

    обмениваться информацией. Этот обмен имеет место при посылке и получении

    сообщений. Компьютерные сети удовлетворяют нашему определению

    распределенных систем. В зависимости от расстояния между компьютерами и их

    принадлежностью, компьютерные сети называются либо глобальными, либо

    локальными.

    Глобальная сеть обычно соединяет компьютеры, принадлежащие различным

    организациям (предприятия, университеты и т.д.). Физическое расстояние

    между узлами обычно составляет 10 километров и более. Каждый узел такой

    сети – это законченная компьютерная система, включающая всю периферию и

    значительное количество прикладного программного обеспечения. Главная

    задача глобальной сети – это обмен информацией между пользователями

    различными узлов.

    Локальная сеть обычно соединяет компьютеры, принадлежащие одной

    организации. Физическое расстояние между узлами обычно 10 километров и

    менее. Узел такой сети – это обычно рабочая станция, файловый сервер или

    сервер печати, т.е. относительно маленькая станция, специализирующаяся на

    особых функциях внутри организации. Главная задача локальной сети – это

    обычный обмен информацией и разделение ресурсов.

    Граница между двумя типами сетей не может быть всегда четко очерчена,

    и обычно различие не столь важно с алгоритмической точки зрения, потому что

    во всех компьютерных сетях встречаются схожие проблемы. Релевантные

    отличия, относящиеся к развитию алгоритмов, следующие:

    1) Параметры надежности. В глобальных сетях вероятность, что что-то

    пойдет не так в течение предачи сообщения никода не может быть

    игнорирована. Распределенные алгоритмы для глобальных сетей обычно

    разрабатываются так, чтобы справляться с возможными неполадками.

    Локальные сети более надежные, и алгоритмы для них могут быть

    разработаны в предположении абсолютной надежности коммуникаций. В

    этом случае, однако, невероятное событие, что что-то произойдет

    не так может быть пропущено, что обусловит неправильную работу

    системы.

    2) Время коммуникации. Времена передачи сообщений в глобальных сетях

    на порядки больше, чем времена передачи в локальных сетях. В

    глобальных сетях время необходимое для обработки сообщения почти

    всегда может быть игнорировано по стравнению со временем передачи

    сообщения.

    3) Гомогенность. Даже хотя в локальных сетях не все узлы обязательно

    равны, обычно возможно принять единое программное обеспечение и

    протоколы для использования в рамках одной организации. В

    глобальных сетях используется множество различных протоколов,

    которые поднимают проблему преобразования между различными

    протоколами и разработки программного обеспечения, которое

    совместимо с различными стандартами.

    4) Взаимное доверие. Внутри одной организации можно доверять всем

    пользователям, но в глобальной сети это определенно не так.

    Глобальная сеть требует развития безопасных алгоритмов, защищающих

    узлы от аггресивных пользователей.

    Раздел 1.1.3 посвящен краткому обсуждлению глобальных сетей,

    локальные сети обсуждаются в разделе 1.1.4.

    1.1.3 Глобальные сети

    Историческое развитие. Большая часть первооткрывательской работы в

    развитии глобальных компьютерных сетей было проделано в проектах агентства

    ARPA министерства обороны США. Сеть ARPANET начала работать в 1969, и

    соединяла в то время 4 узла. Эта сеть выросла до нескольких сотен узлов, и

    другие сети были установлены с использованием подобной технологии (MILNET,

    CYRPRESS). ARPANET содержит специальные узлы (называемые процессорами

    интерфейса сообщений (IMP)), которые предназначены только для обработки

    потока сообщений.

    Когда UNIX системы стали широко использоваться, было признана

    необходимость информационного обмена между различными UNIX машинами, для

    чего была написана программа uucp (Unix-to-Unix CoPy). С помощью этой

    программы можно обмениваться файлами по телефонным каналам и сетям с

    пользователями UNIX – эта программа дала название быстрорастущим UUCP

    сетям. Также другая большая сеть, BITNET, была разработана в восьмидесятые,

    так как ARPANET принадлежала министерству обороны и только несколько

    организаций могли к ней подключаться.

    Сегодня все эти сети соединены между собой с помощью узлов, которые

    принадлежат двум сетям (называемые шлюзами) и позволяющих обмениваться

    информацией узлам различных сетей. Введение унифицированного адресного

    пространства превратило все сети в одну виртуальную сеть, известную как

    Internet. Электронный адрес автора (gerard@cs.ruu.nl) обеспечивает

    информацию о сети, к которой подключен его департамент.

    Алгоритмические проблемы и проблемы организации. Глобальные сети

    всегда организованы как сети типа точка-точка. Это означает, что

    коммуникация между парой узлов осуществляется при помощи механизма

    особенного по отношению к этим двум узлам. Такой механизм может быть

    телефонной линией, оптоволокном или спутниковой связью и т.д. Структура

    соединений в сетях точка-точка может быть хорошо изображена, если

    нарисовать каждый узел как окружность и связи между ними как линии, если

    линия коммуникация существует между этими двумя узлами, см. рис. 1.1.

    Говоря техническим языком, структура представляется графом, грани которого

    представляют собой линии коммуникации в сети. Сводка по терминологии теории

    графов приведена в Дополнении Б.

    [pic]

    Рис. 1.1 Пример сети точка-точка

    Основное назначение глобальных сетей – это обмен информацией,

    например, в форме электронной почты, досок объявлений, и удаленных файлов.

    Разработка приемлемой системы коммнуникаций для этих целей требует решения

    следующих алгоритмических проблем, некоторые из которых обсуждаются в Части

    1 этой книги.

    1) Надежность обмена данными по типу точка-точка (глава 3). Два узла

    соединенные линией, обмениваются данными по этой линии, но они

    должны как-то справляться с потенциальной ненадежностью линии. Из-

    за атмосферных явлений, падения напряжения и других физических

    обстоятельств, сообщение, посланное через линию может быть

    получено с частично искаженным или даже утерянным. Эти нарушения

    при передаче должен быть распознаны и исправлены.

    Эта проблема встречается не только для двух

    напрямую соединенных узлов, но также для узлов, не соединенных

    напрямую, а связанных посредством промежуточных узлов. В этом

    случае проблема даже более сложна, потому что ко всему прочему

    сообщения могут доставляться в порядке, отличном от того, в

    котором они были посланы, а также сообщения могут прибывать с

    большим опозданием или продублированные.

    2) Выбор путей коммуникации. (глава 4). В сети точка-точка обычно

    слишком дорого обеспечивать связь между каждой парой узлов.

    Следовательно, некоторые пары узлов должны положиться на другие

    узлы для того, чтобы взаимодействовать. Проблема маршрутизации

    касается выбора пути (или путей) между узлами, которые хотят

    взаимодействовать. Алгоритм, используемый для выбора пути, связан

    со схемой, по которой узлы именуются, т.е. форматом адреса,

    который узел должен использовать, чтобы послать сообщение другому

    узлу. Выбор пути в промежуточных узлах производится с

    использованием адреса, и выбор может быть сделан эффективно, если

    в адресе кодируется в адресах.

    3) Контроль перегрузок. Пропускная способность коммутируемой сети

    может сильно падать, если много сообщений передается одновременно.

    Поэтому генерирование сообщений различными узлами должно

    управляться и должно зависеть от свободных мощностей сети.

    Некоторые методы предотвращения перегрузок обсуждаются в [Tann88,

    раздел 5.3].

    4) Предотвращение тупиков. (глава 5). Сети типа точка-точка иногда

    называются сетями типа сохранить-и-передать, потому что сообщение,

    которое посылается через несколько промежуточных узлов должно

    сохраняться в каждом из этих узлов, а затем форвардиться к

    следующему узлу. Так как пространство памяти, доступное для этой

    цели в промежуточных узлах ограничено, то память должна тщательно

    управляться для того, чтобы предотвратить тупиковые ситуации. В

    таких ситуациях существует набор сообщений, ни одно из которых не

    может быть отфорвардено, потому что память следующего узла в

    маршруте полностью занято другими сообщениями.

    5) Безопасность. Сети, соединяют компьютеры с различными

    пользователями, некоторые из которых могут попытаться

    злоупотребить или даже испортить системы других. Так как возможно

    зарегистрироваться в компьютерной системе из любой точки мира, то

    требуются надежные методы для аутентификации пользователей,

    криптографические методы, сканирование входящей информации.

    Криптографические методы могут быть использованы, чтобы шифровать

    данные для безопасности от несанкционированного чтения и чтобы

    ставить электронные подписи против несанкционированного написания.

    1.1.4 Локальные сети

    Локальная сеть используется организацией для соединения набора

    компьютеров, которые ей принадлежат. Обычно, основное назначение этих

    компьютеров заключается в разделении ресурсов (как файлов, так и аппаратной

    перефирии) и для облегчения обмена информацией между сотрудниками. Иногда

    сети также используются для повышения скорости вычислений (перекладыванием

    задач на другие узлы) и чтобы позволить некоторым узлам быть для других

    запасными в случае их повреждения.

    Узлы

    Рис. 1.2 Сеть

    с шинной

    организацией

    Примеры и организация. В первой половинек 1970-х локальная сеть

    Ethernet была разработана Xerox. В то время как имена глобальных сетей

    ARPANET, BITNET, и т.д. происходят от конкретных сетей, имена локальных

    сетей – это обычно имена производителей. Есть одна ARPANET, одна BITNET, и

    одна UUCP сеть, каждая компания может установить свою собственную Ethernet,

    Token Ring или SNA сеть.

    В отличие от глобальных сетей, ethernet организована с использованием

    шинной структуры, т.е. сообщение между узлами имеет место посредством

    единственного механизма, к которому все узлы подключены; см. рис. 1.2.

    Шинная организация стала повсеместной для локальных сетей, хотя могут быть

    различия в том как выглядит механизм или как он используется.

    Устройство Ethernet разрешает передачу только одного сообщения в каждый

    момент времени; другие разработки, такие как токен ринг (разработанный в

    лаборатории Цюрих IBM), допускает пространственное использование, которое

    означает, что несколько сообщений могут передаваться через механизм

    коммуникации одновременно. Шинная организация требует немного аппаратуры и

    поэтому дешевая, но имеет тот недостаток, что эта организация не очень

    хорошо масштабируется. Это означает, что существует очень жесткий потолок

    числа узлов, которые могут быть соединены одной шиной. Большие компании со

    многими компьютерами должны соединять их несколькими шинами, и использовать

    мосты для соединения шин друг с другом, создавая иерархию всей сети

    организации.

    Не все локальные сети используют шинную организацию. IBM разработала

    точка-точка сетевой продукт называемый SNA для того, чтобы позволить

    покупателям соединять их разнообразные продукты IBM. Разработка SNA

    усложнялась требованием ее совместимости с почти каждым сетевым продуктом,

    уже предлагаемым IBM.

    Алгоритмические проблемы. Внедрение локальных сетей требует решения

    некоторых, но не всех, проблем, рассмотренных в предыдущем подразделе по

    глобальным сетям. Надежный обмен данными не такая большая проблема, потому

    что шины обычно очень надежны и быстры. Проблема маршрутизации не встает в

    шинных сетях, потому что каждое назначение может быть адресовано прямо по

    сети. В кольцевых сетях все сообщения обычно посылаются в одном направлении

    вдоль кольца и удаляются либо получателем, либо отправителем, что также

    делает проблему маршрутизации исчерпанной. В шине нет перегрузки благодаря

    тому, что каждое сообщение принимается (берется с шины) немедленно после

    его отправки, но все равно необходимо ограничивать нагрузку от сообщений,

    ожидающих в узлах выхода на шину. Раз сообщения не сохраняются в

    промежуточных вершинах, то и не возникает тупика типа сохрани-и-передай.

    Нет необходимости в механизмах безопасности помимо той обычной защиты,

    предлагаемой операционной системой, если компьютерами владеет одна

    компания, которая доверяет своим сотрудникам.

    Использование локальных сетей для распределенного выполнения прикладных

    программ (набора процессов, распространенных по узлам сети) требует решения

    следующих проблем распределенного управления, некоторые из которых

    обсуждаются в части 2.

    1) Широковещание и синхронизация (глава 6). Если информация должна быть

    доступна всем процессам, или все процессы должны ждать выполнения

    некоторого глобального условия, необходимо иметь схему передачи

    сообщений, которая каким-либо образом «дозванивается» до всех

    процессов.

    2) Выборность (глава 7). Некоторые задачи должны быть осуществлены

    точно одним процессом из множества, например, генерирование вывода

    или инициализация структуры данных. Если, как иногда желательно или

    необходимо, нет процесса предназначенного для этого заранее, то

    распределенный алгоритм должен выбрать одни из процессов для

    выполнения задачи.

    3) Обнаружение завершения (глава 8). Не всегда есть возможность для

    процессов в распределенной системе замечать напрямую, что

    распределенные вычисления, в которые они вовлечены, завершены.

    Поэтому обнаружение необходимо для того, чтобы сделать вычисляемые

    результаты окончательными.

    4) Распределение ресурсов. Узел может потребовать доступ к некоторым

    ресурсам, которые доступны, где-либо в сети, но не знает, где этот

    ресурс находится. Поддержка таблицы, которая показывает

    местоположение каждого ресурса не всегда адекватна, потому что число

    потенциальных ресурсов может быть слишком большим для этого, или

    ресурсы могут мигрировать от одного узла к другому. В этом случае,

    запрашивающий узел может опрашивать все или некоторые узлы на

    предмет доступности ресурса, например, используя широковещательный

    механизм. Алгоритмы для этой проблемы могут базироваться на волновых

    механизмах, описанных в главе 6, см., например Баратц и другие

    [BGS87].

    5) Взаимное исключение. Проблема взаимного исключения встает, если

    процессы могут полагаться на общий ресурс, который может быть

    использован только одним ресурсом в каждый момент времени. Таким

    ресурсом может быть принтер или файл, который должен быть

    перезаписан. Распределенному алгоритму в этом случае необходимо

    определить, если требуют процессы доступа одновременно, какому из

    них разрешить использовать ресурс первым. Также удостовериться в

    том, что следующий процесс начнет использовать ресурс, только после

    того, как предыдущий процесс закончит его использовать.

    6) Обнаружение тупиков и их разрешение. Если процессы должны ждать друг

    друга (как в случае, если они разделяют ресурсы, и также, если их

    Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36


    Приглашения

    09.12.2013 - 16.12.2013

    Международный конкурс хореографического искусства в рамках Международного фестиваля искусств «РОЖДЕСТВЕНСКАЯ АНДОРРА»

    09.12.2013 - 16.12.2013

    Международный конкурс хорового искусства в АНДОРРЕ «РОЖДЕСТВЕНСКАЯ АНДОРРА»




    Copyright © 2012 г.
    При использовании материалов - ссылка на сайт обязательна.