A lock is a mechanism to control concurrent access to a data item.
Data items can be locked in two modes
1. Exclusive(X) mode: Data item can be both read as well as written. X-lock is requested using lock-x instruction.
2. Shared(S)-mode: Data item can only be read. S-lock is requested using lock-s instruction
Lock requests are made to concurrency control manager, a transaction can proceed only after request is granted.
Lock Compatibility matrix
- A transaction may be granted a lock on item if the requested lock is compatible with the locks already held on the item by other transactions.
- Any number of transactions can hold shared locks on an item – but if any transaction holds an exclusive lock on the item no other transaction may hold any lock on them.
- If a lock cannot be granted, the requesting transaction is made to wait till all incompatible locks held by other transaction have been released. Locking protocols restrict the set of possible schedules.
- A transaction can unlock a data item Q by the unlock(Q) instruction. Transaction Ti may unlock a data item that it had locked at some earlier point.
Note: that a transaction must hold a lock on a data item as long as it access that item.
Pitfalls of lock-based Protocols
- Neither T3 nor T4 can make progress, executing lock-s(B) causes T4 to wait for T3 to release its lock on B,while executing lock-x(A) causes T3 to wait for T4 to release its lock on A.
- Such a situation is called Deadlock ,to handle a deadlock one of T3 and T4 must be rolled back and its lock is released.
- The probability of deadlock exists in most locking protocols.Deadlocks are necessary evil.
Starvation is also possible if concurrency control manager is badly designed.
- A transaction may be waiting for an X-lock on an item while a sequence of other transaction request and are granted an S-lock on the same item.
- The concurrency control manager can be designed to prevent starvation.
Two Phase locking Protocol
This protocol ensures conflict serializable schedules
Phase 1 : Growing Phase
– transaction may obtain locks
– transaction may not release locks.
Phase 2 : shrinking phase
– transaction may release locks
– transaction may not obtain locks
- The Protocol (Two Phase locking) assures serializability.
- It can be proved that the transactions can be serialized in the order of their lock points (i.e the point where a acquired its final lock)
- Two phase locking does not ensure freedon from deadlock
- Cascading roll back is possible under two phase locking protocol. To avoid this, follow a modified protocol called strict- two phase locking. Here a transaction must hold all its exclusive locks till it commits/aborts.
- Rigorous two phase locking is even strictier, Here all locks are held till commit/abort. In this protocol transactions can be serialized in the order in which they commit.
Two phase locking with lock conversions
- can acquire a lock-s on item.
- can acquire a lock-x on item.
- can convert a lock-s to a lock-X (upgrade)
- can release a lock-s on item
- can release a lock-x on item
- can convert a lock-x to lock-s (downgrade)
This protocol assures serializability. But still relies on the programmer to insert the various locking instruction.
Implementation of locking
- A lock manager can be implemented as a separate process to which transactions send lock and unlock requests
- The lock manager replies to lock request by sending a lock grant messages ( or a message asking the transaction to rollback, in case of a deadlock).
- The requesting transaction waits until its request is answered
- The lock manager maintains a data structure called a lock table to record granted locks and pending requests
- The lock table is usually implemented as an in-memory hash table, indexed on the name of the data item being locked.