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 S_T1(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