While(не конец моделирования) do. Ждать пока каждая из очередей содержит хотя бы одно сообщение

Begin

Ждать пока каждая из очередей содержит хотя бы одно сообщение

Удалить сообщение с наименьшей меткой, просмотрев каждую из очередей.

Обработать это событие

End

Вернёмся к примеру: В очередях последовательно были обработаны события, запланированные на время t1=10, t2=11. Далее процесс ожидает появления сообщения от покупателя. Иначе он не может продолжить работу. Процесс блокируется (рис.14).

Рис. 14. Процесс блокируется, потому что на линии связи с процессом-покупателем нет сообщений.

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

Пример:

Итак, у нас 3 процесса LP1,LP2,LP3. Процесс LP1 блокирован, т.к. ожидает прихода сообщения от LP3 и не может отослать сообщения процессу LP2. Процесс LP2 тоже блокирован, он ожидает сообщений от LP1. Процесс LP3 в свою очередь блокирован, поскольку в его входной очереди нет сообщений от первого процесса LP1. Теперь мы видим, что происходит циклическое ожидание процессов (тупик). Иллюстрацию примера см. на рис.

Для того, чтобы избежать возникновение тупиков, Chandy и Misra предложили использовать нулевые сообщения. Процесс LP_a посылает сообщение с временной меткой T_null процессу LP_b. Этим процесс LP_a сообщает процессу LP_b, что он не пришлёт процессу сообщение с временной отметкой, меньшей, чем T_null. Нулевые сообщения не соответствуют каким-либо физическим явлениям моделируемого объекта.

Рис. 15. Циклическое ожидание процессов.

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

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

Рис. 16. Отсылка по выходным дугам нулевых сообщений.

Каким образом процесс определит временную метку нулевого сообщения, которое он отсылает?

Значение часов каждой линии связи определяет нижнюю границу временной метки следующего события, которое будет извлечено из буфера этой линии связи. Эта нижняя граница в совокупности со сведениями о выполнении процесса являются исходной информацией для определения нижней границы временных меток для всех посылаемых с выходных дуг сообщений. Fujimoto приводит такой пример: если известно, что некоторое обслуживающее устройство обрабатывает заявку в течении T единиц модельного времени, то временная метка любого отсылаемого сообщения по крайней мере на T единиц модельного времени больше, нежели временная метка любого сообщения, которое может появиться в будущем (рис.15).

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

Алгоритм с нулевыми сообщениями (выполняется каждым логическим процессом LP):