程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 數據庫知識 >> SyBase數據庫 >> SyBase教程 >> 數據庫-並發調度的可串行性

數據庫-並發調度的可串行性

編輯:SyBase教程

數據庫-並發調度的可串行性


並發調度的可串行性

DBMS對並發事務不同的調度(schedule)可能會產生不同的結果
什麼樣的調度是正確的?

串行化(Serial)調度是正確的
對於串行調度,各個事務的操作沒有交叉,也就沒有相互干擾,當然也不會產生並發所引起的。如前所述,事務對數據庫的作用是將數據庫從一個一致的狀態轉變為另一個一致的狀態。多個事務串行執行後,數據庫仍舊保持一致的狀態。

可串行化(Serializable)調度
多個事務的並發執行是正確的,當且僅當其結果與按某一次序串行地執行這些事務時的結果相同。可串行化調度當然也保持數據庫的一致狀態

[例]現在有兩個事務,分別包含下列操作:
事務T1:讀B;A=B+1;寫回A
事務T2:讀A;B=A+1;寫回B
現給出對這兩個事務不同的調度策略 

可串行性(Serializability)
是並發事務正確調度的准則。在RDBMS中,作為並發控制的正確性准則。一個給定的並發調度,當且僅當它是可串行化的,才認為是正確調度

可串行化調度的充分條件

一個調度Sc在保證沖突操作的次序不變的情況下,通過交換兩個事務不沖突操作的次序得到另一個調度Sc‘,如果Sc’是串行的,稱調度Sc為沖突可串行化的調度
一個調度是沖突可串行化,一定是可串行化的調度
一般RDBMS都將沖突可串行化作為並發控制的正確性准則

沖突操作(Conflict Operation)

沖突操作是指不同的事務對同一個數據的讀寫操作和寫寫操作
Ri (x)與Wj(x) /* 事務Ti讀x,Tj寫x*/
Wi(x)與Wj(x) /* 事務Ti寫x,Tj寫x*/
其他操作是不沖突操作
不同事務的沖突操作和同一事務的兩個操作不能交換(Commute) ,否則會影響執行的效果

[例]今有調度Sc1=r1(A)w1(A)r2(A)w2(A)r1(B)w1(B)r2(B)w2(B)
把w2(A)與r1(B)w1(B)交換,得到:
    r1(A)w1(A)r2(A)r1(B)w1(B)w2(A)r2(B)w2(B)
再把r2(A)與r1(B)w1(B)交換:
   Sc2=r1(A)w1(A)r1(B)w1(B)r2(A)w2(A)r2(B)w2(B)
Sc2等價於一個串行調度T1,T2,Sc1沖突可串行化的調度
沖突可串行化調度是可串行化調度的充分條件,不是必要條件。還有不滿足沖突可串行化條件的可串行化調度,稱為目標可串行化(view serializability)的調度。
    [例]有3個事務, L1和L2是目標等價的(view equivalence)
       T1=W1(Y)W1(X),T2=W2(Y)W2(X),T3=W3(X)
調度L1=W1(Y)W1(X)W2(Y)W2(X) W3(X)是一個串行調度。
調度L2=W1(Y)W2(Y)W2(X)W1(X)W3(X)不滿足沖突可串行化。但是調度L2是可串行化的,因為L2執行的結果與調度L1相同,Y的值都等於T2的值,X的值都等於T3的值 

封鎖協議

 運用封鎖方法時,對數據對象加鎖時需要約定一些規則 

何時申請封鎖
持鎖時間
何時釋放封鎖等
兩段封鎖協議(Two-Phase Locking,簡稱2PL)是最常用的一種封鎖協議,理論上證明使用兩段封鎖協議產生的是可串行化調度

兩段鎖協議
指所有事務必須分兩個階段對數據項加鎖和解鎖
在對任何數據進行讀、寫操作之前,事務首先要獲得對該數據的封鎖
在釋放一個封鎖之後,事務不再申請和獲得任何其他封鎖

“兩段”鎖的含義
事務分為兩個階段
第一階段是獲得封鎖,也稱為擴展階段
事務可以申請獲得任何數據項上的任何類型的鎖,但是不能釋放任何鎖
第二階段是釋放封鎖,也稱為收縮階段
事務可以釋放任何數據項上的任何類型的鎖,但是不能再申請任何鎖

例
事務Ti遵守兩段鎖協議,其封鎖序列是 :
Slock A    Slock B    Xlock C     Unlock B    Unlock A   Unlock C;
|←      擴展階段    →|  |←      收縮階段           →|
事務Tj不遵守兩段鎖協議,其封鎖序列是: 
Slock A    Unlock A    Slock B    Xlock C    Unlock C    Unlock B;

事務遵守兩段鎖協議是可串行化調度的充分條件,而不是必要條件。
若並發事務都遵守兩段鎖協議,則對這些事務的任何並發調度策略都是可串行化的
若並發事務的一個調度是可串行化的,不一定所有事務都符合兩段鎖協議
兩段鎖協議與防止死鎖的一次封鎖法
一次封鎖法要求每個事務必須一次將所有要使用的數據全部加鎖,否則就不能繼續執行,因此一次封鎖法遵守兩段鎖協議
但是兩段鎖協議並不要求事務必須一次將所有要使用的數據全部加鎖,因此遵守兩段鎖協議的事務可能發生死鎖

封鎖粒度(Granularity)

封鎖對象的大小稱為封鎖粒度(Granularity)
封鎖的對象:邏輯單元,物理單元
例:在關系數據庫中,封鎖對象:
邏輯單元: 屬性值、屬性值集合、元組、關系、索引項、整個索引、整個數據庫等
物理單元:頁(數據頁或索引頁)、物理記錄等

封鎖粒度與系統的並發度和並發控制的開銷密切相關。
封鎖的粒度越大,數據庫所能夠封鎖的數據單元就越少,並發度就越小,系統開銷也越小;
封鎖的粒度越小,並發度較高,但系統開銷也就越大

若封鎖粒度是數據頁,事務T1需要修改元組L1,則T1必須對包含L1的整個數據頁A加鎖。如果T1對A加鎖後事務T2要修改A中元組L2,則T2被迫等待,直到T1釋放A。
如果封鎖粒度是元組,則T1和T2可以同時對L1和L2加鎖,不需要互相等待,提高了系統的並行度。
又如,事務T需要讀取整個表,若封鎖粒度是元組,T必須對表中的每一個元組加鎖,開銷極大

多粒度封鎖(Multiple Granularity Locking)

在一個系統中同時支持多種封鎖粒度供不同的事務選擇

選擇封鎖粒度
同時考慮封鎖開銷和並發度兩個因素,適當選擇封鎖粒度
需要處理多個關系的大量元組的用戶事務:以數據庫為封鎖單位
需要處理大量元組的用戶事務:以關系為封鎖單元
只處理少量元組的用戶事務:以元組為封鎖單位

多粒度樹
以樹形結構來表示多級封鎖粒度
根結點是整個數據庫,表示最大的數據粒度
葉結點表示最小的數據粒度
允許多粒度樹中的每個結點被獨立地加鎖
對一個結點加鎖意味著這個結點的所有後裔結點也被加以同樣類型的鎖
在多粒度封鎖中一個數據對象可能以兩種方式封鎖:顯式封鎖和隱式封鎖
顯式封鎖: 直接加到數據對象上的獨立封鎖
隱式封鎖: 該數據對象沒有獨立加鎖,是由於其上級結點加鎖而使該數據對象加上了鎖
顯式封鎖和隱式封鎖的效果是一樣的!

系統檢查封鎖沖突時
要檢查顯式封鎖
還要檢查隱式封鎖
例如事務T要對關系R1加X鎖
系統必須搜索其上級結點數據庫、關系R1
還要搜索R1的下級結點,即R1中的每一個元組
如果其中某一個數據對象已經加了不相容鎖,則T必須等待

對某個數據對象加鎖,系統要檢查
該數據對象
有無顯式封鎖與之沖突
所有上級結點(祖先)
檢查本事務的顯式封鎖是否與其它事務在該數據對象上的隱式封鎖沖突:(由上級結點已加的封鎖造成的)
所有下級結點(後裔)
看其它事務在下級節點上的顯式封鎖是否與本事務的隱式封鎖(將加到下級結點的封鎖)沖突

數據共享與數據一致性是一對矛盾
數據庫的價值在很大程度上取決於它所能提供的數據共享度
數據共享在很大程度上取決於系統允許對數據並發操作的程度
數據並發程度又取決於數據庫中的並發控制機制
數據的一致性也取決於並發控制的程度。施加的並發控制愈多,數據的一致性往往愈好

數據庫的並發控制以事務為單位
數據庫的並發控制通常使用封鎖機制
兩類最常用的封鎖

並發控制機制調度並發事務操作是否正確的判別准則是可串行性
並發操作的正確性則通常由兩段鎖協議來保證。
兩段鎖協議是可串行化調度的充分條件,但不是必要條件

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved