Цель: Обеспечить выполнение событий в хронологическом порядке и избежать тупиков

While(не конец моделирования) do

Begin

Ждать пока не выполнится условие: каждая очередь FIFO содержит хотя бы одно сообщение.

Удалить событие с наименьшей временной отметкой из FIFO.

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

Послать нулевое сообщение своим соседям с временной меткой, указывающей нижнюю границу будущих событий, посланных этому LP (текущее время + lookahead)

End

Итак, приведённый выше алгоритм с использованием нулевых сообщений позволяет избавиться от тупиков.

Использование lookahead (Забегания вперёд)

Для консервативных алгоритмов синхронизации характерной особенностью является использование предварительного просмотра (lookahead).

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

Обсуждаемый алгоритм допускает множество модификаций, таких как, например, подсчёт lookahead по отдельности для различных исходящих дуг, что приводит к значительному уменьшению простоя логических процессов. К отрицательным характеристикам этого алгоритма можно отнести тот факт, что если процессы сильно связаны, то все логические процессы будут продвигаться лишь на очень малые промежутки времени. Таким образом, моделирование по своей сути будет последовательным. Недостатком алгоритма является и то, что при небольших значениях lookahead возможна ситуация циклического ожидания нескольких LP с небольшими продвижениями локальных часов. В некоторых системах возможно, а зачастую и необходимо, использование нулевого предварительного просмотра (zero lookahead), однако обсуждаемый выше алгоритм не допускает нулевых предварительных просмотров.

Date: 2015-09-18; view: 416; Нарушение авторских прав