Locking data items to prevent multiple transaction from accessing the items concurrently is the most common method used to ensure serializability. In this section, we examine the basic idea behind the locking concepts and introduce two-phase locking protocol.
Locks
Definition: A lock is a variable associated with data items that describe the status of the item with respect to possible operations that can be applied to it.
There are various types of locks are used in concurrency control. We will discuss some of them in detail in the following subsections.
Binary Locks
As we can see from the name of this type, a binary lock can have two states: locked or unlocked. A lock is associated with each database item X. If the value of the lock on X is “locked” then X cannot be accessed by an operations that request the item. If the value of the lock on X is “unlocked” then X can be accessed when requested.
The function lock(X) let the system known whether data item X is locked or not at a point of time. If lock(X) = 1 then X is being locked, if lock(X) = 0 then X is not locked.
For implementing the binary lock, we have two instructions:
- lock_item(X)
- unlock_item(X)
When a transaction requests access to item X, it must issuing the lock_item(X) operation. If X is currently unlocked then it is locked ( lock(X) → 1). If X is locked then the transaction need to wait.
When a transaction finish using the data item X, it issues the unlock_item(X) operation, which set lock(X) to 0 so that X be accessed by other transaction.
A transaction will not issue lock_item(X) if it is already hold the lock on X.
A transaction will not issue unlock_item(X) unless it already hold the lock on X.
Shared/Exclusive Locks
Binary locks are too restrictive to data item since at a certain point of time, at most one transaction can hold a lock on a data item X. In the database system, it should allow multiple transaction access a data item only for reading. Only when a transaction access data item for writing, the transaction can have exclusive lock.
Therefore, we have a different type of lock called shared/exclusive locks or read/write lock.
A lock associated with one data item . Instead of having only two states, now a lock can have three distict states which are read_locked, write_locked and unlock.
Read_lock is a shared lock since multiple transaction can have read_lock on the same data item in order to read the item. Write_lock is exclusive lock because a single transaction exclusively holds the lock on item.
For this type of lock, we have three instructions:
- lock_S(Q) : used to request a shared lock on data item Q
- lock_X(Q) used to request an exclusive lock on data item Q
- unlock(Q) used to unlock data item Q
To access a data item, transaction T must first lock that item. If the data item is already locked by another transaction in an incompatible mode, the lock wil not be granted until all incompatible locks held by other transaction have been released. In such case, T have to wait. The table below shows us the compatibility relation between two modes of locking; the relation comp(A,B) of the matrix has the value true if and only if mode A is compatible with mode B.
| S | X | |
| S | true | false |
| X | false | false |
Transaction T may unlock data item that it had locked at some ealier point.
Consider two transaction T1 and T2 below:
| T1 | T2 |
| lock_X(B) | lock_S(A) |
| read(B) | read(A) |
| B:= B-50 | lock_S(B) |
| write(B) | read(B) |
| lock_X(A) | display(A+B) |
| read(A) | unlock(A) |
| A:= A + 50 | unlock(B) |
| write(A) | |
| unlock(B) | |
| unlock(A) |
In the figure 1, we can see a situation called deadlock which is the state where neither transaction can proceed with its normal execution since they are waiting for each other to release a lock. T1 is currently holding a exclusive lock on B and T2 is requesting a shared lock on B, T2 is waiting for T1 to unlock B. On the other hand, T2 is holding a shared lock on A, T1 is requesting an exclusive lock on A so it is waiting for T2 to unlock A
| T1 | T2 |
| lock_X(B) | |
| read(B) | |
| B:= B-50 | |
| write(B) | |
| lock_S(A) | |
| read(A) | |
| lock_S(B) | |
| lock_X(A) |
If we do not use locking data items as soon as possible when reading or writing them, we can get inconsistency. However, if we do not unlock data item right before requesting a lock on another item, deadlock might occur. We need a set of rules (protocol) indicating when a transaction may lock or unlock each of data items. Locking protocol limits the number of possible schedules.
Two-phases Locking protocol
This is a common locking protocol in database system.
This protocol requires each transaction issues lock and unlock requests in two phases:
- Growing phase: A lock can be obtained but none can be released
- Shrinking phase: existing locks can be released but no new lock can be obtained.
Transaction T1 and T2 above both are two phase
Example of transaction which is not two phase:
| T3 |
| lock_S(A) |
| read(A) |
| unlock(A) |
| lock_S(B) |
| read(B) |
| unlock(B) |
| display(A+B) |
Two –phase locking does not ensure freedom from dead lock. We can see that T1 and T2 are two phase but schedule 1 (figure 1) still has deadlock.
Two phase locking ensure conflict serializability but does not ensure cascadeless.
Cascading rollbacks can be avoided by a modification of two phase locking called strict two-phase locking protocol.
Strict two-phase locking protocol
In addition to locking being two –phase, all exclusive locks taken by a transaction must be held until that transaction commit.
This requirement ensure that no transaction can read a data item which is locking in exclusive mode by an uncommitted transaction.
Most of the database systems implement this strict two-phase locking protocol
