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