Data-Intensive Computing Systems Concurrency Control (II) Shivnath Babu 1 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): unlock: T1 li (A) ui (A) T2 scheduler lock table 4 Rule #1: Well-formed transactions Ti: … li(A) … pi(A) … ui(A) ... 5 Rule #2 Legal scheduler S = …….. li(A) ………... ui(A) ……... no lj(A) 6 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 # locks held by Ti Time Growing Phase Shrinking Phase 12 Schedule G T1 l1(A);Read(A) A A+100;Write(A) l1(B); u1(A) T2 delayed l2(A);Read(A) A Ax2;Write(A);l2(B) 13 Schedule G T1 l1(A);Read(A) A A+100;Write(A) l1(B); u1(A) T2 delayed l2(A);Read(A) A Ax2;Write(A);l2(B) Read(B);B B+100 Write(B); u1(B) 14 Schedule G T1 l1(A);Read(A) A A+1