Lock Based Protocols

Lock-Based Protocols

A lock is simply a mechanism to control concurrent access to data item. Concurrency control in database management system ensures that database transactions are performed concurrently without violating the data integrity of a database. The main goal of concurrency control is to allow several transactions to be executing simultaneously in such a way that collection of manipulated data item is left in a consistent state. A locking protocol is a set of rules which are followed by all transactions while requesting and releasing locks. Locking is a procedure that is used for controlling the concurrent access of data when one transaction is accessing the database. A lock may be a deny access to other transactions to prevent incorrect results. Data item can be locked in two modes:

1. Exclusive (X) mode: In this mode, data item can be read as well as written. The lock-X instructions are used for requesting X-lock.
2. Shared (S) mode: In this mode, data item can be read only. The lock-S instructions are used for requesting S-lock.

Lock requests are made to concurrency-control manager. Transaction is to be proceeded only after request is granted. Lock-compatibility matrix:

A transaction may be granted a lock on an item if the requested lock is compatible with the locks that are already held on the item by another transactions. If a transaction has a shared lock on a data item, it can be read the item but not update it. If a transaction has a shared lock on data items then the other transactions can obtain a shared lock on the data item but not exclusive locks. If a transaction has an exclusive lock on a data item it can be read and updated. If a transaction has an exclusive lock on data items then the other transactions cannot obtain either a shared lock or an exclusive lock on the data item. Any number of transactions can hold shared locks on an item but if any transactions holds an exclusive lock on the item no other transaction may hold any lock on the item.

If a lock cannot be granted, the requesting transaction must wait till all incompatible locks held by other transactions have been released and then the lock is granted.

Pitfalls of Lock-Based Protocols:

Consider the partial schedule:

Neither T₃ nor T₄ can make progress because executing the lock- S (B) causes T₄ to wait for T₃ to release its lock on B while executing lock-X(A) causes T₃ to wait for T₄to release its lock on A. Such a situation is called a deadlock. In order to handle a deadlock one of T₃ orT₄ must be rolled back and its locks are released.Starvation is also possible if concurrency control manager is designed badly. For example:

• Suppose a transaction T2 has a shared mode lock on a data item and another transaction T1 requests an exclusive mode lock on the data item. Clearly T1 has to wait for T2 to release the shared mode lock.
• Meanwhile a transaction T3 may request a shared mode lock on same data item. At this time T2 may release the lock but still T1 has to wait for T3 to finish
• But again, there may be a new transaction T4 that request a shared mode lock on the same data item and is granted the lock before the T3 release it.
• It is possible that there is a sequence of transactions that each requests a shared mode lock on the same data item and each transaction releases the lock a short while after it is granted but T1 never gets the exclusive mode lock on the data item. Therefore the transaction T1 may never make progress and is said to be starved.

Here the concurrency control manager can be designed to prevent starvation. To avoid transaction by granting locks in the following manner:

When a transaction T_i requests for 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 requests before T_i.

The Two-Phase Locking Protocol

Example of a transaction performing not two phase locking:

T₂: lock-S (A);
read (A);
unlock (A);
lock-S (B);
read (B);
unlock (B);
display (A+B).

Locking as presented above is not sufficient to guarantee serializability because if A and B get updated in-between the read of A and B the displayed sum would be wrong. This is a protocol which ensures conflict-serializable schedules.

Phase 1: Growing Phase

• The transaction may obtain locks
• The transaction may not obtain release locks.

Phase 2: Shrinking Phase

• The transaction may release locks
• The 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 that is the point where a transaction acquired its final lock. Two-phase locking does not ensure freedom from deadlocks. Cascading roll-back is possible under two-phase locking. To avoid this we must follow a modified protocol which is called as strict two-phase locking. Here a transaction must hold all its exclusive locks till it commits/aborts.

The rigorous two-phase locking is even stricter as all the locks here are held till commit or abort. In this protocol the transactions can be serialized in the order of the way they commit. There can be conflict serializable schedules which cannot be obtained if two-phase locking is used. However in the absence of extra information (e.g., ordering of access to data) two-phase locking is needed for conflict serializability in the following sense:
For a given a transaction T_i that does not follow two-phase locking we can find a transaction T_j that uses two-phase locking and a schedule for T_i and T_j that is not conflict serializable.

Lock Conversions

Lock conversion provide a mechanism for upgrading a shared lock to exclusive lock and downgrading an exclusive lock to a shared lock. Upgrading can take place in only the growing phase where as downgrading can take places in only the shrinking phase. Two-phase locking with lock conversions:

• First Phase:
  Can acquire a lock-S on item.
  Can acquire a lock-X on item.
  Can convert a lock-S to a lock-X (upgrade).
• Second Phase:
  Can release a lock-S.
  Can release a lock-X.
  Can convert a lock-X to a lock-S (downgrade).

This protocol assures serializability however it still relies on the programmer to insert the various locking instructions.

Implementation of Locking:

A lock manager can be implemented as a separate process where transactions send lock and unlock requests. The lock manager replies to a lock request by sending a lock grant messages (or a message asking the transactions to roll back in case of a deadlock). The requesting transactions waits until it receives answer for its request. The lock manager maintains a data-structure called a lock table in order to record the granted locks and pending requests. The lock table is usually implemented as an in-memory hash table and it is indexed on the name of the data item being locked. Black rectangles indicates the granted locks while white ones indicates the waiting requests. The lock table also records the type of lock that is granted or requested. A new request is added to the end of the queue of requests for the data item and granted if it is compatible with all the earlier locks. Unlock requests result in the request which is being deleted and later the requests are checked to see whether they can now be granted. If the transaction aborts then all waiting or granted requests of the transaction are deleted. The lock manager may keep a list of locks held by each transaction to implement this efficiently.

References:

1. H.F.Korth and A. Silberschatz,"Database system concepts",McGraw Hill,2010
2. A.K.Majumdar and p, Bhatt acharya,"Database Management Systems",Tata McGraw Hill,India,2004
3. F.Korth, Henry. Database System Concepts. 6th edition.