DBMS - 死鎖

在多程序系統中，死鎖是在共享資源環境中出現的一種不希望出現的情況，其中一個程序無限期地等待另一個程序持有的資源。

例如，假設一組事務 {T₀, T₁, T₂, ...,T_n}。T₀ 需要資源 X 來完成其任務。資源 X 由 T₁ 持有，而 T₁ 正在等待資源 Y，該資源由 T₂ 持有。T₂ 正在等待資源 Z，該資源由 T₀ 持有。因此，所有程序都在等待彼此釋放資源。在這種情況下，沒有一個程序能夠完成其任務。這種情況稱為死鎖。

死鎖對系統不利。如果系統陷入死鎖，則參與死鎖的事務將回滾或重新啟動。

死鎖預防

為了防止系統中出現任何死鎖情況，DBMS 會積極檢查所有事務即將執行的操作。DBMS 檢查這些操作並分析它們是否會造成死鎖情況。如果發現可能會發生死鎖情況，則該事務將不被允許執行。

有一些死鎖預防方案使用事務的時間戳排序機制來預先確定死鎖情況。

等待-死亡方案

在這種方案中，如果一個事務請求鎖定另一個事務已經持有衝突鎖的資源（資料項），則可能發生以下兩種情況之一：

• 如果 TS(T_i) < TS(T_j) - 即請求衝突鎖的 T_i 比 T_j 舊 - 則允許 T_i 等待，直到資料項可用。

• 如果 TS(T_i) > TS(t_j) - 即 T_i 比 T_j 新 - 則 T_i 死亡。T_i 稍後會隨機延遲後重新啟動，但時間戳相同。

此方案允許較舊的事務等待，但會終止較新的事務。

等待-傷害方案

在這種方案中，如果一個事務請求鎖定另一個事務已經持有衝突鎖的資源（資料項），則可能發生以下兩種情況之一：

• 如果 TS(T_i) < TS(T_j)，則 T_i 強制 T_j 回滾 - 即 T_i 傷害 T_j。T_j 稍後會隨機延遲後重新啟動，但時間戳相同。

• 如果 TS(T_i) > TS(T_j)，則 T_i 被迫等待，直到資源可用。

此方案允許較新的事務等待；但是，當較舊的事務請求較新事務持有的項時，較舊的事務會強制較新的事務中止並釋放該項。

在這兩種情況下，稍後進入系統的交易都會被中止。

死鎖避免

中止事務並非總是可行的辦法。相反，可以使用死鎖避免機制來提前檢測任何死鎖情況。“等待圖”之類的方案可用，但它們僅適用於事務輕量級且資源例項較少的系統。在龐大的系統中，死鎖預防技術可能效果更好。

等待圖

這是一種簡單的可用方法，用於跟蹤是否可能出現任何死鎖情況。對於進入系統的每個事務，都會建立一個節點。當事務 T_i 請求對某個項（例如 X）的鎖時，該項由另一個事務 T_j 保持，則會從 T_i 到 T_j 建立一條有向邊。如果 T_j 釋放專案 X，則它們之間的邊將被刪除，而 T_i 鎖定資料項。

系統為每個等待其他事務持有的某些資料項的事務維護此等待圖。系統會不斷檢查圖中是否存在任何迴圈。

在這裡，我們可以使用以下兩種方法之一：

• 首先，不允許對另一個事務已鎖定的專案進行任何請求。這並非總是可行的，並且可能導致飢餓，其中事務無限期地等待資料項且永遠無法獲取它。

• 第二個選項是回滾其中一個事務。回滾較新的事務並非總是可行的，因為它可能比較舊的事務更重要。藉助某種相對演算法，可以選擇要中止的事務。此事務稱為**受害者**，此過程稱為**受害者選擇**。