《网的基本概念》PPT课件.ppt

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