題組內容

三、假設資料庫中有三個資料項(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 收到下列操作請求:

請回答以下問題:

(二)此排程於 t9 之後的時間,是否有機會形成死結(Deadlock)?若有, 請指出是那些交易互相等待。(10 分)