Deadlocks

Chia sẻ: Lê Trinh | Ngày: | Loại File: PPT | Số trang:33

Thêm vào BST

Báo xấu

43
lượt xem 3
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Transactions given a timestamp when they arrive … ts(Ti) Ti wounds Tj if ts(Ti)

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Deadlocks

Waitdie  Transactions given a timestamp when they arrive …. ts(Ti)  Ti can only wait for Tj if ts(Ti)
Waitdie1 T1 requests A: wait for T2 or T3 or both? (in my html notes, I assume both) (ts =22) T2 Note: ts between 20 and 25. (ts =20) wait(A) T3 (ts =25)
Waitdie1 One option: T1 waits just for T3, transaction holding lock. But when T2 gets lock, T1 will have to die! (also lots of WFG revision) T1 (ts =22) wait(A) T2 wait(A) (ts =20) wait(A) T 3 (ts =25)
Waitdie2 Another option: T1 waits for both T2, T3 E.g., (saves having to revise WFG) T1 allowed to wait iff there is at least one younger trans waitinvolved with A. But again, when T2 gets lock, T1 must die! T1 (ts =22) wait(A) T2 wait(A) (ts =20) wait(A) T 3 (ts =25)
Waitdie3 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) T1 (ts =22) waitA T2 wait(A) (ts =20) T3 (ts =25)
Woundwait  Transactions given a timestamp when they arrive … ts(Ti)  Ti wounds Tj if ts(Ti)
Woundwait T1 (ts =25) Wait A T2 Wait C (ts =20) Wait B T3 (ts =10)
Woundwait2 T1 requests A: wait for T2 or T3? (ts =15) T2 Note: ts between 10 and 20. (ts =20) wait(A) T3 (ts =10)
Woundwait2 One option: T1 waits just for T3, transaction holding lock. But when T2 gets lock, T1 waits for T2 and wounds T2. T1 Wait A (ts =15) T2 wait(A) (ts =20) wait(A) T3 (ts =10)
Woundwait3 Another option: T1 waits for both T2, T3 ⇒ T2 wounded right away! T1 (ts =15) wait(A) T2 wait(A) (ts =20) wait(A) T3 (ts =10)
Woundwait4 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 may starve. T1 (ts =15) waitA T2 wait(A) (ts =20) T3 (ts =10)
User/Program commands Lots of variations, but in general  Begin_work  Commit_work  Abort_work
Nested transactions User program: ... Begin_work; ... ... If results_ok, then commit work else abort_work
Nested transactions User program: ... Begin_work; Begin_work; ... If results_ok, then commit work else {abort_work; try something else…} ... If results_ok, then commit work else abort_work
Parallel Nested Transactions T1: beginwork ... parallel: T11: begin_work T1 ... T1 commit_work T11 T12 T12: begin_work ... commit_work ... commit_work
Locking Locking What are we really locking?
Example: Ti ... Read record r1 ... Read record r1 do record locking ... Modify record r3 ...
But underneath: If we lock all record id data involved in read R1 of R1, we may prevent R2 an update to R2 (which may require reorganization within R3 block) Disk pages
Solution: view DB at two levels Top level: record actions record locks undo/redo actions — logical e.g., Insert record(X,Y,Z) Redo: insert(X,Y,Z) Undo: delete
Low level: deal with physical details latch page during action (release at end of action)