РАЗДЕЛ 2.
АЛГОРИТМ ПАРАЛЛЕЛЬНОГО ВЫПОЛНЕНИЯ
И СИНХРОНИЗАЦИИ Е-СЕТИ
В разделе формализуются алгоритмы работы Е-сетевого перехода и планировщика при
традиционном последовательном моделировании; выделяются параллельные процессы
переходов и планировщика и описываются формально с помощью процессной алгебры
CSP. На основе консервативной схемы синхронизации разрабатывается алгоритм
параллельного выполнения Е-сетевых имитационных моделей; формализуются
предлагаемые изменения в алгоритме работы Е-сетевого перехода; показывается,
что предлагаемые изменения не нарушают функционирование Е-сетевого перехода и
обеспечивают корректность РСИМ. Обсуждается верификация CSP определений.
2.1. Формальное определение Е-сети
Формально Е-сеть можно определить пятеркой [31, 34, 35, 39]
, (2.1)
где
– конечное непустое множество позиций.
– конечное непустое множество переходов; множества переходов и позиций не
пересекаются .
– входная функция; – означает, что существует дуга, ведущая из позиции
к переходу ; – означает, что такая дуга не существует. Тогда – множество
всех входных позиций перехода .
– выходная функция; – означает, что существует дуга, ведущая от
перехода в позицию ; – означает, что такая дуга не существует. Тогда –
множество всех выходных позиций перехода .
– функция разметки, определяющая маркировку или состояние позиции; –
означает, что позиция свободна (не содержит метку), – означает, что
позиция занята (содержит метку); – начальная разметка сети.
В данной работе будем рассматривать базисный набор переходов, определяющийся
множеством типов . Переход типа моделирует событие, наступающее при выполнении
одного условия. В случае необходимости двух и более условий одновременно
используется переход типа . Разветвление потока информации отображается в
переходе типа . При необходимости изменения направления потока информации по
некоторому условию используется переход типа . Переход типа отражает
приоритетность, устанавливаемую для одних потоков информации по отношению к
другим.
С условными переходами типа и связана одна разрешающая позиция.
Важной особенностью Е-сети является детализация представления метки. С каждой
меткой в Е-сети связаны описателей. Каждый из описателей метки несет в себе
определенную количественную информацию о моделируемом объекте.
Переход Е-сети моделирует некоторое событие не только на уровне выполнения всех
необходимых условий, но и отражает также ряд операций, связанных с данным
событием, посредством модификации описателей меток. Набор операций и условия их
выполнения задаются процедурой преобразования.
Таким образом, любой переход можно описать
для переходов типа , или
(2.2)
для перехода типа
для перехода типа ,
где
– тип перехода;
– время задержки на переходе;
– процедура преобразования перехода;
, – результат вычисления управляющей процедуры. Результат вычисления может
быть неопределенным – или принадлежать множеству входных (для перехода типа )
или выходных (для перехода типа ) позиций, , .
Условием срабатывания перехода типа является наличие метки во входной позиции и
отсутствие метки в выходной позиции. Переход типа срабатывает, если имеется
метка во входной позиции и отсутствуют метки во всех выходных позициях.
Условием срабатывания перехода типа является наличие меток во всех входных
позициях и отсутствует метка в выходной позиции. Необходимым (но не
достаточным) условием срабатывания перехода является наличие метки во входной
позиции. При этом условии сначала должна быть вычислена управляющая процедура,
ассоциированная с управляющей позицией. Если в результате этого вычисления
будет определена выходная позиция и эта выходная позиция будет свободна, то
переход сработает. Если результат вычисления управляющей процедуры не
определен, то переход не сработает. Для срабатывания перехода типа необходимо
(но не достаточно) наличие метки хотя бы в одной входной позиции и отсутствие
метки в выходной позиции. При этом условии должна быть вычислена управляющая
процедура, ассоциированная с управляющей позицией. Если в результате этого
вычисления будет определена входная позиция и эта входная позиция содержит
метку, то переход сработает.
Функция определяет, выполнены ли условия срабатывания перехода ; –
означает, что условия срабатывания выполнены и переход готов к
срабатыванию; – означает, что условия срабатывания не выполнены.
Определение функции в зависимости от типа перехода приведено в таблице 2.1.
Таблица 2.1
Определение функции в зависимости от типа перехода
Графическое
изображение
Формула
если
иначе,
где ,
если
иначе,
где
если
иначе,
где
если
иначе,
где ,
если
иначе,
где ,
При срабатывании Е-сетевого перехода происходит перемещение меток из входных
позиций в выходные по правилам, определенным для различных типов переходов.
Изменение разметки в новую разметку , при срабатывании перехода в
зависимости от его типа приведены в таблице 2.2.
Таблица 2.2
Изменение разметки сети при срабатывании перехода
Графическое изображение
Формула
,
,
Алгоритм работы перехода можно описать блок-схемой (рис. 2.1)
Рис. 2.1. Алгоритм работы Е-сетевого перехода t О T
2.2. Традиционная дискретно-событийная система моделирования
Традиционно дискретно-событийные системы имитационного моделирования [85–89]
строятся на основе планировщика, оперирующего следующими структурами данных
(рис. 2.2):
переменные состояния, описывающие состояние системы;
с