基于Petri网的并行测试资源调度建模与验证

　　1　Petri网的相关知识

　　1.1　Petri网的二元特性

　　在进行系统设计时,识别和分离被动元素(例如条件或状态)与主动元素(例如动作或事件)是非常重要的一步, Petri网对这种二元性提供了强有力的支持。Petri网分别用P(place,库所)元素和T( transi-tion,变迁)元素来表示被动元素和主动元素,它们各自组成的集合是不相交的。将现实世界中的实体解释为被动元素时,由P元素表示(例如 发生条件、资源、地点、等待队列和信道等);将现实世界中的实体解释为主动元素时,由T元素表示(例如事件、变迁、动作、语句的执行和消息的发送/接收 等)。

　　1.2　Petri网的图形表示特征

　　P元素用圆形符号(如圆圈、椭圆等)表示,T元素用方形符号(如方框、粗杠等)表示,元素之间的关系用弧(arc)表示,托肯(token)是 条件满足或状态转移的标志,用黑点表示。对于网的每个图形都有一个包含相同信息的代数表达式,其中包含库所集合、变迁集合和连接弧集合等。

　　1.3　时延Petri网(TdPN)

　　时延Petri网是Petri网在时间控制方面的扩展,其对于时间的处理可以看成是一种特殊的优先级处理。在含有冲突的实例中,具有最早发生时间的那个事件将会发生,而只有互为冲突的事件的发生时间完全相同时,才会产生一个真正的冲突。

　　2　并行测试资源调度的Petri网建模

　　利用Petri网进行系统建模的方法主要有3种:面向状态的方法,面向事件的方法和面向对象的方法。结合并行测试资源调度的特点,本文采用面向状态的方法。

　　2.1　建模背景

　　假设在某个并行自动测试系统中,有2个UUT需要测试,如表1所示。UUT1和UUT2各有3个待测参数;R1、R2、R3分别是完成测试所需 的3个资源,如测试设备等;括号里面的数字是该UUT的某个参数在某一设备上完成测试所需要的时间。例如,R1(4τ) /R3(6τ)表示UUT2的第2个参数测试可以调用资源R1或R3来完成,如果调用R1就需要花费4个单位的时间,如果调用R3就需要花费6个单位的时 间。在自动测试中,经常出现后一个参数的测试过程中需要前一个参数测试的结果,即参数测试顺序不能改变。所以,在本例中假定在同一个UUT测试中,参数测 试的顺序不能更换,即必须先完成参数1的测试才能进行参数2的测试。

　　2.2　建立模型

　　时延Petri网中又分为变迁时延Petri网和库所时延Petri网,前者能够明确地区分系统的状态与动作,适合于工程应用;后者是对前者的 一种演变,在进行空间状态分析时更加合理。本文侧重于工程应用,所以采用了变迁时延Petri网作为建模工具。确立了系统的状态变化(即Petri网的库 所之间的联系)之后,从状态之间的时态依赖关系入手,建立了本文2.1中描述的并行测试资源调度的Petri网模型(如图1所示),其中,库所和变迁的含 义如表2所示。