Sunday 13 July 2014

Database Transactions, Lock Management and Deadlock - Part 3

Deadlock

Consider the following example.

T1
T2
Comment
S(A)

Shared lock granted.
R(A)

T1 reads values of A.

S(A)
T2 asks for shared lock. It can be granted.

R(A)
T2 reads values of A.

X(A)
Cannot be granted because T1 holds a shared lock.
X(A)

Cannot be granted because T2 holds a shared lock.
DEADLOCK

Such a cycle of transactions waiting for locks to be released is called a deadlock. Clearly, these two transactions will make no further progress. Worse, they hold locks that may be required by other transactions. The DBMS must either prevent or detect (and resolve) such deadlock situations.

Deadlock Prevention

In deadlock prevention the transactions are processed in such a way that it never leads to a deadlock. Hence when deadlock prevention is used then deadlock detection mechanism is not required.

We can prevent deadlocks by giving each transaction a priority and ensuring that lower priority transactions are not allowed to wait for higher priority transactions. 

One way to assign priorities is to give each transaction a timestamp when it starts up. The lower the timestamp, the higher the transaction's priority, that is, the oldest transaction has the highest priority.


If a transaction Ti requests a lock and transaction Tj holds a conflicting lock, the lock manager can use one of the following two policies:

·         Wait-die: If Ti has higher priority, it is allowed to wait; otherwise it is aborted.
·         Wound-wait: If Ti has higher priority, abort Tj; otherwise Ti waits.

In the wait-die scheme, lower priority transactions can never wait for higher priority transactions. In the wound-wait scheme, higher priority transactions never wait for lower priority transactions. In either case no deadlock cycle can develop.

Deadlock Detection

Deadlocks tend to be rare and typically involve very few transactions. This observation suggests that rather than taking measures to prevent deadlocks, it may be better to detect and resolve deadlocks as they arise.
In deadlock detection the transactions are allowed to happen without any prior planning and the system is periodically checked for deadlocks. If deadlock is detected then some of the transactions are aborted because "abortion of transaction(s) is must to resolve a deadlock".

The lock manager maintains a structure called a waits-for graph to detect deadlock cycles. The nodes correspond to active transactions, and there is an arc from Ti to Tj if (and only if) Ti is waiting for Tj to release a lock. The lock manager adds edges to this graph when it queues lock requests and removes edges when it grants lock requests.

T1
T2
T3
Comment
X(A)


Exclusive lock granted.
W(A)




X(B)

Exclusive lock granted.

W(B)




X(C)
Exclusive lock granted.


W(C)

X(B)


Wait. T2 holds exclusive lock on B.

X(C)

Wait. T3 holds exclusive lock on C.


X(A)
Wait. T1 holds exclusive lock on A.
DEADLOCK

The corresponding waits-for graph is
The waits-for graph is shows a cycle, which indicate deadlock. A deadlock is resolved by aborting a transaction that is on a cycle and releasing its locks; this action allows some of the waiting transactions to proceed.

How frequently you check the graph for deadlock depends upon activity and urgency of the transaction. If an urgent query is executing and the results are not coming then check for deadlock detection every 2 minutes.

Database Transactions, Lock Management and Deadlock - Part 2

LOCKS

The kind of lock required for reading is – shared lock S(A). An object can be under shared lock for many transactions. If smaller pieces of data are locked the more transactions can go concurrently.

The kind of lock required for writing is – exclusive lock X(A). When data object is modified, there will be only one transaction locking the object under exclusive lock. Exclusive lock can be acquired only if there is no shared lock.


The level to which data object will be locked depends on the database management system.

1. Table level locking – The DBMS maintains list of tables and transactions with the kind of lock acquired on each table. Exclusive lock on a table will make many a transactions to wait even though they want to access different tuples.

2. Row level locking – The DBMS will have list of all rows and referred as TableName.RowNumber. The other fields will be is locked and if it is true then what kind of lock. Hence there is an over head and it is very expensive.

3. Cell level locking – This is called granularity of locking.

4. Final level locking – Few rows e.g. 1st to 10th row of a table is locked. It allows more number of transactions to use the data. It also has an overhead but less expensive than row level locking.

LOCK-BASED CONCURRENCY CONTROL

A DBMS must be able to ensure that only serializable, recoverable schedules are allowed, and that no actions of committed transactions are lost while undoing aborted transactions. A DBMS typically uses a locking protocol to achieve this.

A locking protocol is a set of rules to be followed by each transaction (and enforced by the DBMS), in order to ensure that even though actions of several transactions might be interleaved, the net effect is identical to executing all transactions in some serial order.

Strict Two-Phase Locking (Strict 2PL)

The most widely used locking protocol, called Strict Two-Phase Locking, or Strict 2PL, has two rules.

(1) If a transaction T wants to read (respectively, modify) an object, it first requests a shared (respectively, exclusive) lock on the object.

Of course, a transaction that has an exclusive lock can also read the object; an additional shared lock is not required. A transaction that requests a lock is suspended until the DBMS is able to grant it the requested lock.

The DBMS keeps track of the locks it has granted and ensures that if a transaction holds an exclusive lock on an object, no other transaction holds a shared or exclusive lock on the same object.

(2) All locks held by a transaction are released when the transaction is completed.

Whatever locks a transaction wants to obtain, it can ask for before it starts leaving the locks. Hence there will be 2 phases – a growth phase (where it will go on acquiring the locks) and shrink phase (where it will go on releasing the acquired locks)

E.g. consider two transactions T1 and T2. T1 transfer money from A to B and T2 calculates interest for each account. Now both the transactions are executing concurrently.

Dirty read problem solved using strict 2PL

T1
T2
Comment
S(A)

T1 wants to read value of A. Therefore shared lock granted.
R(A)

T1 reads values of A. A = 1000
X(A)

T1 wants to update value of A. Therefore, exclusive lock granted
W(A)

T1 updates the value of A. A = 900

R(A)
T2 wants to read value of A. But T1 holds an exclusive lock which is not released yet hence T2 has to wait.
S(B)


R(B)

B = 400
X(B)


W(B)

B = 500
Commit

Now T1 has released all the locks it has acquired. Hence T2 can continue.

S(A)


R(A)
A = 900

X(A)


W(A)
A = 909

S(B)


R(B)
B = 500

X(B)


W(B)
B = 505

Commit
T2 will release all the locks it has acquired.

The selection among T1 and T2 will depend upon who obtains the lock first. Hence there will be a strict sequence T1, T2 or T2, T1.

Dirty read problem solved using strict 2PL can result in a deadlock as follows.

T1
T2
Comment
S(A)

Shared lock granted.
R(A)

T1 reads values of A.

S(A)
T2 asks for shared lock. It can be granted.

R(A)
T2 reads values of A.

X(A)
Cannot be granted because T1 holds a shared lock.
X(A)

Cannot be granted because T2 holds a shared lock.
DEADLOCK

The solution is to abort one of the transactions. Once a transaction is aborted, whatever was done will be undone. Hence the new read will be a clean read.

Abortion Rules
1.       Whoever puts shared lock first should be aborted.
2.      Low priority transaction should be aborted.
3.      Very recently started transaction should be aborted.
4.      The one which is close to completion should be allowed to continue and the other is aborted.

LOCK MANAGEMENT

The part of the DBMS that keeps track of the locks issued to transactions is called the lock manager. The lock manager maintains the following tables.

1.      Data Object List - Entry for an object which can be a page, a record, and so on, depending on the DBMS is maintained in this table.
2.      Lock table  - A lock table entry for an object contains the following information:
a.      the number of transactions currently holding a lock on the object (this can be more than one if the object is locked in shared mode)
b.      the nature of the lock (shared or exclusive)
c.       a pointer to a queue of lock requests

Consider that there is ST1(O). Now T2 requests an exclusive lock and at the same time T3 requests a shared lock. In the given scenario T2 has to wait but T3 can be allowed to acquire a shared lock on data object O. But if this continues that T4, T5 … are coming with read requests and they are allowed to jump over T2 then T2 will go into infinitely long wait.

Option 1: T2 should be asked to wait and when the “great moment comes” of no transaction having any lock on data object O, T2 will be allowed to acquire the exclusive lock.

Option 2: If priority of Tn+1 > Tn, then Tn+1 will be allowed to jump in. In this case if T3 is having high priority then it will be allowed else it has to wait and T2 will be given chance to acquire exclusive lock. But if all the transactions coming after T2 are of high priority then T2 will go in infinite wait mode.

Option 3: Allow Tn+1 but at the same time increase the priority of Tn by 1. So Tn+2, Tn+3 may jump over Tn, but a point will reach when T1 will be having very high priority so no one will jump over. Tn will be allowed to move ahead, no matter who all are behind.

Now consider T1, T2 and T3 have share lock on object A and there is a request from T1 for exclusive lock on A. The exclusive lock will be granted only when DBMS ensures that T2, T2 dies off i.e. commit and are not going to come back.

Consider another scenario where T1 and T2 both want exclusive lock on data object A. This leads to a deadlock. Hence DBMS must know the access trend of a transaction. This helps in identifying how many shared and exclusive locks are required by each transaction, on which al data objects and in which order. 

If a transaction holding many locks is aborted then –
1.      You have to release many locks.
2.      But as many locks are released, then many objects will be freed and other transactions can be facilitated.

The trend of the transaction tells where the transaction has reached. If it is near to completion then do no abort

Do you like this article?