Concurrency ControlExample SchedulesExample ScheduleExample Schedule (Cont.)Example Schedules (Cont.)Equivalence by SwappingSlide 7Slide 8Slide 9Slide 10Lock instructionsLocking IssuesSlide 132PhaseLocking2PL IssuesStrict 2PLDealing with DeadlocksExample of Granularity HierarchyCompatibility Matrix with Intention Lock ModesSlide 20ExampleExamplesSlide 23Concurrency ControlConcurrency ControlExample SchedulesExample SchedulesConstraint: The sum of A+B must be the sameBefore: 100+50After: 45+105T1read(A)A = A -50write(A)read(B)B=B+50write(B)T2read(A)tmp = A*0.1A = A – tmpwrite(A)read(B)B = B+ tmpwrite(B)Transactions: T1: transfers $50 from A to B T2: transfers 10% of A to B=150, consistentExample 1: a “serial” scheduleExample ScheduleExample ScheduleAnother “serial” schedule:T1read(A)A = A -50write(A)read(B)B=B+50write(B)T2read(A)tmp = A*0.1A = A – tmpwrite(A)read(B)B = B+ tmpwrite(B)Before: 100+50After: 40+110Consistent but not the same as previous schedule..Either is OK!=150, consistentExample Schedule (Cont.)Example Schedule (Cont.)Another “good” schedule:T1read(A)A = A -50write(A)read(B)B=B+50write(B)T2read(A)tmp = A*0.1A = A – tmpwrite(A)read(B)B = B+ tmpwrite(B)Effect: Before After A 100 45 B 50 105Same as one of the serial schedulesSerializableExample Schedules (Cont.)Example Schedules (Cont.) A “bad” scheduleBefore: 100+50 = 150After: 50+60 = 110 !!Not consistentT1read(A)A = A -50write(A)read(B)B=B+50write(B)T2read(A)tmp = A*0.1A = A – tmpwrite(A)read(B)B = B+ tmpwrite(B)Non SerializableEquivalence by SwappingEquivalence by SwappingT1read(A)A = A -50write(A)read(B)B=B+50write(B)T2read(A)tmp = A*0.1A = A – tmpwrite(A)read(B)B = B+ tmpwrite(B)T1read(A)A = A -50write(A)read(B)B=B+50write(B)T2read(A)tmp = A*0.1A = A – tmpwrite(A)read(B)B = B+ tmpwrite(B)Equivalence by SwappingEquivalence by SwappingT1read(A)A = A -50write(A)read(B)B=B+50write(B)T2read(A)tmp = A*0.1A = A – tmpwrite(A)read(B)B = B+ tmpwrite(B)T1read(A)A = A -50write(A)read(B)B=B+50write(B)T2read(A)tmp = A*0.1A = A – tmpwrite(A)read(B)B = B+ tmpwrite(B)Equivalence by SwappingEquivalence by SwappingT1read(A)A = A -50write(A)read(B)B=B+50write(B)T2read(A)tmp = A*0.1A = A – tmpwrite(A)read(B)B = B+ tmpwrite(B)T1read(A)A = A -50write(A)read(B)B=B+50write(B)T2read(A)tmp = A*0.1A = A – tmpwrite(A)read(B)B = B+ tmpwrite(B)Example Schedules (Cont.)Example Schedules (Cont.) A “bad” scheduleT1read(A)A = A -50write(A)read(B)B=B+50write(B)T2read(A)tmp = A*0.1A = A – tmpwrite(A)read(B)B = B+ tmpwrite(B)XYCan’t move Y below X read(B) and write(B) conflictExample Schedules (Cont.)Example Schedules (Cont.) A “bad” scheduleT1read(A)A = A -50write(A)read(B)B=B+50write(B)T2read(A)tmp = A*0.1A = A – tmpwrite(A)read(B)B = B+ tmpwrite(B)XYCan’t move Y below X read(B) and write(B) conflictOther options don’t work eitherSo: Not Conflict SerializableLock instructionsLock instructionsNew instructions- lock-S: shared lock request- lock-X: exclusive lock request- unlock: release previously held lockExample: lock-X(B)read(B)B B-50write(B)unlock(B)lock-X(A)read(A)A A + 50write(A)unlock(A)lock-S(A)read(A)unlock(A)lock-S(B)read(B)unlock(B)display(A+B)T1T2Locking IssuesLocking IssuesNo xction proceeds:Deadlock- T1 waits for T2 to unlock A- T2 waits for T1 to unlock BT1 T2lock-X(B)read(B)B B-50write(B) lock-X(A)lock-S(A)read(A)lock-S(B)Rollback transactionsCan be costly...Locking IssuesLocking IssuesDoes not ensure serializability by itself:lock-X(B)read(B)B B-50write(B)unlock(B)lock-X(A)read(A)A A + 50write(A)unlock(A)lock-S(A)read(A)unlock(A)lock-S(B)read(B)unlock(B)display(A+B)T1T2T2 displays 50 less!!2PhaseLocking2PhaseLockingExample: T1 in 2PLT1lock-X(B)read(B)B B - 50write(B)lock-X(A)read(A)A A - 50write(A)unlock(B)unlock(A)Growing phaseShrinking phase2PL Issues2PL Issues2PL does not prevent deadlock> 2 xctions involved?- Rollbacks expensiveT1 T2lock-X(B)read(B)B B-50write(B) lock-X(A)lock-S(A)read(A)lock-S(B)Strict 2PLStrict 2PLT1 T2 T3lock-X(A)read(A)lock-S(B)read(B)write(A)unlock(A)<xction fails>lock-X(A)read(A)write(A)unlock(A)lock-S(A)read(A)Strict 2PLwill not allow thatDealing with DeadlocksDealing with DeadlocksHow do you detect a deadlock?Wait-for graphDirected edge from Ti to TjTi waiting for TjT1 T2 T3 T4S(V)X(V)S(W)X(Z)S(V)X(W)T1T2T4T3Suppose T4 requests lock-S(Z)....Example of Granularity HierarchyExample of Granularity Hierarchy The highest level in the example hierarchy is the entire database. The levels below are of type area, file or relation and record in that order.Compatibility Matrix withCompatibility Matrix with Intention Lock Modes Intention Lock ModesThe compatibility matrix for all lock modes is: ISIXSS IXX ISIXSS IXX holderrequestorParent Child can belocked in locked inISIXSSIXXPCIS, SIS, S, IX, X, SIX[S, IS] not necessaryX, IX, [SIX]noneExampleExampleR1t1t2 t3t4T1(IS)T1(S), T2(IX)T2(X)ExamplesExamplesRt1t3t4t2f2.1f2.2f4.2f4.2T1(IX)T1(IX)T1(X)Rt1t3t4t2f2.1f2.2f4.2f4.2T1(IS)T1(S)Rt1t3t4t2f2.1f2.2f4.2f4.2T1(SIX)T1(IX)T1(X)Can T2 access object f2.2 in X mode? What locks will T2 get?ExamplesExamplesT1 scans R, and updates a few tuples:T1 gets an SIX lock on R, then repeatedly gets an S lock on tuples of R, and occasionally upgrades to X on the tuples.T2 uses an index to read only part of R:T2 gets an IS lock on R, and repeatedly gets an S lock on tuples of R.T3 reads all of R:T3 gets an S lock on R. OR, T3 could behave like T2; can use lock escalation to decide which.--IS IX--ISIX S XSX
View Full Document
Unlocking...