郑州网站建设 易云互联,网页设置,手机网站打开微信号,WordPress高级版破解Petri网 Petri网是提出比较早且研究最好的可用于并发建模的流程建模语言。尽管图形表示法直观且简单#xff0c;但是Petri网是可执行的#xff0c;可以使用许多分析技术对其进行分析。Petri网是由库所#xff08;place#xff09;和变迁#xff08;transition#xff09;…Petri网 Petri网是提出比较早且研究最好的可用于并发建模的流程建模语言。尽管图形表示法直观且简单但是Petri网是可执行的可以使用许多分析技术对其进行分析。Petri网是由库所place和变迁transition组成的二分图bipartite。网络结构是静态的但是在触发规则firing rule的控制下托肯token可以流经网络。 Petri网的状态由托肯在各库所的分布确定并称为其标记marking。下图所示的初始标记中只有一个托肯start是唯一标记的库所。 图2 与图1对应的Petri网 下面给出Petri网的形式化定义 定义2Petri网 一个Petri网是一个三元组N (PTF)其中P是库所的有限集合T是变迁的有限集合并且P ∩T∅F⊆(P×T)∪(T×P)是有向弧的集合称为流关系flow relation。一个标记Petri网以(NM)对表示其中N (PTF)是一个Petri网M∈(P)是一个定义在P上的多重集表示该网络的标记marking。标记Petri网的所有标记的集合记为。 上图Petri网可以形式化描述为: P {start,c1,c2,c3, c4,c5, end}, T {a,b,c,d,e,f,g,h}, and F {(start,a),(a,c1),(a,c2),(c1,b),(c1,c), (c2,d), (b,c3), (c,c3), (d,c4), (c3,e), (c4,e), (e,c5), (c5,f), (f,c1),(f,c2),(c5,g),(c5,h),(g, end),(h, end)}。 上述所示的标记是[start]即仅包含一个托肯的多重集。这样标记的Petri网的动态行为由所谓的触发规则定义。 如果其每个输入扩所都包含一个标记则变迁可以使能enabled。使能的变迁会触发时每个输入库所消耗一个托肯并为每个输出库所产生一个托肯。 因此在标记[start]时使能了变迁a。 触发会产生标记[c1c2]。注意消耗了一个托肯并生成了两个托肯。 在标记[c1c2]时变迁a无法使能。但是变迁b、c和d可以使能。从标记[c1c2]开始触发b将导出标记[c2c3]。 此时d仍处于使能状态但b和c则不是。由于涉及f的循环构造因此有无数个从[start]开始标记到[end]结束标记的触发序列。注意这里使能指变迁的状态触发指变迁的发生 下面给出触发规则的形式化定义以描述Petri网的动态特征。 首先给出Petri网中结点的前集和后集的概念 结点的前集记为••{|(, )∈F}即所有指向的入结点的集合。 结点的后集记为••{|(, )∈F}即所有从指出的结点的结合。 定义3触发规则 令(NM)是一个网结构为N (PTF)标记为M∈(P)的标记Petri网。变迁t∈T可以使能记为(NM)[t当前仅当•t≤M这里集合之间的比较可以认为•t包含于M中。触发规则_[__⊆×T×是满足任何(NM)∈和任何t∈T的最小关系(NM)[t⇒(NM)[t (NM \•t∪t•。\是减集合符号 (NM)[t表示在标记M处t是使能的例如图中的(N[start])[aa是使能的。(NM)[t(NM’)表示触发此使能的变迁会导致标记M’。例如(N[start])[a(N[c1c2])和(N[c3c4])[e(N[c5])。 令N(PTF)的(NM0)为标记Petri网。当且仅当对于某个自然数n∈N存在标记M1…Mn且变迁t1…tn∈T时序列σ∈T∗称为(NM0)的触发序列使得σ t1 … tn并且对于所有0≤n的(NM)[t1和(NM)[t 1(NM1)。比如上图一个可能的触发序列σ a,c,d,e,f,b,d,e,g 。 标记M为可达的reachable当且仅当存在一个变迁序列σ使得(NM0)[σ(NM)。 可以为Petri网的变迁定义标签函数称为标签Petri网 定义4标签Petri网 一个标签Petri网是一个五元组N(P, T, F, A, )其中A⊆是活动标签的集合∈T→A是一个标签函数。 理论上多个不同的变迁可以使用相同的标签。可以把变迁标签看做可观测活动observable action。可以需要表示一种不可观察的特殊的标签通常保留标签τ一个变迁t的(t)τ该变迁是不可观测的这样的变迁称为沉默silent变迁或者隐形invisible变迁。显然很容易将一个Petri网转换为一个标签Petri网只需要对每个t∈T应用(t)t然而反过来却不一定能进行转换因为可能存在多个变迁拥有同一个标签。同样可以将一个标签Petri网转换为一个变迁系统为此首先介绍可达图的概念。 定义5可达图 令(N,M0)是一个带初始标记的标签Petri网其中N(P, T, F, A, )。从(N,M0)可以导出一个变迁系统TS(SA’T’)其中S[N,M0Sstart{M0}A’AT’{(M,(t),M’)∈S×A×S|∃t∈T(N,M)[t(N,M’)}。这个TS通常也被称为(N,M0)的可达图Reachability Graph PS 吴哲辉的《Petri网导论》中称为可达标识图可以说是一个东西且这里给出求可达标识图的算法。 图3给出了图2对应的可达图
图3 从图2导出的变迁系统 Petri网并没有明确给出一个终点标记Send的集合。然而在上图的例子中可以得到Send {[end]}。之后我们会学习到Petri网判断死活和活锁的能力。 需要注意的是一个Petri网的变迁可能可以对应相应变迁系统的多个变迁毕竟一个变迁的触发可能可以到不同的标志。如果一个标记Petri网包含比较多的并发结果或者一个库所存在多个托肯则转换成的变迁系统可能很大且复杂。实际上Petri网可能有无限多个可达标记状态这个Petri网不是有界的下面将介绍有界性等概念于是对应的变迁系统也将存在无限个状态PS 这是不可可视化表达的需要用可覆盖性树表出详细见吴哲辉《Petri网导论》。可见使用变迁系统的局限性之大。
图4 一个标记Petri网对应的变迁系统高达6 57776个状态 通过构建可达图如果可能或可覆盖性树人们可以回答有关流程模型行为的各种问题。此外专用的分析技术还可以在不构造状态空间的情况下回答特定问题例如使用Petri网的线性代数表示PS 还是吴哲辉的《Petri网导论》。下面列出了通常在标记Petri网的情况下进行研究的一些通用属性 •k-有界的k-bounded一个标记Petri网(N,M0)是k-有界的当且仅当在任何可达标志状态下没有一个库所的托肯数量会超过k。形式化描述为∀p∈P和M∈(N,M0)有M(p)≤k。 •安全性safe一个标记Petri网是安全的当且仅当它是1-有界的。 •有界性bounded一个标记Petri网是有界的当且仅当存在k∈ℕ使得它是k-有界的。 •无死锁deadlock free一个标记Petri网(N,M0)是无死锁的如果在每个可达标记中都至少有一个变迁是使能的。形式化描述为∀M∈(N,M0)∃t∈T且(N,M)[t。 •活性live一个标记Petri网(N,M0)中的变迁t∈T是活的如果对网中的每一个可达标记t都有可能可以使能。形式化描述为∀M∈(N,M0)∃M’属于[N,M且(N,M’)[t。一个标记Petri网是活的若果网中每一个变迁都是活的。需要注意的是无死锁Petri网并不一定要求是活的活性是更严格的PS 活性是每个状态下每个t都有机会使能无死锁是只要每个状态下都能保证走到终点就好。 Petri网是获得大量理论研究并且可以很好表示并发结构的工具PS 其实Petri网最近十年来严重降温而过程挖掘则在迅速崛起并且有大量的分析技术和工具存在1。然而这里描述只是简单的模型显然无法表示数据相关和时间相关的内容因此一些高级Petri网已经被提出比如有色Petri网Colored Petri nets CPNs这是一种基于Petri网的且得到相当广泛的研究和应用的形式化方法它能处理数据相关和时间相关的内容层面。CPN中的托肯带有数据值和时间戳 数据值通常称为“颜色”描述了由托肯建模的对象的属性 时间戳指示可以消耗令牌的最早时间变迁可以为产生的令牌分配延迟 这样就可以对等待时间和服务时间进行建模。 CPN可以是分层的即可以将变迁分解为子过程从而可以构建大型模型。 CPN工具是一个工具集为CPN的建模和分析提供支持2。 http://www.informatik.uni-hamburg.de/TGI/PetriNets/index.php ↩︎ www.cpntools.org ↩︎
