lect(8)Concurrency Control .pptx

Database Management Systems Concurrency Control Chapter 19  Conflict Serializable Schedules Two schedules are conflict equivalent if: – Involve the same actions of the same transactions – Every pair of conflicting actions is ordered the same way Schedule S is conflict se...

Database Management Systems Concurrency Control Chapter 19  Conflict Serializable Schedules Two schedules are conflict equivalent if: – Involve the same actions of the same transactions – Every pair of conflicting actions is ordered the same way Schedule S is conflict serializable if S is conflict equivalent to some serial schedule Example A schedule that is not conflict serializable: The cycle in the graph reveals the problem. The output of T1 depends on T2, and viceversa Dependency Graph Dependency graph: One node per Xact; edge from Ti to Tj if Tj reads/writes an object last written by Ti. Theorem: Schedule is conflict serializable if and only if its dependency graph is acyclic Review: Strict 2PL Strict Two-phase Locking (Strict 2PL) Protocol: − S(shared) and X (exclusive) lock on object before Reading and writing respectively. − Locks released when the Xact completes. − If an Xact holds an X lock on an object, no other Xact can get a lock (S or X) on that object. Strict 2PL allows only schedules whose precedence graph is acyclic  Two-Phase Locking (2PL) Two-Phase Locking Protocol − S(shared) and X (exclusive) lock on object before Reading and writing respectively. − A transaction can not request additional locks once it releases any locks. − If an Xact holds an X lock on an object, no other Xact can get a lock (S or X) on that object.  View Serializability Schedules S1 and S2 are view equivalent if: – If Ti reads initial value of A in S1, then Ti also reads initial value of A in S2 – If Ti reads value of A written by Tj in S1, then Ti also reads value of A written by Tj in S2 – If Ti writes final value of A in S1, then Ti also writes final value of A in S2 Example (View Serializability)  Lock Management Lock and unlock requests are handled by the lock manager Lock table entry: – Number of transactions currently holding a lock – Type of lock held (shared or exclusive) – Pointer to queue of lock requests  Lock Management cont’d Locking and unlocking have to be atomic operations Lock upgrade: transaction that holds a shared lock can be upgraded to hold an exclusive lock Deadlocks Deadlock: Cycle of transactions waiting for locks to be released by each other. Two ways of dealing with deadlocks: – Deadlock prevention – Deadlock detection  Deadlock Prevention Assign priorities based on timestamps. Assume Ti wants a lock that Tj holds. Two policies are possible: – Wait-Die: It Ti has higher priority, Ti waits for Tj; otherwise Ti aborts – Wound-wait: If Ti has higher priority, Tj aborts; otherwise Ti waits  Deadlock Detection Create a waits-for graph: – Nodes are transactions – There is an edge from Ti to Tj if Ti is waiting for Tj to release a lock Periodically check for cycles in the waits-for graph Deadlock Detection (Continued)