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

§5.3Petri网建模实例•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表示：2130aababbcd4a二、并行活动例：一个具有并行活动或并发性的Petri网说明：1．在Petri网中，两个转移称为并发(concurrent)，仅当它们在因果关系上是独立的，即一个转移可以先于、后于或同时于另一个转移。2.并发可以看做是基于事件集合A={e1，e2，e3，…}上的一种二元关系co，并满足：1)自反的:(eicoei)2)对称的:(e1coe2)==(e2coe1)3)非传递的:(e1coe2)∧(e2coe3)=\=(e1coe3)例：e1：开车（可以开车）e2：唱歌（某人在唱歌）e3：步行（可以步行）显然：(e1coe2)∧(e2coe3)=\=(e1coe3)三、数据流计算例：一个数据流计算的Petri网说明:1.Petri网不仅可以表示控制流，也可以表示数据流2.数据流计算机是一种计算装置，当其操作数到达时，其指令执行可发生，并可并发执行。t5t4t3例如：t1和t2发生t3t4t5例如：t3发生t3t4t5例如：t4发生t3t4t5四、通信协议例：一个通信协议的Petri网模型其中：1．该Petri网描述了一种最简单的通信协议A进程B进程发消息应答A进程B进程发消息应答2．协议：规范的规则“发送消息”发生tAtB“接收消息”发生tAtB“发送应答”发生tAtB“接收应答”发生tAtBtA、tB发生tAtB五、同步控制说明：一个在多处理器或分布式处理系统中，有些资源和信息要被几个处理器所共享。为保证整个系统的正确运行，这种共享必须是可控制的或同步的。Petri网可用来模拟多种同步机制例：一个读者／写者系统的Petri网模型其中：1．P1：表示进程处于“就绪”状态P2：表示进程正在读（成为读进程）P3：表示资源允许进程访问P4：表示进程正在写（成为写进程）K：代表位置标记数和边上的权2．读进程最多可有K个且可以并发地读，写进程只能有一个，当写进程发生时，读进程不能发生。k-1k-1k-1一个读进程正在读，此时不能够写。k-1一个写进程正在写，此时不能够读且不能有第二个写进程进行写。六、生产者/消费者系统例：一个简单的生产者/消费者系统的Petri网描述其中：p1---生产者处于就绪p2---生产者正在生产产品p3---仓库p4---消费者处于就绪p5---消费者正在消费产品•七、形式语言方式：若将Petri网的每个t均标上一个符号，则t的启动序列将识别（产生）一个符号串。•例：识别（产生）字符串aabbcc的过程如下：•产生字符串:a•产生字符串:aa1.a再发生2.a发生1.λ发生•产生字符串:aab•产生字符串:aabbb再发生2.b发生1.λ发生•产生字符串:aabbc•产生字符串:aabbccc再发生2.c发生1.λ发生其中：启动序列集：TL={σ|M0[σMf}={anbncn|n=0}=L(M0)说明：1．由Petri网描述的语言称Petri网语言2．Petri网可以描述的语言有：正则语言、前后文无关和有关语言。八、机械加工例：一个简单的工件加工系统的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网模型如图所示。t2发生(W1操作M1)t3发生(W1操作M1完)t8发生(W2操作M3完)说明：对系统用Petri网建模以后，就可以对模型进行特性分析，以检验实际系统的性能。借助Petri网模型可以研究两类特性：与初始标识有关的特性和与初始标识无关的特性。我们称前一类特性为行为特性(与初始标识相关)，将后一类特性为结构特性(与初始标识无关)