《一部分Peti网的基本概念》由会员分享，可在线阅读，更多相关《一部分Peti网的基本概念（22页珍藏版）》请在金锄头文库上搜索。
1、第一部分 Petri网的基本概念提纲网与网系网与网系统n库所所/变迁系迁系统与加与加权Petri网网n并并发与冲突与冲突网与网系统nPetri网是一种网状信息流模型，包括网是一种网状信息流模型，包括库所和所和变迁两迁两类节点，同点，同时在在库所集上添加表示状所集上添加表示状态信息的托肯分布（信息的托肯分布（标识）库所表示条件、所表示条件、资源、等待源、等待队列和信道等列和信道等变迁表示事件、迁表示事件、动作、作、语句句执行和消息行和消息发送送/接受等接受等一个一个变迁（事件）有一定数量的迁（事件）有一定数量的输入和入和输出出库所，分所，分别代表事件的前置代表事件的前置条件和后置条件条件和后置条
2、件库所中的托肯代表可以使用的所中的托肯代表可以使用的资源数量或数据源数量或数据nPetri网按引网按引发规则使得事件使得事件驱动状状态的演的演变，从而反映系，从而反映系统动态运运行行过程程网与网系统p1p2t1t2c1c2t3t4B例：例：网网N1=(P1,T1; F1)，其中，其中 P1 = p1, p2, c1, c2, B T1=t1, t2, t3, t4 F1=(p1, t1),(t1, p2), 网与网系统n定定义1.1. 三元三元组N=(P,T;F)称作称作网网当且当且仅当：当：（1） P T, P T=;（2） F (P T) (T P);（3）dom(F) cod(F)=P
3、T其中，其中， dom(F)=x P T | y P T: (x, y) F cod(F) =x P T | y P T: (y, x) F这里，这里， P表示库所（表示库所（Place）集合）集合 T表示变迁（表示变迁（Transition）集合）集合 F是网的流关系（是网的流关系（Flow）网与网系统n定定义1.2. 设N=(P,T;F)为一个网，一个网，对 x P T，令，令 x = y | y P T (y, x) F x = y | y P T (x, y) F 称称x为x的的前集前集或或输入集，入集， x为x的的后集后集或或输出集。称出集。称x x 为元素元素x的的外延外延。一个库
4、所的外延是变迁集一个库所的外延是变迁集T T的一个子集的一个子集一个变迁的外延是库所集一个变迁的外延是库所集P P的一个子集的一个子集网与网系统例：例：网网N1=(P1,T1;F1)，其中，其中 t2 = p2 t2 = p1, Bp1p2t1t2c1c2t3t4B网与网系统n定定义1.3. 设N=(P,T;F)为一个网一个网（1）若）若对 x P T， x x =，则称，则称N为一个为一个纯网纯网（pure net）。）。（2）若）若对 x, y P T，(x= y) (x =y ) x=y，则称，则称N为一个为一个简简单网单网（simple net）。）。（3）若）若 p P，|p|=|p
5、|=1，则称，则称N为一个为一个T-图图（T-Graph）或）或标标识图识图（marked graph）。）。（4）若）若 t T，|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 ne
6、t）。）。网与网系统n定定义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,对对p P，有，有网与网系统p1p2t1t2c1c2t3
7、t4Bp1p2t1t2p3p1p2t1t2p3一个网系统的全部可能的运行情况由它的基网一个网系统的全部可能的运行情况由它的基网N N和初始标识和初始标识M M0 0完全确定。完全确定。因此，给出了基网和初始标识，也就唯一确定了一个网系统因此，给出了基网和初始标识，也就唯一确定了一个网系统M M0101=1,0,0=1,0,0M M0202=0,1,0=0,1,0提纲n网与网系网与网系统库所所/变迁系迁系统与加与加权Petri网网n并并发与冲突与冲突库所/变迁系统与加权Petri网n库所所/变迁系迁系统（简称称P/T系系统）是在定）是在定义1.4的的Petri网基网基础上增加两个函数得到的上增加
8、两个函数得到的库所集上的容量函数所集上的容量函数有向有向边上的上的权函数函数n增加增加这两个函数的目的是使得两个函数的目的是使得对某些某些实际系系统建模建模显得方便得方便库所/变迁系统与加权Petri网n定义定义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)其中，
9、其中，M0是初始标识；是初始标识；（5）引发规则：）引发规则：（5.1）对于）对于t T，Mt的引发条件的引发条件（5.2）若）若MtM,对对p P，有，有tH2O222例：化学反应的例：化学反应的P/TP/T系统系统H2O 库所/变迁系统与加权Petri网p1p2t1t2c1c2t3t4B定义定义1.41.4的的PetriPetri网网P/TP/T系统系统p1p2t1t2c1c2t3t4B1t t2 2无法引发无法引发库所/变迁系统与加权Petri网n对于一个于一个库所所/变迁系迁系统=(P,T;F,K,W,M0)，若，若规定定 p P：K(p)= f F：W(f)=1那么，就那么，就变成形
10、如定成形如定义1.4给出的网系出的网系统（原型原型Petri网网）n对于一个于一个P/T系系统，如果，如果规定各个定各个库所的容量都所的容量都为无无穷大，即取消大，即取消库所集上所集上的容量函数而保留有向的容量函数而保留有向边集上的集上的权函数，就得到一种介于原型函数，就得到一种介于原型Petri网和网和P/T系系统之之间的网系的网系统模型模型=(P,T;F,W,M0)，称，称这种模型种模型为加加权Petri网网（weighted Petri net）nP/T系系统并不比原型并不比原型Petri网具有更网具有更强的模的模拟能力，凡是可以用能力，凡是可以用P/T系系统对其建模的其建模的实际系系统
11、，也可以用原型，也可以用原型Petri网网对其建模。每一个其建模。每一个P/T系系统都可都可以以转换为一个行一个行为等效的等效的Petri网网库所/变迁系统与加权Petri网K(p)=2p容量限制容量限制ptt权函数权函数p2pt2p等价的原型等价的原型PetriPetri网网pt提纲n网与网系网与网系统n库所所/变迁系迁系统与加与加权Petri网网并并发与冲突与冲突并发与冲突n定定义1.6. 设PN=(P,T;F,M0)是一个是一个Petri网，网， t1和和t2是是PN中的两中的两个个变迁。如果迁。如果PN的一个的一个标识M使得使得Mt1且且Mt2，那么若，那么若 Mt1M1 M1 t2
12、且且 Mt2M2 M2 t1 则称称t1和和t2在在M并并发，记为Mt1 , t2 。u如果两个事件（变迁）在某状态下都有发生权，而且其中任何一个的发生如果两个事件（变迁）在某状态下都有发生权，而且其中任何一个的发生 都不会使另一个失去发生权，则称这两个事件在该状态下处于并发都不会使另一个失去发生权，则称这两个事件在该状态下处于并发u并发不能简单地理解为并发不能简单地理解为“同时发生同时发生”，而是指事件之间因果上的无依赖性。，而是指事件之间因果上的无依赖性。u按网论的观点，事件的发生只依赖于它们的外延，而与全局情况无关按网论的观点，事件的发生只依赖于它们的外延，而与全局情况无关并发与冲突n定
13、定义1.7. 设PN=(P,T;F,M0)是一个是一个Petri网，网， t1和和t2是是PN中的两个中的两个变迁。迁。如果如果PN的一个的一个标识M使得使得 （1）Mt1 但但 Mt2 ； （2）Mt1M1 M1 t2 则称称t1和和t2存在存在顺序关系序关系。p1p2t1t2p4p6p5t3t4p3p0t0t5并发与冲突n定定义1.8. 设PN=(P,T;F,M0)是一个是一个Petri网，网， t1和和t2是是PN中的两中的两个个变迁。如果迁。如果PN的一个的一个标识M使得使得Mt1且且Mt2，那么若，那么若 Mt1M1 M1 t2 且且 Mt2M2 M2 t1 则称称t1和和t2在在M
14、冲突冲突。冲突关系描述了系统的非确定性：在某情况下有两个（或多个）事件都有权冲突关系描述了系统的非确定性：在某情况下有两个（或多个）事件都有权发生，但在实际运行过程中，只有一个能真正发生。系统存在冲突之处，正发生，但在实际运行过程中，只有一个能真正发生。系统存在冲突之处，正是外界环境可以对其施加控制（加以选择）之处。是外界环境可以对其施加控制（加以选择）之处。并发与冲突t2t1t3t4p1p2p3t3和和t4并发并发t2t1t3t4p1p2p3t1 1和和t t2 2冲突冲突并发和冲突的示例并发和冲突的示例t2t1t3t4p1p2p3控制装置控制装置t2t1p1p2p3p4p5t1 1和和t
15、t2 2不是冲突，而是并发关系不是冲突，而是并发关系并发与冲突混惑的示例混惑的示例t2t1t3p1p2p3p4p5t2t1t3p1p2p3p4p5存在混惑的网系统不是好的系统模型，因为在这种网系统的运行中，冲突是否出现无法确定，不便存在混惑的网系统不是好的系统模型，因为在这种网系统的运行中，冲突是否出现无法确定，不便于对系统施加外部控制，在建立实际系统的于对系统施加外部控制，在建立实际系统的PetriPetri网模型时，应尽量避免出现混惑。网模型时，应尽量避免出现混惑。n混惑混惑 同同时存在并存在并发和冲突，但由于并和冲突，但由于并发事件中的某些事件的事件中的某些事件的发生，会使冲突自生，会使冲突自动消失，如（消失，如（1）所）所示。示。 系系统在某些状在某些状态下存在并下存在并发，并，并发事件中不同事件的事件中不同事件的发生，使得系生，使得系统可能存在冲突，也可能可能存在冲突，也可能不出不出现冲突，如（冲突，如（2）所示。）所示。
