部分Petri网的基本概念

,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第一部分,Petri,网的基本概念,提纲,网与网系统,库所,/,变迁系统与加权,Petri,网,并发与冲突,网与网系统,Petri,网是一种网状信息流模型，包括库所和变迁两类节点，同时在库所集上添加表示状态信息的托肯分布（标识）,库所表示条件、资源、等待队列和信道等,变迁表示事件、动作、语句执行和消息发送,/,接受等,一个变迁（事件）有一定数量的输入和输出库所，分别代表事件的前置条件和后置条件,库所中的托肯代表可以使用的资源数量或数据,Petri,网按引发规则使得事件驱动状态的演变，从而反映系统动态运行过程,网与网系统,p,1,p,2,t,1,t,2,c,1,c,2,t,3,t,4,B,例：,网,N,1,=(P,1,T,1,; F,1,),，其中,P,1,= p,1, p,2, c,1, c,2, B,T,1,=t,1, t,2, t,3, t,4,F,1,=(p,1, t,1,),(t,1, p,2,),网与网系统,定义,1.1.,三元组,N=(P,T;F),称作,网,当且仅当：,（,1,）,P,T,P,T,=,;,（,2,）,F,(,P,T),(,T,P,);,（,3,）,dom(F),cod,(F)=P,T,其中，,dom,(F)=x P,T,| yP,T,: (x, y) F,cod(F) =x P,T,| yP,T,: (y, x) F,这里，,P,表示库所（,Place,）集合,T,表示变迁（,Transition,）集合,F,是网的流关系（,Flow,）,网与网系统,定义,1.2.,设,N=(P,T;F),为一个网，对,xP,T,，令,x = y | yP,T,(y, x)F,x,= y | yP,T,(x, y)F,称,x,为,x,的,前集,或输入集，,x,为,x,的,后集,或输出集。称,x,x,为元素,x,的,外延,。,一个库所的外延是变迁集,T,的一个子集,一个变迁的外延是库所集,P,的一个子集,网与网系统,例：,网,N,1,=(P,1,T,1,;F,1,),，其中,t,2,= p,2,t,2,= p,1, B,p,1,p,2,t,1,t,2,c,1,c,2,t,3,t,4,B,网与网系统,定义,1.3.,设,N=(P,T;F),为一个网,（,1,）若对,xP,T,，,x,x,=,，则称,N,为一个,纯网,（,pure net,）。,（,2,）若,对,x, yP,T,，,(,x=,y),(x,=y,) ,x=y,，则称,N,为一个,简单网,（,simple net,）。,（,3,）若,pP,，,|,p|=|p,|=1,，则称,N,为一个,T-,图,（,T-Graph,）或,标识图,（,marked graph,）。,（,4,）若, t,T,，,|,t|=|t,|=1,，则称,N,为一个,S-,图,（,S-Graph,）或,状态机,（,state machine,）。,（,5,）若,t,1,t,2,T (t,1,t,2,),t,1,t,2, |,t,1,|=|,t,2,|=1,，则称,N,为一个,自由选择网,（,free-choice net,）。,（,6,）若,t,1,t,2,T (t,1,t,2,),t,1,t,2,t,1,=,t,2,，则称,N,为一个,扩充的自由选择网,（,extended free-choice net,）。,网与网系统,定义,1.4.,四元组,PN=(P,T;F,M,0,),称作,Petri,网（网系统）,当且仅当,（,1,）,N=(P,T;F),为一个网；,（,2,）映射,M:P,0,1,2,(,非负整数集,),称为网,N,的一个,标识,，其中，,M,0,是,初始标识；,（,3,）引发规则：,（,3.1,）变迁,t,T,称为,使能的,当且仅当：, p,t,：,M(p)1,，记作,Mt;,（,3.2,）在,M,下使能的变迁,t,可以引发，引发后得到一个新的标识,M,，记作,MtM,对,p,P,，有,网与网系统,p,1,p,2,t,1,t,2,c,1,c,2,t,3,t,4,B,p,1,p,2,t,1,t,2,p,3,p,1,p,2,t,1,t,2,p,3,一个网系统的全部可能的运行情况由它的基网,N,和初始标识,M,0,完全确定。,因此，给出了基网和初始标识，也就唯一确定了一个网系统,M,01,=1,0,0,M,02,=0,1,0,提纲,网与网系统,库所,/,变迁系统与加权,Petri,网,并发与冲突,库所,/,变迁系统与加权,Petri,网,库所,/,变迁系统（简称,P/T,系统）是在定义,1.4,的,Petri,网基础上增加两个函数得到的,库所集上的容量函数,有向边上的权函数,增加这两个函数的目的是使得对某些实际系统建模显得方便,库所,/,变迁系统与加权,Petri,网,定义,1.5.,六元组,=(P,T;F,K,W,M,0,),称作,一个,库所,/,变迁网系统,，其中,（,1,）,N=(P,T;F),为一个网；,（,2,）,W: F,1,2,(,正整数集,),称为权函数；,（,3,）,K: P,1,2,(,正整数集,),称为容量函数；,（,4,）,M: P,0,1,2,是一个标识，满足,p,P,：,M(p)K(p),其中，,M,0,是初始标识；,（,5,）引发规则：,（,5.1,）对于,t,T,，,Mt,的引发条件,（,5.2,）若,MtM,对,p,P,，有,t,H,2,O,2,2,2,例：化学反应的,P/T,系统,H,2,O,库所,/,变迁系统与加权,Petri,网,p,1,p,2,t,1,t,2,c,1,c,2,t,3,t,4,B,定义,1.4,的,Petri,网,P/T,系统,p,1,p,2,t,1,t,2,c,1,c,2,t,3,t,4,B,1,t,2,无法引发,库所,/,变迁系统与加权,Petri,网,对于一个库所,/,变迁系统,=(P,T;F,K,W,M,0,),，若规定, p,P,：,K(p)=, f,F,：,W(f)=1,那么，就变成形如定义,1.4,给出的网系统（,原型,Petri,网,）,对于一个,P/T,系统，如果规定各个库所的容量都为无穷大，即取消库所集上的容量函数而保留有向边集上的权函数，就得到一种介于原型,Petri,网和,P/T,系统之间的网系统模型,=(P,T;F,W,M,0,),，称这种模型为,加权,Petri,网,（,weighted Petri net,）,P/T,系统并不比原型,Petri,网具有更强的模拟能力，凡是可以用,P/T,系统对其建模的实际系统，也可以用原型,Petri,网对其建模。每一个,P/T,系统都可以转换为一个行为等效的,Petri,网,库所,/,变迁系统与加权,Petri,网,K(p)=2,p,容量限制,p,t,t,权函数,p,2,p,t,2,p,等价的原型,Petri,网,p,t,提纲,网与网系统,库所,/,变迁系统与加权,Petri,网,并发与冲突,并发与冲突,定义,1.6.,设,PN=(P,T;F,M,0,),是一个,Petri,网，,t,1,和,t,2,是,PN,中的两个变迁。如果,PN,的一个标识,M,使得,Mt,1,且,Mt,2,，那么若,Mt,1,M,1, M,1,t,2,且,Mt,2,M,2, M,2,t,1,则称,t,1,和,t,2,在,M,并发,，记为,Mt,1,t,2,。,如果两个事件（变迁）在某状态下都有发生权，而且其中任何一个的发生,都不会使另一个失去发生权，则称这两个事件在该状态下处于并发,并发不能简单地理解为,“,同时发生,”,，而是指事件之间因果上的无依赖性。,按网论的观点，事件的发生只依赖于它们的外延，而与全局情况无关,并发与冲突,定义,1.7.,设,PN=(P,T;F,M,0,),是一个,Petri,网，,t,1,和,t,2,是,PN,中的两个变迁。如果,PN,的一个标识,M,使得,（,1,）,Mt,1,但,Mt,2,；,（,2,）,Mt,1,M,1, M,1,t,2,则称,t,1,和,t,2,存在,顺序关系,。,p,1,p,2,t,1,t,2,p,4,p,6,p,5,t,3,t,4,p,3,p,0,t,0,t,5,并发与冲突,定义,1.8.,设,PN=(P,T;F,M,0,),是一个,Petri,网，,t,1,和,t,2,是,PN,中的两个变迁。如果,PN,的一个标识,M,使得,Mt,1,且,Mt,2,，那么若,Mt,1,M,1, M,1,t,2,且,Mt,2,M,2, M,2,t,1,则称,t,1,和,t,2,在,M,冲突,。,冲突关系描述了系统的非确定性：在某情况下有两个（或多个）事件都有权发生，但在实际运行过程中，只有一个能真正发生。系统存在冲突之处，正是外界环境可以对其施加控制（加以选择）之处。,并发与冲突,t,2,t,1,t,3,t,4,p,1,p,2,p,3,t,3,和,t,4,并发,t,2,t,1,t,3,t,4,p,1,p,2,p,3,t,1,和,t,2,冲突,并发和冲突的示例,t,2,t,1,t,3,t,4,p,1,p,2,p,3,控制装置,t,2,t,1,p,1,p,2,p,3,p,4,p,5,t,1,和,t,2,不是冲突，而是并发关系,并发与冲突,混惑的示例,t,2,t,1,t,3,p,1,p,2,p,3,p,4,p,5,t,2,t,1,t,3,p,1,p,2,p,3,p,4,p,5,存在混惑的网系统不是好的系统模型，因为在这种网系统的运行中，冲突是否出现无法确定，不便于对系统施加外部控制，在建立实际系统的,Petri,网模型时，应尽量避免出现混惑。,混惑,同时存在并发和冲突，但由于并发事件中的某些事件的发生，会使冲突自动消失，如（,1,）所示。,系统在某些状态下存在并发，并发事件中不同事件的发生，使得系统可能存在冲突，也可能不出现冲突，如（,2,）所示。,