tailieunhanh - Deadlocks

Transactions given a timestamp when they arrive ts(Ti) Ti wounds Tj if ts(Ti) | Wait-die Transactions given a timestamp when they arrive . ts(Ti) Ti can only wait for Tj if ts(Ti)< ts(Tj) .else die T1 (ts =10) T2 (ts =20) T3 (ts =25) Wait for A Wait for C? Wait fo B T1 (ts =22) T2 (ts =20) T3 (ts =25) wait(A) requests A: wait for T2 or T3 or both? (in my html notes, I assume both) Note: ts between 20 and 25. Wait-die-1 T1 (ts =22) T2 (ts =20) T3 (ts =25) wait(A) wait(A) One option: T1 waits just for T3, transaction holding lock. wait(A) But when T2 gets lock, T1 will have to die! (also lots of WFG revision) Wait-die-1 T1 (ts =22) T2 (ts =20) T3 (ts =25) wait(A) wait(A) wait(A) Another option: T1 waits for both T2, T3 ., (saves having to revise WFG) T1 allowed to wait iff there is at least one younger trans wait-involved with A. But again, when T2 gets lock, T1 must die! Wait-die-2 T1 (ts =22) T2 (ts =20) T3 (ts =25) wait(A) Yet another option: T1 preempts T2 (T2 is just waiting idly anyway), so T1 only waits for T3; T2 then waits for T3 But, T2 may starve? | Wait-die Transactions given a timestamp when they arrive . ts(Ti) Ti can only wait for Tj if ts(Ti)< ts(Tj) .else die T1 (ts =10) T2 (ts =20) T3 (ts =25) Wait for A Wait for C? Wait fo B T1 (ts =22) T2 (ts =20) T3 (ts =25) wait(A) requests A: wait for T2 or T3 or both? (in my html notes, I assume both) Note: ts between 20 and 25. Wait-die-1 T1 (ts =22) T2 (ts =20) T3 (ts =25) wait(A) wait(A) One option: T1 waits just for T3, transaction holding lock. wait(A) But when T2 gets lock, T1 will have to die! (also lots of WFG revision) Wait-die-1 T1 (ts =22) T2 (ts =20) T3 (ts =25) wait(A) wait(A) wait(A) Another option: T1 waits for both T2, T3 ., (saves having to revise WFG) T1 allowed to wait iff there is at least one younger trans wait-involved with A. But again, when T2 gets lock, T1 must die! Wait-die-2 T1 (ts =22) T2 (ts =20) T3 (ts =25) wait(A) Yet another option: T1 preempts T2 (T2 is just waiting idly anyway), so T1 only waits for T3; T2 then waits for T3 But, T2 may starve? And lots of WFG work for Deadlock Mgr (shifting edges) wait-A Wait-die-3 Wound-wait Transactions given a timestamp when they arrive ts(Ti) Ti wounds Tj if ts(Ti)< ts(Tj) else Ti waits “Wound”: Tj rolls back (if it cannot finish in small interval of time) and gives lock to Ti T1 (ts =25) T2 (ts =20) T3 (ts =10) Wait A Wait B Wait C Wound-wait T1 (ts =15) T2 (ts =20) T3 (ts =10) wait(A) requests A: wait for T2 or T3? Note: ts between 10 and 20. Wound-wait-2 T1 (ts =15) T2 (ts =20) T3 (ts =10) wait(A) wait(A) One option: T1 waits just for T3, transaction holding lock. But when T2 gets lock, T1 waits for T2 and wounds T2. Wound-wait-2 Wait A T1 (ts =15) T2 (ts =20) T3 (ts =10) wait(A) wait(A) wait(A) Another option: T1 waits for both T2, T3 T2 wounded right away! Wound-wait-3 T1 (ts =15) T2 (ts =20) T3 (ts =10) wait(A) Yet another option: T1 preempts T2, so T1 only waits for T3; T2 then waits for T3 and T1. T2 is spared! Lots of WFG work for Deadlock Mgr (shifting edges) and T2 .