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

Алгоритм управления временем должен следить за тем, чтобы события выполнялись в хронологическом порядке. Эта задача не является тривиальной. Действительно, логический процесс заранее не может знать о том, на какое время будет запланировано событие, которое он получает от другого логического процесса. Пусть в списке необработанных событий хранится событие с временной меткой 10. Может ли симулятор логического процесса выбрать его для обработки. Это можно было бы сделать, если бы логический процесс каким-нибудь образом знал о том, что другой логический процесс не запланировал для него события, со временем меньшим, чем 10.

Рассмотрим другой пример.

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

Предположим, что покупатель приобрёл товары в магазине на определённую сумму N (в кредит) (событие e1, произошло в момент времени t1 = 9). Магазин уведомил об этом банк (e2, t2 = 10) Сумма на счёте уменьшается: S = S – N. Покупатель посещает банк с целью снять деньги со счёта (e3, t3=11). Если денег на счёте достаточно, то банк выдаёт клиенту (которым является покупатель) запрошенную им сумму. Если счёт меньше запрошенной суммы, то покупателю будет отказано.

Хронологический порядок событий: e1, e2, e3 (рис.11).

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

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

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

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

Распределённый алгоритм должен уметь бороться с такими парадоксами времени.

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

Если мы вернёмся к примеру 1, то консервативный алгоритм не позволит логическому процессу обрабатывать событие с временной отметкой 10, пока не убедится, что другой логический процесс не запланировал для него события с временной меткой, меньшей 10.

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

Рассмотрим более подробно каждый из алгоритмов управления временем.