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

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



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

Рис. 6. Отсылка по выходным дугам нулевых сообщений.
Каким образом процесс определит временную метку нулевого сообщения, которое он отсылает?
Значение часов каждой линии связи определяет нижнюю границу временной метки следующего события, которое будет извлечено из буфера этой линии связи. Эта нижняя граница в совокупности со сведениями о выполнении процесса являются исходной информацией для определения нижней границы временных меток для всех посылаемых с выходных дуг сообщений. Fujimoto приводит такой пример: если известно, что некоторое обслуживающее устройство обрабатывает заявку в течении T единиц модельного времени, то временная метка любого отсылаемого сообщения по крайней мере на T единиц модельного времени больше, нежели временная метка любого сообщения, которое может появиться в будущем (рис. 5).
Как только процесс завершит обработку нулевого или ненулевого сообщения, он вновь посылает нулевое сообщение по выходным дугам. Процесс, получивший нулевое сообщение, обязан вычислить нижнюю границу временной метки и отослать эту информацию свои соседям и т.д.
Алгоритм с нулевыми сообщениями (выполняется каждым логическим процессом LP):
Цель: Обеспечить выполнение событий в хронологическом порядке и избежать тупиков
while (не конец моделирования) do
begin
Ждать пока не выполнится условие: каждая очередь FIFO
содержит хотя бы одно сообщение.
Удалить событие с наименьшей временной отметкой из FIFO.
Обработать это событие.
Послать нулевое сообщение своим соседям с временной меткой,
указывающей нижнюю границу будущих событий, посланных этому LP
(текущее время + lookahead)
end
Итак, приведённый выше алгоритм с использованием нулевых сообщений позволяет избавиться от тупиков.

5.