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

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

Допустим, что мы имеем два логических процесса LP. Предположим, что оба они заблокированы. Каждый из них достиг временной отметки, равной 100 (T_locLP1 =100) и значение lookahead =1. Пусть следующее запланированное событие имеет временную метку, равную 200. Алгоритм с нулевыми сообщениями будет действовать следующим образом: сообщения будут посланы процессами в моменты времени, равные 101, 102,103 и т.д. Это будет продолжаться до тех пор, пока процессы не достигнут временной отметки, равной 200. После этого событие с временной меткой 200 (e_i, 200), будет выполнено. Т.о., мы видим, что было послано и обработано 100 нулевых сообщений до того момента, когда пришёл черёд ненулевого необработанного события. Из примера рис. 16 видно, что алгоритм с нулевыми сообщениями в этом случае неэффективен. Ситуация ещё более изменится к худшему, если мы будем работать с большим количеством процессов.

Рассмотрим пример, который проиллюстрирован на рис.16.

На рисунке видно, что взаимодействуют 3 логических процесса. Нулевые сообщения запланированы на 5.0, 5.5, 6.0 и т.д., они отсылаются через каждые 0.5 минут единиц модельного времени. Нулевых сообщений гораздо больше, нежели в предыдущем примере. Итак, если lookahead мало, то это приводит c к большому количеству нулевых сообщений.

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

Рис. 17. Слишком много нулевых сообщений (lookahead = 0.5)

Многие усовершенствованные алгоритмы используют изложенную только что идею.

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

Chandy и Misra решили эту проблему следующим образом: вычисления продолжаются до возникновения тупика. Далее тупик обнаруживают и устраняют. Тупик может быть устранён по той причине, что сообщение с минимальным временем безопасно и, следовательно, может быть обработано.

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