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

周建勇,于 杰,刘海阳,孙 燕,刘久富,王志胜,杨 忠,刘春生

(1.南京航空航天大学 自动化学院，江苏 南京 210016；2.东南大学 电子工程学院，江苏 南京 211189)

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

周建勇1,于 杰1,刘海阳2,孙 燕1,刘久富1,王志胜1,杨 忠1,刘春生1

(1.南京航空航天大学 自动化学院，江苏 南京 210016；2.东南大学 电子工程学院，江苏 南京 211189)

死锁是系统并发进程中特有的问题，由于发生的不确定性，死锁检测和消除非常困难。在以分支界定法设计最优监控器的基础上，提出了一种可以最大限度保证静态和行为特性任意配置的死锁监控器集成设计方法。该方法通过可达图分析，在满足静态特性和行为特性下，进行可达图删减，从而实现合法标识和非法标识的分离，对分离出的标识建立混合整数线性规划模型，运用分支定界法得到补充监控库所的广义互斥约束模型作为最优监控器，保证了死锁的避免和资源的最大允许利用。以多进程码垛机器人加工系统为例，建立了Petri网模型，结合零件加工过程中资源的占用和释放，对柔性制造系统进行控制器设计。设计的控制器拥有更严格的约束和更简化的模型，对死锁标识的避免是充分的，验证了该算法的有效性。

Petri网；监控器；死锁避免；广义互斥约束

0 引 言

并发进程中由于资源的竞争导致的程序无限等待过程称为死锁。死锁的发生会使整个系统陷于瘫痪，严重影响系统的可用性和可靠性，给生产、生活带来巨大的经济损失，甚至严重的灾害。死锁问题的处理主要有死锁避免、死锁检测与校正、死锁预防这三种方法。

Petri网作为一种用于描述离散、分布式系统的数学建模工具，被用于离散事件系统的建模与分析，其特有的冲突、可达、有界及活性等特性使得其在并发系统中有很好的应用。死锁避免策略通过添加控制库所限制变迁的触发使危险状态和死锁状态分离，由此来获得最佳的和最大行为许可的Petri网控制器。

针对并发进程中的死锁避免策略的监控器设计在最近的文献中颇受关注。文献[1]通过计算与资源分配系统密切相关的信标确定控制器，但随着网图规模呈指数性增长的信标数量使得相应的Petri网控制器在结构上过于复杂。文献[2]通过构造矩阵方程的方法设计分类器，但同样要保证矩阵方程满足相容条件才能判断是否存在符合要求的控制器。因此，设计同时具有最大允许度和死锁避免的监控器显得尤为重要。Cordone等[3-7]提出了一种有效的监控器设计方法，基于广义互斥约束将非法标识集从整个合法标识集向多个子集的合适分离，通过分支定界法有效解决分类的系统探索问题。

文中解决了监控器设计中死锁避免的问题，将监控器设计与约束建模相结合。分析了Petri网可达性，将可达集分为合法标识集和通过变迁触发可达的死锁标识集u。生成过程保证了关于给定特性的的极大性，包括静态和死锁避免等行为特性。特别是，它给出了如何表征带有不可控变迁的网中的合法标识集和有界非法标识集，其中给定的特性都一定要可监控执行。通过分支定界法[8-11]建立混合不等式模型，进一步保证设计的监控器数量的最优性和结构的简洁性。

1 Petri网与广义互斥约束的分类问题

1.1 Petri网基础

定义1：PN=〈P,T,Pre,Post,m0〉为Petri网(PetriNet,PN)。其中，P={P1,P2,…,Pn}称为库所(place)集合；T={T1,T2,…,Tn}称为变迁(transition)集合，P∩T=∅；Pre,Post∈np×nt是输入输出矩阵，m0∈np是初始标识向量，是非负整数集。Pre,Post表示Petri网的库所变迁间的拓扑结构[12]。

定义2：在Petri网的标识M下，如果资源子集RD∈R满足如下两个条件，则称RD处于死锁状态，M被称为死锁标识，记为MD[13]。

(1)RD中所有资源被占用，即M(pr)=0，r∈RD。

(2)所有占用RD中资源的操作都在等待RD中其他的资源，即对于操作pq∈{pq|R(pq)∈RD,M(pq)>0}，存在*(pq*)r∈{pr|r∈RD}。

1.2 Petri网的行为规范

变迁tj∈T在标识m下是使能的当且仅当m≥Preej，其中ej是nt坐标空间下的第j个向量。如果那么tj即可在标识m点火，生成标识m'=m+Cej。通过使能变迁序列从m0可达的标识集就是可达集，定义为有向图就是可达图，其中是节点集，A⊆是有向弧集，通过标签函数h:A→T与Petri网变迁相连。

综上，Petri网无死锁则所有强连通量都有严格大于1的基。

1.3 可达标识的分类问题

定义3：给出Petri网N，Tc≠∅，定义N的不可控子网Nu为N中消除所有可控变迁后的子网。

另一方面，如果没有禁止标识，可以通过一组只包含不可控变迁的点火序列从属于的任意标识可达，那么是可控的。

如果有一条从控制库所到t的弧且控制库所是标记的，网标识使能的变迁t可以通过Petri网监控器禁止。因此，为了通过Petri网控制器执行行为可控合法标识集，如果存在控制库所能够单独禁止变迁的可达标识，必须避免从控制库所到不可控变迁的有向弧，否则就可以通过本体变迁使能。

定理1：一对互斥标识集L和u，PL是L的凸包，当且仅当不存在标识m∈u使得m∈PL时，存在线性分类器将L和u分离[15]。

分离L和u的最优线性分类器可以通过寻找最优覆盖非法集合u的合适子集ui，i=1,2,…,nc，使得每一个子集都存在一个分离ui和L的广义互斥约束。非法集合u的可行覆盖可以通过分支定界法进行系统解决。

2 基于GMEC的死锁避免策略

为了获得一个非冗余模型，并保证包含最小数量的用以执行约束的监控库所在寻找所有约束集的最优监控集合，PN建模过程包括两个步骤：

(2)求解线性分类器(L,k)，将u从分离出来，对任意i有⊆M(L,k)并且M(L,k)∩u=Φ，该分类器性能评估依据主要为添加弧数目和控制库所个数。

2.1 死锁标识集分离

定理2[16]：Petri网〈N,m0〉，RG=(V,A)，其中V=R(N,m0)。存在一组广义互斥约束(L,k)，满足R(N,m0)∩M(L,k)为有限集且包含m0。V*为可达标识集，且满足：

(1)m∈R(N,m0)∩M(L,k)，m=m0或者在可达图上存在一个从m0到m的直达路径，其所有节点都属于V*；

(2)∃m′∈V*{m}使得(m,m′)∈A；

(3)∀tj∉T，存在m′,m″∈V*，使得(m′,m″)∈A，h(m′,m″)=tj，在可达图上存在一个从m到m′的直达路径，其所有节点都属于V*；

(4)∀m′∉V*，使得(m,m′)∈A，h(m,m′)∈Tc，Tc⊆T是可控变迁集。

如果集合V*是空集，则不存在符合要求的分类器；如果V*非空，V*对应的就是最大允许特性的分类器。

算法1。

输入：m0，PN=(P,T,Pre,Post)；

(1)初始化算法变量：V′={m0}，A′=∅。

(2)构造删减的可达图：RG ′=(V′,A′)。若∀m∈V′，∀t∈T，满足m[t〉m′，其m′∈M(L,k)，则设置A′=A′∪{(m,m′)}；若m′∉V′，则设置V′=V′∪{m′}。

(3)依据所要求的行为规范，逐次裁剪下列标识及相关弧的图RG ′。

①所有属于终端SCC状态的维数等于1。

②对任意标识m，∃t∈Tu，m′∉V′都满足：m[t〉m′，对任意标识m，不存在m′∈V′使得(m′,m)∈A′。

首先建立了可达图的最大子图，并包含了使得所有遵守静态约束的状态，其次修剪违反任一行为规范的状态。在这个过程中必须要反复迭代第二步，因为行为规范之间会因为任一状态的减少互相影响，同时死锁状态也会被修剪。最终，迭代修剪将RG ′裁剪为RG*=(V*,A*)。

2.2 Petri网监控器设计

已知Petri网〈N,m0〉，给出合法集合和死锁标识集合u，则存在一个分离器分离这两个子集。通过算法1获得和u，下面给出分离这两个集合的线性分离器的求解过程。

构造如下混合整数线性规划不等式(MIP)[6]：

(1)

∀x∈{γ}:ε+ρ·(γx-1)≤l·x-k≤ρ·γx

(2)

(3)

∀i∈{1,2,…,n}:0≤l[i]≤1∧0≤k≤1

(4)

γx,θ∈{0,1}

(5)

∀j∈J0:l[j]=0∧∀j∈JP:l[j]=l′[Γ(j)]∧k=k′

(6)

相关参数变量定义如下：

J0：状态空间维度集；

JP：JP≡LPJ0；

Γ：JP中元素向子空间VJP的双射；

ε：分离系数(足够接近于0)；

ρ：混合整数线性规划中的比例参数(足够大)；

θ：评价γ[i]与γu[i]的关系参数，当且仅当γ[i]=0∧γu[i]=1时，θ=1。

算法2：

输出：(L,k)。

(1)初始化算法变量。

W=×u，i=0

JP=LP，J0=∅

(2)递归消除非法标识。

whileW≠∅ do

i=i+1；

forall{j|∀(,u)∈W:[j]≥u[j]} do

从JP中移除j；

endfor

将W中元素投射到子集VJP中；

S={|(,u)∈W}

U={u|(,u)∈W}

γ=S∪U

通过输入W，γ，ε和ρ解混合线性规划不等式(1)～(5)生成线性不等式(L′(i,.),k′[i])；

通过式(6)由(L′(i,.),k′[i])构建(L(i,.),k[i])；

从W中删除集合{(,u)∈W|θ=1}；

endwhile

(3)返回(L,k)。

由算法2，可以获得执行最紧凑分类器约束(L,k)，即

L·X≤k

(7)

3 实例验证

码垛机器人加工系统在自动化领域发挥着越来越重要的作用。如果存在不可控变迁方面的问题，会对系统产生死锁之类的影响。文中应用最小监控器集成生成方法，求解避免死锁的最小最紧凑广义互斥约束组，以此监控系统的运行。

图1为一个加工三类工件的码垛机器人零件加工系统的Petri网模型。

图1 码垛机器人加工系统PN模型

该系统包含了两个码垛机器人R1和R2，且每个机器人每次可装载两个或三个工件。另外有四台机床M1～M4，且每台机床可加工两个或三个工件，同时，该单元由三个输入缓存Input1～Input3(i1～i3)，三个输出缓存Output1～Output3(o1～o3)。该加工系统有三条加工线，第一条工序(P1)：R1把工件P1从i1装载到M1上加工，被M1处理后，由R1移到M2上加工，被M2处理后，被R2移到M3上加工，最后由o1输出；第二条工序(P2)：工件P2从i2装载,依次通过机床M3、M2、M1，最后从o2输出；第三条工序(P3)：工件P3从i3装载，通过机床M4加工，最后R2将工件从o3卸载。

三个进程在加工工件的同时竞争共享资源(R1，R2)和(M1～M4)，因此会导致死锁状态的产生。记库所标识量M(pi)为pi。

根据机器人R1和R2的装载量约束可得出：

p1+p16≤2∨p2+p16≤2

(8)

p3+p7+p8+p10+p13≤3

(9)

根据资源M1～M4的容量约束可得出：

p1+p15≤2∨p5+p15≤2

(10)

p2+p6+p14≤2

(11)

p4+p12+p13≤3

(12)

p3+p7+p8+p10+p13≤3

(13)

求解潜在的死锁状态需要遍历可达标识，剔除经过某一变迁序列到达死锁状态的标识。首先通过算法1由可达性分析求解可达标识，本例中满足约束(8)～(10)的标识即为可达标识，通过可达图分析有67 800个标识，这些标识同时包含了合法标识和有界非法标识，有界非法标识通过有限的变迁序列触发会最终导致死锁状态的发生。依据算法1第三步可进行迭代删除非法标识实现标识的分离。

根据算法2以及分离出的标识集合求解最优的线性规划模型作为补充约束。

2p1+2p2+2p3+p8+p9≤4

(14)

2p1+p12+p13+p14+p15≤5

(15)

根据约束(14)、(15)可构建图2所示的死锁监控器，机器人和机床资源库所未画出，控制库所由VS1和VS2组成，容量分别为4和5，另外需要添加10条有向弧。

若采用文献[1]中的算法，需要添加25条弧和5个控制库所，并且合法可达状态个数受到了较大限制，只有6 552个合法状态；而在文中监控器下，所有造成死锁的有界非法标识都将被禁止，添加弧和控制库所个数明显减少，合法可达状态数量增多，如表1所示。

图2 PN控制器模型

控制规则文献[1]方法文中方法控制库所个数添加弧个数合法状态数525655221010525

文中监控器在实现死锁避免的同时，又保证了资源的最大利用。

4 结束语

针对多进程码垛机器人加工系统中的死锁问题，提出一种基于广义互斥约束分离的Petri网的死锁避免策略。区别于一般的线性规划方法，该策略结合了分支定界法对最优解的求取，避免了重复评价所有可能的组合解，降低了算法的复杂度，保证了Petri网的死锁避免特性和最大允许特性。同时，该策略实现了对死锁状态的禁止，其中非法标识的计算在代码量上仍有一定缺陷，随着库所量的增加，系统冗余仍然存在。接下来将研究结合分布式监控器实现对库所的约束，以最小冗余避免死锁的产生。

[1] 胡核算,李志武,王安荣.基于信标的柔性制造系统的优化死锁预防策略[J].控制与决策,2006,21(12):1343-1348.

[2] 罗继亮.Petri网的一类禁止状态问题的混合型监控器算法设计[J].计算机学报,2008,31(2):291-298.

[3]CordoneR,PiroddiL.ParsimoniousmonitorcontrolofPetrinetmodelsofFMS[J].IEEETransitionsonSystem,Man,andCyberneticsPartA:SystemsandHumans,2013,43(1):215-221.

[4]ChenYF,LiZW,KhalguiM,etal.Designofamaximallypermissiveliveness-enforcingPetrinetsupervisorforflexiblemanufacturingsystems[J].IEEETransactionsonAutomationScienceandEngineering,2011,8(2):374-393.

[5]NazeemA,ReveliotisS.Designingcompactandmaximallypermissivedeadlockavoidancepoliciesforcomplexresourceallocationsystemsthroughclassificationtheory:thenonlinearcase[J].IEEETransactionsonAutomaticControl,2012,57(7):1670-1684.

[6]NazeemA,ReveliotisS,WangY,etal.Designingcompactandmaximallypermissivedeadlockavoidancepoliciesforcomplexresourceallocationsystemsthroughclassificationtheory:thelinearcase[J].IEEETransactionsonAutomaticControl,2011,56(8):1818-1833.

[7]BasileF,CordoneR,PiroddiL.IntegrateddesignofoptimalsupervisorsfortheenforcementofstaticandbehavioralspecificationsinPetrinetmodels[J].Automatic,2013,49:3432-3439.

[8]NazeemA,ReveliotisS,WangY,etal.Optimaldeadlockavoidanceforcomplexresourceallocationsystemsthroughclassificationtheory[C]//Procof10thinternationalworkshopondiscreteeventsystems.[s.l.]:[s.n.],2010:277-284.

[9]NazeemA,ReveliotisS.Apracticalapproachtothedesignofmaximallypermissiveliveness-enforcingsupervisorsforcomplexresourceallocationsystems[C]//Procof6thIEEEconferenceonautomationscienceandengineering.[s.l.]:IEEE,2010:451-458.

[10]ReveliotisS,FerreiraP.Deadlockavoidancepoliciesforautomatedmanufacturingcells[J].IEEETransactionsonRobotics&Automation,1996,12(6):845-857.

[11]BanaszakZA,KroghBH.Deadlockavoidanceinflexiblemanufacturingsystemswithconcurrentlycompetingprocessflows[J].IEEETransactionsonRoboticsandAutomation,1990,6(6):724-734.

[12]ZhangYY,YanGF.SynthesisofPetrinetsupervisorsenforcinggeneralconstraints[J].JournalofZhejiangUniversity,2006,7(4):623-628.

[13]GhaffariA,RezgN,XieX.DesignofaliveandmaximallypermissivePetrinetcontrollerusingthetheoryofregions[J].IEEETransactiononRoboticsandAutomation,2003,19(1):137-141.

[14]MoodyJO,AntsaklisPJ.PetrinetsupervisorsforDESwithuncontrollableandunobservabletransitions[J].IEEETransactionsonAutomaticControl,2000,45(3):462-476.

[15]MurataT.Petrinets:properties,analysisandapplication[J].ProceddingsoftheIEEE,1989,77(4):541-580.

[16]ValdesRA,MartinezA,TamaritM.Abranch&boundalgorithmforcuttingandpackingirregularlyshapedpieces[J].InternationalJournalofProductionEconomics,2013,145:463-477.

Deadlock Avoidance Policies of Concurrent Process for Petri Net

ZHOU Jian-yong1，YU Jie1，LIU Hai-yang2，SUN Yan1，LIU Jiu-fu1，WANG Zhi-sheng1，YANG Zhong1，LIU Chun-sheng1

(1.Department of Automation,Nanjing University of Aeronautics and Astronautics,Nanjing 210016,China;2.College of Electronic Engineering,Southeast University,Nanjing 211189,China)

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 Nets;supervisors;deadlock avoidance;generalized mutual exclusion constraints

2015-01-20

2015-06-10

时间：2016-09-18

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

周建勇(1990-)，男，硕士研究生，研究方向为软件工程、离散控制;刘久富，博士，硕士研究生导师，通信作者，研究方向为软件工程、机器人。

http://www.cnki.net/kcms/detail/61.1450.TP.20160918.1707.002.html

TP311

A

1673-629X(2016)11-0005-05

10.3969/j.issn.1673-629X.2016.11.002