高考申論題
115年
[資訊處理] 資料庫應用
第 二 題
📖 題組：
假設資料庫中有三個資料項（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) | | | 請回答以下問題：
假設資料庫中有三個資料項（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) | | | 請回答以下問題：
📝 此題為申論題，共 3 小題
小題 (二)
此排程於 t9 之後的時間，是否有機會形成死結（Deadlock）？若有，請指出是那些交易互相等待。（10 分）
思路引導 VIP
接著思考 t9 之後會發生什麼事。
- 檢視目前狀態：T1 等待 T2 (要 B)，T3 等待 T1 (要 A)。T2 則是唯一正在運行 (Active) 的交易。
小題 (一)
詳細分析從 t1至 t9的執行過程中，各個交易的鎖定狀態變化，並且標記該時間點交易是否會進入阻塞（Blocked/Waiting）狀態？（書寫時，若某個資料項要使用 S 鎖請標註 Lock-S(資料項)，若需要 X 鎖則書寫 Lock-X(資料項)。）（10 分）
思路引導 VIP
看到這類併發控制（Concurrency Control）的題目，必須像模擬器一樣一步一步推進時間軸，並維持一張「目前鎖定狀態表」。 基本規則：
小題 (三)
若排程能順利執行或經由處理後結束，請說明各交易的鎖定點（Lock Point）分別位於那一個時間點。（5 分）
思路引導 VIP
這題考的是 2PL 中的「鎖定點」(Lock Point) 定義。
- 回想定義：鎖定點是交易的「增長階段 (Growing Phase)」的最高峰，也就是該交易「取得其所需所有鎖定」的最後一個時刻 (The point when the final lock is acquired)。