假設資料庫中有三個資料項（Data Items）：A、B、C，其三者初始值皆為 100，當有三筆交易T1、T2 與T3 同時進入系統，各自交易的預期操作順 序如…

題目

假設資料庫中有三個資料項（Data Items）：A、B、C，其三者初始值皆為 100，當有三筆交易T1、T2 與T3 同時進入系統，各自交易的預期操作順 序如下所示： T1：read(A) →write(A) →read(B) →write(B) T2：read(B) →write(B) →read(C) →write(C) T3：read(C) →read(A) →write(A) 假設排程器（Scheduler）採用嚴格兩階段鎖定協定（Strict 2PL）：也就是 「在增長階段（Growing Phase），交易可以取得鎖定，但不能釋放任何鎖 定」以及「在收縮階段（Shrinking Phase），交易持有的所有互斥鎖X(X- lock)必須持續保留，直到交易提交（Commit）或中斷（Abort）後才能一 次釋放」。所有操作皆遵循著「具備鎖定升級：即若交易已持有共享鎖S， 在執行write 前必須升級為互斥鎖X」。考慮排程器依照時間序列t1 至t9 收到下列操作請求： 時間 分配請求與操作 時間 分配請求與操作 t1： T1 請求read(A) t6： T1 請求read(B) t2： T2 請求read(B) t7： T2 請求read(C) t3： T3 請求read(C) t8： T3 請求read(A) t4： T1 請求write(A) t9： T1 試圖提交(commit) t5： T2 請求write(B) 請回答以下問題： 詳細分析從t1 至t9 的執行過程中，各個交易的鎖定狀態變化，並且標 記該時間點交易是否會進入阻塞（Blocked/Waiting）狀態？（書寫時， 若某個資料項要使用S 鎖請標註Lock-S(資料項)，若需要X 鎖則書寫 Lock-X(資料項)。）（10 分） 此排程於t9 之後的時間，是否有機會形成死結（Deadlock）？若有， 請指出是那些交易互相等待。（10 分） 若排程能順利執行或經由處理後結束，請說明各交易的鎖定點（Lock Point）分別位於那一個時間點。（5 分）

參考解答（AI 生成，非官方）

• 一、前提與規則整理：採 Strict 2PL，交易在增長階段只能取得鎖、不得釋放；進入收縮階段後，所有 X 鎖須保留至 commit 或 abort 才一次釋放。讀取需 Lock-S(資料項)，寫入需 Lock-X(資料項)；若已持 S 鎖，write 前須升級（upgrade）為 X 鎖，升級成功條件為無其他交易持有該資料項的 S 或 X 鎖。S 與 S 相容，S 與 X、X 與 X 互斥。
• 二、t1 至 t5 的鎖定狀態：（1）t1 T1 請求 read(A)：取得 Lock-S(A)，成功，T1 持有 S(A)。（2）t2 T2 請求 read(B)：取得 Lock-S(B)，成功，T2 持有 S(B)。（3）t3 T3 請求 read(C)：取得 Lock-S(C)，成功，T3 持有 S(C)。（4）t4 T1 請求 write(A)：需將 S(A) 升級為 Lock-X(A)，因僅 T1 持有 A，升級成功，T1 持有 X(A)。（5）t5 T2 請求 write(B)：將 S(B) 升級為 Lock-X(B)，因僅 T2 持有 B，升級成功，T2 持有 X(B)。此階段尚無任何交易進入阻塞。
• 三、t6 至 t9 的鎖定狀態與阻塞：（1）t6 T1 請求 read(B)：需 Lock-S(B)，但 B 已被 T2 以 X 鎖獨占，違反相容性，T1 進入 Blocked/Waiting，排入 B 的等待佇列。（2）t7 T2 請求 read(C)：需 Lock-S(C)，C 目前僅由 T3 持有 S 鎖，S 與 S 相容，故 T2 取得 Lock-S(C)，成功；T2 現持有 X(B) 與 S(C)。（3）t8 T3 請求 read(A)：需 Lock-S(A)，但 A 已被 T1 以 X 鎖持有，衝突，T3 進入 Blocked。（4）t9 T1 試圖 commit：T1 尚未完成 read(B) 與 write(B)，仍卡在 t6 的等待，且 Strict 2PL 下不得提前釋放 X(A)，故 commit 無法執行，T1 持續阻塞。
• 四、死結判定：t9 之後會形成死結。等待圖（wait-for graph）為 T1 → T2（T1 等 T2 釋放 B 的 X 鎖）、T2 → T3（T2 後續 write(C) 需將 S(C) 升級為 X(C)，但 T3 持有 S(C)）、T3 → T1（T3 等 T1 釋放 A 的 X 鎖），形成 T1 → T2 → T3 → T1 的循環等待，故為死結。處理方式包含：逾時偵測（timeout）、等待圖偵測後選一犧牲者（victim）abort，或採 wait-die / wound-wait 等預防法；亦可調整封鎖粒度或先以 lock ordering 讓交易依固定順序取鎖。
• 五、鎖定點（Lock Point）說明：鎖定點指交易取得「最後一把鎖」的時刻，亦即增長階段結束、進入收縮階段之點。原排程因死結，三筆交易皆未達鎖定點。經處理後之情境：（1）若 abort T3，T3 無鎖定點；T3 釋放 S(C) 後，T2 的 write(C) 升級 X(C) 成功，T2 鎖定點落於該升級時點；T2 commit 釋放 B 後，T1 取得 S(B) 並隨即升級 X(B)，T1 鎖定點落於 X(B) 取得時點。（2）若 abort T1，T1 無鎖定點；T3 取得 S(A) 之時為 T3 鎖定點，T3 commit 釋放 C 後，T2 升級 X(C) 成功之時為 T2 鎖定點。答題時應明確指出鎖定點隨犧牲者選擇而異。

AI 依官方試題文字產生的參考解答，非考選部公告答案，內容僅供備考參考。

官方資料

• 官方試題 PDF