Concurrency Control in Database Management System

Contents:
1.What is Concurrency Control?
2.Lock Based Protocol
3.Two Phase Locking Protocol
4.Deadlock

1. Subject : Database Management System Topic : Concurrency Control

2. CONTENTS What is Concurrency Control? Lock Based Protocol Two Phase Locking Protocol Deadlock

3. What is Concurrency Control? The technique is used to protect data when multiple users are accessing same data concurrently (same time) is called concurrency control

4. Lock Based Protocol

5. Lock Based Protocol Lock is a mechanism to control concurrent access to data item Data items can be locked in two modes: Exclusive (X) Mode :- Data item can be both read as well as written. X-lock is requested using lock-X instruction 2) Shared (S) Mode :- Data item can only be read. S-lock is requested using lock-S instruction Lock requests are made to concurrency-control manager Transaction can proceed only after request is granted

6. Lock Based Protocol Lock-compatibility Matrix : S X S TRUE FALSE X FALSE FALSE A transaction may be granted a lock on an item if the requested lock is compatible with locks already held on the item by other transaction Any number of transactions can hold shared locks on an item, But if any transaction holds an exclusive on the item no other transaction may hold any lock on the item

7. Lock Based Protocol If a lock cannot be granted, the requesting transaction is made to wait till all incompatible locks held by other transaction have been released. The lock is then granted. Example: T1: lock-S(A); // Grant-S(A,T1) read (A); unlock(A); lock-S(B); // Grant-S(B,T1) read (B); unlock(B); display(A+B)

8. Pitfalls of Lock Based Protocol Locking as above is not sufficient to guarantee serializability - if A and B get updated in-between the read of A and B , the displayed sum would be wrong. A locking protocol is a set of rules followed by all transactions while requesting and releasing locks. Locking protocols restrict the set of possible schedules.

9. Pitfalls of Lock Based Protocol Neither T 3 nor T 4 can make progress — executing lock-S (B) causes T 4 to wait for T 3 to release its lock on B , while executing lock-X (A) causes T 3 to wait for T 4 to release its lock on A . Such a situation is called a deadlock . To handle a deadlock one of T 3 or T 4 must be rolled back and its locks released.

10. Pitfalls of Lock Based Protocol Starvation is also possible if concurrency control manager is badly designed. For example: A transaction may be waiting for an X-lock on an item, while a sequence of other transactions request and are granted an S-lock on the same item. The same transaction is repeatedly rolled back due to deadlocks. Concurrency control manager can be designed to prevent starvation.

11. Two Phase Locking Protocol

12. Two Phase Locking Protocol This is a protocol which ensures conflict- serializable schedules. Phase 1: Growing Phase transaction may obtain locks transaction may not release locks Phase 2: Shrinking Phase transaction may release locks transaction may not obtain locks The protocol assures serializability. It can be proved that the transactions can be serialized in the order of their lock points (i.e. the point where a transaction acquired its final lock).

13. Two Phase Locking Protocol Two-phase locking does not ensure freedom from deadlocks Cascading roll-back is possible under two-phase locking. To avoid this, follow a modified protocol called strict two-phase locking . Here a transaction must hold all its exclusive locks till it commits/aborts. Rigorous two-phase locking is even stricter: here all locks are held till commit/abort. In this protocol transactions can be serialized in the order in which they commit.

14. Deadlock

15. Deadlock A set of processes is deadlocked if each process in the set is waiting for an event that only another process in the set can cause. T i T j

16. Four Conditions for Deadlock Mutual exclusion condition each resource assigned to 1 process or is available Hold and wait condition process holding resources can request additional No preemption condition previously granted resources cannot forcibly taken away Circular wait condition must be a circular chain of 2 or more processes each is waiting for resource held by next member of the chain

17. Strategies of Deadlock Handling Deadlock prevention. Prevents deadlocks by restraining requests made to ensure that at least one of the four deadlock conditions cannot occur. Deadlock avoidance. Dynamically grants a resource to a process if the resulting state is safe. A state is safe if there is at least one execution sequence that allows all processes to run to completion. Deadlock detection and recovery. That Allows deadlocks to form; then finds and breaks them.

18. Deadlock Avoidance WAIT-DIE Rule : If T i requests a lock on a data item which is already locked by T j , then T i is permitted to wait if ts ( T i ) < ts ( T j ). If ts ( T i ) > ts ( T j ) , then T i is aborted and restarted with the same timestamp. if ts ( T i ) < ts ( T j ) then T i waits else T i dies non-preemptive: T i never preempts T j prefers younger transactions

19. Deadlock Avoidance WOUND-WAIT Rule : If T i requests a lock on a data item which is already locked by T j , then T i is permitted to wait iff ts ( T i )> ts ( T j ). If ts ( T i )< ts ( T j ), then T j is aborted and the lock is granted to T i . if ts ( T i )< ts ( T j ) then T j is wounded else T i waits preemptive: T i preempts T j if it is younger prefers older transactions

20. Deadlock Detection For deadlock detection, the system must provide An algorithm that examines the state of the system to detect whether a deadlock has occurred And an algorithm to recover from the deadlock A detection-and-recovery scheme requires various kinds of overhead Run-time costs of maintaining necessary information and executing the detection algorithm

21. Thank You…