Đang tạo bản xem trước...
How to enforce serializable schedules? Option 1: run system, recording P(S); at end of day, check for P(S) cycles and declare if execution was good 2
How to enforce serializable schedules? Option 2: prevent P(S) cycles from occurring T1 T2 ….. Tn Scheduler DB 3
A locking protocol Two new actions: lock (exclusive): li (A) unlock: ui (A) T1 T2 lock scheduler table 4
Exercise: • What schedules are legal? What transactions are well-formed? S1 = l1(A)l1(B)r1(A)w1(B)l2(B)u1(A)u1(B) r2(B)w2(B)u2(B)l3(B)r3(B)u3(B) S2 = l1(A)r1(A)w1(B)u1(A)u1(B) l2(B)r2(B)w2(B)l3(B)r3(B)u3(B) S3 = l1(A)r1(A)u1(A)l1(B)w1(B)u1(B) l2(B)r2(B)w2(B)u2(B)l3(B)r3(B)u3(B) 7
Exercise: • What schedules are legal? What transactions are well-formed? S1 = l1(A)l1(B)r1(A)w1(B)l2(B)u1(A)u1(B) r2(B)w2(B)u2(B)l3(B)r3(B)u3(B) S2 = l1(A)r1(A)w1(B)u1(A)u1(B) l2(B)r2(B)w2(B)l3(B)r3(B)u3(B) S3 = l1(A)r1(A)u1(A)l1(B)w1(B)u1(B) l2(B)r2(B)w2(B)u2(B)l3(B)r3(B)u3(B) 8
Schedule F T1 T2 l1(A);Read(A) A A+100;Write(A);u1(A) l2(A);Read(A) A Ax2;Write(A);u2(A) l2(B);Read(B) B Bx2;Write(B);u2(B) l1(B);Read(B) B B+100;Write(B);u1(B) 9
Schedule F A B T1 T2 25 25 l1(A);Read(A) A A+100;Write(A);u1(A) 125 l2(A);Read(A) A Ax2;Write(A);u2(A) 250 l2(B);Read(B) B Bx2;Write(B);u2(B) 50 l1(B);Read(B) B B+100;Write(B);u1(B) 150 250 150 10
Rule #3 Two phase locking (2PL) for transactions Ti = ……. li(A) ………... ui(A) ……... no unlocks no locks 11
Schedule G T1 T2 l1(A);Read(A) A A+100;Write(A) l1(B); u1(A) delayed l2(A);Read(A) A Ax2;Write(A);l2(B) 13
Schedule G T1 T2 l1(A);Read(A) A A+100;Write(A) l1(B); u1(A) delayed l2(A);Read(A) A Ax2;Write(A);l2(B) Read(B);B B+100 Write(B); u1(B) 14
Schedule G T1 T2 l1(A);Read(A) A A+100;Write(A) l1(B); u1(A) l (A);Read(A) delayed 2 A Ax2;Write(A);l2(B) Read(B);B B+100 Write(B); u1(B) l2(B); u2(A);Read(B) B Bx2;Write(B);u2(B); 15
Schedule H (T2 reversed) T1 T2 l1(A); Read(A) l2(B);Read(B) A A+100;Write(A) B Bx2;Write(B) l1(B) l2(A) delayed delayed 16
• Assume deadlocked transactions are rolled back – They have no effect – They do not appear in schedule E.g., Schedule H = This space intentionally left blank! 17
Conflict rules for li(A), ui(A): • li(A), lj(A) conflict • li(A), uj(A) conflict Note: no conflict < ui(A), uj(A)>, < li(A), rj(A)>,... 19
Theorem Rules #1,2,3 conflict (2PL) serializable schedule To help in proof: Definition Shrink(Ti) = SH(Ti) = first unlock action of Ti 20
Hiển thị 20 trang đầu. Tải tài liệu để xem đầy đủ.
Chưa có bình luận nào. Hãy là người đầu tiên!
Bình luận (0)
Chưa có bình luận nào. Hãy là người đầu tiên!