第3章 Petri网.ppt

1 Chapter3Petri网 一 基本定义 1 Petri网结构 2 普通网 3 位置 迁移Petri网 二 Petri网的性质 1 行为性质 2 结构性质 三 Petri网分析技术 1 结构化简 2 可达树 覆盖树 3 状态方程 不变量 四 Petri网规格的例 1 哲学家就餐问题 2 生产者 消费者问题 Petri网的概念最早是由德国的CarlAdamPetri于1962年在其博士论文 自动机通信 中提出来的 它是一种适合于并发 异步 分布式软件系统规格与分析的形式化方法 Petri网分为位置 迁移Petri网和高级Petri网两类 高级Petri网包括 谓词 迁移Petri网 有色Petri网 计时Petri网等 2 一 基本定义 任何系统都可抽象为状态 或者条件 活动 或者事件 及其之间关系的三元结构 在Petri网中 状态用位置 place 表示 活动用迁移 transition 表示 迁移的作用是改变状态 位置的作用是决定迁移能否发生 迁移和位置之间的这种依赖关系用流来表示 Petri网结构 Petri网结构是一个三元组N P T F 其中 P p1 p2 pn 是有限位置集合 T t1 t2 tn 是有限迁移集合 P T P T F P T T P 为流关系 例 Petri网结构N P T F P p1 p2 p3 p4 p5 p6 T t1 t2 t3 t4 t5 F p1 t1 t1 p2 t1 p3 p2 t2 p3 t3 t2 p4 t3 p5 p4 t4 p5 t4 t4 p6 p6 t5 t5 p1 3 一 基本定义 子网结构 对于N1 P1 T1 F1 和N2 P2 T2 F2 如果P1 P2 T1 T2且F1 F2 P1 T1 T1 P1 则称N1是N2的子网结构 前集和后集 对于一个Petri网结构N P T F 设x P T 令 x y y y x F x y y x y F 那么称 x为x的前集或输入集 x 称为x的后集或输出集 在N P T F 中 如果对所有的x P T 都有 x x 则称N为单纯网 purenet 简称纯网 如果对所有的x y X 都有 x y x y x y 则称N为简单网 simplenet Petri网允许位置中包含令牌 token 令牌可以依据迁移的引发而重新分布 具有动态特征的Petri网定义如下 普通Petri网 普通Petri网形式上定义为一个四元组PN P T F M0 N M0 其中 N P T F 是一个Petri网结构 M P Z 非负整数集合 是位置集合上的标识 marking 向量 对于任一位置p P 以M p 表示标识向量M中位置p所对应的分量 称为位置p上的标识或者令牌数目 M0是初始标识向量 在Petri网的图形表示中 标记或令牌用位置中的黑点或数字表示 同一位置中的多个标记代表同一类完全等价的个体 标识向量表示了令牌在位置中的分布 5 一 基本定义 在Petri网中 依据迁移的使能 enable 条件 可以使得使能的迁移引发 fire 迁移的引发会依据引发规则实现令牌的移动 不断变化着的令牌重新分布就描述了系统的动态行为演化 迁移的使能条件I 对于Petri网PN P T F M 如果 p1 p1 t M p1 1 则称t在M下使能 记为M t 迁移的引发规则I 对于Petri网PN P T F M 任何在M下使能的迁移t将会引发 迁移t的引发使得位置中令牌重新分布 从而将标识M变成新标识M 并称M 为M的后继标识 并记为M t M 对于 p P M p 可通过下式计算 M p 1p t t M p M p 1p t tM p 其它 在图 a 所示Petri网中 变迁t1和t2是使能的 在这种情况下 该Petri网的演化 即令牌的变化就可能存在如下3种不同方式 引发t1 引发t2 或者引发t1和t2 也就是说 在给定Petri网的初始标识后 其演化过程可能是不同的 具有不确定性 引发t1所得到的图 b 所示状态 引发t2所得到的图 c 所示状态 引发t1和t2得到图 d 所示状态 在图 b 的情况下 变迁t2和t3使能 在引发变迁t2后 将得到图 d 所示状态 在图 c 的情况下 变迁t1和t4使能 在引发变迁t1后 将同样得到图 d 所示状态 图 d 所示Petri网中 变迁t3和t4是使能的 令牌的变化就可能存在如下2种不同方式 引发t3 或者引发t4 引发t3得到图 e 所示的下一个状态 引发t4得到图 f 所示状态 在图 e 的情况下 变迁t5使能 引发变迁t5后 将得到图 c 所示状态 在图 f 的情况下 变迁t6使能 引发变迁t6后 将得到图 b 所示状态 一 基本定义 一个没有任何输入位置的迁移叫源迁移 一个源迁移的使能是无条件的 一个源迁移的引发只会产生令牌 而不消耗任何令牌 一个没有任何输出位置的迁移叫阱迁移 一个阱迁移的引发只会消耗令牌 而不产生任何新的令牌 位置 迁移Petri网 位置 迁移Petri网 简称为Petri网 形式上定义为一个六元组PN P T F K W M0 N K W M0 其中 N P T F 是一个Petri网结构 K P Z 是位置上的容量函数 Z 是正整数集合 规定了位置上可以包含的令牌的最大数目 对于任一位置p P 以K p 表示向量K中位置p所对应的分量 若K p 表示位置p的容量为无穷 9 W F Z 是流关系上的权函数 规定了令牌传递中的加权系数 对于任一弧f F 以W f 表示向量W中弧f所对应的分量 M P Z 非负整数集合 是位置集合上的标识向量 对于任一位置p P 以M p 表示标识向量M中位置p所对应的分量 并且必须满足M p K p M0是初始标识向量 10 在Petri网的图形表示中 对于弧f F 当W f 1时 将W f 标注在弧上 当W f 1时 省略W f 的标注 当一个位置的容量有限时 通常将K p 写在位置p的圆圈旁 当K p 时 通常省略K p 的标注 容量函数和权函数均为常量1的Petri网称为基本Petri网 简称基本网 或条件 事件网 容量函数恒为无穷和权函数恒为1的Petri网称为普通Petri网 简称为普通网 显然 基本网和普通网都是Petri网的特殊情形 基本网和普通网可以用四元组PN P T F M 来表示 迁移的使能条件II 对于Petri网PN P T F K W M 如果 p1 p1 t M p1 W p1 t 且 p2 p2 t K p2 M p2 W t p2 则称t在M下使能 记为M t 迁移的引发规则II 对于Petri网PN P T F K W M 任何在M下使能的迁移t将会引发 迁移t的引发使得位置中令牌重新分布 从而将标识M变成新标识M 并记为M t M 对于 p P M p 可通过下式计算 M p W p t p t t M p M p W t p p t tM p W p t W t p p t t M p p t t W t1 p2 2 W t3 p5 3 W p6 t5 3 W p1 t1 W t1 p3 W p2 t2 W p3 t3 W t2 p4 W p4 t4 W p5 t4 W t4 p6 W t5 p1 1 K p2 3 K p4 K p5 4 K p6 6 K p1 K p3 K p5 M 1 0 0 1 0 0 的Petri网 顺序 并发 冲突 混惑结构的Petri网模型 顺序关系 设M为Petri网PN的一个标识 若存在t1和t2使得M t1 M 且 M t2 M t2 亦即 在M标识下 t1使能 而t2不使能 且t1的引发会使t2使能 即t2的使能以t1的引发为条件 则称t1和t2在M下有顺序关系 并发关系 设M为Petri网PN的一个标识 若存在t1和t2使得M t1 和M t2 并满足M t1 M1 M1 t2 且M t2 M2 M2 t1 则称t1和t2在M下并发 就是说在M标识下 t1和t2都使能 且它们当中任一个迁移的引发都不会使另一个迁移不使能 冲突关系 设M为Petri网PN的一个标识 若存在t1和t2使得M t1 和M t2 并满足M t1 M1 M1 t2 且M t2 M2 M2 t1 则称t1和t2在M下冲突 就是说M标识下 t1和t2都使能 但它们当中任一个迁移引发都会使另一个迁移不使能 混惑关系 某些情形下 一个Petri网中可能同时存在着并发和冲突 而且并发迁移的引发会引起冲突的消失或出现 下图所示的Petri网中 t1和t3是两个并发迁移 若t3先于t1引发 则t2获得发生权 而且t2和t1处于竞争资源的冲突状态 若进一步在解决冲突时让t2引发 则t1就失去了曾经拥有的发生权 如果在t1和t2的冲突中让t1引发 则p5获得令牌 系统到达最终状态 0 0 1 0 1 0 从初始状态 1 1 0 1 0 0 到达 0 0 1 0 1 0 的另一种可能是t1先引发 然后t3引发 t1和t3并发也到达这一状态 这后两种情况不会出现冲突 换句话说 从所观察到的状态变化 1 1 0 1 0 0 0 0 1 0 1 0 无法判断其间是否出现过冲突 象这样并发和冲突混合在一起产生的困惑 使人无法从终态判断是否有冲突发生过 所以将这种情况称为 混惑 16 二 Petri网的性质 Petri网具有两类性质 与初始标识有关的和与初始标识无关的 前者称为标识有关性质或者行为性质 后者称为标识无关性质或者结构性质 1 行为性质可达性 可达性是研究任何系统动态行为的基础 按照迁移引发规则 使能迁移的引发将改变令牌的分布 产生新的标识 对于初始标识M0 如果存在一系列迁移t1 t2 tn的引发使得M0转换为Mn 则称标识Mn是从M0可达的 记为M0 Mn 其中 M0t1M1t2M2 tnMn 或简记为 t1t2 tn 称为迁移的引发序列 对于Petri网PN N M0 所有可达的标识组成一可达标识集 记为R N M0 或R M0 从M0出发的所有可能引发序列组成一引发序列集 记为L N M0 或L M0 17 行为性质 有界性和安全性 在PN N M0 中 若存在一个非负整数k 使得M0的任一可达标识的每个位置中的标记数都不超过k 即 k Z 对 M R M0 都有k M p 则称位置p为k有界 如果PN中每一位置都是k有界 则称PN为k有界 位置p为1有界称为位置p是安全的 如果PN中每一位置都是安全的 则称PN是安全的 这里的k与Petri网定义中的位置容量K完全不同 是在无限容量网的运行过程中 自动地满足k M p 而Petri网定义中是对某个位置的容量加以限制 从而也强制地使系统运行过程中每个位置中的令牌数不超过一定的上限 18 行为性质 t4 右图中Petri网 在初始标识 1 0 1 0 下的可达标识为 0 1 1 0 0 0 0 1 0 0 1 0 对应的迁移引发序列为t2t3t4 所以R M0 0 1 1 0 0 0 0 1 0 0 1 0 L M0 t2t3t4 故该Petri网在M0下是有界的和安全的 标识 0 1 1 1 1 0 0 1 1 0 0 0 都是不可达标识 左图中Petri网 在初始标识下可能的引发序列有t2t1t2t1 t2t3t4t1t2t3t4t1 t2t3t1t4t2t3t1t4 t2t3t4t1t2t1t2 等 由于引发序列t2t1t2t1 将使p3中的令牌无限制增多 故该Petri网不是有界的 19 行为性质 活性 在PN N M0 中 若存在M R M0 使得迁移t使能 则t是潜在可引发的 如果对任何M R M0 迁移t都是潜在可引发的 即从M0可达的任一标识出发 都可以通过执行某一迁移序列而最终引发t 则称t在标识M0下是活的 如果所有迁移t都是活的 则称PN是活的 或者称M0是N的活标识 对于M R M0 若不存在迁移引发序列使得迁移t最终引发 则称迁移t是死迁移或死的 对于M R M0 若不存在任何迁移t使能 则称PN包含一个死锁 而标识M称为死标识 活的PN中无死锁 20 行为性质 活性 活性是许多系统的理想特性 但这是不现实的 要验证这一特性并不那么简单 因此 可放宽对活性的限制 并定义不同的活性等级 Petri网中迁移t的活性分成如下5级 L0 活的 死的 在任何迁移序列 L M0 中 迁移t都不能引发 L1 活的 可能引发 在某些 L M0 中 迁移t至少引发一次 L2 活的 给定一个正整数k 在某些 L M0 中 迁移t至少引发k次 L3 活的 在某些 L M0 中 迁移t可以无限次地引发 L4 活的 对于每个M R M0 迁移t是L1 活的 如果一个Petri网的每一个迁移都是Lk 活的 则称该Petri网为Lk 活的 k 0 1 2 3 4 如果一个迁移是Lk 活的 而不是Lk 1 活的 k 1 2 3 则称该迁移是严格Lk 活的 显然L0 活的实际上是永不引发的 其它4种活性之间存在如下关系 L4 活的 L3 活的 L2 活的 L1 活的 事实上 活性定义中 PN是活的 对应于活性登记中的 L4 活的 图中Petri网 t1 t2 t3和t4分别是L0 L1 L2和L3 活的 因为t1总是不能引发的 一旦p1因t2引发而失去令牌 就无法再获得令牌 即t2最多只能引发1次 t2引发后 t4不能再引发 t3的最大引发次数为p2中的令牌数 即t4的引发次数 而t4的最大引发次数存在可以任意指定引发序列 在p1有令牌的情况下 t4可以反复连续发生 而不使p1失去令牌 因为无限次地引发t4可使p2中的令牌无限地增加 所以该Petri网不是有界的 图中Petri网L M0 t2t4t5t1t3 t1 引发序列t2t4t5t1t3 使各迁移都引发一次 该Petri网是有界的和安全的 且严格L1 活的 p2 p4 严格L1 活的 活的 可逆性 在PN N M0 中 如果 M R M0 M0 R M 则称该Petri网是可逆的 对于可逆的Petri网 存在引发序列 t1t2 tn 从 M R M0 返回到M0 在很多应用中 仅要求系统回到某个特定状态 而无需返回到初始状态 称这个特定状态为主 home 状态 即对于R M0 的每个标识M 主状态M 都是可达的 有界 非活 可逆R 1 0 0 R 0 1 0 R 0 0 1 0 1 0 1 0 0 0 0 1 L M0 t2t4t2t4 t3t5t3t5 t2t4t3t5t2t4t3t5 t3t5t2t4t3t5t2t4 无界 非活 不可逆 23 行为性质 可覆盖性 在PN N M0 中 如果对于M M R M0 使得 p P 有M p M p 则称标识M是可覆盖的 持续性 在PN N M0 中 如果对于任何两个使能的迁移 其中一个引发以后 另一个仍是使能的 则称PN是持续的 也就是说 具有持续性的PN中 一个迁移一旦使能 将保持这种使能性直至它引发为止 24 行为性质 同步距离 对于PN N M0 任意t1 t2 T的同步距离定义为d12 max t1 t2 其中 是从任意一个标识M R M0 开始的引发序列 t1 和 t2 分别是引发序列 中t1和t2的引发次数 同步距离是用来刻划不同形式的同步关系的 是两个迁移之间这种相对关系的一种定量描述 公平性 在PN N M0 中 对于t1和t2 若不引发其中一个 另一个可以引发的最大次数为有界的 则称这两个迁移具有有界公平关系 若PN中任意一对迁移都存在有界公平关系 则称PN为有界公平网 对于一个引发序列 若 引发序列中迁移的数目 为有限数 或PN中的任何迁移t都在 中无限次出现 则称 为无条件 全局 公平的 如果 L M0 都是无条件公平的 则称PN为无条件公平网 25 2 结构性质 Petri网的结构性质取决于其拓扑结构N 而与初始标识无关 这里 与初始标识无关 有两层含义 任何初始标识M0下均成立 或者存在某一个初始标识M0使其成立 结构活性 对于N 若存在活的初始标识M0 则称N为结构活的 结构有界性 如果N对于任何初始标识M0都有界 则称N具有结构有界性 守恒性 对于 M R M0 如果对应于所有 某些 位置p存在正整数Y p 使得标识的加权和MTY M0TY 常数 则称N为 部分 守恒的 26 2 结构性质 可重复性 如果N存在一个初始标识M0和一个引发序列 L M0 使得所有 某些 迁移引发无限次 则称N为 部分 可重复的 相容性 如果N存在一个初始标识M0和一个从M0返回到M0的引发序列 L M0 使得所有 某些 迁移至少引发一次 则称N为 部分 相容的 结构有界公平性 对于任何初始标识 如果两个迁移之间总存在有界公平关系 则称这两个迁移具有结构有界公平关系 如果N中任何迁移都是有界公平的 则称N为结构有界公平的 三 Petri网的分析技术 1 结构化简结构化简是处理复杂问题的一种方法 其基本原则是在保持化简前后Petri网所具有的某些性质不变的前提下 将多个不同的位置或迁移抽象为单个位置或迁移 消除自循环位置 消除自循环迁移 合并串行位置 合并并行位置 合并串行迁移 合并并行迁移 2 可达树 覆盖树 对于一个Petri网PN N M0 以M0作为树根 树中的结点表示M0经过使能迁移的引发所产生的标识 结点之间的连线表示了标识和迁移之间的关系M t M 可达标识的这种树结构表示 称之为Petri网的可达树 对于有界Petri网 可达树中包含了其所有可达标识 在这种情况下 前面讨论的Petri网的所有性质问题都能由可达树来分析 2 可达树 覆盖树 2 可达树 覆盖树 31 2 可达树 覆盖树 对于无界Petri网 由于可达标识将无限制地增长 故可达树结构的结点也将无限制地增长 为了使所得到的树保持有限 可引入一个被认为是 无限 的特殊符号 该 具有如下特性 k Z 整数集 k k 且 对于结点M 如果从M0到M的路径上存在结点M 满足 p P M p M p 且M M 即 M 是可覆盖的 此时 可对M中满足M p M p 的p用 重置M p 这样得到的树就称为Petri网的覆盖树 2 可达树 覆盖树 覆盖树的构造算法如下 step1 将初始标识M0作为树根 并标记为new step2 若不存在标记为new的标识 停机 step3 选择一个标记为new的标识M 重复以下各步 若从根节点M0到M的路径上有与M相同的标识 将M标记为old 并转step2 若标识M下没有迁移可以引发 则将M记为dead end 并转step2 若标识M下存在可以引发的迁移 则对每个使能迁移t进行如下各步 a 计算在t引发后M的后继标识M 注 若M p 则M p b 若从根节点M0到M 的路径中存在结点M 满足 p P M p M p 且M M 则对M 中的每个满足M p M p 的p 用 重置M p c 将M 作为树的一个标志为new节点 并从M到M 画用t标注的弧 step4 将M标记为old 并转step2 33 2 可达树 覆盖树 利用覆盖树 可以分析Petri网PN N M0 的如下性质 当且仅当覆盖树中不出现含有 的标识时 PN有界 且因此R M0 是有限的 当且仅当覆盖树中每个标识的元素都为0或1时 PN是安全的 当且仅当迁移t T不出现在覆盖树中时 t为死的 即存在死锁 由于 的存在 于覆盖树一般不能用来分析可达性和活性 34 3 状态方程 不变量 Petri网的网结构可以用一个矩阵来表示 对于PN N M0 令P p1 p2 p3 pm T t1 t2 t3 tn 关联矩阵 Petri网PN N M0 的关联矩阵为一个以P T作序标的矩阵C P T Z 整数集合 其矩阵元素C pi tj W tj pi W pi tj 也可以写作 Cij m n Cij m n Cij m n或者C C C 其中 Cij W tj pi 是从迁移tj到它的输出位置pi的弧的权 Cij W pi tj 是从迁移tj的输入位置pi到迁移tj的弧的权 并称C 为Petri网的输入关联矩阵 C 为Petri网的输出关联矩阵 35 如果Petri网PN N M0 是一个纯网 即满足 x P T x x 则对任何pi tj Cij 和Cij 中必至少有一个为0 所以关联矩阵是对Petri网结构的准确描述 如果PN不是纯网 那么Cij 和Cij 就可能全不为0 于是Cij Cij 就是t引发时输入输出的最终效果 而不是对输入和输出的准确描述 36 3 状态方程 不变量 S 向量 T 向量 以位置集P为序标集的列向量V P Z叫做PN的S 向量 以迁移集T为序标集的列向量U T Z叫做Petri网的T 向量 对于关联矩阵为C C C 的Petri网 如果M1 tj M2 则标识向量M2和M1之间的关系 可用下述等式描述 M2 M1 C j C j表示矩阵C的第j列向量 状态方程 若M0 M 则标识向量M0和M之间的关系为 M M0 C U Petri网的状态方程其中 U是PN的T 向量 对于ti T U ti 对应于ti在 中出现的次数 称为迁移的引发向量 37 3 状态方程 不变量 38 3 状态方程 不变量 从关联矩阵和状态方程角度 Petri网的迁移使能条件和引发规则有如下形式 迁移的使能条件III 对于容量无限Petri网PN N M0 M tj iff pi P Cij M pi 或者C j M 其中 C j表示矩阵C 的第j列 迁移的引发规则III 对于Petri网PN N M0 在M下使能迁移tj的引发 产生新的标识M M M C E其中 E是第j个元素为1的单位列向量 39 3 状态方程 不变量 状态方程为部分解决可达性分析问题提供了一个依据 对于Petri网PN N M0 若Md从M0可达 即Md R M0 则Md 0 且必存在迁移引发序列 t1t2 tl 依次引发这些迁移后 标识从M0变成Md 令uk是第k个元素为1 其余元素为0的引发向量 代入 M Md M0 C X 跌代l次可得 X 0X中各元素即为所对应迁移的引发次数 亦即 方程 M Md M0 C X必然存在一个非负整数解 该解即为迁移引发次数向量 40 3 状态方程 不变量 S 不变量 S invariant 设I为PN的S 向量 C是PN的关联矩阵 若CT I 0 就称I为PN的S 不变量 PI p P I p 0 称为I的支撑集 若I 0 就称I为非负S 不变量 PN中有某几个位置中包含的令牌个数之总和在任何可达标识下都不变 T 不变量 T invariant 设J为PN的T 向量 C是PN的关联矩阵 若C J 0 就称J为PN的T 不变量 PJ t T J t 0 称为J的支撑集 若J 0 就称J为非负T 不变量 PN中有某几个迁移的引发 会使得Petri网的标识向量恢复到先前的状态 41 3 状态方程 不变量 图中的Petri网 在任何情况下 所有位置中包含的令牌总数始终为1 从而得到该Petri网的S 不变量 111 T 同时 迁移t1 t2各引发一次 Petri网的状态从M返回到M 则t1 t2是该Petri网的一个T 不变量 类似地 迁移t3 t4各引发一次 Petri网的状态从M返回到M 迁移t1 t2 t3 t4各引发一次 Petri网的状态也从M返回到M 因此 该Petri网有如下三个T 不变量 1100 T 0011 T 1111 T 基于状态方程以及T 不变量和S 不变量 可以对Petri网的一些结构性质进行分析 四 Petri网规格的例 1 哲学家就餐问题五位哲学家pi i 0 1 2 3 4 围圆桌而坐 pi和pi 1 p5 p0 共享餐叉fi 已知pi用餐时需同时占有fi和fi 1两把叉子 f4 f0 1 该问题中 每一位哲学家pi共有三种可能的状态 饥饿状态hi 等待资源 用餐状态ei 使用资源 思考问题ki 无需资源 状态之间通过事件获得资源ti1 事件释放资源ti2和事件请求资源ti3联系在一起 用位置 迁移分别表示相应的状态和事件 可以得到哲学家pi的Petri网模型规约 图中位置pi标记有1个令牌表示 哲学家pi的正在思考问题 fi和fi 1两把叉子均未被占用 将五位哲学家的行为均用Petri网模型规格 并通过它们之间的资源 叉子 共享关系联系起来 便可以得到整个问题的Petri网规格 四 Petri网规格的例 2 生产者 消费者问题生产者 消费者系统包含一个生产者和一个消费者 生产者进程产生消息 并把产生的消息写入一个能容纳两个消息的缓存区中 生产者在进行 生产 动作后 状态由P1转变为P2 而在 写 动作后 状态由P2恢复为P1 消费者进程能读取消息 并把消息从