基于增廣有色Petri網(wǎng)帶封鎖機制的并發(fā)控制模型

陳彥舟 馮朝輝

中國人民公安大學(xué)信息安全系 北京 102600

0 引言

數(shù)據(jù)庫管理系統(tǒng)(DBMS)的一個主要功能是進行數(shù)據(jù)控制，其中并發(fā)控制又是數(shù)據(jù)控制當(dāng)中的一個重要內(nèi)容。并發(fā)控制要解決的問題就是串行化調(diào)度與死鎖檢測，進而破壞死鎖，使系統(tǒng)得以繼續(xù)運行。通常使用各種協(xié)議來對并發(fā)事務(wù)對數(shù)據(jù)庫的訪問進行控制。目前最常用的封鎖協(xié)議是2PL協(xié)議。但是滿足2PL協(xié)議的調(diào)度卻有可能會帶來死鎖和活鎖問題。

Petri網(wǎng)是一種能很好地描述和分析驗證系統(tǒng)動態(tài)性能的工具。研究人員們很自然地用Petri網(wǎng)去描述和學(xué)習(xí)并發(fā)控制系統(tǒng)。如在FMS中，Petri網(wǎng)得到很好的應(yīng)用。文獻[1]通過建立并發(fā)事務(wù)共享數(shù)據(jù)資源的普通Petri網(wǎng)模型，探討了可串行化調(diào)度與死鎖檢測問題，但是當(dāng)系統(tǒng)涉及的事務(wù)與數(shù)據(jù)資源較多時，所構(gòu)造的Petri網(wǎng)模型過于復(fù)雜，出現(xiàn)狀態(tài)“爆炸”現(xiàn)象。

1 并發(fā)事務(wù)帶封鎖機制的增廣有色Petri網(wǎng)模型

本文討論的數(shù)據(jù)庫系統(tǒng)有n個并發(fā)事務(wù)Ti(1 ≤i≤n)和m個共享資源Dj(1 ≤j≤m)。各事務(wù)對共享資源的加鎖情況用矩陣Ln×m表示元素lij定義如下：

定義1：抑制弧/容許弧

（1）FI? (P×T)為抑制弧集，F(xiàn)∏? (P×T)為容許弧集，且FI∩F∏=φ，(FI∪F∏) ∩F=φ；

（2）W: (FI∪F∏) → {0}。

定義2：設(shè)PI(P∏)表示與抑制弧(容許弧)關(guān)聯(lián)的庫所之集合，t在M下可使能發(fā)生，當(dāng)且僅當(dāng)：

若M[t＞，則t在M下可以使能發(fā)生M[t＞M′，則M′的定義是：

2 建立ECPN_LM模型

定義 3：一個描述并發(fā)事務(wù)競爭共享資源的帶封鎖機制的擴展有色Petri網(wǎng)是一個九元組：

ECPN_LM=(P，T；F，F(xiàn)I，F(xiàn)∏，C，I-，I+，M。)

其中：P是庫所的有限集合；T是變遷的有限集合；F=PT∪TP是普通有向弧的有限集合；FI是抑制弧集合；F∏是容許弧集合；C是顏色集合；I-是PT上的負函數(shù)；I+是 P T上的正函數(shù)，它們的規(guī)則與含義如下：pd是可利用共享資源；per是各事務(wù)申請對各共享資源加共享鎖情況；pew是各事務(wù)申請對各共享資源加排它鎖情況；pdr是事務(wù)等待讀共享資源狀態(tài)；ppr是事務(wù)準(zhǔn)備讀共享資源狀態(tài)；ppw是事務(wù)準(zhǔn)備寫共享資源狀態(tài)；pr是事務(wù)讀共享資源狀態(tài)；pw是事務(wù)寫共享資源狀態(tài)；psl是第一個事務(wù)對同一共享資源加共享鎖狀態(tài)；ps是共享鎖；px是排它鎖；pl是 事務(wù)完成讀或?qū)懖僮骱箅x開狀態(tài)。tdr是事務(wù)進入等待狀態(tài)；tpr是事務(wù)準(zhǔn)備讀；tpw是事務(wù)準(zhǔn)備寫；tdpr是等待的事務(wù)準(zhǔn)備讀；tus是事務(wù)不申請共享鎖；ts是事務(wù)申請共享鎖(第一個對此共享資源加的共享鎖)；tx是事務(wù)申請排它鎖；tsu是事務(wù)解開共享鎖；trl是事務(wù)完成讀后準(zhǔn)備離開；twl是事務(wù)完成寫后準(zhǔn)備離開。

F={(per,tpr)，(pew,tpw)，(pd,tpr)，(pd,tpw)，(tpr,pd)，(tpw,pd)，(tpr,ppr)，(tpw,ppw)，(ppr,tus)，(ppr,ts)，(ppw,tx)，(ps,ts)，(px,tx)，(tus,pr)，(ts,pr)，(ts,psl)，(psl,tsu)，(tsu,ps)，(tx,pw)，(twl,px)，(pw,twl)，(pr,trl)，(trl,pl)，(twl,pl)，(per,tdr) ，(tdr,pdr)，(pdr,tdpr)，(tdpr,ppr)}。

FI={(ppw,tpr)，(pdr,tpr)，(ppw,tdpr)，(ps,tus)，(ppr,tsu)，(ppw,tsu)，(pew,tsu)，(pdr,twl)，(per,twl)，(pew,trl)，(ppw,trl)}。

F∏={(ppw,tdr)，(px,tus)，(px,ts)，(ps,tx)}。

C={(T1)，(T2)，… ，(Tn)，(D1)，(D2)，… ，(Dm)，(R)，(W)，(S1)，(S2)，… ，(Sm)，(X1)，(X2)，… ，(Xm)，(Tl1)，(Tl2)，…，(Tln)}，顏色(Ti)(1≤i≤n)與各事務(wù)相對應(yīng)；顏色(Dj)(1≤j≤m)與各共享資源相對應(yīng)；顏色(R)與(W)分別對應(yīng)讀操作和寫操作；顏色(Sj)與(Xj)(1≤j≤m)分別對應(yīng)各共享資源的共享鎖和排它鎖；顏色(Tli)(1≤i≤n)對應(yīng)各事務(wù)完成讀或?qū)戨x開；顏色(Ti,R,Dj)(1≤i≤n且1≤j≤m)表示事務(wù)Ti讀共享資源Dj；顏色(Ti,W,Dj)(1≤i≤n且1≤j≤m)表示事務(wù)Ti寫共享資源Dj。

F1=I-(per,tpr/ (Ti,R,Dj) ) = (Ti,R,Dj) , (lij= 1 , 1 ≤i≤n,1≤j≤m)

F2=I-(pew,tpw/(Ti,W,Dj) ) = (Ti,W,Dj) , (lij= - 1 , 1 ≤i≤n,1≤j≤m)

F3=I-(pd,tpr/(Ti,R,Dj) ) = (Dj) , (lij= 1 , 1 ≤i≤n, 1 ≤j≤m)

F4=I-(pd,tpw/(Ti,W,Dj) ) = (Dj) , (lij= - 1 , 1 ≤i≤n,1≤j≤m)

F9=I-(ppr,tus/(Ti,R,Dj) ) = (Ti,R,Dj) , (lij= 1 , 1 ≤i≤n,1≤j≤m)

F10=I-(ppr,ts/(Ti,R,Dj) ) = (Ti,R,Dj) , (lij= 1 , 1 ≤i≤n,1≤j≤m)

F11=I-(ppw,tx/(Ti,W,Dj) ) = (Ti,W,Dj) , (lij= -1 , 1 ≤i≤n,1≤j≤m)

F12=I-(ps,ts/(Ti,R,Dj) ) = (Sj) , (lij= 1 , 1 ≤i≤n, 1 ≤j≤m)

F13=I-(px,tx/ (Ti,W,Dj) ) = (Xj) , (lij= -1 , 1 ≤i≤n,1≤j≤m)

F17=I-(psl,tsu/ (Sj) ) = (Sj) , (lij= 1 , 1 ≤i≤n, 1 ≤j≤m)

F21=I-(pw,twl/ (Ti,W,Dj) ) = (Ti,W,Dj) , (lij= - 1 , 1 ≤i≤n,1≤j≤m)

F22=I-(pr,trl/ (Ti,R,Dj) ) = (Ti,R,Dj) , (lij= 1 , 1 ≤i≤n,1≤j≤m)

F25=I-(per,tdr/ (Ti,R,Dj))= (Ti,R,Dj),(lij= 1 , 1 ≤i≤n, 1≤j≤m)

F27=I-(pdr,tdpr/ (Ti,R,Dj)) = (Ti,R,Dj),(lij= 1 , 1 ≤i≤n,1≤j≤m)

F5=I+(pd,tpr/ (Ti,R,Dj)) = (Dj) , (lij= 1 , 1 ≤i≤n, 1 ≤j≤m)

F6=I+(pd,tpw/(Ti,W,Dj) ) = (Dj) , (lij= -1 , 1 ≤i≤n,1≤j≤m)

F7=I+(ppr,tpr/ (Ti,R,Dj) ) = (Ti,R,Dj) , (lij= 1 , 1 ≤i≤n,1≤j≤m)

F8=I+(ppw,tpw/(Ti,W,Dj) ) = (Ti,W,Dj) , (lij= - 1 , 1 ≤i≤n,1≤j≤m)

F14=I+(pr,tus/(Ti,R,Dj))= (Ti,R,Dj) , (lij= 1 , 1 ≤i≤n,1≤j≤m)

F15=I+(pr,ts/ (Ti,R,Dj) ) = (Ti,R,Dj) , (lij= 1 , 1 ≤i≤n,1≤j≤m)

F16=I+(psl,ts/ (Ti,R,Dj) ) = (Sj) ,(lij= 1 , 1 ≤i≤n, 1 ≤j≤m)

F18=I+(ps,tsu/ (Sj) ) = (Sj) , (lij= 1 , 1 ≤i≤n, 1 ≤j≤m)

F19=I+(pw,tx/ (Ti,W,Dj) ) = (Ti,W,Dj) , (lij= - 1 , 1 ≤i≤n,1≤j≤m)

F20=I+(px,twl/ (Ti,W,Dj) ) = (Xj) ,(lij= -1 , 1 ≤i≤n,1≤j≤m)

F23=I+(pl,trl/ (Ti,R,Dj) ) = (Tli) , (lij= 1 , 1 ≤i≤n, 1 ≤j≤m)

F24=I+(pl,twl/ (Ti,W,Dj) ) = (Tli) , (lij= -1 , 1 ≤i≤n,1≤j≤m)

F26=I+(pdr,tdr/ (Ti,R,Dj) ) = (Ti,R,Dj) , (lij= 1 , 1 ≤i≤n,1≤j≤m)

F28=I+(ppr,tdpr/ (Ti,R,Dj) ) = (Ti,R,Dj) , (lij= 1 , 1 ≤i≤n,1≤j≤m)

FI1=I-(ppw,tpr/ (Ti,R,Dj) ) = { (Tk,W,Dj) } ∩M(ppw) , (lij=1,lkj= -1,1 ≤i,k≤n, 1 ≤j≤m)

FI2=I-(pdr,tpr/ (Ti,R,Dj) ) = { (Tk,R,Dj) } ∩M(pdr) ,(lij=lkj=1,1 ≤i,k≤n, 1 ≤j≤m)

FI3=I-(ppw,tdpr/ (Ti,R,Dj) ) = { (Tk,W,Dj) } ∩M(ppw),(lij= 1 ,lkj= -1,1 ≤i,k≤n, 1 ≤j≤m)

FI4=I-(ps,tus/ (Ti,R,Dj) ) =M(ps) ,(lij= 1 , 1 ≤i≤n,1≤j≤m)

FI5=I-(ppr,tsu/ (Sj) ) = { (Tk,R,Dj) } ∩M(ppr) ,(lkj=1,1 ≤k≤n, 1 ≤j≤m)

FI6=I-(ppw,tsu/ (Sj) ) = ( { (Ti,W,Dk) } ∩M(ppw))∧

({(Ti,R,Dj) } ∩M(pr) ),(lij= 1 ,lik= -1,1 ≤i≤n, 1 ≤j,k≤m)

FI7=I-(pew,tsu/ (Sj) ) = ( { (Ti,W,Dk) } ∩M(pew))∧

({(Ti,R,Dj) } ∩M(pr) ),(lij= 1 ,lik=-1,1 ≤i≤n, 1 ≤j,k≤m)

FI8=I-(pdr,twl/ (Ti,W,Dj) ) = { (Ti,R,Dk) } ∩M(pdr) ,(lij=- 1 ,lik= 1,1 ≤i≤n, 1 ≤j,k≤m)

FI9=I-(per,twl/ (Ti,W,Dj) ) = { (Ti,R,Dk) } ∩M(per) ,(lij=- 1 ,lik= 1,1 ≤i≤n, 1 ≤j,k≤m)

FI10=I-(pew,trl/ (Ti,R,Dj) ) = { (Ti,W,Dk) } ∩M(pew),(lij= 1 ,lik= -1,1 ≤i≤n, 1 ≤j,k≤m)

FI11=I-(ppw,trl/ (Ti,R,Dj) ) = { (Ti,W,Dk) } ∩M(ppw),(lij= 1 ,lik= -1,1 ≤i≤n, 1 ≤j,k≤m)

F∏1=I-(ppw,tdr/ (Ti,R,Dj) ) = { (Tk,W,Dj) } ∩M(ppw),(lij= 1 ,lik= -1,1 ≤i,k≤n, 1 ≤j≤m)

F∏2=I-(px,tus/ (Ti,R,Dj) ) = { (Xj) } ∩M(px) ,(lij=1,1≤i≤n, 1 ≤j≤m)

F∏3=I-(px,ts/ (Ti,R,Dj) ) = { (Xj) } ∩M(px) ,(lij=1,1≤i≤n, 1 ≤j≤m)

F∏4=I-(ps,tx/ (Ti,R,Dj) ) = { (Sj) } ∩M(ps) ,(lij=-1,

1 ≤i≤n, 1 ≤j≤m)

3 模型分析與驗證

3.1 封鎖機制的正確性分析

由 E CPN_LM模型可知，對于一個共享資源Dj(1≤j≤m)可有三個狀態(tài)：無任何操作，被加了共享鎖，被加了排它鎖。當(dāng)事務(wù)在讀預(yù)備狀態(tài)ppr時，如果事務(wù)操作滿足ts(此時對于共享資源Dj來說，它沒有被加排它鎖((Xj)∈M(px))，且沒有被加共享鎖((Sj)∈M(ps)))，那么事務(wù)申請共享鎖(ts使能發(fā)生)，同時做M(ps) - (Sj)：代表已對Dj加共享鎖。當(dāng)此事務(wù)在讀共享資源Dj時，另一事務(wù)也進入讀預(yù)備狀態(tài)ppr。此時，ts不滿足使能條件，而tus使能發(fā)生(因為對已加共享鎖的資源Dj來說，其它進程可對它進行讀操作，而不必再申請鎖)。當(dāng)庫所ppr，ppw，pew為空時，代表最后一個讀資源Dj的事務(wù)離開了且同時符合 2 PL協(xié)議(接下來會談到)。此時，tsu使能發(fā)生，釋放共享鎖。根據(jù)寫操作原則，對共享資源Dj的寫操作每時每刻都只能有一個，所以當(dāng)事務(wù)Ti在寫預(yù)備狀態(tài)ppw時，若對想寫的共享資源Dj(Dj已加共享鎖((Sj)?M(ps))，又或者先前已有事務(wù)對Dj加了排它鎖((Xj)?M(px)))，那么tx不能發(fā)生。否則tx將使能發(fā)生并對資源Dj加排它鎖。當(dāng)Ti進入寫操作狀態(tài)pw后，只有符合2PL協(xié)議后，twl才使能發(fā)生，解開排它鎖。

3.2 寫者優(yōu)先分析

在ECPN_LM模型中，當(dāng)某時刻有事務(wù)Ti(1≤i≤n)要對Dj(1≤j≤m)進行寫操作，此時來到寫預(yù)備狀態(tài)，并通過抑制弧抑制后來的想對共享資源Dj進行讀操作的事務(wù)。若系統(tǒng)內(nèi)已存在對資源Dj進行讀操作的事務(wù)((Sj)?M(ps))，那么tx不能發(fā)生，只有這些讀Dj的事務(wù)全部讀完并離開((Sj)∈M(ps))時，tx才能發(fā)生。然后事務(wù)Ti對資源Dj加排它鎖，并且進入寫操作pw，而此時其它想對共享資源Dj進行讀操作的事務(wù)可進入讀預(yù)備狀態(tài)ppr并等待共享鎖。

3.3 滿足2PL協(xié)議分析

在ECPN_LM模型中，由FI6，F(xiàn)I7，F(xiàn)I8，F(xiàn)I9四條抑制弧來保證調(diào)度滿足 2PL。變遷tsu要想在(Sj) (即最后一個事務(wù)解除對共享資源Dj所加的共享鎖)情況下發(fā)生，那么庫所pew，ppw中的標(biāo)識和庫所ppr中的標(biāo)識必須被全部移走，即事務(wù)Ti只有在獲得所需的全部鎖之后才能解除其對共享資源Dj所加的共享鎖。而當(dāng)tl發(fā)生后，事務(wù)Ti不再有讀寫操作。同理，變遷twl要想在(Xj) (即事務(wù)解除對共享資源Dj所加的排它鎖)情況下發(fā)生，那么庫所per，pdr中的標(biāo)識必須被全部移走，即事務(wù)Ti只有在獲得所需的全部鎖之后才能解除其對共享資源Dj所加的排它鎖。因此其變遷發(fā)生的序列所對應(yīng)的調(diào)度滿足2PL。

3.4 系統(tǒng)無活鎖分析

在 ECPN_LM 模型中，若有事務(wù)欲對共享資源Dj(1≤j≤m)進行寫操作，且此事務(wù)已進入寫預(yù)備狀態(tài)ppw，那么往后所有欲對共享資源Dj進行讀操作的事務(wù)將進入等待狀態(tài)pdr(由抑制弧FI1和容許弧F∏1實現(xiàn))。當(dāng)寫Dj的事務(wù)進入寫操作(tx使能發(fā)生)時，所有因等待讀Dj的等待事務(wù)進入讀預(yù)備狀態(tài)ppr，且通過抑制弧FI2實現(xiàn)先來先服務(wù)。注：庫所pdr的標(biāo)識的顏色集按隊列排隊。

3.5 死鎖檢測分析

設(shè)調(diào)度s由 R MG(ECPN_LM)中從M。到端點M的路徑上的變遷列組成的，則s是死鎖狀態(tài)，當(dāng)且僅當(dāng)M(pr) ≠ 0或M(pw) ≠ 0 。注：可達標(biāo)識圖 RMG(ECPN_LM)可由文獻[2]中所提到的算法構(gòu)造。

假設(shè)s是死鎖狀態(tài)，說明s中必存在兩個以上的事務(wù)，它們由于相互擁有對方所需資源的鎖而無法運行。

假設(shè)數(shù)據(jù)庫系統(tǒng)有兩個并發(fā)事務(wù)(T1,T2)，競爭兩個共享資源(D1,D2)，其中T1要求對資源D1加共享鎖，對資源D2加排它鎖；T2要求對資源D1加排它鎖，對資源D2加共享鎖，加鎖矩陣為那么按ECPN_LM模型運行至以下任一種情況：

系統(tǒng)出現(xiàn)死鎖狀態(tài)，所以若調(diào)度從M。到端點M′或者M′的路徑上的變遷列組成，則系統(tǒng)會出現(xiàn)死鎖狀態(tài)。

若按ECPN_LM模型運行至以下情況：

(Tl1) + (Tl2))，系統(tǒng)不出現(xiàn)死鎖狀態(tài)，所以若調(diào)度由從M。到端點M′的路徑上的變遷序列組成，則系統(tǒng)不會出現(xiàn)死鎖狀態(tài)，且該調(diào)度為可串行化調(diào)度。

4 結(jié)論

本模型在一定程度上有適用性，但還有很多問題沒有解決，如：用戶優(yōu)先級問題，中斷處理問題，安全性檢測問題，數(shù)據(jù)恢復(fù)問題。所以很多問題還需進一步探討。

[1]HAN Yao-jun.WU Zhe-hui.Petri net-based serializability and deadlock detection in concurrency control of database[A].第十七屆全國數(shù)據(jù)庫學(xué)術(shù)會議論文集[c].保定:河北大學(xué)出版社.2000.

[2]韓耀軍,蔣昌俊,羅雪梅.數(shù)據(jù)庫系統(tǒng)并發(fā)控制的擴展有色Petri網(wǎng)方法[J].同濟大學(xué)學(xué)報(自然科學(xué)版).2004.

[3]韓耀軍,羅雪梅,蔣昌俊.擴展 Petri網(wǎng)在實時數(shù)據(jù)庫并發(fā)控制中的應(yīng)用[J].系統(tǒng)仿真學(xué)報.2003.

[4]左鳳朝.基于Petri網(wǎng)的數(shù)據(jù)庫系統(tǒng)并發(fā)控制模型[J].計算機工程與應(yīng)用.2002.