Лекция 16. Тенденции в области распределенных систем - Лекция, раздел Философия, Распределенные системы и алгоритмы В Одной Из Своих Статей В 2001 Году Дж. Бэкус Отметил, Что Компьютерная Револ...
В одной из своих статей в 2001 году Дж. Бэкус отметил, что компьютерная революция испытала три волны. Первая волна началась с коммерциализацией кремниевых чипов и продолжалась 10-15 лет. Вторая волна связана с развитием технологий программного обеспечения и началась приблизительно в середине 80-х годов XX века. Третья волна началась в конце 90-х годов XX века и связана с развитием сетей и использованием их для коммуникаций компьютеров.
Третья волна послужила источником последующего бума информационных технологий. Рост технологических возможностей привел к тому, что компьютерные устройства стали значительно меньше по размерам и быстрее.
В последние годы появилось несколько новых направлений компьютерных исследований. В самостоятельную дисциплину оформляется сетевой компьютинг, разработка распределенных систем.
В основе технологий распределенных систем лежат удаленный доступ, высокая степень доступности ресурсов, устойчивость к сбоям и отказам, удаленное взаимодействие пользователей.
В настоящее время развитие распределенных и параллельных систем стимулируется такими задачами как информационный поиск и создание механизмов индексирования для поисковых машин, обеспечение мобильного мультимедиа, построение мультиагентных интеллектуальных систем, хранение терабайтных и пентабайтных массивов данных, обработка естественных языков, исследования в биоинформатике. Традиционные задачи моделирования в науке и технике, как и раньше, требуют все больших мощностей.
Эти задачи выдвигают требования к компьютерным системам, которые не могут быть удовлетворены в рамках просто «высокопроизводительных вычислений», например, с помощью параллельных суперкомпьютеров.
Вот только некоторые из требований и ограничений:
1. Пространственная распределенность компонент приложения и ресурсов системы, их динамическая природа (компоненты приложения и ресурсы могут динамически создаваться, перемещаться, становиться недоступными, уничтожаться).
2. Увеличивающаяся важность соединения в одно логическое целое (при сохранении физической разделенности) структурированных и неструктурированных ресурсов распределенных данных.
3. Мультидисциплинарные приложения требуют обеспечения взаимодействия отдельных моделей в рамках объединенной модели, требуют совместной работы исследователей, находящихся в разных научных центрах.
4. Высокая степень взаимодействия пользователей требует значительной гибкости при проектировании, реализации, сопровождении и модификации компонент программного обеспечения – в поддержке жизненного цикла систем.
5. Преобладание «нерегулярных» вычислений, не укладывающихся в циклы простой структуры с элементами массивов простого строения (что было бы так удобно для реализации на параллельном суперкомпьютере).
6. Применение методов, первоначально появившихся в исследованиях по искусственному интеллекту, для решения задач управления программными приложениями на различных этапах их жизненного цикла.
Одним из новых направлений в распределенных системах, в рамках которых есть надежда продвинуться вперед в удовлетворении перечисленных требований, является Grid computing – обработка информации в суперсетях (Грид).
В основе Грида лежат (в дополнение к распределенному компьютингу) федеративное объединение сообществ пользователей (без жесткой централизации), виртуализация ресурсов, стандартизация, маскирование неоднородности условий работы.
Под сообществом или виртуальной организацией понимается множество распределенных в сети ресурсов, управляемых по одним и тем же правилам; можно понимать также некоторую область администрирования. Виртуализация означает, что ресурсы в сообществе представлены так, что скрыто их местонахождение и принадлежность (правило не без исключений).
Стандартизация означает, что федерация построена на открытых стандартах, протоколах и интерфейсах. Маскирование неоднородностей означает, что программное обеспечение промежуточного уровня в Грид должно обеспечить «стирание различий» между программными обеспечениями промежуточного уровня виртуальных организаций.
Можно написать условную «формулу»:
Грид компьютинг = распределенный компьютинг + {федеративное объединение сообществ, виртуализация, стандартизация, маскирование неоднородностей}
Грид отличается от Интернета (точнее, его службы WWW) прежде всего тем, что поддерживает не только работу с распределенной информацией, но и использование распределенных вычислительных мощностей для выполнения приложений пользователей.
Грид характеризуется огромным (а часто, неопределенным) количеством взаимодействующих однородных и неоднородных компьютеров. Неоднородных – не только с аппаратной точки зрения, но и работающих с разными программными платформами, разными языковыми средствами.
Конечно, гораздо меньше проблем было бы, если бы все процессоры были одинаковы, а приложения функционировали на одной программной платформе. Но это линия развития суперкомпьютеров, супердорогих и относительно малочисленных в мире. Она существует и пока никуда не исчезает. Суперкомпьютеры – это «мамонты», но, возможно, они не вымрут. Суперкомпьютеры используются там, где они нужны относительно малому числу пользователей для решения сложных задач. На сегодня – это оборонные задачи (системы ПВО), задачи прогноза погоды и др.
Суперкомпьютеры мало доступны массовому пользователю, кроме тех случаев, когда суперкомпьютер (обычно, принадлежащий крупному научному центру) включается в Грид.
Надо заметить, что многие современные вычислительные комплексы, подпадающие под понятие «суперкомпьютер», строятся по кластерной схеме, т.е. их архитектуры движутся в сторону распределенных систем.
Грид привлекателен тем, что его почти не надо создавать – он вырастает сам. Это объективная реальность, как говорят философы. Только его рост нужно направлять, культивируя положительные изменения и своевременно предупреждая проблемы. Но для этого нужен план.
Грид требует переосмысления применяемых вычислительных моделей, средств их поддержки. Здесь недостаточно традиционных постулатов «открытых систем» – обеспечения интероперабельности систем управления различными ресурсами, масштабируемости и проч. Эти постулаты не теряют своего значения. Но требуется создание новых абстракций, языков программирования, средств поддержки для того, чтобы Грид был более эффективным.
Для динамического и адаптивного распределения ресурсов и управления ресурсами требуется развитие новых моделей и методов. Причем эти методы должны учитывать, что, одновременно, и сами приложения, пользующиеся этими ресурсами, изменяются в процессе работы.
Что касается конечного пользователя, то ему требуется определенная унификация в доступе к различным ресурсам Грид, несмотря на их разнородность и принадлежность многообразным собственникам.
Распределенные системы и Грид используют несколько уровней децентрализации данных и управления для того, чтобы адаптироваться к требованиям приложения. Децентрализация касается пространственного (географического) распределения, доступности данных, надежности хранения и использования, а также способов вычисления и коммуникации.
Приведенные выше требования предполагают высокую степень «прозрачности», при которой нижние уровни реализации скрыты, а на уровне приложения используются только значимые для этого уровня концепции.
Все темы данного раздела:
Сосредоточенные и распределенные системы
Во многих случаях термин «распределенная» является альтернативой термину «сосредоточенная». Так бывает, когда существуют (или могут существовать) системы, решающие одинаковые задачи, системы, функц
Тандемы распределенных систем
Рассмотрим две системы, S1 и S2 . Первая система функционирует для достижения некоторой цели G1 . При этом в любой момент времени имеется некот
Лекция 2. Распределенные задачи и алгоритмы
С системой S связана цель G, ради которой система функционирует. Эта цель ставится самой системой (если система – активная), или поставлена извне. Для достижения цели в системе должна
Лекция 3. Надежность и безопасность распределенных систем
Сравним сосредоточенную и распределенную системы с точки зрения надежности и безопасности.
Под надежностью понимается в соответствии с ГОСТ 27.002-89 свойство системы сохранять во в
Структура информационного пространства
Хотя термин «информационное пространство» является лишь метафорой, обратимся к проблеме анализа структуры этого пространства. Математики привыкли связывать с любым пространством некоторую структуру
Структура региональной системы образования и предпосылки создания РРИСО
Возникает естественный вопрос: почему выбран именно такой масштаб? Почему – региональная система? Дело в том, что это в определенном смысле минимаксный вариант. Уровень отдельного учебного заведени
Структуры РРИСО
Структуру РРИСО можно рассматривать с нескольких точек зрения. Прежде всего, это наиболее очевидная – географически ориентированная структура. Многие (но не все) элементы информационной системы при
Подсистемы. Взаимоотношения структур
Каждая из структур РРИСО строится по своим законам, поэтому, не стоит ожидать изоморфизма между парами структур. Идеально, если одни структуры являются надстройками над другими, использующими механ
Условная корпоративность
Хотя мы называем РРИСО корпоративной системой в силу того, что имеется определенный административный «каркас» на множестве ее пользователей, и у нее довольно четкая целевая направленность, тем не м
Неоднородность
Неоднородность – одна из важнейших характеристик РРИСО. Если многие корпоративные системы являются однородными, или неоднородность имеет место в одном - двух аспектах построения системы, то неоднор
Интегрируемость
Это одно из ключевых свойств в характеристике РРИСО. Это и «врожденное» и приобретаемое свойство.
Невозможно представить себе, чтобы такая система создавалась «с нуля». Существуют базы дан
Лекция 6. Моделирование распределенных систем. Язык Triad
Исследование распределенных систем – трудная задача. Прежде всего, распределенная система должна быть описана, т.е. должна быть построена модель системы. Для этой цели можно использовать различные
Model System2 (k, m, n: integer) def
System2 := star(Server, Serv[a..c]) + star(Serv[a], Node[1..k]) + star(Serv[b], Node[k+1..m]) + star(Serv[c], Node[m+1..n])
enddef.
For i:= 1 to n do
routine(System2.Node[i]) := Generator
endf.
При этом создается n экземпляров рутины Generator. Для каждого экземпляра рутины создается свой комплект локальных пер
For i:= 1 to n – 1 do
System := System + (System.Node[i] « System.Node[i + 1])
endf;
System := System + (System.Node[n] « System.Node[1])
В цикле к системе добавляются ребра м
Лекция 7. Распределенное имитационное моделирование
В одной из лекций шла речь о методах исследования распределенных систем. В качестве одного из методов рассматривался метод имитационного моделирования.
Если предположить, что предметом исс
Причины для перехода к распределенному моделированию
Использование распределенного моделирования объясняется:
- возможностью использования вычислительных ресурсов нескольких процессоров (компьютеров) для выполнения имитационного эксперимента
Два направления в развитии распределенных систем моделирования
Развитие распределенного имитационного моделирования идет по двум направлениям. Это монолитные системы моделирования и готовые системы моделирования, объединенные с помощью специального программног
Физическое время
Рассмотрим пример: пусть на нескольких компьютерах (клиентах) располагаются директории с файлами – списки товаров, на сервере – сводная директория, которая периодически обновляется. Приложение, рас
Управление временем в последовательном имитационном моделировании
Известно, что большую роль в имитационных моделях играет фактор времени. По определению имитационное моделирование является методом исследования динамических систем, в котором реальный объек
Управление временем в распределенном моделировании
Управление временем в распределённом моделировании должно обеспечивать выполнение событий в правильном хронологическом порядке. Более того, на алгоритмы синхронизации возлагается обязанность коррек
Парадоксы времени
Алгоритм управления временем должен следить за тем, чтобы события выполнялись в хронологическом порядке. Эта задача не является тривиальной. Действительно, логический процесс заранее не может знать
Консервативное управление временем
Первые алгоритмы синхронизации использовали консервативный подход. Принципиальная задача консервативного протокола – определить время, когда обработка очередного события из списка необработанных со
Алгоритм с нулевыми сообщениями
Первыми консервативными алгоритмами считаются алгоритмы, разработанные Bryant, Chandy, Misra.
Алгоритм предполагает:
- Топология процессов, которые посылают сообщения друг другу,
Использование дополнительной информации о временной метке следующего события
Рассмотрим подробнее недостатки алгоритмы с нулевыми сообщениями. Итак, одним из недостатков алгоритма является тот факт, что он может сгенерировать слишком большое количество нулевых сообщений.
Оптимистическое управление временем
В отличие от консервативных алгоритмов, не допускающих нарушения ограничения локальной каузальности, оптимистические методы не следят за этим ограничением. Однако этот подход гарантирует выявление
Лекция 9. Балансировка нагрузки в распределенных системах
Балансировка нагрузки (Load Balancing) применяется для оптимизации выполнения распределённых (параллельных) вычислений с помощью распределённой (параллельной) ВС. Балансировка
Статическая и динамическая балансировки
Следует различать статическую и динамическую балансировки.
Статическая балансировка выполняется до начала выполнения распределенн
Оценка загрузки
На этом этапе осуществляется приблизительная оценка загрузки каждого процессора. Полученная информация о загрузке используется в качестве базы данных для процесса балансировки, во-первых, для опред
Инициализация балансировки загрузки
Слишком частое выполнение балансировки загрузки может привести к тому, что выполнение имитационной модели только замедлится. Затраты на саму балансировку могут превзойти возможную выгоду от ее пров
Балансировка загрузки распределенной имитационной модели
В одной из предыдущих лекций мы рассматривали вопросы реализации распределенных систем имитации. Балансировку необходимо выполнять и при проведении распределённого моделирования. Первоначальная цел
Динамическая балансировка и перенос нагрузки
Алгоритм динамической балансировки использует характеристики состояния системы и принимает решение о том, с какого компьютера и на какой следует перенести работу во время моделирования. Это подход
RCL – cтратегия переноса нагрузки
Рассмотрим три алгоритма динамического переноса нагрузки, предложенные разработчиками SPEEDES:
- случайный алгоритм (random, R);
- алгоритм, основанный на коммуникациях (communica
Действия первого уровня
В начале действий по переносу нагрузки информации все компьютеры прекращают свою работу, и каждый получает информацию о локальной нагрузке в текущий момент времени. Информация о локальной нагрузке
Действия второго уровня
Действия второго уровня охватывают все рабочие станции распределённой системы. Конкретной количество нагрузки посылается с одной рабочей станции на другую. Основные действия связаны с выбором нагру
Реализация
Стратегия динамического переноса нагрузки RCL была разработана для SPEEDES с целью повышения её производительности. Были проведены эксперименты для выявления конкретных параметров, которые влияют н
Распределенные веб-сервисы
В настоящее время веб-сервисы находят все более широкое применение. Они используются в самых разных случаях в Интернет. Быстрое увеличение числа веб-сервисов и пользователей этих сервисов требует в
Использование мобильных агентов
Наряду с традиционными подходами (парадигма обмена сообщениями) рассмотрим другой – мультиагентный подход.
Напомним, что мобильный агент – это программный компонент, который может автомати
Различные подходы к балансировке, основанные на технологии клиент-сервер
Рассмотрим различные подходы к балансировке нагрузки. Выделяют следующие категории:
- клиентские;
- основанные на DNS;
- диспетчерские;
- серверные.
Мультиагентный подход к балансировке
Мобильные агенты используются для поддержки балансировки загрузки в параллельных и распределенных вычислениях. Рассмотрим кратко несколько проектов.
Проект Traveller
Проект
Лекция 10. Распределенные интеллектуальные системы на основе агентов
Современные системы искусственного интеллекта часто строятся как системы взаимодействующих и сотрудничающих агентов.
Одним из расширений понятия программы стало понятие агента. Оно появило
Агенты и МАС
Развитие интеллектуальных агентов и МАС очень популярны в среде исследователей ИС.
В области ИС интеллектуальные агенты используются, прежде всего, для интеграции информационных систем, по
Лекция 11. Распределенное хранение информации
Источники информации часто, как говорилось ранее, находятся в различных точках физического пространства. Если информация из этих источников не используется сразу, а потребность в ней возникает лишь
Фрагментация
Реляционные базы данных хранят отношения – таблицы, состоящие из строк и столбцов. Строка отношения называется кортежем и представляет собой запись (record в смысле языка программирования, н
Репликация
Под репликацией понимается создание копий некоторых фрагментов отношений и одновременное хранение нескольких копий на разных сайтах (в разных локальных БД). Репликация используется для того,
Схемы владения данными в распределенной БД
Выше, рассматривая распределенную базу данных, состоящую из локальных сайтов, мы неявно предполагали, что для каждой единицы данных существует вполне определенный единственный сайт, владеющий этими
Лекция 12. Волновые алгоритмы распространения информации
Многие задачи в распределенных системах решаются путем пересылки сообщений согласно некоторой схемы, которая гарантирует участие всех сайтов. Эта схема зависит от топологических особенностей систем
Алгоритм для кольцевой архитектуры
Если сайты распределенной системы соединены однонаправленными каналами связи так, что образуют граф – ориентированный цикл, применим следующий волновой алгоритм.
Суть его в следующем. Один
Алгоритм для структуры – дерева
Предположим, что соединение сайтов распределенной системы каналами образует граф – неориентированное дерево. Из теории графов известны следующие факты для деревьев:
1) дерево – связный аци
Алгоритм голосования
Алгоритм голосования применяется для распределенных систем, имеющих структуры полных графов. В этом случае инициатором может быть любой сайт. Для графа – звезды его тоже можно использовать, но иниц
Фазовый алгоритм
Фазовый алгоритм является децентрализованным алгоритмом для произвольных ориентированных графов. Двунаправленные связи тоже могут присутствовать, но они должны быть заданы парой параллельных встреч
Алгоритм Финна
Алгоритм Финна – еще один волновой алгоритм, который можно использовать в ориентированных сетях произвольной топологии. Он не требует того, чтобы диаметр сети был известен заранее, но подразумевает
Распространение информации с обратной связью
Важным применением волновых алгоритмов является случай, когда некоторая информация должна быть передана всем процессам и определенные процессы должны быть оповещены о завершении передачи. Эта задач
Синхронизация
Волновые алгоритмы могут использоваться для случаев, когда должна быть достигнута глобальная синхронизация процессов. Задача синхронизации формулируется следующим образом. В каждом процессе q
Вычисление нижней грани
Продемонстрируем применение волновых алгоритмов для вычисления функций, значения которых зависят от входов процесса на каждом сайте. В качестве представителей таких функций будут рассмотрены алгори
Лекция 13. Алгоритмы обхода сайтов
Алгоритмом обхода называется алгоритм, обладающий следующими тремя свойствами.
1) В каждом вычислении один сайт-инициатор, который начинает выполнение алгоритма, посылая ровно одно сообщен
Алгоритм обхода тора
Граф вида «тор» представляет собой решетку с дополнительными ребрами, соединяющими вершины из верхнего ряда («строки») решетки с вершинами из нижнего ряда, а также с ребрами, соединяющими вершины и
Алгоритм обхода гиперкуба
В теории графов известен класс графов Qn , называемых кубами размерности n, или гиперкубами. Это семейство описывается формулами Qn = K2
Алгоритм Тарри
Алгоритм обхода для произвольных связных графов был дан Тарри. Алгоритм основан на следующих двух правилах.
1. Процесс никогда не передает маркер дважды по одному и тому же каналу.
Лекция 14. Алгоритмы выбора сайтов
Во многих распределенных системах один из сайтов играет роль координатора при выполнении распределенного алгоритма. Иногда координатором является сайт, который инициировал выполнение алгоритма. Но
Алгоритм смещения
Алгоритм предназначен для динамического выбора координатора на основе локальных оценок сайтов. Предполагается, что каналы связи надежны, а сайты иногда могут прерывать (например, из-за отказов) сво
Выбор с помощью алгоритма для деревьев
Если топология распределенной системы – дерево или доступно остовное дерево системы, выбор можно провести с помощью алгоритма, приведенного в лекции 12. В этом алгоритме требуется, чтобы все концев
Алгоритмы выбора для кольцевых архитектур
В алгоритме Лелана для распределенной системы с архитектурой кольца (ориентированного цикла) каждый инициатор вычисляет список идентификаторов всех инициаторов, после чего выбирается инициатор с на
Лекция 15. Поиск в пиринговых системах
Пиринговые системы (peer-to-peer, P2P) – это такие компьютерные сети, в которых не используется классическая схема клиент-сервер, разделяющая множество всех узлов на два подмножества – серверов и к
Архитектура Грид
Следуя традиционному построению распределенных систем, можно описать архитектуру Грид, состоящую из четырех слоев:
1. Пользовательские интерфейсы, приложения и среда решения задач (problem
Мобильный компьютинг
Самостоятельным направлением является мобильный компьютинг. В его основе (в дополнение к распределенному компьютингу) лежат:
1) сети, обеспечивающие подключение к ним
Тотальный компьютинг
Английский термин pervasive computing обозначает проникающий, распространяющийся повсюду, всеобъемлющий, глубоко влияющий (компьютинг). Тотальный компьютинг ставит во главу угла конечного пользоват
Новости и инфо для студентов