Стр. 39 - Параллельное программирование

ПАРАЛЛЕЛЬНОЕ ПРОГРАММИРОВАНИЕ
37
Рис. 4.4. Пример маркированной сети Петри
Сети Петри были разработаны и используются для моделирования параллель-
ных и асинхронных систем. При моделировании в сетях Петри места символизиру-
ют какое-либо состояние системы, а переход - какие-то действия, происходящие в
системе. Система, находясь в каком-то состоянии, может порождать определенные
действия, и наоборот, выполнение какого-то действия переводит систему из одного
состояния в другое.
Текущее состояние системы определяет маркировка сети Петри, т.е. располо-
жение меток (токенов) в местах сети. Выполнение действия в системе, в сетях Петри
определяется как срабатывание переходов. Срабатывание переходов порождает но-
вую маркировку, т.е. новое размещение меток (токенов) в сети. Определим функ-
ционирование маркированных сетей, основанное на срабатывании отдельных
переходов.
Определение. Правило срабатывания переходов. Пусть марки-
рованная сеть:
• переход считается возбужденным при маркировке , если
;
• переход , возбужденный при маркировке , может сработать, приведя к
новой маркировке , которая вычисляется по правилу .
Срабатывание перехода обозначается как .
Иными словами, переход считается возбужденным при некоторой маркировке,
если в каждом его входном месте имеется количество меток не менее кратности со-
ответствующих дуг. Возбужденный переход может сработать, причем при срабаты-
вании из каждого его входного места изымается, а в каждое входное добавляется
( )
0 , , ,MFTS =Σ
T t ∈ S M µ ∈
t M * ≥
t M
M ′ * * t t MM+ − =′
M tM′ > [