調查局三等申論題
114年
[資訊科學組] 資料庫應用
第 一 題
📖 題組：
假設資料庫對交易（Transaction）採用基本的兩階段鎖（basic two-phrase locking）的機制，在這種機制下有可能產生死鎖（deadlock）。假設 read_item(X) 代表交易對資料項目 X 讀取，write_item(X) 代表交易對資料項目 X 寫入新值，read_lock(X) 代表交易對 X 下 read_lock，write_lock(X) 代表交易對 X 下 write_lock，其餘類推。T1、T2 兩個交易原先期待進行的內容如下表左右兩欄。實際上系統不是序列化（Serial）排程，而是將交易交織進行。假設在兩個交易交織進行的α排程（Schedule），T2 在時戳（Timestamp）為 1000 時開始，T1 在時戳為 1010 時開始。在這個α排程下，系統偵測到有死鎖產生的可能。
假設資料庫對交易（Transaction）採用基本的兩階段鎖（basic two-phrase locking）的機制，在這種機制下有可能產生死鎖（deadlock）。假設 read_item(X) 代表交易對資料項目 X 讀取，write_item(X) 代表交易對資料項目 X 寫入新值，read_lock(X) 代表交易對 X 下 read_lock，write_lock(X) 代表交易對 X 下 write_lock，其餘類推。T1、T2 兩個交易原先期待進行的內容如下表左右兩欄。實際上系統不是序列化（Serial）排程，而是將交易交織進行。假設在兩個交易交織進行的α排程（Schedule），T2 在時戳（Timestamp）為 1000 時開始，T1 在時戳為 1010 時開始。在這個α排程下，系統偵測到有死鎖產生的可能。
📝 此題為申論題，共 2 小題
小題 (一)
請繪出其可能導致死鎖的等待圖（wait-for graph），其中必須標註等待的資源。（5 分）
思路引導 VIP
本題重點在於分析「兩階段鎖（2PL）」機制下，多個交易交織執行時產生的「循環等待（Circular Wait）」。解題時應先找出 T1 與 T2 共同存取的資源（資源 A 與 C），並根據題目給定的啟動順序（T2 先、T1 後）模擬鎖定情形，找出雙方互相等待對方釋放鎖的節點，最後將此等待關係轉換為有向圖（Wait-for Graph）。
小題 (二)
在上述 α排程下，資料庫管理系統有死鎖預防機制（deadlock prevention scheme）以避免死鎖，下列各種不同機制，請說明每個交易分別會發生的情況。
⑴採 Wait-die。（5 分）
⑵採 Wound-wait。（5 分）
⑶採 No waiting。（5 分）
⑷採 Cautious waiting。（5 分）
⑴採 Wait-die。（5 分）
⑵採 Wound-wait。（5 分）
⑶採 No waiting。（5 分）
⑷採 Cautious waiting。（5 分）
思路引導 VIP
首先確認交易的時戳大小，判斷誰是老交易（T2，時戳1000）、誰是年輕交易（T1，時戳1010）。接著，因為題目未明示交織排程中是誰先觸發等待，需將死鎖衝突拆分為「T1 請求 T2 的鎖」與「T2 請求 T1 的鎖」兩種可能情境。最後，依據各死鎖預防機制的定義（如 Wait-die 的「老等小死」、Wound-wait 的「老殺小等」、Cautious waiting 的「狀態檢查」）分別闡述 T1 與 T2 會發生的動作（等待 Wait、中止 Abort/Die 或擊傷 Wound）。
交易死鎖預防機制
💡 利用時戳(Timestamp)打破循環等待，實現死鎖預防。
| 比較維度 | Wait-die (等-死) | VS | Wound-wait (傷-等) |
|---|---|---|---|
| 機制性質 | 非搶占式 | — | 搶占式 |
| 老請求少 | 老交易進入等待 | — | 老交易強迫少交易回滾 |
| 少請求老 | 少交易直接回滾 | — | 少交易進入等待 |
💬兩者皆利用時戳順序確保不會形成環狀等待，差別在於誰被強制回滾。
