活鎖和死鎖

一、活鎖

如果事務T1封鎖了資料R，事務T2又請求封鎖R，于是T2等待。T3也請求封鎖R，當T1釋放了R上的封鎖之後系統首先準許了T3的請求，T2 仍然等待。然後T4又請求封鎖R，當T3釋放了R上的封鎖之後系統又準許了T4的請求，...，T2有可能永遠等待，這就是活鎖的情形，如圖8.4(a) 所示。

避免活鎖的簡單方法是采用先來先服務的政策。

二、死鎖

如果事務T1封鎖了資料R1，T2封鎖了資料R2，然後T1又請求封鎖R2，因T2已封鎖了R2，于是T1等待T2釋放R2上的鎖。接着T2又申 請封鎖R1，因T1已封鎖了R1，T2也隻能等待T1釋放R1上的鎖。這樣就出現了T1在等待T2，而T2又在等待T1的局面，T1和T2兩個事務永遠不 能結束，形成死鎖。

1. 死鎖的預防

在資料庫中，産生死鎖的原因是兩個或多個事務都已封鎖了一些資料對象，然後又都請求對已為其他事務封鎖的資料對象加鎖，進而出現死等待。防止死鎖的發生其實就是要破壞産生死鎖的條件。預防死鎖通常有兩種方法：

① 一次封鎖法

一次封鎖法要求每個事務必須一次将所有要使用的資料全部加鎖，否則就不能繼續執行。

一次封鎖法雖然可以有效地防止死鎖的發生，但也存在問題，一次就将以後要用到的全部資料加鎖，勢必擴大了封鎖的範圍，進而降低了系統的并發度。

② 順序封鎖法

順序封鎖法是預先對資料對象規定一個封鎖順序，所有事務都按這個順序實行封鎖。

順序封鎖法可以有效地防止死鎖，但也同樣存在問題。事務的封鎖請求可以随着事務的執行而動态地決定，很難事先确定每一個事務要封鎖哪些對象，是以也就很難按規定的順序去施加封鎖。

可見，在作業系統中廣為采用的預防死鎖的政策并不很适合資料庫的特點，是以DBMS在解決死鎖的問題上普遍采用的是診斷并解除死鎖的方法。

2. 死鎖的診斷與解除

① 逾時法

如果一個事務的等待時間超過了規定的時限，就認為發生了死鎖。逾時法實作簡單，但其不足也很明顯。一是有可能誤判死鎖，事務因為其他原因使等待時間超過時限，系統會誤認為發生了死鎖。二是時限若設定得太長，死鎖發生後不能及時發現。

② 等待圖法

事務等待圖是一個有向圖G=(T,U)。 T為結點的集合，每個結點表示正運作的事務；U為邊的集合，每條邊表示事務等待的情況。若T1等待T2,則T1、T2之間劃一條有向邊，從T1指向T2。 事務等待圖動态地反映了所有事務的等待情況。并發控制子系統周期性地（比如每隔1分鐘）檢測事務等待圖，如果發現圖中存在回路，則表示系統中出現了死鎖。

DBMS的并發控制子系統一旦檢測到系統中存在死鎖，就要設法解除。通常采用的方法是選擇一個處理死鎖代價最小的事務，将其撤消，釋放此事務持有的所有的鎖，使其它事務得以繼續運作下去。當然，對撤消的事務所執行的資料修改操作必須加以恢複。

參考資料： http://ptc3.fjpt.cn.net/dxx/jpkc/db/courseware/8/8.4.0.htm