Chapter 18: Concurrency ControlChapter 18 Concurrency ControlExample:Schedule ASchedule BSchedule CSchedule DSchedule EPowerPoint PresentationSlide 10Slide 11Slide 12Returning to ScConceptsDefinitionSlide 16Precedence graph P(S) (S is schedule)Exercise:LemmaSlide 20TheoremHow to enforce serializable schedules?Slide 23A locking protocolRule #1: Consistent transactionsRule #2 Legal schedulerSlide 27Slide 28Slide 29Rule #3 Two phase locking (2PL) for transactionsSlide 31Schedule GSlide 33Slide 34Schedule H (T2 reversed)Slide 36Slide 37Slide 38Shared locksSlide 40Slide 41Option 2: UpgradeSlide 43Lock types beyond S/XUpdate locksSolutionHow does locking work in practice?Slide 48Slide 49Lock table ConceptuallyLock info for A - exampleWhat are the objects we lock?Slide 53SummaryChapter 18 1Chapter 18:Concurrency Control(Slides by Hector Garcia-Molina,http://www-db.stanford.edu/~hector/cs245/notes.htm)Chapter 18 2Chapter 18 Concurrency Control T1 T2 … TnDB(consistencyconstraints)Chapter 18 3Example:T1: Read(A) T2: Read(A)A  A+100 A  A2Write(A) Write(A)Read(B) Read(B)B  B+100 B  B2Write(B) Write(B)Constraint: A=BChapter 18 4Schedule AT1 T2Read(A); A  A+100Write(A);Read(B); B  B+100;Write(B);Read(A);A  A2;Write(A); Read(B);B  B2;Write(B);A B25 25125125250250250 250Chapter 18 5Schedule BT1 T2Read(A);A  A2;Write(A);Read(B);B  B2;Write(B);Read(A); A  A+100Write(A);Read(B); B  B+100;Write(B);A B25 255050150150150 150Chapter 18 6Schedule CT1 T2Read(A); A  A+100Write(A);Read(A);A  A2;Write(A);Read(B); B  B+100;Write(B); Read(B);B  B2;Write(B);A B25 25125250125250250 250Chapter 18 7Schedule DT1 T2Read(A); A  A+100Write(A);Read(A);A  A2;Write(A); Read(B);B  B2;Write(B);Read(B); B  B+100;Write(B);A B25 2512525050150250 150Chapter 18 8Schedule ET1 T2’Read(A); A  A+100Write(A);Read(A);A  A1;Write(A); Read(B);B  B1;Write(B);Read(B); B  B+100;Write(B);A B25 2512512525125125 125Same as Schedule Dbut with new T2’Chapter 18 9•Want schedules that are “good”,regardless of–initial state and–transaction semantics•Only look at order of read and writesExample: Sc=r1(A)w1(A)r2(A)w2(A)r1(B)w1(B)r2(B)w2(B)Chapter 18 10Sc’=r1(A)w1(A) r1(B)w1(B)r2(A)w2(A)r2(B)w2(B) T1 T2Example: Sc=r1(A)w1(A)r2(A)w2(A)r1(B)w1(B)r2(B)w2(B)Chapter 18 11However, for Sd:Sd=r1(A)w1(A)r2(A)w2(A) r2(B)w2(B)r1(B)w1(B)Chapter 18 12T1 T2 Sd cannot be rearrangedinto a serial scheduleSd is not “equivalent” toany serial scheduleSd is “bad”• T2  T1 • Also, T1  T2Chapter 18 13Returning to ScSc=r1(A)w1(A)r2(A)w2(A)r1(B)w1(B)r2(B)w2(B) T1  T2 T1  T2 no cycles  Sc is “equivalent” to aserial schedule(in this case T1,T2)Chapter 18 14ConceptsTransaction: sequence of ri(x), wi(x) actionsConflicting actions: r1(A) w2(A) w1(A) w2(A) r1(A) w2(A)Schedule: represents chronological orderin which actions are executedSerial schedule: no interleaving of actions or transactionsChapter 18 15DefinitionS1, S2 are conflict equivalent schedulesif S1 can be transformed into S2 by a series of swaps on non-conflicting actions.Chapter 18 16DefinitionA schedule is conflict serializable if it is conflict equivalent to some serial schedule.Chapter 18 17Nodes: transactions in SArcs: Ti  Tj whenever- pi(A), qj(A) are actions in S- pi(A) <S qj(A)- at least one of pi, qj is a writePrecedence graph P(S) (S is schedule)Chapter 18 18Exercise:•What is P(S) forS = w3(A) w2(C) r1(A) w1(B) r1(C) w2(A) r4(A) w4(D)•Is S serializable?Chapter 18 19LemmaS1, S2 conflict equivalent  P(S1)=P(S2)Chapter 18 20Note: P(S1)=P(S2)  S1, S2 conflict equivalentCounter example:S1=w1(A) r2(A) w2(B) r1(B) S2=r2(A) w1(A) r1(B) w2(B)Chapter 18 21TheoremP(S1) acyclic  S1 conflict serializableChapter 18 22How 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 goodChapter 18 23Option 2: prevent P(S) cycles from occurring T1 T2 ….. TnSchedulerDBHow to enforce serializable schedules?Chapter 18 24A locking protocolTwo new actions:lock (exclusive):li (A) unlock: ui (A)schedulerT1 T2locktableChapter 18 25Rule #1: Consistent transactionsTi: … li(A) … pi(A) … ui(A) ...Chapter 18 26Rule #2 Legal schedulerS = …….. li(A) ………... ui(A) ……... no lj(A)Chapter 18 27•What schedules are legal?What transactions are consistent?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)Exercise:Chapter 18 28Schedule FT1 T2l1(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)Chapter 18 29Schedule FT1 T2 25 25l1(A);Read(A)A A+100;Write(A);u1(A) 125l2(A);Read(A)A Ax2;Write(A);u2(A) 250l2(B);Read(B)B Bx2;Write(B);u2(B) 50l1(B);Read(B)B B+100;Write(B);u1(B) 150 250 150A BChapter 18 30Rule #3 Two phase locking (2PL)for transactionsTi = ……. li(A) ………... ui(A) ……...no unlocks no locksChapter 18 31 # locks held by TiTime Growing Shrinking Phase PhaseChapter 18 32Schedule GT1 T2l1(A);Read(A)A A+100;Write(A)l1(B); u1(A) l2(A);Read(A) A Ax2;Write(A);ll22(B)(B) delayedChapter 18 33Schedule GT1 T2l1(A);Read(A)A A+100;Write(A)l1(B); u1(A) l2(A);Read(A) A Ax2;Write(A);ll22(B)(B)Read(B);B B+100Write(B); u1(B) delayedChapter 18 34Schedule GT1 T2l1(A);Read(A)A A+100;Write(A)l1(B); u1(A) l2(A);Read(A) A Ax2;Write(A);ll22(B)(B)Read(B);B B+100Write(B); u1(B) l2(B); u2(A);Read(B) B Bx2;Write(B);u2(B); delayedChapter 18 35Schedule H (T2 reversed)T1 T2l1(A); Read(A) l2(B);Read(B)A A+100;Write(A) B Bx2;Write(B)ll11(B)(B) l l22(A)(A)delayeddelayeddeadlockChapter 18 36•Assume deadlocked transactions are rolled back–They have no effect–They do not appear in scheduleE.g., Schedule H on previous slideChapter 18 37We can show that rules #1,2,3  conflict-serializable schedules(see textbook)Chapter 18 38•Beyond this simple 2PL protocol, it is all a matter of improving performance and allowing more concurrency….–Shared locks–Multiple granularity–Inserts, deletes and phantoms–Other types of C.C. mechanismsChapter 18 39Shared locksSo far:S =