Concurrency Control Example Schedules Transactions T1 transfers 50 from A to B T2 transfers 10 of A to B T1 read A A A 50 write A read B B B 50 write B Example 1 a serial schedule T2 Constraint The sum of A B must be the same Before 100 50 150 consistent read A tmp A 0 1 A A tmp write A read B B B tmp write B After 45 105 Example Schedule Another serial schedule T1 read A A A 50 write A read B B B 50 write B T2 read A tmp A 0 1 A A tmp write A read B B B tmp write B Before 100 50 After 40 110 150 consistent Consistent but not the same as previous schedule Either is OK Example Schedule Cont Another good schedule T1 read A A A 50 write A T2 Effect read A tmp A 0 1 A A tmp write A read B B B 50 write B read B B B tmp write B Before A 100 B 50 After 45 105 Same as one of the serial schedules Serializable Example Schedules Cont A bad schedule T1 read A A A 50 T2 read A tmp A 0 1 A A tmp write A read B write A read B B B 50 write B Before 100 50 150 After 50 60 110 Not consistent Non Serializable B B tmp write B Equivalence by Swapping T1 read A A A 50 write A T2 read A tmp A 0 1 A A tmp write A read B B B 50 write B T1 read A A A 50 write A read B B B 50 write B read B B B tmp write B T2 read A tmp A 0 1 A A tmp write A read B B B tmp write B Equivalence by Swapping T1 read A A A 50 write A T2 read A tmp A 0 1 A A tmp write A read B B B 50 write B T1 read A A A 50 write A read B B B 50 write B read B B B tmp write B T2 read A tmp A 0 1 A A tmp write A read B B B tmp write B Equivalence by Swapping T1 read A A A 50 write A T2 read A tmp A 0 1 A A tmp write A read B B B 50 write B read B B B tmp write B T1 read A A A 50 write A read B B B 50 write B T2 read A tmp A 0 1 A A tmp write A read B B B tmp write B Example Schedules Cont A bad schedule T1 read A A A 50 X T2 read A tmp A 0 1 A A tmp write A read B write A read B B B 50 write B B B tmp write B Y Can t move Y below X read B and write B conflict Example Schedules Cont A bad schedule T1 read A A A 50 X T2 read A tmp A 0 1 A A tmp write A read B write A read B B B 50 write B Y Can t move Y below X read B and write B conflict Other options don t work either So Not Conflict Serializable B B tmp write B Lock instructions New instructions lock S shared lock request lock X exclusive lock request unlock release previously held lock Example T1 lock X B read B B B 50 write B unlock B lock X A read A A A 50 write A unlock A T2 lock S A read A unlock A lock S B read B unlock B display A B Locking Issues No xction proceeds Deadlock T1 T1 waits for T2 to unlock A lock X B T2 waits for T1 to unlock B read B T2 B B 50 write B lock S A Rollback transactions Can be costly read A lock S B lock X A Locking Issues Does not ensure serializability by itself T1 lock X B read B B B 50 write B unlock B lock X A read A A A 50 write A unlock A T2 lock S A read A unlock A lock S B read B unlock B display A B T2 displays 50 less 2PhaseLocking Example T1 in 2PL Growing phase Shrinking phase T1 lock X B read B B B 50 write B lock X A read A A A 50 write A unlock B unlock A 2PL Issues 2PL does not prevent deadlock T1 T2 lock X B read B 2 xctions involved Rollbacks expensive B B 50 write B lock S A read A lock S B lock X A Strict 2PL T1 T2 T3 lock X A read A lock S B read B write A unlock A lock X A Strict 2PL will not allow that read A write A unlock A lock S A read A xction fails Dealing with Deadlocks How do you detect a deadlock Wait for graph Directed edge from Ti to Tj Ti waiting for Tj T1 T2 T3 T2 T4 T1 T4 T3 X Z X V X W S V S W S V Suppose T4 requests lock S Z Example 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 with Intention Lock Modes The compatibility matrix for all lock modes is requestor IS holder IX S S IX X IS IX S S IX X Parent locked in IS IX S SIX X Child can be locked in IS S IS S IX X SIX S IS not necessary X IX SIX none P C Example T1 IS T2 IX R1 t1 t2 T1 S t3 t4 T2 X T1 IX t1 Examples T1 IX T1 X f2 1 T1 IS R t2 f2 2 t3 t4 f4 2 t1 T1 S f4 2 R t3 t2 f2 1 t4 f4 2 f2 2 T1 SIX R Can T2 access object f2 2 in X mode What locks will T2 get t1 T1 IX T1 X f2 1 t2 f2 2 t3 t4 f4 2 f4 2 f4 2 Examples T1 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 S X IS IX S X
View Full Document
Unlocking...