調查局三等申論題
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
解此題需先理解基本兩階段鎖（Basic 2PL）的特性以及死鎖產生的必要條件（循環等待）。由於原題遺漏了交易操作明細表，解題時應自行假設兩個交易分別持有不同資料項目（如X、Y）的鎖，並請求對方已持有的資料項目，進而畫出呈現循環等待且明確標註等待資源的等待圖（Wait-for Graph）。
小題 (二)
在上述 α排程下，資料庫管理系統有死鎖預防機制（deadlock prevention scheme）以避免死鎖，下列各種不同機制，請說明每個交易分別會發生的情況。
⑴採 Wait-die。（5 分）
⑵採 Wound-wait。（5 分）
⑶採 No waiting。（5 分）
⑷採 Cautious waiting。（5 分）
思路引導 VIP
先釐清交易的時戳大小以判斷資歷：T2 時戳為 1000（較老），T1 時戳為 1010（較年輕）。接著依照各項死鎖預防機制（如 Wait-die 為「老等少死」、Wound-wait 為「老殺少等」）的定義，分別探討 T1 請求 T2 資源，以及 T2 請求 T1 資源兩種情境下的具體處置與結果。