一种基于Petri网的自动测试系统死锁预防策略

针对自动测试系统中多任务并行测试复杂,容易出现死锁现象的问题,提出一种基于Petri网的死锁预防策略。首先为自动测试系统建立一个Petri网模型,然后将Petri网的状态方程作为约束条件,求出模型的发射序列即系统中无死锁的任务调度路径。Petri网的发射序列求解一直是NP问题,

一种基于Petri网的自动测试系统死锁预防策略1

马敏，陈光礻禹

电子科技大学自动化工程学院，四川成都（610054）

摘 要：针对自动测试系统中多任务并行测试复杂，容易出现死锁现象的问题，提出一种基于Petri网的死锁预防策略。首先为自动测试系统建立一个Petri网模型，然后将Petri网的状态方程作为约束条件，求出模型的发射序列即系统中无死锁的任务调度路径。Petri网的发射序列求解一直是NP问题，针对这种情况，引入遗传算法对可行解空间进行搜索。

关键词：自动测试系统，并行测试，死锁，Petri网，遗传算法 中图分类号：TP202

1 引 言

随着自动测试系统的发展，多任务并行测试技术越来越受到广泛的应用。自动测试系统在同一时间完成多项测试任务，需要对被测任务和测试资源进行合理的调度，否则很容易发生死锁现象[1]。一旦发生死锁现象，系统就无法正常工作，因此死锁一直都是系统设计者在组建系统之前，必须考虑避免的现象。

Petri网是Petri博士于1962年提出的一种系统描述和分析的形式化建模工具。它作为一种数学方法，在离散事件系统建模、分析、性能评价和控制设计中得到广泛的应用，而且它能模拟系统的并发和冲突行为，反映系统的动态行为，因此经常被用来处理系统死锁问题[2]，也适用于并行自动测试系统。同样Petri网技术也已经应用到测试领域，文献[3]就是运用Petri 网来进行测试仪器特性描述。基于这种情况，本文提出一种基于Petri网的自动测试系统死锁预防策略，并结合遗传算法搜索可行解。

2 基于Petri网的自动测试系统死锁描述

2.1 Petri网基本原理

Petri网（Timed Transition Petri Net）定义为以下5元组：

PN={P，T，I，O，M0}此处：P={p1,...,pn}是库所的有限集合，n>0为库所的个数；

T={t1,...,tm}是变迁的有限集合，m>0为变迁的个数，并要求PIT=Φ；I:P×T→N是输

入函数，N={0,1,...}为非负整数集；O:T×P→N是输出函数；M0是Petri网的初始状态。

2.2系统的Petri网模型

首先为支持多任务并行测试的自动测试系统建立一个Petri网模型，描述系统的结构与性能。

建立自动测试系统Petri网模型的步骤如下：

1) 根据库所和变迁的定义以及测试实施的过程，确定自动测试系统的库所集和变迁集。 2) 确定库所和变迁之间的关系，得到自动测试系统初始Petri模型。

3) 根据Petri网的基本规则和实际系统的状况，确定Petri模型的初始状态，即初始状态下的托肯数 (token)，得到最终的Petri网模型。

自动测试系统Petri网模型中的库所可以分为三类，分别是操作库所，资源库所和闲置

1

本课题得到教育部博士点基金（20030614006）的资助。

针对自动测试系统中多任务并行测试复杂,容易出现死锁现象的问题,提出一种基于Petri网的死锁预防策略。首先为自动测试系统建立一个Petri网模型,然后将Petri网的状态方程作为约束条件,求出模型的发射序列即系统中无死锁的任务调度路径。Petri网的发射序列求解一直是NP问题,

库所。其中操作库所代表被测件的某一个参数的测试过程；资源库所代表测试过程中用到的测试资源，如测试仪器，计算机等；闲置库所代表测试过程的开始和结束状态。Petri网模型中的变迁表示测试进行的过程，也可以反映测试子任务调度的路径，本文中将每个参数的测试看作一项子任务。例如：有两个测试任务J1，J2需要并行完成，每个测试任务需要完成三个参数的测试，故分解为三个子任务，三个子任务按顺序完成后，该测试任务结束，而且每个参数测试需要一定的测试仪器如m1,m2,m3。如表1 所示：

表1 一个并行测试的例子 待测参数 J1 J2 参数1 参数2 参数3

m1

m2 m3

m2m1m3

根据上述模型建立的规则，可以得到这两个测试任务并行完成的Petri网模型，如图1所示：

JP6

JJ2

P6

t5t5

P7t6

P7t6

P8

P8

t7P9

t7P9

t8P10

t8P10

图1 并行测试的系统Petri网模型 图2 系统死锁的Petri网描述

在该模型中，p1, p6表示两个测试任务的开始，p5,p10表示两个测试任务的结束，它们为闲置库所；p2,p3,p4表示测试任务J1中三个参数的测试过程，p7,p8,p9表示测试任务

J2中三个参数的测试过程，它们为操作库所；m1,m2,m3是资源库所。模型中的变迁t1,t2...,t8

表示每个子任务的开始与结束。m1,m2,m3中的托肯表示有三种资源可用，某一个子任务完成后，资源被释放给下一个子任务；p1, p6中的托肯表示等待测试的两个任务。

2.3系统死锁的描述

所谓死锁是指多任务在运行中为了竞争资源陷入了一个僵局。一个任务锁定了另一个任务所需要的资源，而另一个任务又锁定了这个任务所需资源，两个任务都在等待对方释放资源，这就形成了一个死循环。支持并行测试的自动测试系统可能会在运行中出现死锁的情况。例如表1 所举的例子，测试任务J1在完成了参数1的测试后会锁定资源m1，等待测试任务J2释放m2，而J2会锁定m2等待J1释放m1。这种死锁现象可用如图2的Petri网模型表示。出现了死锁现象，系统就无法继续正常运行。

针对自动测试系统中多任务并行测试复杂,容易出现死锁现象的问题,提出一种基于Petri网的死锁预防策略。首先为自动测试系统建立一个Petri网模型,然后将Petri网的状态方程作为约束条件,求出模型的发射序列即系统中无死锁的任务调度路径。Petri网的发射序列求解一直是NP问题,

一般情况下，如果在Petri网可达树中各变迁至少引发了一次，没有从不引发的变迁，对于Petri网模型的终止标识Mf(Mf∈R(M0))必然有一条从M0到Mf的变迁路径：

σ:M0(σ>Mf，即该Petri网是活的，不会有死锁发生。基于这种理论，人们研究了很多方

法来预防死锁的发生。如Viswanadham[4]等人提出搜索系统可达标识图，去除会使死锁发生的变迁来避免死锁，但这种方法搜索步数很难确定，不易实施。而Mu Der Jeng[5]提出了一种利用启发式搜索算法，搜索系统的局部可达标识图，剔出死锁标识来得到系统可行的变迁发这种方法利用启发式信息减小了搜索空间，可以快速的找到没有死锁发生的变迁射序列σ。

发射序列。但是随着Petri网的复杂化，会发生“状态空间爆炸”问题，遇到这种情况即使是局部可达标识图都很难生成。鉴于这种情况，可引入遗传算法这种有效的全局搜索算法，对Petri网模型的变迁序列进行搜索，得到无死锁的发射序列σ。它比启发式搜索具有更高的搜索效率。

3 基于遗传算法的发射序列求解

3.1 Petri网的发射序列

Petri 网的状态方程为：

Mk=Mk 1+CVk (1)

其中C是Petri网的关联矩阵，Vk是发射序列σ中第k个发射向量。每个发射向量必须满足的变迁发射条件是：C=C+ C ，Mk 1>C Vk。假设初始状态标识M0通过发射序列σ到达终止状态标识Mf，那么Petri网的状态方程可以写为：

Mf=M0+CVk …… 此处隐藏：7878字，全部文档内容请下载后查看。喜欢就下载吧 ……