《數(shù)據(jù)庫系統(tǒng)》英文教學(xué)課件

數(shù)據(jù)庫系統(tǒng)英文教學(xué)課件,數(shù)據(jù)庫系統(tǒng),數(shù)據(jù)庫,系統(tǒng),英文,教學(xué),課件 Concurrency ControlR&G-Chapter 17Smile,it is the key that fits the lock of everybodys heart.Anthony J.DAngelo,The College Blue BookReviewACID transaction semantics.Today:focus on Isolation propertySerial schedules safe but slowTry to find schedules equivalent to serial Conflicting OperationsNeed a tool to decide if 2 schedules are equivalentUse notion of“conflicting”operationsDefinition:Two operations conflict if:They are by different transactions,they are on the same object,and at least one of them is a write.Conflict Serializable SchedulesDefinition:Two schedules are conflict equivalent iff:They involve the same actions of the same transactions,andevery pair of conflicting actions is ordered the same wayDefinition:Schedule S is conflict serializable if:S is conflict equivalent to some serial schedule.Note,some“serializable”schedules are NOT conflict serializableA price we pay to achieve efficient enforcement.Conflict Serializability IntuitionA schedule S is conflict serializable if:You are able to transform S into a serial schedule by swapping consecutive non-conflicting operations of different transactions.Example:R(A)R(B)W(A)W(B)R(A)W(A)R(B)W(B)W(A)R(B)R(B)R(A)W(B)W(A)W(B)R(A)R(A)R(B)W(A)W(B)R(A)W(A)R(B)W(B)Conflict Serializability(Continued)Heres another example:Serializable or not?R(A)W(A)R(A)W(A)NOT!Dependency GraphDependency graph:One node per XactEdge from Ti to Tj if:An operation Oi of Ti conflicts with an operation Oj of Tj andOi appears earlier in the schedule than Oj.Theorem:Schedule is conflict serializable if and only if its dependency graph is acyclic.TiTjExampleA schedule that is not conflict serializable:The cycle in the graph reveals the problem.The output of T1 depends on T2,and vice-versa.T1T2ABDependency graphT1:R(A),W(A),R(B),W(B)T2:T1:R(A),W(A),R(B),W(B)T2:R(A),W(A),R(B),W(B)T1:R(A),W(A),R(B),W(B)T2:R(A),W(A),R(B),W(B)T1:R(A),W(A),R(B),W(B)T2:R(A),W(A),R(B),W(B)T1:R(A),W(A),R(B),W(B)T2:R(A),W(A),R(B),W(B)Two-Phase Locking(2PL)rules:Xact must obtain a S(shared)lock before reading,and an X(exclusive)lock before writing.Xact cannot get new locks after releasing any locks.SXSXLockCompatibilityMatrixTwo-Phase Locking(2PL),cont.2PL guarantees conflict serializabilitytime#locks heldrelease phaseacquisition phaseBut,does not prevent Cascading Aborts.Strict 2PLProblem:Cascading AbortsExample:rollback of T1 requires rollback of T2!Strict Two-phase Locking(Strict 2PL)protocol:Same as 2PL,except:Locks released only when transaction completes i.e.,either:(a)transaction has committed(commit record on disk),or (b)transaction has aborted and rollback is complete.T1:R(A),W(A),R(B),W(B),AbortT2:R(A),W(A)Strict 2PL(continued)#locks heldacquisition phasetimerelease all locks at end of xactNext.A few examplesLock_X(A)Read(A)Lock_S(A)A:=A-50Write(A)Unlock(A)Read(A)Unlock(A)Lock_S(B)Lock_X(B)Read(B)Unlock(B)PRINT(A+B)Read(B)B:=B+50Write(B)Unlock(B)Non-2PL,A=1000,B=2000,Output=?Lock_X(A)Read(A)Lock_S(A)A:=A-50Write(A)Lock_X(B)Unlock(A)Read(A)Lock_S(B)Read(B)B:=B+50Write(B)Unlock(B)Unlock(A)Read(B)Unlock(B)PRINT(A+B)2PL,A=1000,B=2000,Output=?Lock_X(A)Read(A)Lock_S(A)A:=A-50Write(A)Lock_X(B)Read(B)B:=B+50Write(B)Unlock(A)Unlock(B)Read(A)Lock_S(B)Read(B)PRINT(A+B)Unlock(A)Unlock(B)Strict 2PL,A=1000,B=2000,Output=?Venn Diagram for SchedulesAll SchedulesAvoid Cascading AbortSerialView SerializableConflict Serializable Which schedules does Strict 2PL allow?All SchedulesAvoid Cascading AbortSerialView SerializableConflict SerializableLock ManagementLock and unlock requests handled by Lock ManagerLM keeps an entry for each currently held lock.Entry contains:List of xacts currently holding lockType of lock held(shared or exclusive)Queue of lock requestsLock Management,cont.When lock request arrives:Does any other xact hold a conflicting lock?If no,grant the lock.If yes,put requestor into wait queue.Lock upgrade:xact with shared lock can request to upgrade to exclusiveLock_X(A)Lock_S(B)Read(B)Lock_S(A)Read(A)A:=A-50Write(A)Lock_X(B)ExampleDeadlocksDeadlock:Cycle of transactions waiting for locks to be released by each other.Two ways of dealing with deadlocks:preventiondetectionMany systems just punt and use TimeoutsWhat are the dangers with this approach?Deadlock DetectionCreate and maintain a“waits-for”graphPeriodically check for cycles in graphDeadlock Detection(Continued)Example:T1:S(A),S(D),S(B)T2:X(B)X(C)T3:S(D),S(C),X(A)T4:X(B)T1T2T4T3Deadlock PreventionAssign priorities based on timestamps.Say Ti wants a lock that Tj holds Two policies are possible:Wait-Die:If Ti has higher priority,Ti waits for Tj;otherwise Ti abortsWound-wait:If Ti has higher priority,Tj aborts;otherwise Ti waitsWhy do these schemes guarantee no deadlocks?Important detail:If a transaction re-starts,make sure it gets its original timestamp.-Why?SummaryCorrectness criterion for isolation is“serializability”.In practice,we use“conflict serializability,”which is somewhat more restrictive but easy to enforce.Two Phase Locking and Strict 2PL:Locks implement the notions of conflict directly.The lock manager keeps track of the locks issued.Deadlocks may arise;can either be prevented or detected.