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

Begin

Просмотреть список SE = {l_i}, где l_i = (e_i, t_i), 0£ i £ n и выбрать элемент с минимальным временем t_i.

Systemtime:= min(t_i);

Передать управление событию e_i из элемента l_i = (e_i, t_i);

Обработать это событие. Если событие e_i запланировало новое событие e_j (т.е. было выполнено преобразование Sch), то соответствующий элемент l _j следует поместить в список событий SE, т.е. выполнить операцию SE:=SE + l _j

End

Если сразу несколько событий запланировано на одно и то же время, то они выполняются последовательно друг за другом (квазипараллельно), системное время systemtime не изменяется до тех пор, пока все эти события не будут обработаны.

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

Если число элементов в списке SE велико, поиск события с минимальным временем (и включение в список нового элемента) может занять много времени. Для оптимизации этого процесса исследователи предлагают усовершенствованные алгоритмы:

- Поиск с начала и конца списка.

- Использование различных списков для различных типов событий.

- Использование дополнительного указателя на середину списка. Сначала происходит сравнение с нужным элементом, а потом поиск происходит в нужной половине списка.

- Использование множества запланированных событий в виде бинарного дерева.

- Хранение наряду с календарём событий массива указателей на элементы списка. Таким образом, список событий делится на подсписки (между двумя соседними указателями). Эти подсписки соответствуют интервалам системного времени. Длины всех интервалов равны фиксированному значению. Это значение задаётся пользователем. При планировании нового события вычисляется его индекс в массиве указателей, после чего новый элемент календаря событий может быть размещён в соответствующем его подсписке.

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