吳國鳳， 胡德啟， 安 磊， 鄭禮良

（合肥工業(yè)大學(xué) 計(jì)算機(jī)與信息學(xué)院，安徽 合肥 230009）

含有不可控變遷的Petri網(wǎng)死鎖避免策略

吳國鳳， 胡德啟， 安 磊， 鄭禮良

（合肥工業(yè)大學(xué) 計(jì)算機(jī)與信息學(xué)院，安徽 合肥 230009）

文章針對(duì)Petri網(wǎng)建模的并發(fā)系統(tǒng)中的死鎖問題，利用Petri網(wǎng)可達(dá)樹分析方法檢測系統(tǒng)死鎖的存在，結(jié)合Petri網(wǎng)控制器的設(shè)計(jì)來達(dá)到預(yù)防和避免死鎖的目的；提出了一種新的約束設(shè)計(jì)思想，進(jìn)行控制器設(shè)計(jì)，使得系統(tǒng)不會(huì)出現(xiàn)死鎖；更進(jìn)一步地考慮到控制器設(shè)計(jì)過程中存在不可控變遷的情況下系統(tǒng)避免死鎖的設(shè)計(jì)問題。

Petri網(wǎng)；控制器；混合約束；死鎖

并發(fā)進(jìn)程的死鎖問題是分布式系統(tǒng)中的一個(gè)重要研究課題［1］。在多個(gè)并發(fā)進(jìn)程系統(tǒng)中，如果每個(gè)進(jìn)程持有某種資源，同時(shí)又等待其他進(jìn)程所持有的各種資源，此時(shí)，每個(gè)進(jìn)程都持有一定資源但又都無法推進(jìn)，這樣就形成了死鎖［2］，這樣的死鎖在分布式系統(tǒng)中時(shí)有出現(xiàn)，因此，發(fā)現(xiàn)和提出好的死鎖檢測、預(yù)防和解除方法尤為重要。

文獻(xiàn)［3］提出了基于庫所不變量的控制器設(shè)計(jì)算法，該方法利用整個(gè)Petri網(wǎng)的關(guān)聯(lián)矩陣來計(jì)算控制器，計(jì)算的復(fù)雜度比較大，而且只適用于安全網(wǎng)。文獻(xiàn)［4］提出了Parikh向量不等式的約束轉(zhuǎn)換算法，再用基于庫所不變量的控制器算法設(shè)計(jì)控制器。但是，以上各種方法并沒有把控制器算法應(yīng)用于解決Petri網(wǎng)的死鎖問題。

本文在總結(jié)上述控制器設(shè)計(jì)算法時(shí)存在問題和研究Petri網(wǎng)建模的并發(fā)系統(tǒng)中的死鎖問題基礎(chǔ)上，利用Petri網(wǎng)可達(dá)樹分析方法檢測系統(tǒng)死鎖的存在，設(shè)計(jì)出一種可以避免死鎖的約束條件，結(jié)合Petri網(wǎng)控制器的設(shè)計(jì)來達(dá)到預(yù)防和避免死鎖的目的［5－6］。

1 基本知識(shí)

1.1 動(dòng)態(tài)死鎖

定義1 Petri網(wǎng)系統(tǒng)Σ＝（S，T；F，μ0），如果存在標(biāo)識(shí)μ∈R（Σ，μ0），對(duì)任意的一個(gè)變遷t∈T，狀態(tài)函數(shù)δ（μ，t）無定義，那么則稱標(biāo)識(shí)μ為死鎖標(biāo)識(shí)［2］。

定義2 Petri網(wǎng)系統(tǒng)Σ＝（S，T；F，μ0），如果可達(dá)標(biāo)識(shí)集合中存在死鎖標(biāo)識(shí)，那么Petri網(wǎng)中存在死鎖［2］。

定理1 分布式并發(fā)進(jìn)程中存在死鎖，且僅當(dāng)其Petri網(wǎng)模型的可達(dá)樹中存在死標(biāo)識(shí)。

動(dòng)態(tài)死鎖反映了Petri網(wǎng)系統(tǒng)的動(dòng)態(tài)運(yùn)行特征，如果Petri網(wǎng)系統(tǒng)發(fā)生死鎖，那么該P(yáng)etri網(wǎng)的可達(dá)標(biāo)識(shí)集合中一定有與之相對(duì)應(yīng)的死標(biāo)識(shí)。因此，Petri網(wǎng)的動(dòng)態(tài)死鎖問題就可以歸結(jié)為Petri網(wǎng)的可達(dá)標(biāo)識(shí)集合中是否有死標(biāo)識(shí)的問題。

1.2 線性不等式約束

線性不等式約束是Petri網(wǎng)控制器構(gòu)建的前提，對(duì)于實(shí)際系統(tǒng)，結(jié)合控制要求，往往能將控制要求轉(zhuǎn)變?yōu)橐粋€(gè)不等式或不等式組。

一般的線性不等式又叫單純的標(biāo)識(shí)約束，它的約束形式為Lμ≤b，其中，L∈；μ∈Zn×1；b∈；n為 Petri網(wǎng)中的庫所數(shù)；nc為不等式約束的個(gè)數(shù)。

混合約束同一般的線性不等式約束相比有更強(qiáng)的描述能力，它是指標(biāo)識(shí)約束和變遷激發(fā)約束同時(shí)存在的約束，約束形式為C＝Lrμr＋λrqr≤b。其中，qr是第r個(gè)變遷的激發(fā)索引，當(dāng)qr＝1時(shí)，就表示第r個(gè)變遷tr被激發(fā)；λr∈；nr為約束變遷的個(gè)數(shù)；nc為約束條件的個(gè)數(shù)。這種不等式約束稱為混合約束。

2 存在不可控變遷的Petri網(wǎng)死鎖避免策略

2.1 死鎖檢測算法

根據(jù)Petri網(wǎng)可達(dá)標(biāo)識(shí)樹的生成算法［7］，對(duì)輸出結(jié)果稍作修改，就可以輸出在死標(biāo)識(shí)狀態(tài)下含有死標(biāo)識(shí)的庫所集。

設(shè)庫所si對(duì)應(yīng)于標(biāo)識(shí)μi，在死標(biāo)識(shí)μi狀態(tài)下含有死鎖標(biāo)識(shí)的庫所集Mi＝｛s1，…，sk｝和死標(biāo)識(shí)數(shù)目ai，死標(biāo)識(shí)集合DM＝?，與之對(duì)應(yīng)的Mi的集合DS＝?。

（1）以庫所si為頭結(jié)點(diǎn)，如果系統(tǒng)出現(xiàn)死鎖，那么μi就為一個(gè)死鎖標(biāo)識(shí)，輸出｛μi；Mi；ai｝，執(zhí)行步驟（2）；否則執(zhí)行步驟（3）。

（2）重新選擇一個(gè)庫所，如果是重復(fù)節(jié)點(diǎn)，執(zhí)行步驟（3）；否則執(zhí)行步驟（1）。

（3）庫所sj為重復(fù)節(jié)點(diǎn)，如果選定庫所si，它的其中一個(gè)輸出變遷可以激發(fā)而產(chǎn)生的庫所為sj，那么令si＝sj，執(zhí)行步驟（1）。

重復(fù)執(zhí)行步驟（1）～（3）。

該算法得到DM＝｛μ1，…，μn｝，DS＝｛M1，…，Mn｝和A＝［a1，…，an］T。由于含有死鎖標(biāo)識(shí)的庫所集DS＝｛M1，…，Mi｝中可能存在重復(fù)向量，要對(duì)該庫所集簡化，從而可以得到一個(gè)新的含有死標(biāo)識(shí)的庫所集DS′＝｛M1，…，Ml｝。

2.2 構(gòu)造混合約束

利用上述的死鎖檢測算法，可以得到在死標(biāo)識(shí)狀態(tài)下含有死標(biāo)識(shí)的庫所集和死標(biāo)識(shí)數(shù)目。構(gòu)造庫所約束條件的主要思想是：只要在死標(biāo)識(shí)狀態(tài)下含有死標(biāo)識(shí)庫所中的標(biāo)識(shí)數(shù)目之和小于該死標(biāo)識(shí)總數(shù)，就可以得到一個(gè)關(guān)于約束庫所的約束條件，即Ci＝∑si≤ai－1，其中si是在標(biāo)識(shí)μi狀態(tài)下含有死標(biāo)識(shí)的庫所。這樣就構(gòu)造出一個(gè)庫所約束條件C＝Lrμr≤b。它的意義是如果這些庫所中的標(biāo)識(shí)數(shù)目之和不能大于或者等于死鎖標(biāo)識(shí)數(shù)時(shí)，那么該系統(tǒng)一定出現(xiàn)了死鎖。則庫所約束條件為：

其中，b＝min｛a1－1，…，ai－1｝。

通過對(duì)Petri網(wǎng)系統(tǒng)的基本性質(zhì)和運(yùn)行規(guī)律進(jìn)行分析和總結(jié)，不難得到產(chǎn)生死鎖的4個(gè)必要條件，即互斥、占有等待、不剝奪、環(huán)路等待。構(gòu)造變遷約束條件的主要思想是：選取的約束變遷對(duì)應(yīng)著庫所約束條件，使變遷不能同時(shí)激發(fā)，達(dá)到無死鎖狀態(tài)，即在變遷約束條件C＝λrqr≤c下，死鎖不能出現(xiàn)。不難看出，上述約束條件不是唯一的，只要破壞其中一個(gè)必要條件，系統(tǒng)就會(huì)無死鎖。則變遷約束條件為：

因此，根據(jù)上述庫所約束條件和變遷約束條件寫出混合約束，即

2.3 含有不可控變遷的控制器設(shè)計(jì)方法

如果一個(gè)變遷的激發(fā)不能通過外部的行為進(jìn)行禁止，那么則稱該變遷為不可控變遷。因?yàn)椴豢煽刈冞w只能由受控Petri網(wǎng)的結(jié)構(gòu)和狀態(tài)來決定，與外部環(huán)境無關(guān)，因此，如果Petri網(wǎng)系統(tǒng)中存在不可控變遷，需要對(duì)不可控變遷進(jìn)行等價(jià)變換才能對(duì)控制進(jìn)行設(shè)計(jì)，使得系統(tǒng)無死鎖。

給定一組約束，而且Petri網(wǎng)系統(tǒng)中存在不可控變遷，控制器可能會(huì)禁止不可控變遷的激發(fā)，那么則稱該約束為禁止約束，反之稱為允許約束。禁止約束必須要轉(zhuǎn)化為允許約束，才能計(jì)算控制器［8－9］。

2.4 不可控變遷的轉(zhuǎn)換

對(duì)形如C＝Lrμr＋λrqr≤b的混合約束轉(zhuǎn)換，有如下2種算法。

2.4.1 算法1

（1）對(duì)約束條件進(jìn)行約束轉(zhuǎn)換，轉(zhuǎn)化形式為Lrμr≤k和λrsr≤b－k，其中k∈［0，b］。

（2）檢測約束的允許性，即是否滿足條件LDuv≤0，其中Duv為關(guān)聯(lián)矩陣與不可控變遷的相關(guān)子集。如果該約束條件成立，那么該約束條件是允許約束，就不需要處理，直接進(jìn)行控制器設(shè)計(jì)；否則，執(zhí)行步驟（3）。

（3）如果LDuv＞0，那么它就為禁止約束?？梢詫rμr≤k轉(zhuǎn)化為一個(gè)允許約束，即L′μr≤k，使得L′Duv≤0成立，從而得到一個(gè)新的允許約束：C′＝L′μr＋λrqr。

通過矩陣變換的方法求新的系數(shù)方程L′，設(shè)

其中，I為對(duì)角矩陣，M（i，j）表示矩陣M中的第（i，j）個(gè)元素，令j＝1。

2.4.2 算法2

（1）若M（k＋h＋1…k＋h＋nc，j）中存在M（s，j）＞0，執(zhí)行步驟（2）；否則，令j＝j(luò)＋1，重新執(zhí)行步驟（1）。

（2）若M（1…k＋h，j）中不存在M（s，j）＞0，則不能設(shè)計(jì)出合法的控制器；否則找出min（｜M（k＋h＋1…k＋h＋nc），j｜），滿足M（q，j）＜0，執(zhí)行步驟（3）。

（3）如 果｜M（q，j）｜≥M（s，j），則 執(zhí) 行M（s，·）＝M（s，·）＋M（q，·）；否則執(zhí)行d＝floor（M（s，j）／｜M（q，j）｜）。

如果 mod（M（s，j），M（q，j））＝0成立，那么M（s，·）＋dM（q，·），否 則M（s，·）＝M（s，·）＋（d＋1）M（q，·）。

（4）重新執(zhí)行步驟（1），一直到M（k＋h＋1…k＋h＋nc，j）中不存在M（s，j）＞0；這時(shí)，M矩陣變換為：

從而得出L′＝R＋Lr。

2.5 避免死鎖的控制器設(shè)計(jì)步驟

為了更好地設(shè)計(jì)控制器，作如下假設(shè)：Petri網(wǎng)中存在引發(fā)死鎖變遷中某個(gè)或者某些變遷為不可控變遷；Petri網(wǎng)模型中無自環(huán)。

算法步驟如下：

（1）確定約束庫所Cs和約束變遷Ct。

（2）根據(jù)約束條件寫出約束庫所的局部關(guān)聯(lián)矩陣D0和系數(shù)矩陣L，為了進(jìn)行約束轉(zhuǎn)換，把D0擴(kuò)展為：

其中，h≥0，sm，…，sm＋h為與不可控變遷相關(guān)聯(lián)的非約束庫所。

（3）判斷約束的允許性，即是否滿足LDuv≤0。如果滿足條件就是約束條件，令L′＝L，執(zhí)行步驟（5），否則執(zhí)行步驟（4）。

（4）用等價(jià)變換的約束轉(zhuǎn)換算法把禁止約束轉(zhuǎn)化成新的允許約束：C′＝L′μr＋λrqr。

（5）控制器庫所的局部關(guān)聯(lián)矩陣為：Dc＝－Lr′D0。

（6）對(duì)控制器庫所的局部關(guān)聯(lián)矩陣Dc增加約束變遷行tr，在tr行中對(duì)應(yīng)約束變遷的位置上填寫1，其他位置寫0，即

對(duì)控制器的增廣局部關(guān)聯(lián)矩陣Dc′中的元素分布情況，可以根據(jù)以下規(guī)則構(gòu)建控制器庫所與變遷之間的流關(guān)系和權(quán)值：① 如果在約束變遷tr的元素1對(duì)應(yīng)著矩陣sc行的元素大于0，那么在控制器庫所sc與該變遷之間構(gòu)建一條雙向弧，控制器庫所sc是該變遷的輸出庫所；② 如果在約束變遷tr的元素1對(duì)應(yīng)著矩陣sc行的元素小于等于0，那么就在控制器庫所sc與該變遷之間構(gòu)建一條流關(guān)系，即控制器庫所是該變遷的輸入庫所；③ 如果在約束變遷tr的元素0對(duì)應(yīng)著矩陣sc行的元素小于0，那么在控制器庫所sc與該變遷之間構(gòu)建一條流關(guān)系，即控制器庫所是該變遷的輸入庫所；④ 如果在約束變遷tr的元素0對(duì)應(yīng)著矩陣sc行的元素大于等于0，那么在控制器庫所sc與該變遷之間構(gòu)建一條流關(guān)系，即控制器庫所是該變遷的輸出庫所；⑤當(dāng)一個(gè)變遷激發(fā)導(dǎo)致約束中的標(biāo)識(shí)數(shù)目減少時(shí)，就讓控制器庫所成為不可控變遷的輸入庫所的輸入變遷的一個(gè)輸入庫所。反之，控制器庫所成為該變遷的一個(gè)輸出庫所的輸出變遷的輸入庫所，以此來保證所有庫所中的標(biāo)識(shí)數(shù)目不變。

（7）計(jì)算控制器庫所增廣的初始標(biāo)識(shí)：μc0＝b′－L′μr0。

2.6 控制器設(shè)計(jì)的復(fù)雜性分析

本文采用的不可控變遷的約束轉(zhuǎn)換算法，與C－變換的約束轉(zhuǎn)換算法相比，不需要建立中間模型，并且用線性拆分和線性組合的方法代替C-變換和C－逆變換2個(gè)過程來進(jìn)行約束轉(zhuǎn)換。該算法用不等式計(jì)算，不需要進(jìn)行矩陣計(jì)算，大大減少了計(jì)算的復(fù)雜度和難度。本文中的控制器設(shè)計(jì)算法用局部關(guān)聯(lián)矩陣代替關(guān)聯(lián)矩陣，結(jié)合局部設(shè)計(jì)原則設(shè)計(jì)控制器，隨著系統(tǒng)的規(guī)模變大和結(jié)構(gòu)更復(fù)雜，控制器設(shè)計(jì)時(shí)的計(jì)算量大大減少。

3 應(yīng)用舉例

一個(gè)并發(fā)系統(tǒng)的簡單的Petri網(wǎng)系統(tǒng)，如圖1（實(shí)線部分）所示。

圖1 含有不可控變遷的Petri網(wǎng)預(yù)防死鎖的系統(tǒng)模型

該網(wǎng)系統(tǒng)存在死鎖，利用2.1所述算法，可以得到該P(yáng)etri網(wǎng)系統(tǒng)模型的死鎖標(biāo)識(shí)集合DM＝｛μ2，μ7｝、在死鎖標(biāo)識(shí)μ2和μ7狀態(tài)下含有死鎖標(biāo)識(shí)的庫所集都為M＝｛s2，s8｝和死鎖標(biāo)識(shí)數(shù)目a＝2。因?yàn)樵谒梨i標(biāo)識(shí)μ2和μ7產(chǎn)生時(shí)，含有死鎖標(biāo)識(shí)的庫所集都為M＝｛s2，s8｝，所以DS中只有一個(gè)向量。因此，可以構(gòu)造一個(gè)庫所約束條件為：

分析死鎖產(chǎn)生的原因，只要變遷t1和t7同時(shí)不能發(fā)生時(shí)，該系統(tǒng)就不會(huì)出現(xiàn)死鎖。因此，可以構(gòu)造一個(gè)變遷約束條件為：

可以根據(jù)庫所約束條件和變遷約束條件，構(gòu)造出混合約束為：

其中，約束庫所為Cs＝｛s2，s8｝；約束變遷為Ct＝｛t1，t7｝。

要想避免死鎖，就要在不等式約束μ2＋μ8＋q1＋q7≤1條件下設(shè)計(jì)控制器。假設(shè)t2為不可控變遷，設(shè)計(jì)控制器來實(shí)現(xiàn)下面的混合約束，使得該P(yáng)etri網(wǎng)不會(huì)出現(xiàn)死鎖［10－12］。

構(gòu)建局部關(guān)聯(lián)矩陣D和系數(shù)矩陣Lr：

由于t2為不可控變遷，所以Duv＝［－1，1，0］T。

因?yàn)長rDuv＝1＞0，則要進(jìn)行約束轉(zhuǎn)換。令

經(jīng)過變換后得到一個(gè)矩陣：

從而可以得到：

因?yàn)橐呀?jīng)把禁止約束轉(zhuǎn)化為允許約束，所以可以得出一個(gè)新的約束條件，即

從而可以得出控制器庫所的局部關(guān)聯(lián)矩陣：

控制器庫所的局部增廣關(guān)聯(lián)矩陣：

利用控制器庫所構(gòu)建流關(guān)系的規(guī)則，來構(gòu)建控制器庫所與之相連的變遷的流關(guān)系。同時(shí)求解出控制器庫所的初始標(biāo)識(shí)數(shù)目：

由圖1可見，sc為控制器庫所，虛線部分為控制器與相關(guān)變遷之間的流關(guān)系。

利用本文中改進(jìn)的可達(dá)標(biāo)識(shí)樹死鎖檢測算法進(jìn)行驗(yàn)證，得到DM＝?，DS＝?，｜A｜＝0。從而可以得出增加一個(gè)控制器庫所sc所得的Petri網(wǎng)就變成一個(gè)活網(wǎng)，死鎖檢測和預(yù)防過程完畢。

4 結(jié)束語

本文通過死鎖檢測算法檢測出死鎖標(biāo)識(shí)和對(duì)應(yīng)的庫所集，構(gòu)造庫所約束，結(jié)合產(chǎn)生死鎖的必要條件構(gòu)造變遷約束，從而得出一個(gè)混合約束。利用約束條件設(shè)計(jì)控制器，避免死鎖的發(fā)生。在文獻(xiàn)［13］的基礎(chǔ)上，考慮在Petri網(wǎng)中存在不可控變遷的情況下，提出了預(yù)防和避免死鎖的解決方法。通過線性不等式的等價(jià)轉(zhuǎn)換把禁止約束轉(zhuǎn)化為允許約束，得出新的約束條件，然后再設(shè)計(jì)控制器，達(dá)到預(yù)防和避免死鎖的目的。同時(shí)，本文在已給出的死鎖檢測方法的基礎(chǔ)上，采用了局部設(shè)計(jì)的原則設(shè)計(jì)控制器來預(yù)防和避免死鎖。由于只考慮與約束變遷和不可控變遷相關(guān)的庫所和變遷，使得計(jì)算量大大減少。

［1］畢 翔，韓江洪，王躍飛，等.面向PLC的離散事件控制系統(tǒng)設(shè)計(jì)方法研究［J］.合肥工業(yè)大學(xué)學(xué)報(bào)：自然科學(xué)版，2010，33（9）：1333－1337.

［2］吳哲輝.Petri網(wǎng)導(dǎo)論［M］.北京：機(jī)械工業(yè)出版社，2006：88－91.

［3］Moody J O，Antsaklis P J.Petri net supervisors for DES with uncontrollable and unobservable transitions［J］.IEEE Transactions on Automatic Control，2000，45 （3）：461－477.

［4］Iordache U V，Antsaklis P J.Synthesis of supervisors enforcing general linear constraints in petri nets［J］.IEEE Transactions on Automatic Control，2003，48（11）：2036－2039.

［5］林 闖.隨機(jī)Petri網(wǎng)和系統(tǒng)性能評(píng)價(jià)［M］.北京：清華大學(xué)出版社，2000：67－71.

［6］王衛(wèi)紅.建模與仿真［M］.北京：科學(xué)出版社，2002：74－76.

［7］Cui Huangqing，Wu Zhehui.PMI programs’petri net model and its dynamic properties［J］.Journal of System Simulation，2006，18（9）：2455－2460.

［8］Tanenbaum A S.Distributed operating system［M］.北京：清華大學(xué)出版社，1997：58－60.

［9］Han Yaojun，Wu Zhehui.Petri net－based serializability and deadlock detection in concurrency control of database［C］／／第十七屆全國數(shù)據(jù)庫學(xué)術(shù)會(huì)議論文集.河北保定：河北大學(xué)出版社，2000：104－106.

［10］Xing K Y，Tian F，Yang X J.Optimal deadlock avoidance petri net supervisors for automatic manufacturing system［J］.Journal of Control Theory and Applications，2007，5（2）：289－295.

［11］盧 超，盧炎生，謝曉東，等.一種基于依賴分析的并發(fā)程序潛在死鎖檢測算法［J］.小型微型計(jì)算機(jī)系統(tǒng)，2007，28（5）：841－844.

［12］周之英.現(xiàn)代軟件工程［M］.北京：科學(xué)出版社，2001：98－99.

［13］Yamalidou K，Moody J O，Lemmon M，et al.Feedback control of petri nets bases on place invariants［J］.Automatica，1999，32（1）：15－28.

Avoiding deadlock with uncontrollable transition in Petri net

WU Guo－feng， HU De－qi， AN Lei， ZHENG Li－liang
（School of Computer and Information，Hefei University of Technology，Hefei 230009，China）

To solve the deadlock problem of the distributed system in Petri net，this paper proposes a method to detect the deadlock by the analysis of the reachable marking tree and prevent it by the design of the Petri net controller.And a new view of mixed constraints is presented for the controller design.Furthermore，how to avoid deadlock in the circumstance of the uncontrollable transition with the design of Petri net controller is studied.

Petri net；controller；mixed constraint；deadlock

TP399

A

1003－5060（2012）04－0472－05

10.3969／j.issn.1003－5060.2012.04.009

2011－03－14；

2011－04－20

國家自然科學(xué)基金－廣東聯(lián)合基金重點(diǎn)資助項(xiàng)目（U1135003）

吳國鳳（1954－），女，安徽合肥人，合肥工業(yè)大學(xué)副教授，碩士生導(dǎo)師.

（責(zé)任編輯 呂 杰）