基于增廣有色Petri網帶封鎖機制的并發控制模型

陳彥舟 馮朝輝

中國人民公安大學信息安全系 北京 102600

0 引言

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

Petri網是一種能很好地描述和分析驗證系統動態性能的工具。研究人員們很自然地用Petri網去描述和學習并發控制系統。如在FMS中，Petri網得到很好的應用。文獻[1]通過建立并發事務共享數據資源的普通Petri網模型，探討了可串行化調度與死鎖檢測問題，但是當系統涉及的事務與數據資源較多時，所構造的Petri網模型過于復雜，出現狀態“爆炸”現象。

1 并發事務帶封鎖機制的增廣有色Petri網模型

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

定義1：抑制弧/容許弧

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

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

定義2：設PI(P∏)表示與抑制弧(容許弧)關聯的庫所之集合，t在M下可使能發生，當且僅當：

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

2 建立ECPN_LM模型

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

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

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

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)與各事務相對應；顏色(Dj)(1≤j≤m)與各共享資源相對應；顏色(R)與(W)分別對應讀操作和寫操作；顏色(Sj)與(Xj)(1≤j≤m)分別對應各共享資源的共享鎖和排它鎖；顏色(Tli)(1≤i≤n)對應各事務完成讀或寫離開；顏色(Ti,R,Dj)(1≤i≤n且1≤j≤m)表示事務Ti讀共享資源Dj；顏色(Ti,W,Dj)(1≤i≤n且1≤j≤m)表示事務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)可有三個狀態：無任何操作，被加了共享鎖，被加了排它鎖。當事務在讀預備狀態ppr時，如果事務操作滿足ts(此時對于共享資源Dj來說，它沒有被加排它鎖((Xj)∈M(px))，且沒有被加共享鎖((Sj)∈M(ps)))，那么事務申請共享鎖(ts使能發生)，同時做M(ps) - (Sj)：代表已對Dj加共享鎖。當此事務在讀共享資源Dj時，另一事務也進入讀預備狀態ppr。此時，ts不滿足使能條件，而tus使能發生(因為對已加共享鎖的資源Dj來說，其它進程可對它進行讀操作，而不必再申請鎖)。當庫所ppr，ppw，pew為空時，代表最后一個讀資源Dj的事務離開了且同時符合 2 PL協議(接下來會談到)。此時，tsu使能發生，釋放共享鎖。根據寫操作原則，對共享資源Dj的寫操作每時每刻都只能有一個，所以當事務Ti在寫預備狀態ppw時，若對想寫的共享資源Dj(Dj已加共享鎖((Sj)?M(ps))，又或者先前已有事務對Dj加了排它鎖((Xj)?M(px)))，那么tx不能發生。否則tx將使能發生并對資源Dj加排它鎖。當Ti進入寫操作狀態pw后，只有符合2PL協議后，twl才使能發生，解開排它鎖。

3.2 寫者優先分析

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

3.3 滿足2PL協議分析

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

3.4 系統無活鎖分析

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

3.5 死鎖檢測分析

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

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

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

系統出現死鎖狀態，所以若調度從M。到端點M′或者M′的路徑上的變遷列組成，則系統會出現死鎖狀態。

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

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

4 結論

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

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

[2]韓耀軍,蔣昌俊,羅雪梅.數據庫系統并發控制的擴展有色Petri網方法[J].同濟大學學報(自然科學版).2004.

[3]韓耀軍,羅雪梅,蔣昌俊.擴展 Petri網在實時數據庫并發控制中的應用[J].系統仿真學報.2003.

[4]左鳳朝.基于Petri網的數據庫系統并發控制模型[J].計算機工程與應用.2002.