一种基于Petri网和AGA算法的测试系统死锁预防策略  

Test system deadlock-prevention method based on Petri net and genetic algorithm

作　　者：马敏[1] 黄建国[1] 夏侯士戟[1] 

机构地区：[1]电子科技大学自动化工程学院,成都610054

出　　处：《仪器仪表学报》2008年第1期33-37,共5页Chinese Journal of Scientific Instrument

基　　金：国家自然科学基金(60674077;60673011);总装备部预研基金(9140A16060406DZ0213);校青年基金(JX0635)资助项目

摘　　要：在自动测试系统中,很多任务需要并行测试。测试过程比串行测试复杂,较容易出现死锁现象,因此提出一种基于Pe-tri网和自适应遗传算法(adaptive genetic algorithm)的死锁预防策略。在该策略中,首先为自动测试系统建立一个Petri网模型,然后将Petri网的状态方程作为约束条件,最后求出模型的发射序列即系统中无死锁的任务调度路径。Petri网的发射序列求解一直是NP问题,针对这种情况,引入自适应遗传算法对可行解空间进行全面的搜索,可得到所有无死锁的路径。最后,通过雷达接收机的并行测试例子,和启发式算法搜索进行对比,进一步体现了该死锁预防策略的优越性。In automatic test system （ATS）, many test tasks need parallel test. Parallel test process is more complex than series test. Deadlock often happens, so a new method based on Petri net and adaptive genetic algorithm is used to prevent deadlock. In the method, a Petri net model of ATS is set up at first. Then the state equation of Petri net model is used as the constraint to find the firing sequence without deadlock. The firing sequence of the Petri net is also the task scheduling sequence without deadlock of ATS. Because it is a NP difficult problem, adaptive genetic algorithm （AGA） is used to search all the deadlock-free sequences. At last, a radar receiver parallel test is used to prove that AGA is superior to Heuristic algorithm in the test.

关 键 词：自动测试系统 并行测试 死锁 PETRI网 自适应遗传算法 

分 类 号：TP202[自动化与计算机技术—检测技术与自动化装置]