岳 昊，李文杰

(1.漳州師范學院 計算機科學與工程系,福建 漳州 363000；2.山東科技大學 機電學院,山東 青島 266510;3.西北核技術研究所,陜西 西安 710065)

由于存在共享資源，加之對共享資源的管理不當，柔性制造系統(tǒng)(flexible manufacturing systems，簡稱FMS)會出現可能的死鎖[1].在FMS中，死鎖狀態(tài)就是由于有限資源的共享而導致的一種操作間的循環(huán)等待狀態(tài)，即每種操作都在等待某些資源，而這些資源又被其它操作所占用.死鎖問題最早是由計算機科學家在研究操作系統(tǒng)的進程管理時正式提出的[2].生死鎖的4個必要條件如下所述[3]：①互斥條件：一個資源每次只能被一個進程使用.②請求與保持條件：一個進程因請求資源而阻塞時，對已獲得的資源保持不放.③不剝奪條件:進程已獲得的資源，在末使用完之前，不能強行剝奪.④循環(huán)等待條件:若干進程之間形成一種頭尾相接的循環(huán)等待資源關系.這4個條件是死鎖的必要條件.只要系統(tǒng)發(fā)生死鎖，這些條件必然成立，而只要上述條件之一不滿足，就不會發(fā)生死鎖.

不同于阻塞，死鎖會引起系統(tǒng)部分或全部的停頓，系統(tǒng)的死鎖是制約系統(tǒng)控制和調度實現的關鍵問題[4].而共享資源則是死鎖發(fā)生的根本原因.因此，很多學者對柔性制造系統(tǒng)中的共享資源進行了深入的研究[4-9].文獻[5]將制造系統(tǒng)中的共享資源分為順序互相抑制(sequential mutual exclusion,SME)，和并行互相抑制(parallel mutual exclusion,PME)兩種結構.在文獻[5]的基礎上，文獻[4,6～9]深入研究了獨立制造過程的共享資源.其中，文獻[4,6]針對具有多個并行共享資源的系統(tǒng)，提出了該類系統(tǒng)具有可能死鎖的一個充分必要條件.而文獻[7]則提出了具有順序共享資源制造系統(tǒng)Petri網控制器的形式化設計理論和方法.文獻[8]從另外一個角度出發(fā)，根據FMS中多種操作對有限資源的競爭會導致死鎖狀態(tài)，介紹了一種死鎖避免方法.文獻[9]則利用Petri網為多資源共享系統(tǒng)建立模型，并討論了系統(tǒng)的安全性與無死鎖性.

在柔性制造系統(tǒng)中，引發(fā)死鎖的資源不僅限于獨立制造過程所共享的資源，也包括同一加工過程的不同加工操作所共享的資源.本文定義加工過程內共享資源，并通過一實際制造系統(tǒng)的Petri網模型，說明此類資源可能導致系統(tǒng)死鎖.

1 基本概念和定義

考查制造系統(tǒng)中的共享資源，對制造系統(tǒng)的建模采用Petri網這種形式化數學工具.因此，本文研究對象為一類S3PR網FMS的Petri網模型.有關S3PR網的相關定義及性質詳見文獻[1]，下面只給出同本文密切相關的基本概念和相關說明.

定義1[1]一個簡單加工過程(simple sequential process，簡稱S2P)一個網N=(P∪{p0},T,F)，其中：

1)P≠φ(稱p∈P為一個操作庫所)，p0?P(稱p0為一個過程空閑庫所)；

2)N是一個強連通的S-圖；

3)N中的每一個圈都包含p0.

定義2[1]稱網N=(P∪{p0}∪PR,T,F)是一個帶有資源的簡單加工過程(simple sequential process with resources，簡稱S2PR)，其中：

1)N的由P∪{p0}∪T生成的子網是一個簡單加工過程；

2)PR≠φ(稱r∈PR為一個資源或一個資源庫所)，(P∪{p0})∩PR=φ；

3)?p∈P，?t∈·p，?t/∈p·，?rp∈PR，·t∩PR=t/·∩PR={rp}；

4)下面兩點成立：①?r∈PR,··r∩P=r··∩P≠φ；②?r∈PR,·r∩r·=φ;

5)··(p0)∩PR=(p0)··∩PR=φ.

?r∈PR，記H(r)=··r∩P=r··∩P，即使用資源r的操作庫所集合.記H(r1)∪H(r2)∪…∪H(rm)為∪r∈RH(r)，其中R={r1,r2,…,rm}為一個資源子集.在下文的S2PR中記P0={p0}.

關于定義2的說明：由條件1)和2)知S2PR是在S2P的基礎上加上了若干個資源及相關弧形成的；條件3)說明S2PR中的每一個操作庫所使用且僅使用一個資源；條件4)中的①說明對于每一個資源而言，在S2PR中都存在使用它的操作庫所，②說明相鄰的兩個操作庫所使用的資源不同；條件5)說明過程空閑庫所不使用任何資源.

定義3[1]遞歸定義S2PR系統(tǒng)(systemofsimplesequentialprocesswithresources，簡稱S3PR網)如下：

1)一個S2PR是一個S3PR網；

例如,圖3所示的S3PR網N由圖1和圖2中的兩個S2PR組合得到：

圖4 一個實際的柔性制造系統(tǒng)Petri網模型

圖1 一個S2PRN1 圖2 一個S2PRN2 圖3 一個S3PR網N

2 加工過程內共享資源

就制造系統(tǒng)而言，機器(包括各種加工機床)、托盤、機械臂、緩沖庫等常常作為若干分支(如加工單元)等共享的資源[9].所謂共享資源，其可能是因為被多個獨立加工過程的不同加工操作所共用，而成為“共享”資源.也可能是因為被同一加工過程內的不同加工操作所共用.目前的研究大多是獨立加工過程的共享資源，而本節(jié)將定義同一加工過程內的共享資源.

實例設某加工中心有兩臺機器M1，M2，加工兩種工件J1，J2，每臺機器同時只能加工一個工件.兩種工件的輸入工件庫分別為I1，I2，存放若干個(分別為C1個和C2個)待加工工件，輸出工件庫分別為O1，O2，緩沖庫為B1，B2，每個緩沖庫同時只能放置一個待加工或已加工完畢的工件.

為了方便討論，可將上面的加工過程看成是一個閉合加工過程，對此將待建模型中的Ii與Oi合并(i=1,2)，得到如下閉合式的加工系統(tǒng)Petri網模型.

讀者不難理解模型中網元素(即變遷、庫所和有向弧)的意義.在圖4中，容易發(fā)現M1，M2，B1，B2均為共享資源.其中由定義4，可知B1，B2是都是同一加工過程內的共享資源.考查系統(tǒng)模型如下兩種死鎖狀態(tài).

在圖5和圖6所示的死鎖狀態(tài)中，加工系統(tǒng)均被迫處于停頓狀態(tài)，沒有工件的加工過程可以推進.在圖5中，造成死鎖狀態(tài)的是共享資源M1和M2，而在圖6中，造成死鎖狀態(tài)的卻是加工過程內共享資源B1.

圖5 死鎖狀態(tài)1 圖6 死鎖狀態(tài)2

3 結束語

柔性制造系統(tǒng)中的共享資源可能導致系統(tǒng)死鎖.現有研究結果都是針對獨立加工過程之間的共享資源.本文則以同一加工過程內的不同加工操作所共享的資源作為研究對象，并將其定義為加工過程內共享資源.文中指出，加工過程內共享資源亦有可能產生系統(tǒng)死鎖.為了避免系統(tǒng)因死鎖而陷入癱瘓狀態(tài)，對此類資源同樣需要合理分配與管理.

參考文獻:

[1]Ezpeleta J, Colom J M,Martinez J.A petri net based deadlock prevention policy for flexible manufacturing systems[J].IEEE Trans Robot Automat,1995,11(4):173-184.

[2]黃忠華.自動制造系統(tǒng)中的無死鎖調度與控制[D].上海:上海交通大學,2007.

[3]Coffman E G,Elphick M J,Shoshani A.System deadlocks[J].ACM Computing Surveys,1971(3):67-78.

[4]李志武,賈建援,王安榮.復制并行共享資源與系統(tǒng)死鎖[J].中國機械工程,2003,14(4):280-284.

[5]Zhou M C, DiCesare F. Parallel and sequential mutual exclusion for Petri net modeling of manufacturing systems with shared resources[J].IEEE Trans Robotics and Automation,1991,7(4):515-527.

[6]李志武,陶曉峰.復雜并行共享資源柔性制造系統(tǒng)中的死鎖結構[J].機械科學與技術,2002,21(4):543-545.

[7]李志武,郝林.順序共享資源制造系統(tǒng)Petri網控制器的形式化設計方法[J].機械科學與技術,2002,21(3):488-490.

[8]韓贊東,李基范.FMS中資源共享導致的死鎖狀態(tài)及其避免方法[J].中國機械工程，2004,15(10):212-216.

[9]許廣銀.多資源共享系統(tǒng)的死鎖分析與控制[J].應用科學學報1998,16(3):331-337.

[10]張會福.數字制造系統(tǒng)資源共享理論框架及關鍵技術研究[D].武漢：武漢理工大學,2007.

[11]薛雷,郝躍.面向柔性制造系統(tǒng)的基于“自治子網”的Petri網結構化建模方法及其活性保障策略[J].中國科學，2003,33(10):876-886.