Petri网并发进程的死锁避免策略  

Deadlock Avoidance Policies of Concurrent Process for Petri Net

作　　者：周建勇[1] 于杰[1] 刘海阳[2] 孙燕[1] 刘久富[1] 王志胜[1] 杨忠[1] 刘春生[1] 

机构地区：[1]南京航空航天大学自动化学院,江苏南京210016 [2]东南大学电子工程学院,江苏南京211189

出　　处：《计算机技术与发展》2016年第11期5-9,共5页Computer Technology and Development

基　　金：国家自然科学基金资助项目(60674100);南京航空航天大学专项资助项目(NS2010069)

摘　　要：死锁是系统并发进程中特有的问题,由于发生的不确定性,死锁检测和消除非常困难。在以分支界定法设计最优监控器的基础上,提出了一种可以最大限度保证静态和行为特性任意配置的死锁监控器集成设计方法。该方法通过可达图分析,在满足静态特性和行为特性下,进行可达图删减,从而实现合法标识和非法标识的分离,对分离出的标识建立混合整数线性规划模型,运用分支定界法得到补充监控库所的广义互斥约束模型作为最优监控器,保证了死锁的避免和资源的最大允许利用。以多进程码垛机器人加工系统为例,建立了Petri网模型,结合零件加工过程中资源的占用和释放,对柔性制造系统进行控制器设计。设计的控制器拥有更严格的约束和更简化的模型,对死锁标识的避免是充分的,验证了该算法的有效性。Deadlock is a unique error in concurrent process. Due to the uncertainty of the occurrence, it is difficult to detect and eliminate the deadlock. Building on recent results regarding optimal supervisor design with branch ＆ bound methods, an integrated modeling approach is proposed that can be used to derive a minimal supervisor guaranteeing the attainment of an arbitrary set of static and behavioral specifications in a maximally permissive way. This method prunes the reachability graph by the analysis of graph, to ensure the separation of legal markings and illegal markings, and builds the mixed integer linear programming to obtain generalized mutual exclusion constraints as the optimal supervisor. The system model of FMS is built with Petri Net. Based on the occupation and release of resource in the machining process,research is made on application in robot processing system. The optimal supervisors generating from the algorithm show stricter constrains and more simplified model,achieving deadlock avoidance policy, which have proved the effectiveness of this method.

关 键 词：PETRI网 监控器 死锁避免 广义互斥约束 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]