(b) t1, t2 是并发的, 且若 t2 在 t1 前点火,
则 t1 与 t3 冲突.
图 1.5. 对称与非对称
Petri 网的可达图是其可能状态和使能迁移关系的图表示.
(a) 一个 Petri 网
(b) 上述网的可达图 图 1.6. 可达图
3
北京师范大学信息科学学院
知识工程研究中心
二. Petri 网的行为
M(p) § M £(p). 对一个迁移 t, 用 Mt 记可以使能的最小状态. 定理. Petri 网(N, M0)中的迁移 t 是 L1-活性的 ‹ Mt 是可覆盖的.
5
北京师范大学信息科学学院
知识工程研究中心
2.6 持续性 Petri 网(N, M)称为持续的, 如果(N, M)中任何两个使能迁移 t1, t2, t1 的点火不 会改变 t2 的使能性. 例如, 所有标记图都是持续的, 但持续的网不一定都是标记图.
北京师范大学信息科学学院
知识工程研究中心
Petri 网: 基本概念和分析方法
记号: N = {0, 1, 2, … }, N+ = {0, 1, 2, … }.
一. 基本概念
一个 Petri 网由五个部分组成 PN = (P, T, F, W, M0), 其中: P 是位置(place)的有限集合; T 是迁移(transition)的有限集合; P … T = «, P » T ∫ «; F Œ (P ä T) » (P ä T)是有向弧的集合; w : F ö N+是弧的权函数; M0 : P ö N 是初始标记(初始状态). 注. 不带初始状态的 Petri 网记为 N = (P, T, F, W), 带有初始状态 M0 的 Petri 网则记为(N, M0). 若 PN 是一个 Petri 网, 则映射 M : P ö N 称为一个状态. 对 p œ P, 若 M(p) = k, 则称位置 p 标记有 k 个符号(token).
M(p) - w(p, t)
若 p 是 t 的输入位置
M £(p) = M(p) + w(t, p)
若 p 是 t 的输出位置
M(p)
若 p 为其它位置
则称 t 被点火(击发), 且系统从状态 M 迁移到状态 M £, 记为 M t M £.
例 1. 化学反应 2H2 + O2 ö 2H2O 的 Petri 网表示.
且对" p œ P, M £(p) ¥ M ££(p), 则对满足 M £(p) > M ££(p)的 每个 p œ P, 用w代替 M £(p). Step 2.4.3) 将 M £做为一个新节点, 并从 M 到 M £画一条标记为 t 的 有向弧. 例 1. 考虑图 3.1 所表示的 Petri 网. 根据上述算法, 我们可以画出其可覆盖 树(图 3.2).
例 3. 迁移 t2, t3 是并发的, 而此网是一个标记图.
2
北京师范大学信息科学学院
知识工程研究中心
图 1.4. 并发
既有并发迁移又有冲突迁移的 Petri 网称为混合型的. 并发迁移与其它迁移 可以是对称的(同时冲突), 也可以是非对称的.
(a) t1, t2 是并发的, 而且都与 t3 冲突.
图 2.1. 活性网
活性概念可以分层. 设 t 是 Petri 网(N, M0)中的一个迁移. 则: (1) 若对 L(M0)中任何点火序列, t 都不能被点火, 则称 t 是 L0-活性的(死的);
4
北京师范大学信息科学学院
知识工程研究中心
(2) 若对 L(M0)中的某个点火序列, t 至少能被点火一次, 则称 t 是 L1-活性的 (潜在可点火的);
图 1.2. 饮料贩卖机的 Petri 网模拟.
若存在某个位置 p, p 是至少两个迁移的输入位置, 则称此网为非确定的, 或 者根据特定的应用领域, 称为冲突, 决策或者选择等.
图 1.3. 冲突, 决策, 选择
两个迁移 t1, t2 œ T 称为并发的, 如果 t1, t2 是因果独立的, 即两者都可以先后 点火或者并行点火.
同, 将 M 标记为“old”, 并继续再选一个标记为“new”的节点. Step 2.3) 若在状态 M 下, 没有任何使能的迁移, 将 M 标记为“dead-end”. Step 2.4) 对状态 M 下每个使能的迁移 t, 做:
Step 2.4.1) 得到状态 M 下迁移 t 点火后迁移的新状态 M £. Step 2.4.2) 在从根节点到 M 的道路上, 若存在 M ££, 使得 M £ ∫ M ££,
" n œ N, w > n, w ≤ n = w, w ¥ w. 设(N, M0)是 Petri 网, (N, M0)的可覆盖树 T 按照以下算法生成. 可覆盖树生成算法. Step 1) 将初始状态设为根节点, 并标记为上“new”. Step 2) 如果当前存在标记为“new”的节点, 做:
Step 2.1) 选择一个标记为“new”的节点 M. Step 2.2) 若状态 M 与从根节点到 M 的道路上的某个节点表示的状态相
Petri 网可达性问题. 对(N, M0)的任何状态 M, 是否 M œ R(M0) ? 2.2 有界性 设 k œ N. Petri 网(N, M0)称为 k-有界的, 如果对任何位置 p 和状态 M œ R(M0),
M(p) § k. (N, M0)称为安全的, 如果它是 1-有界的.
2.3 活性 Petri 网(N, M0)称为活性的, 如果在任何状态 M œ R(M0)下, 通过适当的点火 序列后, 每个迁移最终都可以被点火. 在活性 Petri 网中, 无论怎样选取点火序列, 都保证不会出现死锁. 例如, 下 面的通信协议的 Petri 网表示是活性的:
图 2.4. 同步距离 6
北京师范大学信息科学学院
知识工程研究中心
2.8 公平性 设(N, M)是 Petri 网, 称两个迁移 t1, t2 处于有界公平关系(bounded fair, B-fair) 下, 如果一个可点火而另一个不可点火的最大次数是有界的. Petri 网(N, M)称为 有界公平的(B-fair), 如果该网中的任何迁移对都处于有界公平关系. 一个点火序列s称为无条件公平的, 如果s是有限的, 或者网中的每个迁移 在s中出现无限次. Petri 网(N, M)称为无条件公平的, 如果每个点火序列s都是无 条件公平的. 定理. (1) 任何 B-fair 网是无条件公平的. (2) 任何有界无条件公平网是 B-fair 网. 例如, 图 2.4 中的网既不是 B-fair 网, 也不是无条件公平网, 因为 t3, t4 不出现 在无限点火序列s = t2 t1 t2 t1......中. 图 2.3 中的网是无条件公平网, 但不是 B-fair 网, 因为若 p2 中的符号个数无 界, 那么 t2 点火而其它迁移不点火的次数也无界. 下面的图 2.5 是一个 B-fair / 无条件公平网
7
北京师范大学信息科学学院
知识工程研究中心
三. Petri 网的分析方法
3.1 可覆盖树方法 Petri 网的可覆盖树表明了该网中所有可能到达的状态(树的节点)和使能的 迁移(弧的标记). 记号: 为了表示无界标记, 用w表示“无限”正整数, 即w满足条件:
(3) 若对任何 k œ N, 关于 L(M0)中的某个点火序列, t 至少能被点火 k 次, 则 称 t 是 L2-活性的;
(3) 若在 L(M0)中的某个点火序列中, t 可以不定地出现, 则称 t 是 L3-活性的; (4) 若对每个 M œ R(M0), t 都是 L3-活性的, 则称 t 是 L4-活性的(活性的). 对 k = 0, 1, 2, 3, 4, Petri 网(N, M0)称为 Lk-活性的, 如果该网中的每个迁移都 是 Lk-活性的. 显然有:
迁移(点火)法则. 设 M : P ö N 是 Petri 网(N, M0)的一个状态, t œ T. (1) 迁移 t 称为在状态 M 下使能的(enable), 如果对 t 的任何输入位置 p, 有:
M(p) ¥ w(p, t). (2) 设迁移 t 在状态 M 下为使能的, M £是如下定义的状态: 对 p œ P,
图 3.1. 一个 Petri 网(N, M0), M0 = (1 0 0).
8
北京师范大学信息科学学院
知识工程研究中心
图 3.2. 上述 Petri 网的可覆盖树
从 Petri 网(N, M0)的可覆盖树 T 出发, 可以研究该网的性质. 典型结果有: (1) (N, M0)是有界的(所以 R(M0)是有限的) ‹ w不出现在 T 的任何节点的标
L4-活性 fl L3-活性fl L2-活性 fl L1-活性 对 k = 1, 2, 3, Petri 网(N, M0)称为严格 Lk-活性的, 如果(N, M0)是 Lk-活性的, 但不是 Lk+1-活性的. 例如, 图 2.2 中的网不是活性的. 如果 t1 先点火, 任何迁移都不能再点火了.
图 2.2. 安全的, 严格 L1-活性的, 但非活性的 Petri 网.
2.7 同步距离
图 2.3. 持续的, 但非标记图
设(N, M)是 Petri 网, s是一个点火序列, t 是一个迁移. 用s-(t)记迁移 t 在s中点
火的次数. 对(N, M)中的两个迁移 t1, t2, t1, t2 之间的同步距离定义为:
d12
=
max s
|
s-(t1)
-
s-(t2)
|.
例如, 在下图 2.4 中, d12 = 1, d34 = 1, d13 = ¶.
号中. (2) (N, M0)是安全的 ‹ 只有 0 和 1 出现在 T 的任何节点的标号中. (3) 迁移 t 是死的 ‹ 在 T 的任何弧的标记上都不出现 t. (4) 若 M 是从 M0 可达的, 则 T 中存在一个节点 M £, 使得 M £ ¥ M. 对于有界的 Petri 网(N, M0), 其可覆盖树 T 也称为可达树, 因为 T 包含了(N, M0)的所有可达状态. 在这种情况下, 有关(N, M0)的所有行为分析问题都可以通 过可达树来完成. 可覆盖树方法本质上是一种穷举方法, 因此它的主要缺点是复 杂性问题. 若 Petri 网(N, M0)不是有界的, 则由于引进符号w时丢失了信息(同一个符号 可表示不同内容), 所以不能单独用可覆盖树方法求解可达性和活性问题. 例 2. 图 3.3 中的两个 Petri 网活性不同, (a)中的网是活的, 而(b)中的网在 t1, t2, t3 点火后, 再没有使能的迁移.