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