文章目錄

• 一：可串行化調度
• 二：沖突可串行化調度
• • （1）沖突操作
  • （2）可串行化調度的充分條件：沖突可串行化
• 三：兩段鎖協議
• 四：封鎖的粒度
• • （1）概念
  • （2）選擇封鎖的原則
  • （3）多粒度封鎖
  • • A：多粒度樹
    • B：多粒度封鎖協議
  • （4）意向鎖

一：可串行化調度

可串行化調度：多個事務的并發執行是正確的，當且僅當其結果與按某一次序串行地執行這些事務時的結果相同，稱這種調度策略為可串行化(serializable)調度。可串行性是并發事務正確調度的準則， 也即一個給定的并發調度，當且僅當它是可串行化的，才認為是正確調度

例如，下面有兩個事務，分別包含下列操作

事務$T_1$： 讀B、A=B+1、寫回A；
事務$T_2$： 讀A、B=A+1、寫回B；

假設A、B初值均為2，兩個事務最多只有兩種串行執行策略

• $T_1$->$T_2$：A=3，B=4
• $T_2$->$T_1$：A=4，B=3

因此事務$T_1$和$T_2$不管怎樣交叉并行運行，只有兩種正確的結果（如上）。其他結果均是錯誤的，相應調度也稱之為不可串行化調度

二：沖突可串行化調度

（1）沖突操作

沖突操作：是指不同事務對同一個數據的讀寫操作和寫寫操作。除此之外，其他操作均為不沖突操作

• $R_i(x)$與$W_j(x)$：事務$T_i$讀x，事務$T_j$寫x
• $W_i(x)$與$W_j(x)$：事務$T_i$寫x，事務$T_j$寫x

另外注意各種交換

• 不同事務的沖突操作不可交換
• 同一事務內部的兩個操作不可交換
• 不同事務，同一數據的讀讀操作可以交換
• 不同事務，不同數據，無論讀寫均可交換

（2）可串行化調度的充分條件：沖突可串行化

沖突可串行化：一個調度SC在保證沖突操作的次序不變的情況下，通過交換兩個事務不沖突操作的次序得到另一個調度SC${}^{‘}$，如果SC${}^{‘}$是串行的，則稱調度SC為沖突可串行化的調度。若一個調度是沖突可串行化的，那么它一定是可串行化的調度

• 注意：沖突可串行化調度是可串行化調度的充分條件，不是必要條件。也就是說有可能某個調度是可串行調度，但它卻不是沖突可串行化調度

例如，現在有一個調度SC1=$r_1(A)w_1(A)r_2(A)w_2(A)r_1(B)w_1(B)r_2(B)w_2(B)$

考察兩個不同事務的交界處，看它是否滿足交換的條件

交換后SC1變為了SC2=$r_1(A)w_1(A)r_1(B)w_1(B)r_2(A)w_2(A)r_2(B)w_2(B)$，它等價于一個串行調度$T_1$->$T_2$，因此SC1是沖突可串行化調度，也一定是一個可串行化調度

三：兩段鎖協議

兩段鎖協議（2PL）：兩段鎖協議是三級封鎖協議的特例，目前DBMS普遍采用該種協議實現并發調度的可串行性。具體內容如下

• 在對任何數據進行讀、寫操作之前，首先要申請并獲得對該數據的封鎖
• 在釋放一個封鎖之后，事務不再申請和獲得任何其他封鎖

其中“兩段”是指事務分為兩個階段

• 第一階段：獲得封鎖，也稱為擴展階段
• 第二階段：釋放封鎖，也稱為收縮階段

另外還需要注意

• 事務遵守兩段鎖協議是可串行化調度的充分條件，而非必要條件
• 若并發事物都遵循兩段鎖協議，則對其的任何并發點都策略都是可串行化的
• 若對并發事務的一個調度是可串行化的，不一定所有事務都符合兩段鎖協議

最后注意區分兩段鎖協議和一次封鎖法

• 一次封鎖法要求每個事務必須一次將所有要使用的數據全部加鎖，否則就不能繼續執行，因此一次封鎖法遵守兩段鎖協議
• 但是兩段鎖協議并不要求事務必須一次將所有要使用的數據全部加鎖，因此遵守兩段鎖協議的事務可能發生死鎖

四：封鎖的粒度

（1）概念

封鎖粒度(granularity)：是指封鎖對象的大小。封鎖對象可以是邏輯單元，也可以是物理單元。封鎖粒度與系統并發度和并發控制的開銷密切相關，一般來說，封鎖粒度越大，數據庫所能封鎖的數據單元就越少，并發度越小，開銷越小

• 邏輯單元：元組、關系、整個數據庫等
• 物理單元：頁（數據頁或索引頁）、物理記錄等

（2）選擇封鎖的原則

• 需要處理多個關系的大量元組的用戶事務時以數據庫為封鎖單位
• 需要處理大量元組的用戶事務時以關系為封鎖單元
• 只處理少量元組的用戶事務時以元組為封鎖單位

（3）多粒度封鎖

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

A：多粒度樹

多粒度樹是以樹形結構來表示多級封鎖粒度的方法

• 根結點是整個數據庫，表示最大的數據粒度
• 葉結點表示最小的數據粒度

B：多粒度封鎖協議

多粒度封鎖協議：允許多粒度樹中的每個結點被獨立地加鎖，對一個結點加鎖意味著這個結點的所有后裔結點也會被加上相同類型的鎖。因此，在多粒度封鎖中一個數據對象可能存在如下兩種封鎖方式

• 顯式封鎖：直接加到數據庫對象上的封鎖
• 隱式封鎖：由于上級結點加鎖而使該數據對象也被加鎖

多粒度封鎖方法中，顯式封鎖和隱式封鎖的效果是一樣的，因此系統檢查封鎖沖突時不僅要檢查顯式封鎖還要檢查隱式封鎖

• 例如事務$T$要對關系$R_1$加$X$鎖，系統必須搜索其上級結點數據庫、關系$R_1$以及$R_1$的下級結點，即$R_1$中的每一個元組，上下搜索。如果其中某一個數據對象已經加了不相容鎖，則$T$必須等待

（4）意向鎖

• 一般地，對某個數據對象加鎖，系統要檢查該數據對象上有無顯式封鎖與之沖突:再檢查其所有上級結點，看本事務的顯式封鎖是否與該數據對象上的隱式封鎖(即由于上級結點已加的封鎖造成的)沖突;還要檢查其所有下級結點，看它們的顯式封鎖是否與本事務的隱式封鎖(將加到下級結點的封鎖)沖突
• 可以看出，這樣的檢查方法效率很低，因此意向鎖由此誕生

---

意向鎖：如果對一個結點加意向鎖，則說明該結點的下層結點正在被加鎖；對任一結點加鎖時，必須先對它的上層結點加意向鎖。有如下三種常用的意向鎖

• 意向共享鎖（IS鎖）：如果對一個數據對象加IS鎖，表示它的后裔結點擬(意向)加S鎖
• 意向排他鎖（IX鎖）：如果對一個數據對象加IX鎖，表示它的后裔結點擬(意向)加X鎖
• 共享意向排他鎖（SIX鎖）：如果對一個數據對象加SIX鎖，表示對它加S鎖，再加IX鎖，即SIX=S+IX

---

鎖相容矩陣

總結

以上是生活随笔為你收集整理的（数据库系统概论|王珊）第十一章并发控制-第五、六、七节：并发调度的可串行性、两段锁协议和封锁的粒度的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。