Concurrency Control

• When several transactions execute concurrently in the database, however, the isolation property may no longer be preserved.




• To ensure that it is, the system must control the interaction among the concurrent transactions; this control is achieved through one of a variety of mechanisms called concurrency control schemes.

Lock-Based Protocols

• To ensure isolation we require that data items be accessed in a mutually exclusive manner; that is, while one transaction is accessing a data item, no other transaction can modify that data item.




• The most common method used to implement this requirement is to allow a transaction to access a data item only if it is currently holding a lock on that item.




• There are two modes in which a data item may be locked :-




1. Shared : If T_i has obtained a shared mode lock on item Q, then T_i can read Q but not write Q.




2. Exclusive : If T_i has obtained an exclusive mode lock on item Q, then T_i can read Q and write Q.




• The transaction makes the request to the concurrency-control manager. The transaction can proceed with the operation only after the concurrency-control manager grants the lock to the transaction.




• The use of these two lock modes allows multiple transactions to read a data item but limits write access to just one transaction at a time.




• Shared mode is compatible with shared mode, but not with exclusive mode. At any time, several shared-mode locks can be held simultaneously (by different transactions) on a particular data item. A subsequent exclusive-mode lock request has to wait until the currently held shared-mode locks are released.




• Deadlock is a situation that is created when locking mechanism is used. The transactions wait for each other indefinitely in a deadlock. This situation can be resolved by rolling back a few transactions and unlocking data-items held by them.

Granting of Locks - Starvation

• Suppose a data item Q is present and a transaction T₁ holds a shared lock on it.




• T₂ requests for an exclusive lock on Q but has to wait as locks are incompatible.




• However a second transaction T₃ that request shared lock may be granted it. Now T₂ has to wait for T₃ to be over.




• Thus, T₂ may never get its lock granted as shared lock requests may come from other transactions. This situation is called starvation of T₂.




• We can avoid starvation of transactions by granting locks in the following manner: When a transaction T_i requests a lock on a data item Q in a particular mode M, the concurrency-control manager grants the lock provided that:




• There is no other transaction holding a lock on Q in a mode that conflicts with M.




• There is no other transaction that is waiting for a lock on Q and that made its lock request before T_i.

The Two-Phase Locking Protocol

• This protocol requires that each transaction issue lock and unlock requests in two phases:




1. Growing phase : A transaction may obtain locks, but may not release any lock.




2. Shrinking phase : A transaction may release locks, but may not obtain any new locks.




• Initially, a transaction is in the growing phase. The transaction acquires locks as needed. Once the transaction releases a lock, it enters the shrinking phase, and it can issue no more lock requests.




• The two-phase locking protocol ensures conflict serializability.




• Two-phase locking does not ensure freedom from deadlock.




• Cascading rollback may occur under two-phase locking.





• T3 and T4 are in Two phase (deadlocked) but T1 and T2 are not in two phase.




• Note that the unlock instructions do not need to appear at the end of the transaction.




• Although T5, T6, T7 are in two phase but a failure of T5 leads to cascading rollback of T6 and T7.

Strict two-phase locking protocol.

• Cascading rollbacks can be avoided by a modification of two-phase locking called the strict two-phase locking protocol.




• This protocol requires not only that locking be two phase, but also that all exclusive-mode locks taken by a transaction be held until that transaction commits.




• This requirement ensures that any data written by an uncommitted transaction are locked in exclusive mode until the transaction commits, preventing any other transaction from reading the data.

Rigorous two-phase locking protocol

• Requires that all locks be held until the transaction commits.




• With rigorous two-phase locking, transactions can be serialized in the order in which they commit.

Deadlock Handling

• There are two principal methods for dealing with the deadlock problem. We can use a deadlock prevention protocol to ensure that the system will never enter a deadlock state.




• Alternatively, we can allow the system to enter a deadlock state, and then try to recover by using a deadlock detection and deadlock recovery scheme.




• Both methods may result in transaction rollback. Prevention is commonly used if the probability that the system would enter a deadlock state is relatively high; otherwise, detection and recovery are more efficient.




• Note that a detection and recovery scheme requires overhead that includes not only the run-time cost of maintaining the necessary information and of executing the detection algorithm, but also the potential losses inherent in recovery from a deadlock.

Deadlock Prevention

• There are two approaches to deadlock prevention.




1. One approach ensures that no cyclic waits can occur by ordering the requests for locks, or requiring all locks to be acquired together.




2. The other approach is closer to deadlock recovery, and performs transaction rollback instead of waiting for a lock, whenever the wait could potentially result in a deadlock




• First approach requires that :-




1. each transaction locks all its data items before it begins execution




2. either all are locked in one step or none are locked




3. There are two main disadvantages to this protocol :




1. it is often hard to predict, before the transaction begins, what data items need to be locked;




2. data-item utilization may be very low, since many of the data items may be locked but unused for a long time.




• Second approach for preventing deadlocks is : -




1. To impose an ordering of all data items, and to require that a transaction lock data items only in a sequence consistent with the ordering.




2. A variation of this approach is to use a total order of data items, in conjunction with two-phase locking.




3. Once a transaction has locked a particular item, it cannot request locks on items that precede that item in the ordering.




4. This scheme is easy to implement, as long as the set of data items accessed by a transaction is known when the transaction starts execution.




• The alternate strategy allows system uses these timestamps to decide whether a transaction should wait for a resource or roll back. Two different deadlock-prevention schemes using timestamps have been proposed:




1. Wait die (nonpreemptive technique) : When transaction T_i requests a dataitem currently held by T_j , T_i is allowed to wait only if it has a timestamp smaller than that of T_j. Otherwise, T_i is rolled back (dies).




2. Wound wait (preemptive technique) : When transaction T_i requests a dataitem currently held by T_j , T_i is allowed to wait only if it has a timestamp larger than that of T_j. Otherwise, T_j is rolled back.




• The major problem with both of these schemes is that unnecessary rollbacks may occur.

Graph-Based Protocols - tree protocol

• In the tree protocol, the only lock instruction allowed is lock - X. Each transaction T_i can lock a data item at most once, and must observe the following rules:




1. The first lock by T_i may be on any data item.




2. Subsequently, a data item Q can be locked by T_i only if the parent of Q is currently locked by T_i.




3. Data items may be unlocked at any time.




4. A data item that has been locked and unlocked by T_i cannot subsequently be relocked by T_i.




• All schedules that are legal under the tree protocol are conflict serializable.






1. T₁₀ : lock-X(B); lock-X(E); lock-X(D); unlock(B); unlock(E); lock-X(G); unlock(D); unlock(G)




2. T₁₁ : lock-X(D); lock-X(H); unlock(D); unlock(H)




3. T₁₂ : lock-X(B); lock-X(E); unlock(E); unlock(B).




4. T₁₃ : lock-X(D); lock-X(H); unlock(D); unlock(H).







• Tree protocol ensures freedom from deadlock. It does not ensure recoverability and cascadelessness. To ensure recoverability and cascadelessness, the protocol can be modified to not permit release of exclusive locks until the end of the transaction.




• The tree-locking protocol has an advantage over the two-phase locking protocol in that unlocking may occur earlier. Earlier unlocking may lead to shorter waiting times, and to an increase in concurrency.




• However, the protocol has the disadvantage that, in some cases, a transaction may have to lock data items that it does not access. For example, a transaction that needs to access data items A and J in the database graph of Figure above must lock not only A and J,but also data items B, D and H.




• This additional locking results in increased locking overhead, the possibility of additional waiting time, and a potential decrease in concurrency. Further, without prior knowledge of what data items will need to be locked, transactions will have to lock the root of the tree, and that can reduce concurrency greatly.

Deadlock Detection - wait-for graph

• Deadlocks can be described precisely in terms of a directed graph called a wait-for graph. This graph consists of a pair G =(V, E), where V is a set of vertices and E is a set of edges. The set of vertices consists of all the transactions in the system.




• If there is an edge from T_i to T_j in the wait for graph, this means that T_i is waiting for transaction T_j to release a data item that it needs.




• A deadlock exists in the system if and only if the wait-for graph contains a cycle. Each transaction involved in the cycle is said to be deadlocked.




• To detect deadlocks, the system needs to maintain the wait-for graph, and periodically to invoke an algorithm that searches for a cycle in the graph.

VIEW SERIALIZABILITY

• Consider two schedules S and S' where the same set of transactions participates in both schedules. The schedules S and S' are said to be view equivalent if three conditions are met:




1. For each data item Q, if transaction T_i reads the initial value of Q in schedule S, then transaction T_i must, in schedule S', also read the initial value of Q.




2. For each data item Q, if transaction T_i executes read(Q) in schedule S, and if that value was produced by a write(Q) operation executed by transaction T_j, then the read(Q) operation of transaction T_i must, in schedule S' , also read the value of Q that was produced by the same write(Q) operation of transaction T_j.




3. For each data item Q, the transaction (if any) that performs the final write(Q) operation in schedule S must perform the final write(Q) operation in schedule S'.






• Every conflict-serializable schedule is also view serializable, but there are view-serializable schedules that are not conflict serializable.




• Blind writes are Write(Q) operations without Read(Q) they appear in a view-serializable schedule that is not conflict serializable.

Previous

Next