[發(fā)明專利]確保時態(tài)一致性的實時并發(fā)控制方法

無效

• 申請?zhí)枺?/td>: 201010132642.9
• 申請日: 2010-03-26
• 公開（公告）號: CN101814091A
• 公開（公告）日: 2010-08-25
• 發(fā)明（設(shè)計）人: 肖迎元;尹波;申艷;劉鳳連
• 申請（專利權(quán)）人: 天津理工大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 天津佳盟知識產(chǎn)權(quán)代理有限公司 12002
• 代理人: 侯力

1.一種確保時態(tài)一致性的實時并發(fā)控制方法，其特征在于，該方法具體描述如下：

第1、時態(tài)一致性的形式化定義

第1.1、本發(fā)明方法描述中將使用的一些符號及其含義：

符號?????????含義

t????????????系統(tǒng)中的任一事務(wù)

Op_i??????????事務(wù)對數(shù)據(jù)對象的一次讀或?qū)懖僮?/p>

DS(t)????????t需要存取的時態(tài)數(shù)據(jù)對象的集合

DS₁(t)???????t已存取的時態(tài)數(shù)據(jù)對象的集合

DS₂(t)???????t尚未存取的時態(tài)數(shù)據(jù)對象的集合

T(t，X_i)?????t訪問時態(tài)數(shù)據(jù)對象X_i的時刻

V(t，X_i)?????t訪問X_i時，X_i的狀態(tài)(值)

V(Op_i，X)????表示Op_i作用在數(shù)據(jù)對象X上的值

表示Op_i和Op_r是作用在數(shù)據(jù)對象X上的一對沖突操作

P(t)?????????t的優(yōu)先級

????????????????????????????????????????；

第1.2、定義1時態(tài)數(shù)據(jù)對象：時態(tài)數(shù)據(jù)對象X定義為一個三元組：X::＝＜V(X)，ST(X)，VI(X)＞；其中，V(X)表示X的當前狀態(tài)或值；ST(X)表示采樣時刻，即采樣X所對應(yīng)的外部客觀環(huán)境某一特征量的時間；VI(X)表示X的有效期，即自ST(X)算起，V(X)具有有效性的時間長度；

第1.3、定義2外部一致性：時態(tài)數(shù)據(jù)對象X被稱為滿足外部一致性，如果有ST(X)+VI(X)≥T_c成立，這里，T_c表示當前時刻；

第1.4、定義3相互關(guān)聯(lián)集：用來做決策或?qū)С鲂聰?shù)據(jù)的一組時態(tài)數(shù)據(jù)對象稱為一個相互關(guān)聯(lián)集；

第1.5、定義4相互一致性：設(shè)R＝{X₁，X₂，...，X_m}是一個相互關(guān)聯(lián)集，V(R)表示R中時態(tài)對象在某一時刻值的集合，即V(R)＝{V(X₁)，V(X₂)，...，V(X_m)}；若如下條件成立：V(X_j)∈V(R)(|ST(X_i)-ST(Y_j)|≤R_mvi)，則稱V(R)滿足相互一致性；這里，R_mvi為R的關(guān)聯(lián)有效期，它的取值因應(yīng)用語義而定，通常R_mvi取R中所有時態(tài)對象有效期的最小值；

第1.6、定義5數(shù)據(jù)的時態(tài)一致性：若一個時態(tài)數(shù)據(jù)對象既滿足外部一致性又是相互一致性的，則稱它滿足時態(tài)一致性；

第1.7、定義6事務(wù)的時態(tài)一致性：假定DS(t)＝{X₁，X₂，...，X_m}，若事務(wù)t同時滿足下列條件：

(1)---∀Xi∈DS(t)(T(t,Xi)<ST(Xi)+VI(Xi))]]>

(2){V(t，X₁)，V(t，X₂)，...，V(t，X_m)}滿足相互一致性

則稱事務(wù)t滿足時態(tài)一致性；

第2、數(shù)據(jù)相似與操作相似的形式化定義

第2.1、定義7沖突事務(wù)對：設(shè)t_r和t_h為并發(fā)執(zhí)行的一對事務(wù)，若存在Op_i∈t_r，Op_j∈t_h，Op_i和Op_j作用在同一數(shù)據(jù)對象上且有一個為寫操作，則稱t_r和t_h為一沖突事務(wù)對；

第2.2、定義8數(shù)據(jù)相似：對于時態(tài)數(shù)據(jù)對象X的兩個取值V₁(X)和V₂(X)，若下面條件滿足：

|f(V₁(X)-f(V₂(X))|≤α

則稱V₁(X)和V₂(X)是數(shù)據(jù)相似的，記為：V₁(X)≈V₂(X)；這里，f表示從X的取值集合到實數(shù)集的一個映射；α為預先定義的相似閾值；

第2.3、定義9操作相似：設(shè)t_m和t_n為并發(fā)執(zhí)行的一對事務(wù)，Op_i∈t_m和Op_j∈t_n且Op_i和Op_j為作用在同一數(shù)據(jù)對象X上，若下列條件滿足：

V(Op_i，X)≈V(Op_j，X)

則稱Op_i和Op_j是操作相似的，記為：Op_i≈Op_j；

第3、數(shù)據(jù)庫狀態(tài)相似與相似可串行化

第3.1、定義10數(shù)據(jù)庫狀態(tài)相似：假定SD_i，SD_j分別表示數(shù)據(jù)庫在兩不同時刻的數(shù)據(jù)值的集合，X表示某一時態(tài)數(shù)據(jù)對象，V_i(X)表示X在SD_i中的值，V_j(X)表示X在SD_j中的值，若下面條件滿足：則稱SD_i和SD_j狀態(tài)相似，記為：SD_i≈SD_j；

第3.2、定義11相似可串行化：假定Sch_a是并發(fā)事務(wù)集{t₁?t₂，...，t_n}的一個調(diào)度，SD_a是Sch_a產(chǎn)生的數(shù)據(jù)庫的一個狀態(tài)，若下面的條件滿足：則稱Sch_a是相似可串行化的；這里，Sch_b表示某一串行調(diào)度；SD_b表示Sch_b產(chǎn)生的數(shù)據(jù)庫的一個狀態(tài)；

第4、基于相似性的數(shù)據(jù)沖突解決策略

第4.1、鎖類型定義及鎖相容性矩陣

基于相似性思想，進一步對傳統(tǒng)的鎖類型進行擴展，在現(xiàn)有的R讀鎖、W寫鎖基礎(chǔ)上新增了SR相似讀鎖和SW相似寫鎖，并給出了鎖相容性矩陣：

其中，Y表示“允許”，N表示“不允許”

第4.2、數(shù)據(jù)沖突解決策略

當一事務(wù)對某個時態(tài)數(shù)據(jù)對象執(zhí)行讀操作或?qū)懖僮鲿r，它首先申請該數(shù)據(jù)對象上的R鎖或W鎖，若調(diào)度器Scheduler沒檢測到操作沖突，它授予該事務(wù)相應(yīng)的鎖；若檢測到操作沖突，它判斷沖突操作是否為相似操作，若為相似操作，則授予相應(yīng)的SR鎖或SW鎖；當沖突操作為相似性操作時，申請SR鎖或SW鎖不與其它任何鎖沖突；

假定Op_i和Op_j是一對作用在數(shù)據(jù)對象X上的并發(fā)操作，并假定Op_j已持有對X的訪問權(quán)限，而Op_i正在請求對X的訪問權(quán)限，對數(shù)據(jù)沖突的解決采用如下策略：

策略1：假定Op_i和Op_j為一對寫-寫沖突操作，若有Op_i≈Op_j，則Op_i立即獲得對X的訪問權(quán)限而不管Op_j是否釋放對X的訪問權(quán)限。

策略2：假定Op_i和Op_j為一對寫-讀沖突操作，若有V(Op_i，X)≈V(Op_j，X)，則Op_i立即獲得對X的訪問權(quán)限而不管Op_j是否釋放對X的訪問權(quán)限；

在策略1和策略2中，Op_i被稱為相對于Op_j的相似寫操作，記作

策略3：假定Op_i和Op_j為一對讀-寫沖突操作，若有V(Op_j，X)≈BeforeImage(Op_j，X)，則Op_i立即獲得對X的訪問權(quán)限而不管Op_j是否釋放對X的訪問權(quán)限；這里，BeforeImage(Op_j，X)代表數(shù)據(jù)對象X在操作Op_j前的值；

在策略3中，Op_i被稱為相對于Op_j的相似讀操作，記作

第5、確保時態(tài)一致性的實時并發(fā)控制方法

定義12假定ST代表與事務(wù)t_r并發(fā)執(zhí)行的事務(wù)的集合，假定X為一時態(tài)數(shù)據(jù)對象，若條件：成立，則稱ST₁為作用在X上的t_r的最大沖突事務(wù)集；

假定t_r為正在請求對X_i上鎖的事務(wù)，Op_i為t_r的作用在X_i上的操作；ST₁為事務(wù)t_r的作用在X_i上的最大沖突事務(wù)集；ST_h表示ST₁中已持有X_i的鎖的事務(wù)集合；Max(P(ST_h))表示ST_h中事務(wù)的最高優(yōu)先級；SO_h表示持有X_i上的鎖并與Op_i沖突的操作的集合，即SO_h1表示屬于SO_h的寫操作的集合；

確保時態(tài)一致性的實時并發(fā)控制方法的具體實現(xiàn)算法描述如下：

Begin

1.If(P(t_r)＞Max(P(ST_h)))

2.If((DS₁(t_r)∪{X_i}滿足相互一致性)∧(T(t_r，X_i)＜SI(X_i)+VI(X_i)))

4.t_r獲得相應(yīng)的SW鎖或SR鎖；

5.Else

6.夭折ST_h中與Op_i不滿足操作相似性的事務(wù)，而讓t_r獲得它正在請求的鎖；

7.Else

8.t_r被夭折；

9.Else

10.If((DS₁(t_r)∪{X_i}滿足相互一致性)∧(T(t_r，X_i)＜SI(X_i)+VI(X_i)))

12.t_r獲得相應(yīng)的SW鎖或SR鎖；

13.Else

14.t_r被阻塞；

15.Else

16.t_r被夭折；

End。