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

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

Рис. 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 алгоритма с целью оптимизации основывались на параметрах, задаваемых пользователем. Позже применялись адаптивные подходы, которые следили за выполнением алгоритма и выполняли регулировку этого алгоритма с целью повышения его скорости выполнения.