Распределенные системы и алгоритмы

А.И.Миков, Е.Б.Замятина



Распределенные системы и алгоритмы



Курс лекций





Содержание

Лекция 1. Распределенные системы
Лекция 2. Распределенные задачи и алгоритмы
Лекция 3. Надежность и безопасность распределенных систем
Лекция 4. Пример. Распределенная информационная система организации. Концепции
Лекция 5. Пример. Распределенная информационная система организации. Архитектура
Лекция 6. Моделирование распределенных систем. Язык Triad
Лекция 7. Распределенное имитационное моделирование
Лекция 8. Синхронизация времени в распределенном имитационном моделировании
Лекция 9. Балансировка нагрузки в распределенных системах
Лекция 10. Распределенные интеллектуальные системы на основе агентов
Лекция 11. Распределенное хранение информации
Лекция 12. Волновые алгоритмы распространения информации
Лекция 13. Алгоритмы обхода сайтов
Лекция 14. Алгоритмы выбора сайтов
Лекция 15. Поиск в пиринговых системах
Лекция 16. Тенденции в области распределенных систем


Лекция 1. Распределенные системы
Под системой понимается множество элементов и связей между ними. Обозначим V – множество элементов системы. Тогда бинарное отношение R2 Í V ´ V задает наличие попарных связей между элементами. Если для некоторых элементов xÎV и yÎV пара (x, y)Î R2 , то в системе существует связь от x к y. Если (x, y)Ï R2 , то такой связи нет. Порядок элементов в паре важен, так как связи могут быть направленными, несимметричными.
В системе могут быть не только попарные связи, но и связи троек элементов. Такие связи описываются тернарными отношениями R3 Í V ´ V ´ V = V 3. Например, связь «ребенок и его родители» – связь трех элементов.
В общем случае в системе могут быть также связи, задаваемые отношениями R4 ÍV 4 , R5 Í V 5.,…, Rn Í V n. Здесь n – количество элементов в системе.
С каждым отношением связан определенный смысл, выражаемый высказыванием, например, «x следует за y», «x посылает сигнал y», «x – ребенок y и z» и т.д. Иначе говоря, вместо отношений (или вместе с отношениями) удобно рассматривать соответствующие предикаты P2 , P3 , P4 ,…, Pn . В дополнение к перечисленным рассматривают и предикаты P1 , которые можно интерпретировать как выражение свойств элементов множества V.
Подчеркнем, что бинарных отношений в системе может быть несколько. Например, в цилиндре двигателя автомобиля газ (бензино-воздушная смесь), загораясь, толкает поршень и, одновременно, нагревает его. Т.е. существует отношение «x толкает y» и отношение «x нагревает y». Ясно, что в зависимости от целей исследования системы одни отношения рассматриваются как существенные, а другие – как второстепенные.
Множественность касается не только бинарных, но и тернарных и других отношений. В общем случае систему можно описать как набор S = {V, {Pi, j}}, где индекс i обозначает арность отношения (или количество мест предиката), а индекс j дает возможность различать отношения одной и той же арности.
Некоторые из предикатов P1, j могут характеризовать местоположение элемента системы. Например, его географические координаты, пространственные координаты (спутник связи), нахождение в определенном помещении (компьютер локальной сети) и т.д. Подмножества элементов, имеющих одно и то же (в пределах некоторого допуска, приближения) местоположение, мы будем называть сайтами. Аналогично, некоторые из предикатов P2, j могут характеризовать взаимное расположение элементов, например, расстояние, время передачи сигнала, стоимость переноса информации или вещества от одного элемента системы к другому. Взаимное расположение может быть существенным и для троек элементов, и для четверок и т.д., и выражаться соответствующими предикатами.
Распределенными системами будем называть такие системы, для которых предикаты местоположения элементов или групп элементов играют существенную роль с точки зрения функционирования системы, а, следовательно, и с точки зрения анализа и синтеза системы.
Распределенные системы могут быть непрерывными и дискретными.
Непрерывные распределенные системы характеризуются бесконечным количеством элементов, а также тем, что в любой малой окрестности любого элемента (в смысле предикатов местоположения) находится, по крайней мере, еще один элемент.
Примером непрерывной распределенной системы является стальной лист, нагреваемый в одной точке газовой горелкой. Элементы системы – это «точки» листа с определенными координатами. Каждая точка в некоторый момент времени характеризуется значением температуры, а весь лист описывается некоторым температурным полем. Температуры близко расположенных точек имеют мало отличающиеся друг от друга значения, зависящие от удаленности этих точек от источника тепла. С течением времени значения температур увеличиваются до некоторых пределов, зависящих от температуры горелки, координат точек, величины теплоотдачи листа в окружающее пространство.
Дискретные распределенные системы характеризуются тем, что элементы системы четко «очерчены», отделены друг от друга. Один из видов отношений – бинарное отношение «быть соседними элементами». Между двумя соседними элементами других элементов нет. Это не означает, что между ними нельзя включить какой-либо третий элемент. Но тогда первые два перестают быть соседними.
В дальнейшем рассматриваются в основном дискретные системы.

Примеры распределенных систем.

1. Сеть газопроводов.
Сеть газопроводов состоит из газоперекачивающих станций, газораспределительных узлов, трубопроводов. Трубопроводы соединяют между собой станции и узлы. Трубопроводы проложены также к источникам (месторождениям) газа и к потребителям газа.
Основное отношение в системе – это соединение (направленное) элементов: соединение трубопровода и газоперекачивающей станции, соединение трубопровода и газораспределительного узла. Важными параметрами элементов являются их местоположения (в географическом смысле). Для трубопровода местоположение задается более сложным образом, чем для станций и узлов: как минимум, это две точки – начало и конец трубопровода, в общем случае – это кривая в трехмерном пространстве (разница высот должна приниматься во внимание при перекачке газа).
Для эксплуатации сети газопроводов должны постоянно решаться задачи измерения давления в различных точках сети, определения объемов пропущенного газа, регулирования потоков газа. Характерно, что эти задачи, с одной стороны, распределены в сети (т.е. ставятся и решаются в различных точках системы), с другой стороны, являются частями общей задачи управления сетью, связывающей источники газа с потребителями.
2. Электросети.
Электросеть включает линии электропередач различного напряжения и трансформаторные подстанции. Электросеть соединена с «генерирующими объектами» - ГЭС, теплоэлектростанциями, АЭС, и с потребителями. Трансформаторные подстанции, генерирующие объекты, потребители имеют географические координаты. Линии электропередач характеризуются плоскими кривыми (разница высот не имеет значения для электрического тока).
Для управления сетью необходимо знать значения электрического напряжения в различных точках сети, падение напряжения в ЛЭП, значения потребляемого тока. Вся эта информация распределена по сети. По сети распределены также устройства управления участками сети – различные коммутаторы, переключатели, выключатели. Задача управления сетью с точки зрения оптимизации потоков электроэнергии решается централизованно, но иногда она разбивается на подзадачи, решаемые в определенных секторах сети. Например, известные «веерные отключения» при перегрузке сети, перенаправление потоков из одних регионов в другие в соответствии с временем суток и т.д.
Кроме этого решаются задачи для совместной работы сетей разных стран. В этом случае орган, принимающий централизованные решения, отсутствует, и задача решается как распределенная.
3. Сети связи.
Это один из ярких примеров распределенных систем, особенно в тех случаях, когда сети связи используются для передачи компьютерной информации, т.е. в качестве компьютерных сетей.
Каждый узел сети характеризуется скоростью обработки информации. В сетях связи – это скорость коммутации (переключения) каналов связи. В компьютерных сетях в узле сети может находиться сервер, который выполняет определенное обслуживание по поступающим запросам. Время этого обслуживания – дополнительная характеристика узла сети.
Каналы связи, соединяющие узлы, различаются своей пропускной способностью – скоростью передачи информации и иными техническими характеристиками (оптоволоконные, кабельные, спутниковые каналы, радиоканалы и др.). В зависимости от этого они могут требовать различных процедур обслуживания.
В целом сеть связи должна обеспечить передачу сообщения от одного узла к другому. Причем эти узлы могут быть не связаны непосредственно друг с другом каналом связи. Тогда требуется проложить маршрут от одного узла к другому, проходящий через промежуточные узлы.
Задача маршрутизации – типичная распределенная задача оптимизационного характера. Она имеет многообразные постановки.
Простейший вариант – статическое решение. По заданной топологии сети, известным пропускным способностям каналов и средним задержкам в узлах можно для каждой пары узлов vi и vj найти оптимальный маршрут и всегда им пользоваться.
Но интенсивность запросов к разным узлам различна и может изменяться в течение суток или еще быстрее. В результате перед некоторыми узлами образуются большие очереди запросов, увеличивающие время прохождения сообщения по маршруту. Или, при заполнении буфера очередей сообщения могут получать отказ в обслуживании. В этом случае оптимальным может оказаться другой маршрут.
Такие ситуации приводят к необходимости динамической маршрутизации, т.е. определении маршрута сообщения уже во время его перемещения по сети.
Задача маршрутизации входит как составная часть в более общую задачу управления сетью связи.
4. Логистические системы.
Система перевозки грузов включает транспортные средства (грузовики, поезда, самолеты, корабли), транспортные пути (автомобильные, железные дороги, морские и речные пути и др.), склады, порты, станции, погрузочно-разгрузочные механизмы и проч.
При транспортировке конкретного груза от поставщика к получателю логистическая цепочка может включать довольно большое количество элементов системы, в том числе многочисленные перегрузки с одного вида транспорта на другой. При этом транспортное средство зачастую везет одним рейсом грузы от разных поставщиков разным получателям. Каждый элемент логистической системы характеризуется определенным набором параметров – грузоподъемностью, скоростью, размером грузов, объемом складских помещений, количеством причалов в порту и т.д.
Если к этому добавить то, что чуть ли не каждый элемент имеет своего собственника, то станет понятно, что централизованно решать задачу оптимизации доставки грузов (минимальное время при ограничении на стоимость или минимальная стоимость при ограничении на время) невозможно.
Это типичная распределенная задача, решаемая в отдельных элементах системы. И как результат «сшивки решений» получается общее решение задачи управления всей логистической системой методом, похожим на самоорганизацию.
5. Банковская система.
Почти каждый банк самостоятелен. Банковская система распределена по всему Земному шару. Но у всех банков есть общая задача – обслужить клиента, где бы он ни был. Клиент должен иметь возможность получить свои деньги даже там, где о его банке никогда не слышали. Или сделать банковский перевод в далекую страну. Для осуществления этих операций банки связаны между собой системой договоров и поддерживающими эту систему техническими средствами.
Клиент, находящийся в пункте A, ставит задачу проводки платежа из своего банка, находящегося в пункте B, в банк получателя, находящийся в пункте C. При этом получатель, находящийся в пункте D, должен получить уведомление. Это общая задача, которая разделяется банками на части, решаемые в разных местах, т.е. превращается в распределенную задачу.
6. Корпорации.
Крупные фирмы (и даже не очень крупные) имеют офисы и производства, рассредоточенные в пределах города, страны и даже всей планеты, а в будущем с освоением полезных ископаемых на Луне или Марсе, заберутся и туда. Причины рассредоточенности различны. Может быть, это отсутствие достаточных помещений в одном месте или другие подобные факторы.
Но есть и совершенно объективные причины создания удаленных подразделений (отделений) корпораций. Прежде всего, это приближение к рынку сбыта продукции. Рынок, по определению, является рассредоточенной системой по большим территориям. Для того чтобы эффективно работать на рынке, корпорация создает региональные отделения. Например, транснациональные корпорации обычно открывают отделения по Западной Европе, Восточной Европе, Африке и Ближнему Востоку, Азии, Америке. При большом рынке происходит еще большее географическое дробление.
Вторая причина создания удаленных подразделений – вынесение производств в другие страны. Штаб-квартира корпорации, как правило, находится в высокоразвитой стране, в которой законодательно закреплена довольно высокая заработная плата наемных работников. Производства же выносятся в те страны, где работники довольствуются весьма скромной оплатой. Соответственно, прибыли корпорации растут. Это касается и высокотехнологичных областей.
Например, в некоторых американских исследованиях утверждается, что в США профессия программиста в ближайшие десятилетия будет неперспективной: рост потребности в труде программистов будет отставать от роста потребности в труде многих других специалистов. Он будет отставать даже от среднего (по всем специальностям) роста потребности в специалистах. Причина простая – работа по программированию будет заказываться работникам в других странах. В настоящее время Индия стала одной из таких стран. Программный продукт при этом выпускается не с маркой «made in India», а под маркой корпорации – заказчика.
Наличие отделений у корпорации приводит к необходимости создания распределенных информационных систем.

7. Государственное и муниципальное управление.
Системы государственного и муниципального управления, что называется, «по определению» являются распределенными системами. Или можно сказать «естественными распределенными системами». Такими же естественными, как и газовые и электросети. Управление, выработанное в столице, может достигать своих целей только при помощи своих уполномоченных на местах. Равно, как и сбор информации, необходимой для выработки управления, также производится на местах.

Сосредоточенные и распределенные системы

Множество элементов в каждой из систем, обычно, можно разделить на два подмножества, V(Sd) = Ud È Wd , V(Ssa) = Usa È Wsa . Множества,… Часто элементы из множества W имеют определенную «протяженность» в… Но в ряде случаев элементы связи имеют сложное строение, описываемое не только тремя пространственными…

Тандемы распределенных систем

Цель G2 создания системы S2 и/или цель функционирования системы S2 является производной от цели G1 .
Например, S1 – коммерческая организация (фирма). Ее цель G1 – поддержание… Таким образом, системы S1 и S2 образуют своего рода «тандем», являющийся новой системой – фирмой с корпоративной…

Лекция 2. Распределенные задачи и алгоритмы

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

Лекция 3. Надежность и безопасность распределенных систем

Под надежностью понимается в соответствии с ГОСТ 27.002-89 свойство системы сохранять во времени в установленных пределах значения всех параметров,… Многие системы не являются абсолютно надежными, т.е. свойство надежности… Надежность принято характеризовать вероятностью отказа в работе (или вероятностью безотказной работы) в течение…

Лекция 4. Пример. Распределенная информационная система организации. Концепции

В качестве примера рассмотрим корпоративную информационную систему – Региональная распределенная информационная система образования (РРИСО). Ее основное назначение – информационное объединение на территории региона (области, края) многочисленных субъектов, занимающихся образовательной и научной деятельностью, т.е. создание «информационного подпространства образования и науки региона». Это подпространство образуется как пересечение общего информационного пространства (cyberspace) региона и глобального научного и образовательного информационного пространства.

Структура информационного пространства

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

Структура региональной системы образования и предпосылки создания РРИСО

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

Структуры РРИСО

Вторая структура РРИСО – типы данных. Множество хранимых и обрабатываемых документов должно быть разбито на некоторые классы, логически связанные…
Третья структура РРИСО – функциональная. Многообразие функций – независимых; являющихся композицией более частных;…

Подсистемы. Взаимоотношения структур

Однако процесс создания и ввода в действие информационной системы накладывает некоторые условия на согласование структур. Этот процесс состоит из…

Портал РРИСО

Основное назначение портала – интерфейс между пользователем и программным и информационным обеспечением РРИСО. Под «пользователем» понимается не только человек - индивидуум, работающий с порталом через стандартный или специализированный браузер, но и внешняя программа, автономная или входящая в состав какой-либо внешней (по отношению к РРИСО) информационной системы.
В связи с этим карта портала должна быть структурой данных, доступной для чтения, позволяющей внешним программам осуществлять стандартизованными средствами поиск информации в РРИСО, и включение информации в РРИСО (в разрешенных случаях).

Подсистема ведения первичной документации и репортинга

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

Подсистема мониторинга образования

Эта подсистема составляет часть контура обратной связи в системе управления образованием и наукой. Если подсистема ведения первичной документации реализует функции своего рода «датчиков» в системе управления, то подсистема мониторинга осуществляет агрегирование данных и редукцию их количества. Таким образом, число данных, используемых в анализе, значительно уменьшается, но ценность (информативность) каждого агрегированного параметра соответственно возрастает.
Подсистема мониторинга решает и задачу идентификации, получая (настраивая) модель системы образования и науки как объекта управления.
Результаты работы подсистемы мониторинга могут использоваться самостоятельно в виде аналитических отчетов (более высокий уровень, чем статистические отчеты), а могут быть и исходной информацией в подсистеме принятия решений, замыкающей контур управления.

Хранилище РРИСО

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

Подсистема подготовки и принятия решений

Предназначена для высокоуровневой обработки информации с применением методов экспертных систем, искусственного интеллекта. Использует информацию, получаемую из подсистемы мониторинга и из хранилища. Обладает развитыми средствами диалога для постановки задач. Это своеобразный язык, сочетающий в себе выбор из меню различных типов, задание числовых значений, дат, слов для поиска.

Подсистема внутреннего документооборота

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

Эталонная база нормативных актов

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

Подсистема единого государственного экзамена

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

Подсистема информирования абитуриентов

Тесно связана с подсистемой ЕГЭ. Позволяет абитуриентам получать оперативную информацию о вузах, специальностях и направлениях обучения, профессорско-преподавательском составе, проводить анализ своих возможностей по поступлению в тот или иной вуз на основе полученных баллов ЕГЭ и коэффициентов их перевода в баллы вуза.

Подсистема поддержки образовательного процесса

Подсистема основывается на принципах дистанционного обучения. Содержит программные средства и учебные ресурсы, разработанные с использованием международного стандарта IMS. Она может использоваться заинтересованными организациями и даже преподавателями, ведущими индивидуальную деятельность, как Web-сервис. РРИСО не является центром (дистанционного) обучения, а предоставляет лишь средство субъектам системы образования, образовательным учреждениям, имеющим соответствующую лицензию.

Подсистема предметных олимпиад

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

Реестр сервисов

База данных, поддерживающая обмен программными средствами, специально спроектированными для работы в распределенной среде интернета (Web-сервисы). Информацию о Web-сервисах авторы помещают, используя правила UDDI. Это позволяет во многих случаях отыскивать и подключать Web-сервисы автоматически.

Подсистема безопасности

Точнее было бы говорить о политике безопасности РРИСО, поскольку элементы, обеспечивающие защиту информации (антивирусную защиту, защиту от НСД, криптографическую защиту и проч.) «растворены» во всех подсистемах и имеют не только программный, но и аппаратный и организационный характер. Таким образом, защита – комплексная.


Характеристики РРИСО



Распределенность

По классификации сетей РРИСО можно отнести к классу WAN – wide area networks. В дополнение к географической распределенности можно отметить распределенность источников информации, распределенность данных и распределенность сервисов (функций). Основой распределенной ИС является распределенная база данных (РаБД) – совокупность логически взаимосвязанных баз данных, распределенных в компьютерной сети. К.Дейт вводит для РаБД 12 правил, первым из них является локальная автономность: локальные данные должны находиться под локальным владением и управлением, включая функции безопасности, целостности, представления данных в памяти. Исключением может быть ситуация, когда ограничения целостности охватывают данные нескольких узлов или когда управление распределенной транзакцией осуществляется некоторым внешним узлом.

Условная корпоративность

1. Значительная, в том числе юридическая, независимость большинства пользователей системы и организаций, владеющих узлами системы.
2. Семантическая широта информации, представленной в ИС, не сводящаяся только… 3. Большая динамика состава пользователей как по количеству, так и по характеристикам, ролям: ежегодный выпуск из…

Неоднородность

Неоднородны информационные потоки. Наряду с относительно хорошо прогнозируемыми потоками регламентированной информации (списки вновь поступивших… Неоднородно прикладное программное обеспечение, с которым работают… Неоднородны локальные базы данных. На двух разных узлах базы данных одинакового назначения могут быть построены…

Многовариантность доступа

Следствием неоднородности информационного пространства и неоднородности РРИСО является необходимость обеспечения нескольких способов доступа пользователей к системе. При этом должна быть обеспечена мобильность пользователей, эффективное использование каналов связи и защита информации.
Первое направление – внутрисистемные средства доступа, основанные на корпоративном физическом уровне транспортной сети (оптоволокно, выделенные линии, входящие в состав сети образования и науки), и соответствующие программные средства локальных сетей и удаленного доступа. Пользователи в этом случае работают через специализированный интерфейс РРИСО. Вся информация физически циркулирует внутри корпоративной сети, и ее защита обеспечивается общесетевыми средствами.
Второе направление – внутрисистемные средства доступа, использующие сети независимых провайдеров. В этом случае используется доступ по коммутируемым линиям, информационные потоки нуждаются в специальной защите. Интерфейс пользователя может быть таким же, как и в первом случае. В том и другом случае пользователь «привязан» к своему компьютеру, на котором установлено программное обеспечение информационной системы.
Третье направление – доступ через Интернет, т.е. с использованием не только общих сетей, но и общих сетевых служб – WWW, mail, ftp и проч. Интерфейс пользователя включает браузеры и программы электронной почты. Информация, подготовленная им на клиентском ПО РРИСО, затем может быть передана им в систему по электронной почте с любого доступного компьютера. Это повышает его мобильность. Аналогично пользователь может запросить получение по почте необходимой информации. В случае использования WWW пользователь еще более мобилен, и может даже в ряде случаев не иметь на своем компьютере специализированного клиентского ПО, заполняя всевозможные формы на сервере в интерактивном режиме.
Четвертое направление, в программном отношении не имеющее особенностей по отношению ко второму или третьему направлениям, следует, однако, упомянуть особо. Сетевые реалии сегодняшнего дня говорят о том, что одним из часто используемых способов передачи информации является перенос ее на дискетах или других устройствах хранения электронной информации.

Интегрируемость

Невозможно представить себе, чтобы такая система создавалась «с нуля». Существуют базы данных, коллекции документов в электронном виде в отдельных… Что касается программных компонент, то, действительно, они проектируются и… Механизм интеграции должен действовать и в развитой РРИСО, поскольку внешние информационные системы, по-прежнему,…

Лекция 5. Пример. Распределенная информационная система организации. Архитектура

В качестве примера рассмотрим корпоративную информационную систему – Региональную распределенную информационную систему образования (РРИСО).
Задачи РРИСО (рис. 3):
1) Ведение централизованной базы данных для обеспечения управления системой.
2) Интеграция неоднородных баз данных педагогической и управленческой информации.
3) Обеспечение единого интерфейса пользователя и формирования типовых документов.
4) Создание централизованной электронной библиотеки и поддержка работы учащихся, преподавателей с периферийными электронными библиотеками.
5) Поддержка дистанционного обучения и независимого тестирования.
6) Совместное использование вычислительных ресурсов и оборудования.
7) Автоматический обмен электронной информацией между учреждениями образования, автоматизация процессов создания, обработки и хранения информации.
8) Защита информации, размещенной в РРИСОН, и авторских прав разработчиков БД, электронных учебных материалов и приложений.
9) Поддержка групповой работы при подготовке электронных учебных материалов, обучении, научных исследованиях.
10) Интеграция с аналогичными информационными системами зарубежных и отечественных компьютерных сетей.



Рис. 3. Региональная распределенная информационная система образования

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



Рис. 4. Структура объекта автоматизации

Целью функционирования информационной системы является мониторинг в сфере образования (рис. 5).


Рис. 5. Мониторинг в сфере образования региона


Региональная распределенная информационная система имеет иерархическую организацию (рис. 6).
Иерархическая структура системы обусловлена наличием нескольких уровней управления образованием: региональный уровень (Департамент образования и структурные подразделения администрации региона), уровень крупных муниципальных образований (органы управления образованием, подразделения администрации города - регионального центра), уровень районов области и городских районов, уровень отдельных образовательных учреждений различных типов и видов, других ведомств, учреждений и организаций, обеспечивающих социальное обслуживание, защиту прав детей и подростков.
Автоматизация информационного обмена обеспечивает согласованность данных, используемых на различных уровнях информационной системы, повышает их достоверность.




Рис. 6. Информационные связи в предметной области

Взаимодействие между органами управления образованием и образовательными учреждениями, существующие между ними информационные потоки, определяются положением о департаменте образования региона. ИС должна иметь архитектуру, соответствующую структуре объекта автоматизации. Разрабатываемая система должна включать подсистемы, принадлежащие нескольким уровням иерархии:

• Уровень образовательных учреждений. Компоненты этого уровня различаются по набору реализуемых в них функций в зависимости от типа образовательного учреждения. Основное назначение этих компонентов в данной системе – сбор первичной информации о деятельности образовательного учреждения и формирование отчетности (сведений о деятельности конкретных образовательных учреждений различных типов) для органов управления образованием и органов государственной статистики, а также поддержание функций управления образовательным учреждением, организации учебного процесса в нем. Необходимость объединения этих функций в одном приложении диктуется требованием минимизации ручной обработки информации, повторного ее ввода и дублирования, что является источником ошибок при эксплуатации информационных систем.
• Уровень муниципальных органов управления образованием районов региона. Основным назначением данных подсистем является получение первичной информации от образовательных учреждений, ее интеграция и передача на вышестоящий уровень, формирование отчетности (сведений о деятельности учебных учреждений района, города) для вышестоящих органов управления образованием и органов государственной статистики, а также поддержание функций управления образовательными учреждениями соответствующей территории.
• Уровень Департамента образования региона. Основным назначением компонентов данного уровня является анализ полученной от подсистем нижележащих уровней информации, поддержание функций управления образованием, формирование государственной статистической отчетности и поддержание комплексной системы мониторинга в сфере образования.

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




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

Архитектура ИС соответствует многоуровневой структуре системы образования региона. Система включает подсистемы нескольких уровней (рис. 7):
• Информационные системы образовательных учреждений различных типов и видов.
• Информационные системы муниципальных (территориальных, районных) органов управления образованием.
• Информационную систему органов управления образованием регионального уровня.

В системе регионального масштаба должна поддерживаться возможность распределенного хранения и распределенной обработки данных.
Каждая подсистема работает со своей локальной базой данных, но единой моделью. Данные фрагментированы. Для реализации возможности передачи данных между БД подсистем используется компонент реплицирования данных.
Все изменения, вносимые в модель данных при необходимости ее расширения, настройки на новые информационные потребности, передаются в те подсистемы, работу которых затрагивают обновления.
Интеграция подсистем реализуется на основе технологии BizTalk Server.
Программная платформа технологии – Microsoft .NET.




Рис. 8. Компоненты программного обеспечения подсистем РРИСО

Программное обеспечение ИС (рис. 8) гибко конфигурируется при установке: осуществляется настройка на выполнение функций подсистемы соответствующего уровня, на работу в учреждениях образования различных типов и видов, различные условия эксплуатации.
Пользователи имеют возможность осуществлять поиск и отбор документов, их просмотр (через компоненты управления документами).
В системе поддерживаются функции автоматизации выполнения типовых операций, делопроизводства и документооборота (через компоненты управления бизнес-процессами). Изменения в БД вносятся только через выполнение соответствующих операций, в ходе которых изменяются первичные данные, создаются документы.
Выполнение операций и работа с документами осуществляются в соответствии с правами пользователей, определяемыми их принадлежностью к определенной категории, должностными обязанностями.



Лекция 6. Моделирование распределенных систем. Язык Triad

Распределенная система характеризуется распределенной структурой, т.е. набором дискретных (отделенных друг от друга) элементов или подсистем и… Язык Triad предполагает самостоятельное описание структуры (Str), алгоритмов… Основным слоем является слой структуры, именно он отражает распределение и связи элементов. Описание структуры…

Model System2 (k, m, n: integer) def

enddef.

Оно задает модели имя (System2) и определяет, что модель зависит от трех целочисленных параметров k, m, n. Таким…

Initial

schedule (Repeat, 0.0)

Endi

event Repeat;
out; schedule (Repeat, 2.4)

Ende

endrout.
Здесь Generator – имя рутины, Repeat – имя события, 2.4 – интервал между событиями.
Часть initial определяет начальные условия (в том числе, начальные действия). В данном тексте – это планирование события Repeat через 0.0 единиц времени, т.е. в момент старта процесса имитационного моделирования.
В момент совершения события Repeat рутина выдает выходное сообщение, которое при наличии структуры попадет в рутины смежных вершин, став для них входным сообщением. В данном тексте никакого «значения» сообщения в операторе out нет. Оно может быть определено позже, в слое сообщений. Оно может остаться и неопределенным: иногда важен сам факт получения сообщения, а не его значение, или оно может быть ясно по умолчанию.
В этот же момент вновь планируется событие Repeat через 2.4 единицы времени.
Таким образом, рутина Generator будет, начиная с момента времени 0.0, регулярно через 2.4 единицы времени выдавать сообщения. Этот процесс неограничен и прекратится только с окончанием сеанса моделирования.
Можно задать семейство рутин, зависящих от параметра T:
routine Generator (real T)

Initial

schedule (Repeat, 0.0)

Endi

event Repeat;
out; schedule (Repeat, T)

Ende

endrout.
Параметров может быть несколько, все они передаются по значению в момент создания экземпляра рутины и предназначены для «настройки» конкретного экземпляра.
В данном примере нет входного события, т.е. узел с рутиной Generator не реагирует ни на какие приходящие к нему сообщения. В более сложных случаях входное событие в рутине может присутствовать.
По правилам языка Triad входное событие в рутине может быть только одно. Оно не имеет имени и не может планироваться внутри данной рутины.
Следующий пример управляемого генератора ControlledGenerator показывает использование входного события.
routine ControlledGenerator (real T)

Initial

Boolean Run;
Run := false

Endi

event;

IfRunthenRun := false else begin Run := true; schedule(Repeat, 0.0) end



Ende

event Repeat;
out; ifRunthen schedule (Repeat, T)

Ende

endrout.
Событие Repeat планирует свое повторение только в том случае, если переменная Run имеет значение «истина» (true). Первоначально (в части initial) значение этой переменной установлено как «ложь» (false). Поэтому генератор не работает.
При получении сообщения (не важно какого) срабатывает входное событие, переключающее значение Run на «истину» и планирующее немедленно событие Repeat. Генератор начинает работать.
При поступлении следующего сообщения (опять не важно какого) вновь срабатывает входное событие. Но сейчас значение Run уже «истина» и тогда оно меняется на противоположное. Генератор прекращает работу. Третье сообщение вновь включает генератор, четвертое – вновь выключает и т.д.
Как видно из приведенных примеров, значения сообщений иногда не нужны, а, следовательно, можно обойтись без описания слоя сообщений. В других случаях достаточно предопределенных типов данных (integer, real, Boolean). Специального описания слоя сообщений также не требуется.
В сложных случаях моделирования при построении многоуровневых иерархических моделей требуется и построение структурных типов сообщений. Не останавливаясь здесь на этом, отметим, что оно производится подобно тому, как это делается в универсальных языках программирования (за исключением синтаксиса).
После описания структуры и рутин необходимо произвести наложение рутин на вершины графа, описывающего структуру. Делается это специальными операторами наложения, имеющими вид
routine(Node[i]) := Generator.
В нашем примере можно произвести наложение одной и той же рутины на все периферийные узлы:

For i:= 1 to n do

endf.
При этом создается n экземпляров рутины Generator. Для каждого экземпляра… Важной особенностью языка Triad является возможность выполнения операций над моделями систем и, следовательно,…

For i:= 1 to n – 1 do

endf;
System := System + (System.Node[n] « System.Node[1])
В цикле к системе добавляются ребра между первым и вторым узлами, между вторым и третьим узлами, …, между…

Лекция 7. Распределенное имитационное моделирование

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

Причины для перехода к распределенному моделированию

- возможностью использования вычислительных ресурсов нескольких процессоров (компьютеров) для выполнения имитационного эксперимента… - использованием локальной памяти других процессоров (компьютеров);
- одновременным запуском нескольких репликаций параллельно на нескольких компьютерах (снижение временных затрат на…

Два направления в развитии распределенных систем моделирования

Для создания новых высокоэффективных «монолитных» систем моделирования, в которых поддерживается параллельное дискретно-событийное моделирование… Вторая парадигма, которая появилась в распределенном моделировании – это…

Синхронизация времени в распределенных вычислениях

Для выполнения распределенной модели необходимо реализовать взаимодействие ее компонентов. Кроме того, необходимо синхронизовать выполнение этих компонентов.
Проблемы синхронизации времени актуальны для всех распределенных приложений.

Физическое время

tсервера > tпоследнего обновления клиента > tпоследнего обновления сервера
то приложение переписывает этот файл в сводную директорию.
На первый взгляд достаточно простая задача может быть выполнена некорректно. Это может произойти из-за…

Управление временем в последовательном имитационном моделировании

Прежде всего, следует определить, что следует понимать под термином «время» в имитационном моделировании. В работе Fujimoto и других работах по… - Физическое время (physical-Tp) – это время, которое используется в реальной… - Модельное время (simulation time - Ts) – это представление физического времени в модели. Так работу предприятия в…

While(не конец моделирования) do



Begin

Просмотреть список SE = {li}, где li = (ei , ti), 0£ i £ n и выбрать элемент с минимальным временем ti.
Systemtime := min(ti);
Передать управление событию ei из элемента li = (ei , ti);
Обработать это событие. Если событие ei запланировало новое событие ej (т.е. было выполнено преобразование Sch), то соответствующий элемент lj следует поместить в список событий SE, т.е. выполнить операцию SE:=SE + lj

End



Если сразу несколько событий запланировано на одно и то же время, то они выполняются последовательно друг за другом (квазипараллельно), системное время systemtime не изменяется до тех пор, пока все эти события не будут обработаны.
Для того чтобы поиск был эффективным, обычно список запланированных событий упорядочивают по возрастанию. Симулятор должен поместить новый элемент в календарь событий, причём упорядоченность по возрастанию должна быть сохранена.
Если число элементов в списке SE велико, поиск события с минимальным временем (и включение в список нового элемента) может занять много времени. Для оптимизации этого процесса исследователи предлагают усовершенствованные алгоритмы:
- Поиск с начала и конца списка.
- Использование различных списков для различных типов событий.
- Использование дополнительного указателя на середину списка. Сначала происходит сравнение с нужным элементом, а потом поиск происходит в нужной половине списка.
- Использование множества запланированных событий в виде бинарного дерева.
- Хранение наряду с календарём событий массива указателей на элементы списка. Таким образом, список событий делится на подсписки (между двумя соседними указателями). Эти подсписки соответствуют интервалам системного времени. Длины всех интервалов равны фиксированному значению. Это значение задаётся пользователем. При планировании нового события вычисляется его индекс в массиве указателей, после чего новый элемент календаря событий может быть размещён в соответствующем его подсписке.




Лекция 8. Синхронизация времени в распределенном имитационном моделировании

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

Управление временем в распределенном моделировании

Сделаем предположение, что имитационная модель представляет собой совокупность логических процессов (LPi), которые взаимодействуют друг с другом,… Будем рассматривать каждый логический процесс как последовательный симулятор,… Работа симулятора заключается в том, чтобы выбрать из списка необработанных событий событие с минимальной временной…

Парадоксы времени

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

Консервативное управление временем

Большинства консервативных алгоритмов основано на вычислении LBTS (Lower Bound on the Time Stamp – нижняя граница временных меток) будущих… Будем считать, что логические процессы не содержат событий, запланированных на…


Алгоритм с нулевыми сообщениями

Алгоритм предполагает:
- Топология процессов, которые посылают сообщения друг другу, известна и… - Каждый логический процесс посылает сообщения с неубывающими временными метками.


While(не конец моделирования) do



Begin

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

End


Вернёмся к примеру: В очередях последовательно были обработаны события, запланированные на время t1=10, t2=11. Далее процесс ожидает появления сообщения от покупателя. Иначе он не может продолжить работу. Процесс блокируется (рис.14).


Рис. 14. Процесс блокируется, потому что на линии связи с процессом-покупателем нет сообщений.

Несмотря на то, что алгоритм обеспечивает локальную каузальность, при его выполнении могут возникнуть тупики. Действительно, если нижняя граница временных отметок на всех линиях связи будет меньше, чем необработанные события, то это приведет к ожиданию выполнения другого цикла.
Пример:
Итак, у нас 3 процесса LP1,LP2,LP3. Процесс LP1 блокирован, т.к. ожидает прихода сообщения от LP3 и не может отослать сообщения процессу LP2. Процесс LP2 тоже блокирован, он ожидает сообщений от LP1. Процесс LP3 в свою очередь блокирован, поскольку в его входной очереди нет сообщений от первого процесса LP1. Теперь мы видим, что происходит циклическое ожидание процессов (тупик). Иллюстрацию примера см. на рис.
Для того, чтобы избежать возникновение тупиков, Chandy и Misra предложили использовать нулевые сообщения. Процесс LPa посылает сообщение с временной меткой Tnull процессу LPb. Этим процесс LPa сообщает процессу LPb, что он не пришлёт процессу сообщение с временной отметкой, меньшей, чем Tnull. Нулевые сообщения не соответствуют каким-либо физическим явлениям моделируемого объекта.

Рис. 15. Циклическое ожидание процессов.
Процессы отсылают нулевые сообщения по всем выходным дугам после обработки очередного события. Нулевое сообщение служит дополнительной информацией для того, чтобы определить очередное безопасное событие.
Нулевое сообщение обрабатывается как обычное сообщение за исключением того факта, что ни одна переменная процесса и никакое событие не будут запланированы. Локальное время логического процесса продвигается до временной отметки нулевого сообщения.

Рис. 16. Отсылка по выходным дугам нулевых сообщений.
Каким образом процесс определит временную метку нулевого сообщения, которое он отсылает?
Значение часов каждой линии связи определяет нижнюю границу временной метки следующего события, которое будет извлечено из буфера этой линии связи. Эта нижняя граница в совокупности со сведениями о выполнении процесса являются исходной информацией для определения нижней границы временных меток для всех посылаемых с выходных дуг сообщений. Fujimoto приводит такой пример: если известно, что некоторое обслуживающее устройство обрабатывает заявку в течении T единиц модельного времени, то временная метка любого отсылаемого сообщения по крайней мере на T единиц модельного времени больше, нежели временная метка любого сообщения, которое может появиться в будущем (рис.15).
Как только процесс завершит обработку нулевого или ненулевого сообщения, он вновь посылает нулевое сообщение по выходным дугам. Процесс, получивший нулевое сообщение, обязан вычислить нижнюю границу временной метки и отослать эту информацию свои соседям и т.д.
Алгоритм с нулевыми сообщениями(выполняется каждым логическим процессом LP):

Цель: Обеспечить выполнение событий в хронологическом порядке и избежать тупиков



While(не конец моделирования) do



Begin

Ждать пока не выполнится условие: каждая очередь FIFO содержит хотя бы одно сообщение.
Удалить событие с наименьшей временной отметкой из FIFO.
Обработать это событие.
Послать нулевое сообщение своим соседям с временной меткой, указывающей нижнюю границу будущих событий, посланных этому LP (текущее время + lookahead)

End


Итак, приведённый выше алгоритм с использованием нулевых сообщений позволяет избавиться от тупиков.
Использование lookahead (Забегания вперёд)
Для консервативных алгоритмов синхронизации характерной особенностью является использование предварительного просмотра (lookahead).
Предположим, что некоторый логический процесс имеет локальное время с отметкой T. Процесс может гарантировать, что любое будущее сообщение, отосланное им, будет иметь временную метку, превосходящую временную метку пришедшего позднее сообщения, на величину, равную T+L. В этом случае говорят, что процесс имеет предварительный просмотр величиной, равной L. Предварительный просмотр используют для того, чтобы вычислить временную метку нулевого сообщения. Величина предварительного просмотра указывает на то, что на протяжении некоторого временного отрезка L исходящих сообщений не будет.
Обсуждаемый алгоритм допускает множество модификаций, таких как, например, подсчёт lookahead по отдельности для различных исходящих дуг, что приводит к значительному уменьшению простоя логических процессов. К отрицательным характеристикам этого алгоритма можно отнести тот факт, что если процессы сильно связаны, то все логические процессы будут продвигаться лишь на очень малые промежутки времени. Таким образом, моделирование по своей сути будет последовательным. Недостатком алгоритма является и то, что при небольших значениях lookahead возможна ситуация циклического ожидания нескольких LP с небольшими продвижениями локальных часов. В некоторых системах возможно, а зачастую и необходимо, использование нулевого предварительного просмотра (zero lookahead), однако обсуждаемый выше алгоритм не допускает нулевых предварительных просмотров.

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

Допустим, что мы имеем два логических процесса LP. Предположим, что оба они заблокированы. Каждый из них достиг временной отметки, равной 100… Рассмотрим пример, который проиллюстрирован на рис.16.
На рисунке видно, что взаимодействуют 3 логических процесса. Нулевые сообщения запланированы на 5.0, 5.5, 6.0 и т.д.,…

Оптимистическое управление временем






Выбор алгоритма для реализации системы моделирования

Алгоритмы синхронизации – это достаточно хорошо изученная область дискретного распределённого моделирования. Тем не менее, не существует общего мнения на тот счёт, какой из алгоритмов синхронизации лучше: консервативный или оптимистический. Действительно, выбор алгоритма зависит от конкретного приложения:
- Если приложение имеет хорошие характеристики для использования lookahead (заглядывания вперёд, предварительного просмотра) и вычисление этого lookahead в конечном счёте незначительно увеличивает накладные расходы на разработку приложения, то рекомендуется использовать консервативный алгоритм.
- С другой стороны, в некоторых приложениях оптимистический алгоритм будет выполняться скорее, но к его недостаткам можно отнести тот факт, что реализация оптимистического алгоритма сложна и требует большого количества памяти.



Лекция 9. Балансировка нагрузки в распределенных системах

Следует различать декомпозицию задач и проблему отображения задач на вычислительную среду. Декомпозиция задачи является этапом процесса создания… Итак, будем считать, что распределенное приложение представляет собой… Однако при выполнении распределенного приложения возникает конфликт между сбалансированным распределением объектов по…

Балансировка вычислительной нагрузки



Причины возникновения несбалансированной нагрузки

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

Статическая и динамическая балансировки

Статическая балансировка выполняется до начала выполнения распределенного приложения. Очень часто при распределении логических процессов по… Это объясняется тем, что:
- Может измениться вычислительная среда, в которой происходит выполнение приложения, какой либо вычислительный узел…

Постановка задачи динамической балансировки

Цель балансировки загрузки может быть сформулирована следующим образом:

Исходя из набора задач, включающих вычисления и передачу данных, и сети компьютеров определенной топологии, найти такое распределение задач по компьютерам, которое обеспечивает примерно равную вычислительную загрузку компьютеров и минимальные затраты на передачу данных между ними.
Представим распределенное приложение в виде графа. Пусть Gp = {V, E}, V –множество вершин (задачи распределенного приложения), E – множество дуг графа – связи между задачами распределенного приложения. Пусть TM – множество моделей распределенных приложений, Gp Î TM.

Задача балансировки ставится как задача отображения неизоморфных связных графов, B: TM ® NG , где TM – множество графов моделей, NG – множество графов – конфигураций компьютерной сети. Граф G Î NG , G = {C, Ed}, определяется множеством вычислительных узлов C и множеством ребер Ed, обозначающих линии связи. Можно рассматривать NG как суперграф, содержащий все возможные (допустимые) графы G в качестве подграфов.

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

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

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

Оценка загрузки

В основном такая база данных состоит из двух типов данных:
- Данные о работе процессора (информация уровня процессора). Эти данные… - Данные о работе распределенного приложения. Данные включают время выполнения отдельной задачи, время простоя,…

Инициализация балансировки загрузки

Для этого следует:
- Определить момент возникновения дисбаланса загрузки.
- Определить степень необходимости балансировки путем сравнения возможной пользы от ее проведения и затрат на нее.
…

Принятие решений в процессе балансировки

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


Перемещение объектов

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


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

Из всего вышесказанного можно сделать вывод о том, что для проведения балансировки во время имитационного моделирования необходимо разработать специальное программное обеспечение. Это программное обеспечение включает:
- Программные средства, обеспечивающие оценку состояния распределённой имитационной модели и вычислительной среды (подсистема анализа).
- Управляющую программу, принимающую решение о моменте проведения балансировки, и о том, какие логические процессы следует переместить с одного процессора на другой.
- Программные средства, реализующие перемещение объекта с процессора на процессор.
- Подсистему визуализации, отображающую распределение компонентов имитационного моделирования по вычислительным узлам, коммуникационную среду, изменение состояния имитационной модели и вычислительной среды.
- Базу данных, которая хранит информацию о компонентах имитационной модели и о вычислительной среде.


Балансировка загрузки распределенной имитационной модели

В большинстве случаев алгоритм балансировки разрабатывается для конкретного класса задач. В других случаях балансировка предполагает большие… Алгоритм динамической балансировки в SPEEDES предполагает пересылку (перенос,… В SPEEDES рассматривается универсальная балансировка, которую можно применить к задачам различных типов, причём…

Динамическая балансировка и перенос нагрузки

Перенос нагрузки (или перенос объекта или процесса), – это механизм, который используется для переноса работы с одного компьютера на другой. Если… Балансировку и перенос нагрузки используют для повышения производительности…

RCL – cтратегия переноса нагрузки

- случайный алгоритм (random, R);
- алгоритм, основанный на коммуникациях (communication, С);
- алгоритм, основанный на вычислении нагрузки (load, L).


Действия первого уровня

- Количество нагрузки (Ld).
- Количество времени, потраченное процессором на обработку приложений SPEEDES… - Количество нагрузки, которая была обработана с момента последнего переноса(LdM).


Действия второго уровня

Нагрузка определяется как вся работа, которая должна быть выполнена для обработки запланированных событий, находящихся в очереди. Поскольку SPEEDES… К примеру, предположим, что моделируемый объект содержит два события типа 1 и…

Случайный алгоритм

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

Алгоритм, основанный на коммуникациях

Посылающий компьютер выбирает локальные объекты, которые наиболее часто обмениваются информацией с принимающим компьютером. Этот подход может сократить время на коммуникацию между двумя логическими процессами. Но он требует больших накладных расходов, поскольку на каждом компьютере должна быть таблица коммуникаций, в которой отмечается частота обменов каждого объекта, находящегося на Csender с другими компьютерами. Таблица должна всё время обновляться. Кроме того, для выбора объекта с целью его переноса следует использовать алгоритмы сортировки и поиска. Известно, что алгоритмы линейного поиска и сортировки при большом количестве объектов время выполнения этих алгоритмов может быть значительным. .


Алгоритм, основанный на вычислении нагрузки

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

Реализация

В результате исследований было обнаружено, что процедуру Migrate() следует выполнять в конце цикла GVT (Global Virtual Time). Действительно, события… Каждый из алгоритмов был протестирован на трёх наборах входных данных. При… Результаты можно интерпретировать следующим образом:


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



Распределенные веб-сервисы

Для реализации высокопроизводительных и надежных веб-серверов используют распределенные веб-серверы. Распределенные веб-серверы представляют собой… · Они могут быть интегрированы в кластер веб-серверов, соединенных через… Распределенные веб-серверы обладают высокой степенью масштабируемости. Количество их может быть увеличено простым…

Балансировка загрузки распределенных веб-сереров

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


Использование мобильных агентов

Напомним, что мобильный агент – это программный компонент, который может автоматически передвигаться с одного узла сети на другой вместе со своим… Преимущества использования этого подхода в следующем:
- Агенты могут разделить функциональность при проектировании веб-систем. В традиционном подходе балансировки загрузки,…

Различные подходы к балансировке, основанные на технологии клиент-сервер

- клиентские;
- основанные на DNS;
- диспетчерские;


Мультиагентный подход к балансировке

Проект Traveller
Проект TRAVELER – инфраструктура на Java агентах для поддержки параллельных… Проект Messengers


Лекция 10. Распределенные интеллектуальные системы на основе агентов

Одним из расширений понятия программы стало понятие агента. Оно появилось в связи с использованием программ не только для решения численных задач… Обычная вычислительная программа, например, программа расчета колебаний… Программа реального времени функционирует (запускается, приостанавливается, возобновляется, завершается, запускается…

Агенты и МАС

В области ИС интеллектуальные агенты используются, прежде всего, для интеграции информационных систем, пользователей, оборудования, для поддержки… Существенными в понятии агента являются понятия делегирования и автономии. Это… Исследования в области МАС отличаются от исследований в области распределенного ИИ. В ИИ функционирование системы…

Лекция 11. Распределенное хранение информации

Если база данных находится в непосредственной окрестности источника и потребителя информации, то мы называем такую БД локальной. Если же БД… В том случае, если имеется несколько источников информации и баз данных,… Точнее, под распределенной БД понимается набор логически связанных между собой разделяемых данных, которые…

Фрагментация


Таб.№
Фамилия
Имя
Отчество
Год рождения
А5
Соловьев
Александр
…
Рис. 21. Пример отношения


Репликация

Репликация способствует и повышению надежности хранения данных, поскольку одни и те же данные хранятся в разных местах. Репликация особенно важна… Репликация приводит и к определенным трудностям. Локальные БД постоянно… Выход может состоять в том, чтобы одновременно с локальной базой данных обновлять и все копии этой БД или ее…

Initial

состояние сайта := “инициализация”

Endi



Event



If message.code = “включить данные в БД” then



Begin

start; write(“начало транзакции”);
L := Æ;
out “приготовиться к изменениям”;
состояние сайта := “ожидание”;
schedule (TimeOut, T)

End



Else if message.code = “готов” then



Begin

Include(L, message.id);

If L = S then



Begin

L := Æ;out “общее обновление”;
состояние сайта := “обновление”

End



End



Else if message.code = “выполнено” then



Begin

Include(L, message.id);

If L = S then



Begin

write(“транзакция завершена”);
состояние сайта := “завершено”

End



End



Else if message.code = “не готов” then



Begin

write(“не готов менеджер копии”);
out “общий возврат”;

End



Else if message.code = “не выполнено” then



Begin

write(“не выполнил менеджер копии”);
out “общий возврат”;

End



Else if message.code = “отказ принят” then



Begin

Include(L, message.id);

If L = S then



Begin

write(“отказы подтверждены”);
состояние сайта := “завершено”

End



End



Endc

ende;
eventTimeOut;
write(“время истекло”);
состояние сайта := “завершено”;
out “общий возврат”;
ende.

Менеджер сайта – владельца исходной базы данных получает сообщение “включить данные в БД” при необходимости корректировки копий. Менеджер заносит соответствующую запись “начало транзакции” в свой журнал, готовит структуру данных (L := Æ) для занесения в нее в будущем информации о готовности периферийных сайтов и рассылает всем сообщение “приготовиться к изменениям”. Кроме этого, менеджер устанавливает предельное время (T) для проведения всего процесса.
Менеджеры mj сайтов начинают присылать сообщения о своей готовности. Идентификаторы этих сайтов заносятся в множество L. Если все сайты готовы, то при приходе последнего сообщения выполнится условие L = S, т.е. множество сайтов, сообщивших о своей готовности, совпадает с множеством всех сайтов.
После этого менеджер M отправляет всем mj сообщение “общее обновление”. Далее идет процесс, похожий на предыдущий. Только теперь менеджеры mj проводят обновления и сообщают об этом словом “выполнено”. Если все выполнят обновления, то транзакция завершается.
Если какой-либо из сайтов не готов или не выполнил обновление, то менеджер M дает команду “общий возврат”, отменяющую транзакцию. После отмены он ожидает подтверждений о принятии отмены от менеджеров копий базы данных.
Рутины менеджеров копий:
routine m

Initial

состояние сайта := “готов”

Endi



Event

case message = “приготовиться к изменениям”:

If test(состояние сайта) = “готов” then



Begin

write(“начинается обновление”);
блокировка доступа к копии БД;
out(“готов”);
schedule (TimeOut, T)

End



Else



Begin

write(“не готов”); out(“не готов”); откат транзакции

End

message = “общее обновление”:

If test(состояние сайта) = “готов” then



Begin

write(“произведено обновление”); put; out(“выполнено”);

End



Else



Begin

write(“не готов”); out(“не выполнено”); откат транзакции

End


message = “общий возврат”:

Begin

write(“отказ инициатора обновления”); откат транзакции; out(“отказ принят”);
состояние сайта := “готов”

End



Endc

ende;
event TimeOut;
состояние сайта := “не готов”; снятие блокировки доступа к копии БД
ende.

Переменная «состояние сайта» является на каждом сайте разделяемой между менеджером копии и другими управляющими программами. Первоначально менеджер копии mj устанавливает ее значение как “готов”. Впоследствии другие управляющие программы могут присваивать ей как значение “готов”, так и значение “не готов”.
Таким образом, при получении пакета изменяемых данных и сообщения (message) “приготовиться к изменениям” от менеджера M состояния сайтов с копиями могут быть различными.
В случае готовности менеджер сайта с копией БД заносит в свой журнал запись “начинается обновление”, блокирует доступ пользователей к копии БД, сообщает менеджеру M о своей готовности и включает «часы» для ожидания в течение времени T. Если транзакция не завершается почему-либо в течение этого времени, то состояние сайта меняется на “не готов” и блокировка доступа к копии БД для пользователей снимается. В дальнейшем готовность может быть вновь установлена, но в данном протоколе это действие не отражено.
Приведенный протокол, очевидно, допускает блокировки обновления данных отдельными сайтами, что является его недостатком. Избежать блокировок можно специальными методами, например, применением трехфазной фиксацией транзакций.

Схемы владения данными в распределенной БД

Однако, реальная ситуация не всегда соответствует этой схеме. Существуют мобильные пользователи (и источники данных), перемещающиеся от сайта к… В литературе рассматриваются несколько схем владения данными:
1) ведущий/ведомый;


Лекция 12. Волновые алгоритмы распространения информации

Распределенные алгоритмы обычно допускают большой набор возможных трасс вычислений благодаря недетерминированности как в процессах, так и в… Волновой алгоритм - это распределенный алгоритм, который удовлетворяет… 1. Конечность. Каждое вычисление содержит конечное число событий.


Алгоритм для кольцевой архитектуры

Суть его в следующем. Один из сайтов – инициатор посылает маркер token своему единственному соседу по выходу (в ориентированном цикле каждый сайт… Любой сайт (кроме инициатора), получив маркер, тут же отправляет его соседу.…


Initial

out token;

Endi

event;
ifmessage = token thenreturn(OK)

Ende

endrout.
Здесь идентификатор message обозначает пришедшее на вход рутины сообщение. Этот идентификатор не описывается, он является системной переменной без определенного типа. Реально пришедшее на вход сообщение, «скрывающееся» за этим идентификатором, тип может иметь (кроме абстрактных сообщений). Поэтому в операциях сравнения сначала сравниваются (динамически) типы левой и правой частей, а при совпадении типов – значения.
Рутины остальных узлов имеют вид:
routine OtherNode
event;
ifmessage = token then out token;

Ende

endrout.
Таким образом «волна», начатая инициатором, заканчивается, когда возвращается к инициатору. Описанный распределенный алгоритм выполняется за время O(n).
Алгоритм можно расширить на случай двунаправленного цикла. Каждый узел имеет двух соседей и связи между ними симметричны (ненаправленны). Поэтому, следует ввести понятия «левого» и «правого» соседа. Инициатор направляет маркер только одному, например, правому соседу, и ожидает возвращения маркера слева. Также поступает и любой другой сайт.
Метод можно использовать и еще для более широкого класса архитектур распределенных систем, в которых существует гамильтонов цикл, проходящий через все сайты. Однако формулировка соответствующего алгоритма будет более сложной: для каждого сайта должен быть определен «сосед справа в гамильтоновом цикле».

Алгоритм для структуры – дерева

1) дерево – связный ациклический граф;
2) количество вершин в дереве на единицу больше, чем количество ребер;
3) в нетривиальном дереве имеется, по крайней мере, две вершины, степени которых равны единице; эти вершины называются…

Алгоритм голосования

Существо алгоритма заключается в следующем.
Инициатор отправляет по одному маркеру каждому соседнему сайту (по… Легко модифицировать этот алгоритм на случаи голосования по простому большинству, квалифицированному большинству и…

Initial

integer counter;
counter := 0;
out token;

Endi

event;

Ifmessage = token then

if (counter = n – 2)thenreturn(OK)

Else counter := counter + 1 endi



Ende

endrout.
Здесь оператор out token означает передачу маркеров token всем смежным сайтам.
Рутины остальных сайтов имеют вид:
routine OtherNode
event;
case of polus

Ifmessage = token then out token through polus endi



Endc



Ende

endrout.
Здесь оператор case of – оператор распознавания входа. Идентификатор polus обозначает полюс, на который пришло сообщение, подобно тому, как само сообщение «скрывается» за идентификатором message. Оператор out token through polus возвращает маркер token через тот полюс сайта, на который пришел этот маркер, т.е. инициатору алгоритма.
Описанный распределенный алгоритм выполняется за время O(n).
Алгоритм «Эхо»
Алгоритм «Эхо» может работать для любой топологии распределенной системы. Как и предыдущий алгоритм, в нем имеется один инициатор.
Алгоритм использует метод прохода по графу, называемый «поиск (или просмотр графа) в ширину», описанный, в частности, в учебнике Л.Н.Королева, А.И.Микова «Информатика. Введение в компьютерные науки» для поиска множества R достижимых вершин из данной вершины start.
Метод состоит в том, чтобы продвигаться от начальной вершины по ширине всего фронта, включив сначала в множество R все вершины, смежные с вершиной start, затем смежные со смежными и так далее. В описанном ниже методе Expand(R) расширения множества R множество Out(R) – это множество всех вершин, смежных с вершинами из R, так сказать, достижимых за один шаг. В частности, может оказаться, что все они уже принадлежат R и тогда дальнейшее расширение невозможно. На этом процесс прекращается.

Expand(R):
begin
if Out(R) Ë R then
begin Out(R) Þ R;
Expand(R)
end
end;

Первый вызов – Expand(Out(start)); Предполагается, что Out(Æ) = Æ , Æ Í Æ.

В алгоритме «Эхо» инициатор посылает маркеры всем своим соседям. Любой сайт s (не инициатор), получивший первый раз маркер от одного из своих соседей (обозначим этого соседа pre), рассылает маркеры всем соседним сайтам, кроме того, от которого получил маркер. Соседи поступают точно так же. Волна удаляется от инициатора.
Дальнейший процесс рассмотрим на примере дерева. Волна доходит до некоторых из висячих вершин. Висячей вершине отправлять маркер дальше некуда. Тогда она возвращает его той вершине, от которой получила (вот оно «эхо»). Вершины, получившие «эхо» от своих соседей, возвращают маркеры своим вершинам pre. Те, в свою очередь, генерируют «эхо» своим предшественникам. Наконец «эхо» доходит до инициатора. Инициатор, получив «эхо» от всех своих соседей, выполняет процедуру return(OK).
Ниже приведен распределенный алгоритм, состоящий из описаний процесса вычислений для сайта – инициатора и описаний процессов для сайтов – не-нициаторов. В тексте описания процесса тот сайт, на котором этот процесс выполняется (свой сайт), обозначен идентификатором this (в традициях языка Симула-67). Множество Out(this) – это множество сайтов, смежных по выходу с сайтом this, т.е. тех сайтов, на которые с сайта this можно отправить сообщения по однонаправленным или двунаправленным каналам связи. Функция card( ) задает число кардинальности (мощность) множества, являющегося аргументом этой функции. Переменные, встречающиеся в текстах процессов – локальные (по экземпляру для каждого процесса): обмен информацией между процессами происходит только посредством сообщений, разделяемые переменные отсутствуют. Начальные значения счетчиков counter равны 0.

Процесс для инициатора:
begin for u Î Out(this) do out token to u ;

While counter < card(Out(this)) do

begin receive token; counter := counter + 1 end ;
return(OK)
end ;

Процессы для не-инициаторов:
begin receive token from u ; pre(this) := u ; counter := counter + 1 ;
for (u Î Out(this))&(u ¹ pre(this)) do out token to u ;

While counter < card(Out(this)) do

begin receive token; counter := counter + 1 end ;
out token to pre(this)

End



Фазовый алгоритм

Переменные в тексте алгоритма имеют следующий смысл.
counter_out – счетчик, подсчитывающий количество маркеров token, посланных… counter_in – массив счетчиков, по одному счетчику на каждого соседа по входу. Хранит количество маркеров, посланных…

Begin ifthis - инициаторthen

begin forr Î Out(this) do out token to r ;
counter_out := counter_out + 1
end;

Whilemin(counter_in) < ddo

beginreceive token from u ;
counter_in [u] := counter_in [u] + 1 ;

If(min(counter_in) ³ counter_out) & (counter_out < d) then

begin forr Î Out(this) do out token to r ;
counter_out := counter_out + 1

End

end;
return(OK)

End



Алгоритм может использоваться в ориентированных сетях произвольной топологии, где каналы могут передавать сообщения только в одном направлении. В этом случае, соседи s являются соседями по входу (процессы, которые могут посылать сообщения s) и соседями по выходу (процессы, которым s может посылать сообщения).
В фазовом алгоритме каждый процесс посылает ровно d сообщений каждому соседу по выходу. Только после того, как k сообщений было получено от каждого соседа по входу, (k + 1)-ое сообщение посылается каждому соседу по выходу.

Алгоритм Финна

Процесс сайта s содержит два множества идентификаторов процессов, Inc(s) и NInc(s). Неформально говоря, Inc(s) – это множество процессов u таких,… Изначально Inc(s) = {s}, а NInc(s) = Æ. Каждый раз, когда одно из… При разработке распределенных алгоритмов для различных приложений часто в качестве подзадач возникает несколько общих…

Распространение информации с обратной связью

Формируется подмножество процессов из тех, кому известно сообщение M (одно и то же для всех процессов), которое должно быть распространено, т.е. все… Оповещение в PIF-алгоритме можно рассматривать как событие return(OK).
Любой волновой алгоритм может использоваться как PIF-алгоритм. Действительно, пусть A – волновой алгоритм. Чтобы…

Синхронизация

В алгоритмах синхронизации события bp будут рассматриваться как события return(OK).
Любой волновой алгоритм может использоваться как алгоритм синхронизации.…

Вычисление нижней грани

Как известно из курса математики, если (X, £) – частичный порядок, то c называют нижней гранью a и b, если c £ a, c £ b, и "… Задача вычисления нижней грани в распределенной системе формулируется… Событие write, которое заносит значение в out, рассматривается в алгоритме вычисления нижней грани как событие…

Лекция 13. Алгоритмы обхода сайтов

1) В каждом вычислении один сайт-инициатор, который начинает выполнение алгоритма, посылая ровно одно сообщение.
2) Процесс сайта, получая сообщение, либо посылает одно сообщение дальше,… 3) Алгоритм завершается в инициаторе и к тому времени, когда это происходит, процесс каждого сайта посылает сообщение…

Алгоритм обхода полного графа

Полный граф содержит все возможные связи между вершинами. Пусть n – количество узлов в полном графе. По отношению к данному узлу this – инициатору обозначим множество остальных вершин полного графа: {u1, u2, .., un – 1}.
Полный граф можно обойти путем последовательного опроса. Алгоритм подобен соответствующему алгоритму из предыдущей лекции, но за один раз опрашивается только один сосед инициатора. Только когда получен ответ от одного соседа, опрашивается следующий. Таким образом, сообщение с номером (2i – 1) – это опрос для сайта ui , а сообщение с номером 2i – ответ этого сайта. Всего же за время исполнения происходит обмен 2(i – 1) сообщениями.
Алгоритм последовательного опроса:
Процесс сайта – инициатора:
vari: integer init 0 ; (* счетчик *)
Для инициатора:

Begin whilei < n – 1 do

begin out token to ui+1 ;
receive token; i := i + 1
end ;
return(OK)

End


Процесс сайта не-инициатора:

Begin receive token from u ; out token to u end



Алгоритм обхода тора



Рис. 26. Тор 3 ´ 5. Ребра различных направлений.


End


На рис. 27 и 28 показан порядок обхода торов 3 ´ 4 и 2 ´ 5. Звездочкой обозначен сайт – инициатор обхода, а буквами «ОК» – сайт, сообщающий о завершении обхода. Около ребра записано число – значение k, которое передается по этому ребру от одного сайта к другому.


Рис. 27. Порядок обхода тора 3 ´ 4

Рис. 28. Порядок обхода тора 2 ´ 5


Алгоритм обхода гиперкуба

Эта операция для графов A и B определяется следующим образом.
Результатом операции является граф C = A ´ B, множество вершин которого… Множество ребер E(C) графа C порождается множествами ребер E(A) и E(B). Пусть вершина v1 ÎV(C) соответствует…

End



End


Из алгоритма видно, что решение принимается после 2n пересылок маркера. Пусть p0 – инициатор, а pk – процесс, который получает маркер (token, k). Для любого k < 2n, обозначения pk и pk+1 отличаются на 1 бит, индекс которого обозначим как l(k), удовлетворяющий следующему условию:

Т.к. для любого i < n существует равное количество k Î {0, ..., 2n} с l(k) = i, то p0 = p2n и решение принимается в инициаторе. Можно показать, что из pa = pb следует, что 2n|(b – a), откуда следует, что все p0, ..., p2n-1 различны.

Алгоритм Тарри

1. Процесс никогда не передает маркер дважды по одному и тому же каналу.
2. Не-инициатор передает маркер своему предшественнику (соседу, от которого он…


End


Для каждого процесса при получении token от s:
begin ifpre = udef then pre := s;
if " u Î Out(this) : used[u]
then return(OK)
else if$ u Î Out(this): (u ¹ pre & Øused[u])
then begin выбор u Î Out(this) {pre} с Øused[u] ;
used[u] := true ; out token to u

End

else begin used[pre] := true ;
out token to pre

End



End


Так как процесс каждого сайта передает маркер через каждый канал не более одного раза, то каждый процесс получает маркер через каждый канал не более одного раза. Каждый раз, когда маркер захватывается не-инициатором u, получается, что процесс u получил маркер на один раз больше, чем послал его. Отсюда следует, что количество каналов, инцидентных u, превышает количество каналов, использованных u, по крайней мере, на 1. Таким образом, u не завершает процесс, а передает маркер дальше. Следовательно, завершение процесса производится в сайте-инициаторе.
Ниже показывается, что когда алгоритм завершается, каждый процесс передал маркер.
(1) Все каналы, инцидентные инициатору, были пройдены один раз в обоих направлениях. Инициатором маркер был послан по всем каналам, иначе алгоритм не завершился бы. Инициатор получил маркер ровно столько же раз, сколько отправил его; так как инициатор получал маркер каждый раз через другой канал, то маркер пересылался через каждый канал по одному разу.
(2) Для каждого посещаемого процесса u все каналы, инцидентные u были пройдены один раз в каждом направлении. Предположив, что это не так, выберем в качестве u первый встретившийся процесс, для которого это не выполняется, и заметим, что из пункта (1) u не является инициатором. Из выбора u, все каналы, инцидентные pre(u) были пройдены один раз в обоих направлениях, откуда следует, что u переслал маркер своему предшественнику. Следовательно, u использовал все инцидентные каналы, чтобы переслать маркер; но, так как маркер в конце остается в инициаторе, u получил маркер ровно столько же раз, сколько отправил его, т.е. u получил маркер по одному разу через каждый инцидентный канал. Мы пришли к противоречию.
(3) Все процессы были посещены и каждый канал был пройден по одному разу в обоих направлениях. Если есть непосещенные процессы, то существуют соседи u и s такие, что u был посещен, а s не был. Это противоречит тому, что все каналы u были пройдены в обоих направлениях. Следовательно, из пункта (2), все процессы были посещены и все каналы пройдены один раз в обоих направлениях.
Каждое вычисление алгоритма Тарри определяет остовное дерево графа. В корне дерева находится инициатор, а каждый не-инициатор u в конце вычисления занес своего предшественника в дереве в переменную pre.


Лекция 14. Алгоритмы выбора сайтов

1. Выход из строя оборудования на сайте – координаторе, в связи с чем, этот сайт не может продолжать управлять процессами в распределенной… 2. Метод координации, реализованный на сайте, оказался неэффективным.
3. Изменения в интенсивности использования различных сайтов системы, приводящие к тому, что координация из прежнего…

Алгоритм смещения

Сайты обмениваются сообщениями с тремя возможными значениями: «выборы», «ответ», «координатор». Сообщение «выборы» посылается для объявления… Алгоритм выборов может начать любой сайт Si , который определил, что текущий… Алгоритм состоит из следующих шагов.


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

Когда сайт получит сообщение <wakeup> через каждый канал, он начинает выполнять алгоритм из лекции 12, который расширен таким образом, чтобы… В тексте алгоритма логическая переменная sent («отправлено») используется,…


Begin ifthis - инициатор then

beginis_sent := true ;
forallq Î Out(this) dosend <wakeup> to q
end ;

While counter < card(Out(this)) do

beginreceive <wakeup> ; counter := counter + 1 ;

If notis_sent then

beginis_sent := true ;
forall q Î Out(this) do send <wakeup> to q

End

end ;
(* Начало алгоритма из лекции 12 *)

Whilecard{q : Ørecp[q]} > 1 do

beginreceive (token, r) from q ; recp[q] := true ;
if est(r) > est(m) then m := r
end;
send (token, m) to q0 with Ørecp[q0] ;
receive (token, r) from q0 ;
if est(r) > est(m) then m := r; (* return(OK) с ответом m *)
ifm = this thenstate := coordinator elsestate := lost ;
forallq Î Out(this), q ¹ q0 dosend (token, m) to q

End


Когда хотя бы один сайт инициирует выполнение алгоритма, все сайты посылают сообщения <wakeup> всем своим соседям, и каждый сайт начинает выполнение алгоритма для дерева после получения сообщения <wakeup> от каждого соседа. Все процессы завершают алгоритм для дерева с одним и тем же значением оценки, а именно, с наибольшей оценкой сайта. Единственный сайт с такой оценкой закончит выполнение в состоянии координатор, а все остальные сайты – в состоянии проигравший.
Через каждый канал пересылается по два сообщения <wakeup> и по два сообщения <tok,r>, откуда сложность сообщений равна 4N–4. В течение D единиц времени после того, как первый процесс начал алгоритм, каждый процесс послал сообщения <wakeup>, следовательно, в течение D+1 единиц времени каждый процесс начал волну. Легко заметить, что первое решение принимается не позднее, чем через D единиц времени после начала волны, а последнее решение принимается не позднее D единиц времени после первого, откуда полное время равно 3D+1.
Если порядок сообщений в канале может быть изменен (т.е. канал – не FIFO), процесс может получить сообщение (token, r) от соседа прежде чем он получил сообщение <wakeup> от этого соседа. В этом случае сообщение (token, r) может быть временно сохранено или обработано как сообщения (token, r), прибывающие позднее.

Алгоритмы выбора для кольцевых архитектур

Когда инициатор p получает свой собственный маркер, маркеры всех инициаторов прошли через p, и p выбирается лишь в том случае, если p имеет… Алгоритм Лелана:



Begin ifthis - инициатор then

beginstate := cand ; send (token, this) to Nextp ; receive (token, q) ;

Whileq ¹ this do

beginListp := Listp È {q} ;
send (token, q) to Nextp ; receive (token, q) ;
end ;
ifthis = max (Listp) thenstate := coordinator
elsestate := lost

End

else repeatreceive (token, q) ; send (token, q) to Nextp ;
ifstate = sleep thenstate := lost
untilfalse

End


Так как порядок маркеров в кольце сохраняется (из предположения о каналах FIFO), и инициатор q отправляет (token, q) до того как получит (token, p), то инициатор p получает (token, q) прежде, чем вернется (token, p). Отсюда следует, что каждый инициатор p заканчивается со списком Listp, совпадающим с множеством всех инициаторов, и единственным выбираемым сайтом становится инициатор с наибольшей оценкой.
Все не-инициаторы приходят в состояние проигравший, но навсегда остаются в ожидании сообщений (token, r). Ожидание может быть прервано, если лидер посылает по кольцу специальный маркер, чтобы объявить об окончании выборов.
Алгоритм Чанга-Робертса, приведенный ниже, устраняет из кольца маркеры тех сайтов, для которых очевидно, что они проиграют выборы. В этом смысле он улучшает алгоритм Лелана. Т.е. инициатор p удаляет из кольца маркер (token, q), если est(q) < est(p). Инициатор p становится проигравшим, когда получает маркер с идентификатором q, таким что est(q) > est(p), или координатором, когда он получает маркер с идентификатором p.

var state : (sleep, coordinator, lost);

Begin ifthis - инициатор then

beginstate := cand ; send (token, this) to Nextp ;
repeatreceive (token, q) ;
ifq = this thenstate := coordinator

Else ifest(this) < est(q)then

begin ifstate = cand thenstate := lost ;
send (token, q) to Nextp

End

untilstate = coordinator

End

else repeatreceive (token, q) ; send (token, q) to Nextp ;
ifstate=sleep thenstate := lost
untilfalse
end(* Только координатор может завершить выполнение программы. Он передает сообщение всем сайтам, чтобы сообщить им свой идентификатор. *)

Пусть p0 – инициатор с наибольшим идентификатором. Все процессы являются либо не-инициаторами, либо инициаторами с идентификаторами меньшими p0, поэтому все процессы передают дальше маркер (token, p0), отправленный p0. Следовательно, p0 получает свой маркер обратно и становится выбранным.
Не-инициаторы не могут быть выбраны, так как все они приходят в состояние проигравший самое позднее, когда через них передается маркер p0. Инициатор p с оценкой est(p) < est(p0) не может быть выбран; p0 не передаст дальше маркер (token, p), поэтому p никогда не получит свой собственный маркер. Такой инициатор p приходит в состояние проигравший самое позднее, когда через него передается маркер (token, p0).



Рис. 30. Иллюстрация к алгоритму Чанга-Робертса

На рис. 30 изображен некоторый момент выполнения алгоритма Чанга-Робертса. На кольце расположены сайты. На внешней стороне кольца указаны их идентификаторы, на внутренней – величины оценок, на основе которых производится выбор координатора. Кружок с числом 2 – маркер (token, 2), переносящий номер сайта, для которого оценка имеет значение «31», стрелка указывает направление движения маркера. Начальный сайт при выполнении алгоритма указан звездочкой – это сайт 1 с оценкой est(1) = 24.



Лекция 15. Поиск в пиринговых системах

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

Begin

С вероятностью Pf : frozen := true, steps := hf
Инициировать поток ответов Aq
Распространить q

End

On QueryReceived(q) {от соседнего узла получен запрос}

Begin

counter := counter + 1;
if frozen & (steps = counter)

Then



Begin

Заморозить q;
Присоединить q к наиболее подходящему потоку ответов, если такой поток существует

End



Else



Begin

if Øfrozen then вычислить ответ и вернуть его обратно
if counter < max_steps then распространить q

End



End


OnResultReceived(rq) {от соседнего узла получен ответ}

Begin



For каждого запроса qi , присоединенного к q do

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

Then



Begin

Создать копию ответа rq как ответ rqi ;
Направить rqi как ответ rqi на запрос qi
end;
if this = инициатор запроса q
thenДобавить rq к потоку ответов Aq
else Направить rq обратно в качестве ответа

End


Алгоритм использует два параметра: вероятность Pf замораживания запроса и число steps шагов, которые должен сделать запрос q до того, как его заморозят. Узел-инициатор принимает решение с вероятностью Pf о том, следует ли заморозить новый запрос. Затем запрос q распространяется как обычно.
Предположим, что q был избран для замораживания, и через steps шагов он достигает узла pi . Алгоритм приостанавливает распространение запроса q на данном направлении, проверяет все активные потоки ответов на узле pi , и присоединяет q к наиболее «подходящему» из них. Если же потоков нет, то происходит только приостановка запроса. Запрос будет заморожен на всех узлах, находящихся на расстоянии steps от узла-инициатора p.
Когда ответ попадает в поток, алгоритм ищет любые присоединенные к потоку запросы. Для каждого запроса создается экземпляр этого ответа и направляется на узел, отправивший запрос.




Лекция 16. Тенденции в области распределенных систем

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

Архитектура Грид

1. Пользовательские интерфейсы, приложения и среда решения задач (problem-solving envieronment).
2. Средства разработки, программные модели, языки программирования.
3. Промежуточное программное обеспечение (middleware) Грид: управление ресурсами; фиксация информации и ее…

Мобильный компьютинг

1) сети, обеспечивающие подключение к ним в любой географической точке (сотовые и проч.);
2) мобильный доступ к информации (возможность получения информации при… 3) адаптивность приложений,


Тотальный компьютинг

М.Сатьянараян формулирует четыре новые области исследований в дополнение к областям мобильного компьютинга, вместе с ним образующие область… 1) эффективное использование персонального умного пространства, имея в виду… 2) невидимость (умного пространства) – минимальное отвлечение внимания пользователя на управление окружающими…

Глобальное умное пространство = Грид компьютинг + тотальный компьютинг

Оно отличается тем, что пространство становится уже не персональным (хотя, ближнее окружение, подпространство остается) как в тотальном компьютинге, а глобальным. В нем действует уже не один пользователь, а множество пользователей, каждый со своим персональным подпространством. Но технические, технологические, информационные «барьеры» между подпространствами отсутствуют. Это не означает полной открытости. Любой пользователь может применить для охраны своего пространства от несанкционированного доступа средства компьютерной безопасности. Правда, они тоже должны «поумнеть» по сравнению с современными средствами информационной безопасности. Это еще одна перспективная задача.
Если перейти от моделей конечных пользователей к задачам, стоящим перед программистами распределенных систем, то можно отметить все возрастающую важность программного обеспечения промежуточного уровня (middleware). Оно важно и для Грида и для тотального компьютинга. Многие считают, что middleware – это ключ к следующему поколению компьютинга.