111/13/97 N-1© 1997 UW CSEConcurrency ControlChapter 18.1, 18.2, 18.5, 18.711/13/97 N-2Locks• A lock is associated with each (lockable)item in the DB– describes status of that itemMain idea: transaction must lock an itembefore using it.• Con: added overhead; decreased parallelism• Pro: used properly, locks guarantee thatschedules are serializable11/13/97 N-3Binary Locks• Binary lock: statuses are "locked" and"unlocked"• Rules for use (just common sense, orcommon courtesy):– T must lock item before reading or writing it.– T must unlock item when finished with it.– T will not try to lock an item it's already locked.– T will not try to unlock an item it doesn'talready have locked.• Implementation: Queue of waiting T's.11/13/97 N-4Multimode Locks• Only slightly more complicated• Three states:– read-locked ("shared-locked")– write-locked ("exclusive-locked)– unlocked• Multiple T's can hold the item read-locked,only one can write-lock it.• Rules of common courtesy similar to binarylocks11/13/97 N-5Are Locks Enough?• L Sadly… no.• Locks alone do not guarantee serializability.• J Happily… there is a simple protocol(2PL) which uses locks to guaranteeserializability.– Easy to explain– Easy to implement– Easy to enforce11/13/97 N-6The Two-Phase Locking ProtocolT is said to follow the 2PL if all lockoperations precede the first unlock.• T must also follow the courtesy rules, ofcourse• Such a T has two phases:– Expanding: locks but no unlocks– Shrinking: unlocks but no locks211/13/97 N-72PL is Good Stuff• 2PL is widely used– Can be adapted to variety of situations, such asdistributed processing• Variations:– Basic 2PL (as described)– Conservative 2PL: T locks all items beforeexecution– Strict 2PL: T doesn't unlock any items untilafter COMMIT or ABORT.11/13/97 N-8But is it the last word?Is there a snake in the Garden of Eden?• 2PL reduces concurrency L– Conservative and strict variants reduce it evenmore, because they hold locks longer.• Basic and strict 2PL are both subject todeadlock L11/13/97 N-9Deadlock• Deadlock occurs when two transactions areeach waiting for the other– e.g., each waiting for a lock that the other holds– can also be deadlocks in larger circles of T's• 2PL is not deadlock-free• Two possible approaches:– Deadlock prevention (don’t let it happen)– Deadlock detection (notice when it's happenedand take recovery action)11/13/97 N-10Deadlock Prevention UsingTimestamps• Transaction timestamps: unique numericalidentifiers, same order as the starting orderof the T's.– Notation: TS(Ti)– Not necessarily a system clock value– Could be simply integer++ for each T• Interesting factoid: global timestamptechniques can be used in distributedsystems, even when each system has itsown clock.11/13/97 N-11Two TS Schemes• Suppose Tj has locked X, and now Ti wantsto lock X.• Wait-die:if TS(Ti)<TS(Tj) then Ti is allowed to waitelse Ti dies and is restarted with its same TS.• Wound-wait:if TS(Ti)<TS(Tj) then abort Tj and restart with itssame TSelse Ti is allowed to wait.11/13/97 N-12TS Schemes• In both schemes, the older T has a certainpreferential treatment.– An aborted and restarted T always keeps itoriginal TS.– Thus it gets older with respect to the other Ts,so eventually it gets the preference.311/13/97 N-13Deadlock Prevention WithoutTimestamps• No waiting: If T needs X and X is alreadylocked, immediately abort T, restart later.– May cause lots of restarting• Cautious waiting: Suppose Ti needs X, andX is already locked by Tj.If Tj is waiting for anything, then abort Tjelse abort Ti.• Timeout: If T waits longer than some fixedtime, abort and restart T.11/13/97 N-14Deadlock Detection• Simple idea:– Do nothing to prevent deadlocks– Make a check periodically to see if there aredeadlock; if so, chose victim(s) to abort• Pro: no elaborate protocols needed• Con: deadlock might go undetected for awhile• Deadlocks tend to be rare on lightly loadedsystems, frequent on heavily loaded systems11/13/97 N-15Detection Algorithm• "Wait-for" graph:– One node per T– Directed edge Ti→Tj if Ti wants to lock Xwhich is already locked by Tj.Theorem: There is a deadlock iff the wait-forgraph has a cycle.• Issues– When to run the algorithm– How to select the victims11/13/97 N-16Starvation and Livelock• Another snake in the Garden of Eden• A T might be aborted and restartedindefinitely: Starvation• A T might wait indefinitely, not for thesame other T (deadlock), but for differentreasons at different times: Livelock• Footnote: Some people use "starvation" foreither situation.11/13/97 N-17Concurrency Control UsingTimestamp OrderingMain idea: insure that conflicting operationsoccur in timestamp order• Each item X must have a read TS and awrite TS– = TS's of the T which last read or wrote X• If T wants to use X, then X's TSs arechecked. For a conflicting operation, TS(T)must be later. If not, T is aborted andrestarted with a new (later) TS.11/13/97 N-18TO Properties• Guarantees serializability– in fact, guarantees conflict serializability• Deadlock free• Not starvation free L– You hope that eventually T becomes "lateenough" to slide through, but that might
View Full Document
Unlocking...