高级软件工程(第5章：形式化开发方法-2建模实例)课件.ppt

5. 3 Petri网建模实例,Petri网的作用：是系统建模与性能分析的良好工具 Petri网适用于：具有并发、异步、分布、并行、 不确定性和随机性的系统建模 下面运用上一节给出的Petri网的基本原理对几个典型系统的建模实例进行讨论一、有限状态机 例：一个自动面包售货机Petri网模型，系统需求： 1可接收硬币：0.5元和1.0元 2销售价格：1.5和2.0元 3售货机的最大硬币存储量为2.0元 此售货机的状态图可用如下Petri网表示：,例：1.5=1.0+0.5,例：1.5=1.0+0.5,,,取1.5元面包转移发生,其中： 1 位置代表售货机（自动机）的状态 如：5个位置分别代表5种硬币投放状态（p1放置一个标 记作为Petri网的初始标识，表示售货机最初硬币存 储量为0元） 2转移标记，如“投1元”，代表转向条件 令：M为转移条件标记 N为当前状态位置标记 则转移M发生时所达到的新位置的标记： N=N+M 说明： 1如果一个Petri网是状态机，则Petri网中的每个转移t 恰有一条输入弧和一条输出弧 2任何一个有限状态机都可以用Petri网来模拟。

其中: a：投0.5元 b：投1.0元 c：取1.5元面包 d：取2元面包,此售货机的状态图也可用如下DFA表示：,二、并行活动 例：一个具有并行活动或并发性的Petri网,说明： 1在Petri网中，两个转移称为并发(concurrent)，仅 当它们在因果关系上是独立的，即一个转移可以 先于、后于或同时于另一个转移2. 并发可以看做是基于事件集合A=e1，e2，e3，上 的一种二元关系co，并满足： 1) 自反的: (ei co ei) 2) 对称的: (e1 co e2)== (e2 co e1) 3) 非传递的: (e1 co e2)(e2 co e3) == (e1 co e3) 例：e1：开车（可以开车） e2：唱歌（某人在唱歌） e3：步行（可以步行） 显然：(e1 co e2)(e2 co e3) == (e1 co e3),三、数据流计算 例：一个数据流计算的Petri网,,说明: 1.Petri网不仅可以表示控制流，也可以表示数据流 2.数据流计算机是一种计算装置，当其操作数到达 时，其指令执行可发生，并可并发执行例如：t1 和 t2发生,t4,t5,例如：t3发生,t5,例如：t4发生,四、通信协议 例：一个通信协议的Petri网模型,,其中：1该Petri网描述了一种最简单的通信协议,2协议：规范的规则,“发送消息”发生,“接收消息”发生,“发送应答”发生,“接收应答”发生,tA,tB,tA 、tB发生,五、同步控制 说明：一个在多处理器或分布式处理系统中，有些资 源和信息要被几个处理器所共享。

为保证整个系 统的正确运行，这种共享必须是可控制的或同步 的 Petri网可用来模拟多种同步机制 例：一个读者写者系统的Petri网模型,,其中：1P1：表示进程处于“就绪”状态 P2：表示进程正在读（成为读进程） P3：表示资源允许进程访问 P4：表示进程正在写（成为写进程） K：代表位置标记数和边上的权 2读进程最多可有K个且可以并发地读，写进程只能有 一个，当写进程发生时，读进程不能发生k-1,一个读进程正在读，此时不能够写k-1,,,一个写进程正在写，此时不能够读且不能有第二个写进程进行写六、生产者/消费者系统,例：一个简单的生产者/消费者系统的Petri网描述,,其中：p1---生产者处于就绪 p2---生产者正在生产产品 p3---仓库 p4---消费者处于就绪 p5---消费者正在消费产品,七、形式语言 方式：若将Petri网的每个t均标上一个符号，则t的启动序 列将识别（产生）一个符号串例：识别（产生）字符串 aabbcc 的过程如下：,,,产生字符串:a,产生字符串:aa,,,产生字符串:aab,,产生字符串:aabb,,产生字符串:aabbc,产生字符串:aabbcc,其中： 启动序列集：TL=| M0Mf =an bn cn | n =0 =L(M0) 说明： 1由Petri网描述的语言称Petri网语言 2Petri网可以描述的语言有：正则语言、前 后文无关和有关语言。

八、机械加工 例：一个简单的工件加工系统的Petri网模型,,其中 ： 1若将工件视为作业（或数据），该图将成为一个简 单计算机系统的Petri网表示 2若考虑对工具的使用，可根据使用方式的不同列举 出如下三种形式的Petri网模型第一种形式：,其中：1.转移t1、t2代表完成相应作业（加工相应数据） ，两个t1、t2公用一个工具 2.两个转移t1、t2不能同时发生，但每个转移都可 以多次发生第二种形式：,其中：t1、t2可以多次发生，但t2必须紧接t1发生,,,第三种形式：,其中：t1、t2各自使用自己的工具,,例：一个多机床、多工人操作的Petri网模型,若有三台不同机床M1、M2、M3和两个操作工人W1、W2 W1可以操作M1和M2，W2可以操作M1和M3，工件分两步进行加工，第一步用机床M1，第二步用机床M2或M3，体现这种加工规则的Petri网模型如图所示t8发生(W2操作M3完),,,,,说明：,对系统用Petri网建模以后，就可以对模型进行特 性分析，以检验实际系统的性能借助Petri网模型 可以研究两类特性：与初始标识有关的特性和与初 始标识无关的特性。

我们称前一类特性为行为特性 (与初始标识相关)，将后一类特性为结构特性(与初 始标识无关),。