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

Рис. 1. Банк получает сообщения в хронологическом порядке

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

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


Рис. 2. Хронологический порядок событий нарушен

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

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

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

Первые алгоритмы синхронизации использовали консервативный подход. Принципиальная задача консервативного протокола – определить время, когда обработка очередного события из списка необработанных событий является "безопасным". Иными словами, событие является безопасным, если можно гарантировать, что процесс в дальнейшем не получит от других процессов событие с меньшей временной меткой. Консервативный подход не позволяет выполнять событие до тех пор, пока нет гарантии, что оно является безопасным.
Большинства консервативных алгоритмов основано на вычислении LBTS (Lower Bound on the Time Stamp – нижняя граница временных меток) будущих сообщений, которые могут быть получены логическим процессом. Этот механизм позволяет определить, является ли очередной событие из списка необработанных событий безопасным. Действительно, если консервативный алгоритм определит, что LBTS = 11, то все события из списка необработанных событий с временной отметкой, меньшей 11, являются безопасными и могут быть выполнены. Соответственно, события с временной меткой, большей 11 не являются безопасными и не могут быть выполнены. Что касается событий, которые имеют временную отметку, равную 12 (LBTS = 12), то их обработка зависит от реализации конкретного консервативного алгоритма и правил, по которому должны обрабатываться события, запланированные на один и тот же момент времени (одновременные события – simultaneous events).
Будем считать, что логические процессы не содержат событий, запланированных на одно и то же модельное время.


Рис. 3. Процесс "Банк" и очереди FIFO для каждой из линий связи

4.