周建勇,于 杰,劉海陽,孫 燕,劉久富,王志勝,楊 忠,劉春生

(1.南京航空航天大學(xué) 自動化學(xué)院，江蘇 南京 210016；2.東南大學(xué) 電子工程學(xué)院，江蘇 南京 211189)

Petri網(wǎng)并發(fā)進(jìn)程的死鎖避免策略

周建勇1,于 杰1,劉海陽2,孫 燕1,劉久富1,王志勝1,楊 忠1,劉春生1

(1.南京航空航天大學(xué) 自動化學(xué)院，江蘇 南京 210016；2.東南大學(xué) 電子工程學(xué)院，江蘇 南京 211189)

死鎖是系統(tǒng)并發(fā)進(jìn)程中特有的問題，由于發(fā)生的不確定性，死鎖檢測和消除非常困難。在以分支界定法設(shè)計(jì)最優(yōu)監(jiān)控器的基礎(chǔ)上，提出了一種可以最大限度保證靜態(tài)和行為特性任意配置的死鎖監(jiān)控器集成設(shè)計(jì)方法。該方法通過可達(dá)圖分析，在滿足靜態(tài)特性和行為特性下，進(jìn)行可達(dá)圖刪減，從而實(shí)現(xiàn)合法標(biāo)識和非法標(biāo)識的分離，對分離出的標(biāo)識建立混合整數(shù)線性規(guī)劃模型，運(yùn)用分支定界法得到補(bǔ)充監(jiān)控庫所的廣義互斥約束模型作為最優(yōu)監(jiān)控器，保證了死鎖的避免和資源的最大允許利用。以多進(jìn)程碼垛機(jī)器人加工系統(tǒng)為例，建立了Petri網(wǎng)模型，結(jié)合零件加工過程中資源的占用和釋放，對柔性制造系統(tǒng)進(jìn)行控制器設(shè)計(jì)。設(shè)計(jì)的控制器擁有更嚴(yán)格的約束和更簡化的模型，對死鎖標(biāo)識的避免是充分的，驗(yàn)證了該算法的有效性。

Petri網(wǎng)；監(jiān)控器；死鎖避免；廣義互斥約束

0 引 言

并發(fā)進(jìn)程中由于資源的競爭導(dǎo)致的程序無限等待過程稱為死鎖。死鎖的發(fā)生會使整個系統(tǒng)陷于癱瘓，嚴(yán)重影響系統(tǒng)的可用性和可靠性，給生產(chǎn)、生活帶來巨大的經(jīng)濟(jì)損失，甚至嚴(yán)重的災(zāi)害。死鎖問題的處理主要有死鎖避免、死鎖檢測與校正、死鎖預(yù)防這三種方法。

Petri網(wǎng)作為一種用于描述離散、分布式系統(tǒng)的數(shù)學(xué)建模工具，被用于離散事件系統(tǒng)的建模與分析，其特有的沖突、可達(dá)、有界及活性等特性使得其在并發(fā)系統(tǒng)中有很好的應(yīng)用。死鎖避免策略通過添加控制庫所限制變遷的觸發(fā)使危險(xiǎn)狀態(tài)和死鎖狀態(tài)分離，由此來獲得最佳的和最大行為許可的Petri網(wǎng)控制器。

針對并發(fā)進(jìn)程中的死鎖避免策略的監(jiān)控器設(shè)計(jì)在最近的文獻(xiàn)中頗受關(guān)注。文獻(xiàn)[1]通過計(jì)算與資源分配系統(tǒng)密切相關(guān)的信標(biāo)確定控制器，但隨著網(wǎng)圖規(guī)模呈指數(shù)性增長的信標(biāo)數(shù)量使得相應(yīng)的Petri網(wǎng)控制器在結(jié)構(gòu)上過于復(fù)雜。文獻(xiàn)[2]通過構(gòu)造矩陣方程的方法設(shè)計(jì)分類器，但同樣要保證矩陣方程滿足相容條件才能判斷是否存在符合要求的控制器。因此，設(shè)計(jì)同時具有最大允許度和死鎖避免的監(jiān)控器顯得尤為重要。Cordone等[3-7]提出了一種有效的監(jiān)控器設(shè)計(jì)方法，基于廣義互斥約束將非法標(biāo)識集從整個合法標(biāo)識集向多個子集的合適分離，通過分支定界法有效解決分類的系統(tǒng)探索問題。

文中解決了監(jiān)控器設(shè)計(jì)中死鎖避免的問題，將監(jiān)控器設(shè)計(jì)與約束建模相結(jié)合。分析了Petri網(wǎng)可達(dá)性，將可達(dá)集分為合法標(biāo)識集和通過變遷觸發(fā)可達(dá)的死鎖標(biāo)識集u。生成過程保證了關(guān)于給定特性的的極大性，包括靜態(tài)和死鎖避免等行為特性。特別是，它給出了如何表征帶有不可控變遷的網(wǎng)中的合法標(biāo)識集和有界非法標(biāo)識集，其中給定的特性都一定要可監(jiān)控執(zhí)行。通過分支定界法[8-11]建立混合不等式模型，進(jìn)一步保證設(shè)計(jì)的監(jiān)控器數(shù)量的最優(yōu)性和結(jié)構(gòu)的簡潔性。

1 Petri網(wǎng)與廣義互斥約束的分類問題

1.1 Petri網(wǎng)基礎(chǔ)

定義1：PN=〈P,T,Pre,Post,m0〉為Petri網(wǎng)(PetriNet,PN)。其中，P={P1,P2,…,Pn}稱為庫所(place)集合；T={T1,T2,…,Tn}稱為變遷(transition)集合，P∩T=?；Pre,Post∈np×nt是輸入輸出矩陣，m0∈np是初始標(biāo)識向量，是非負(fù)整數(shù)集。Pre,Post表示Petri網(wǎng)的庫所變遷間的拓?fù)浣Y(jié)構(gòu)[12]。

定義2：在Petri網(wǎng)的標(biāo)識M下，如果資源子集RD∈R滿足如下兩個條件，則稱RD處于死鎖狀態(tài)，M被稱為死鎖標(biāo)識，記為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網(wǎng)的行為規(guī)范

變遷tj∈T在標(biāo)識m下是使能的當(dāng)且僅當(dāng)m≥Preej，其中ej是nt坐標(biāo)空間下的第j個向量。如果那么tj即可在標(biāo)識m點(diǎn)火，生成標(biāo)識m'=m+Cej。通過使能變遷序列從m0可達(dá)的標(biāo)識集就是可達(dá)集，定義為有向圖就是可達(dá)圖，其中是節(jié)點(diǎn)集，A?是有向弧集，通過標(biāo)簽函數(shù)h:A→T與Petri網(wǎng)變遷相連。

綜上，Petri網(wǎng)無死鎖則所有強(qiáng)連通量都有嚴(yán)格大于1的基。

1.3 可達(dá)標(biāo)識的分類問題

定義3：給出Petri網(wǎng)N，Tc≠?，定義N的不可控子網(wǎng)Nu為N中消除所有可控變遷后的子網(wǎng)。

另一方面，如果沒有禁止標(biāo)識，可以通過一組只包含不可控變遷的點(diǎn)火序列從屬于的任意標(biāo)識可達(dá)，那么是可控的。

如果有一條從控制庫所到t的弧且控制庫所是標(biāo)記的，網(wǎng)標(biāo)識使能的變遷t可以通過Petri網(wǎng)監(jiān)控器禁止。因此，為了通過Petri網(wǎng)控制器執(zhí)行行為可控合法標(biāo)識集，如果存在控制庫所能夠單獨(dú)禁止變遷的可達(dá)標(biāo)識，必須避免從控制庫所到不可控變遷的有向弧，否則就可以通過本體變遷使能。

定理1：一對互斥標(biāo)識集L和u，PL是L的凸包，當(dāng)且僅當(dāng)不存在標(biāo)識m∈u使得m∈PL時，存在線性分類器將L和u分離[15]。

分離L和u的最優(yōu)線性分類器可以通過尋找最優(yōu)覆蓋非法集合u的合適子集ui，i=1,2,…,nc，使得每一個子集都存在一個分離ui和L的廣義互斥約束。非法集合u的可行覆蓋可以通過分支定界法進(jìn)行系統(tǒng)解決。

2 基于GMEC的死鎖避免策略

為了獲得一個非冗余模型，并保證包含最小數(shù)量的用以執(zhí)行約束的監(jiān)控庫所在尋找所有約束集的最優(yōu)監(jiān)控集合，PN建模過程包括兩個步驟：

(2)求解線性分類器(L,k)，將u從分離出來，對任意i有?M(L,k)并且M(L,k)∩u=Φ，該分類器性能評估依據(jù)主要為添加弧數(shù)目和控制庫所個數(shù)。

2.1 死鎖標(biāo)識集分離

定理2[16]：Petri網(wǎng)〈N,m0〉，RG=(V,A)，其中V=R(N,m0)。存在一組廣義互斥約束(L,k)，滿足R(N,m0)∩M(L,k)為有限集且包含m0。V*為可達(dá)標(biāo)識集，且滿足：

(1)m∈R(N,m0)∩M(L,k)，m=m0或者在可達(dá)圖上存在一個從m0到m的直達(dá)路徑，其所有節(jié)點(diǎn)都屬于V*；

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

(3)?tj?T，存在m′,m″∈V*，使得(m′,m″)∈A，h(m′,m″)=tj，在可達(dá)圖上存在一個從m到m′的直達(dá)路徑，其所有節(jié)點(diǎn)都屬于V*；

(4)?m′?V*，使得(m,m′)∈A，h(m,m′)∈Tc，Tc?T是可控變遷集。

如果集合V*是空集，則不存在符合要求的分類器；如果V*非空，V*對應(yīng)的就是最大允許特性的分類器。

算法1。

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

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

(2)構(gòu)造刪減的可達(dá)圖：RG ′=(V′,A′)。若?m∈V′，?t∈T，滿足m[t〉m′，其m′∈M(L,k)，則設(shè)置A′=A′∪{(m,m′)}；若m′?V′，則設(shè)置V′=V′∪{m′}。

(3)依據(jù)所要求的行為規(guī)范，逐次裁剪下列標(biāo)識及相關(guān)弧的圖RG ′。

①所有屬于終端SCC狀態(tài)的維數(shù)等于1。

②對任意標(biāo)識m，?t∈Tu，m′?V′都滿足：m[t〉m′，對任意標(biāo)識m，不存在m′∈V′使得(m′,m)∈A′。

首先建立了可達(dá)圖的最大子圖，并包含了使得所有遵守靜態(tài)約束的狀態(tài)，其次修剪違反任一行為規(guī)范的狀態(tài)。在這個過程中必須要反復(fù)迭代第二步，因?yàn)樾袨橐?guī)范之間會因?yàn)槿我粻顟B(tài)的減少互相影響，同時死鎖狀態(tài)也會被修剪。最終，迭代修剪將RG ′裁剪為RG*=(V*,A*)。

2.2 Petri網(wǎng)監(jiān)控器設(shè)計(jì)

已知Petri網(wǎng)〈N,m0〉，給出合法集合和死鎖標(biāo)識集合u，則存在一個分離器分離這兩個子集。通過算法1獲得和u，下面給出分離這兩個集合的線性分離器的求解過程。

構(gòu)造如下混合整數(shù)線性規(guī)劃不等式(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)

相關(guān)參數(shù)變量定義如下：

J0：狀態(tài)空間維度集；

JP：JP≡LPJ0；

Γ：JP中元素向子空間VJP的雙射；

ε：分離系數(shù)(足夠接近于0)；

ρ：混合整數(shù)線性規(guī)劃中的比例參數(shù)(足夠大)；

θ：評價(jià)γ[i]與γu[i]的關(guān)系參數(shù)，當(dāng)且僅當(dāng)γ[i]=0∧γu[i]=1時，θ=1。

算法2：

輸出：(L,k)。

(1)初始化算法變量。

W=×u，i=0

JP=LP，J0=?

(2)遞歸消除非法標(biāo)識。

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，γ，ε和ρ解混合線性規(guī)劃不等式(1)～(5)生成線性不等式(L′(i,.),k′[i])；

通過式(6)由(L′(i,.),k′[i])構(gòu)建(L(i,.),k[i])；

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

endwhile

(3)返回(L,k)。

由算法2，可以獲得執(zhí)行最緊湊分類器約束(L,k)，即

L·X≤k

(7)

3 實(shí)例驗(yàn)證

碼垛機(jī)器人加工系統(tǒng)在自動化領(lǐng)域發(fā)揮著越來越重要的作用。如果存在不可控變遷方面的問題，會對系統(tǒng)產(chǎn)生死鎖之類的影響。文中應(yīng)用最小監(jiān)控器集成生成方法，求解避免死鎖的最小最緊湊廣義互斥約束組，以此監(jiān)控系統(tǒng)的運(yùn)行。

圖1為一個加工三類工件的碼垛機(jī)器人零件加工系統(tǒng)的Petri網(wǎng)模型。

圖1 碼垛機(jī)器人加工系統(tǒng)PN模型

該系統(tǒng)包含了兩個碼垛機(jī)器人R1和R2，且每個機(jī)器人每次可裝載兩個或三個工件。另外有四臺機(jī)床M1～M4，且每臺機(jī)床可加工兩個或三個工件，同時，該單元由三個輸入緩存Input1～I(xiàn)nput3(i1～i3)，三個輸出緩存Output1～Output3(o1～o3)。該加工系統(tǒng)有三條加工線，第一條工序(P1)：R1把工件P1從i1裝載到M1上加工，被M1處理后，由R1移到M2上加工，被M2處理后，被R2移到M3上加工，最后由o1輸出；第二條工序(P2)：工件P2從i2裝載,依次通過機(jī)床M3、M2、M1，最后從o2輸出；第三條工序(P3)：工件P3從i3裝載，通過機(jī)床M4加工，最后R2將工件從o3卸載。

三個進(jìn)程在加工工件的同時競爭共享資源(R1，R2)和(M1～M4)，因此會導(dǎo)致死鎖狀態(tài)的產(chǎn)生。記庫所標(biāo)識量M(pi)為pi。

根據(jù)機(jī)器人R1和R2的裝載量約束可得出：

p1+p16≤2∨p2+p16≤2

(8)

p3+p7+p8+p10+p13≤3

(9)

根據(jù)資源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)

求解潛在的死鎖狀態(tài)需要遍歷可達(dá)標(biāo)識，剔除經(jīng)過某一變遷序列到達(dá)死鎖狀態(tài)的標(biāo)識。首先通過算法1由可達(dá)性分析求解可達(dá)標(biāo)識，本例中滿足約束(8)～(10)的標(biāo)識即為可達(dá)標(biāo)識，通過可達(dá)圖分析有67 800個標(biāo)識，這些標(biāo)識同時包含了合法標(biāo)識和有界非法標(biāo)識，有界非法標(biāo)識通過有限的變遷序列觸發(fā)會最終導(dǎo)致死鎖狀態(tài)的發(fā)生。依據(jù)算法1第三步可進(jìn)行迭代刪除非法標(biāo)識實(shí)現(xiàn)標(biāo)識的分離。

根據(jù)算法2以及分離出的標(biāo)識集合求解最優(yōu)的線性規(guī)劃模型作為補(bǔ)充約束。

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

(14)

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

(15)

根據(jù)約束(14)、(15)可構(gòu)建圖2所示的死鎖監(jiān)控器，機(jī)器人和機(jī)床資源庫所未畫出，控制庫所由VS1和VS2組成，容量分別為4和5，另外需要添加10條有向弧。

若采用文獻(xiàn)[1]中的算法，需要添加25條弧和5個控制庫所，并且合法可達(dá)狀態(tài)個數(shù)受到了較大限制，只有6 552個合法狀態(tài)；而在文中監(jiān)控器下，所有造成死鎖的有界非法標(biāo)識都將被禁止，添加弧和控制庫所個數(shù)明顯減少，合法可達(dá)狀態(tài)數(shù)量增多，如表1所示。

圖2 PN控制器模型

控制規(guī)則文獻(xiàn)[1]方法文中方法控制庫所個數(shù)添加弧個數(shù)合法狀態(tài)數(shù)525655221010525

文中監(jiān)控器在實(shí)現(xiàn)死鎖避免的同時，又保證了資源的最大利用。

4 結(jié)束語

針對多進(jìn)程碼垛機(jī)器人加工系統(tǒng)中的死鎖問題，提出一種基于廣義互斥約束分離的Petri網(wǎng)的死鎖避免策略。區(qū)別于一般的線性規(guī)劃方法，該策略結(jié)合了分支定界法對最優(yōu)解的求取，避免了重復(fù)評價(jià)所有可能的組合解，降低了算法的復(fù)雜度，保證了Petri網(wǎng)的死鎖避免特性和最大允許特性。同時，該策略實(shí)現(xiàn)了對死鎖狀態(tài)的禁止，其中非法標(biāo)識的計(jì)算在代碼量上仍有一定缺陷，隨著庫所量的增加，系統(tǒng)冗余仍然存在。接下來將研究結(jié)合分布式監(jiān)控器實(shí)現(xiàn)對庫所的約束，以最小冗余避免死鎖的產(chǎn)生。

[1] 胡核算,李志武,王安榮.基于信標(biāo)的柔性制造系統(tǒng)的優(yōu)化死鎖預(yù)防策略[J].控制與決策,2006,21(12):1343-1348.

[2] 羅繼亮.Petri網(wǎng)的一類禁止?fàn)顟B(tài)問題的混合型監(jiān)控器算法設(shè)計(jì)[J].計(jì)算機(jī)學(xué)報(bào),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

國家自然科學(xué)基金資助項(xiàng)目(60674100)；南京航空航天大學(xué)專項(xiàng)資助項(xiàng)目(NS2010069)

周建勇(1990-)，男，碩士研究生，研究方向?yàn)檐浖こ獭㈦x散控制;劉久富，博士，碩士研究生導(dǎo)師，通信作者，研究方向?yàn)檐浖こ?、機(jī)器人。

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