Lock Based Protocol 2

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

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

Pit falls of lock based protocol

• 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.

Lock conversions
Two phase locking with lock conversions
Fisrt 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 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

1. A lock manager can be implemented as a separate process to which transactions send lock and unlock requests
2. 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).
3. The requesting transaction waits until its request is answered
4. The lock manager maintains a data structure called a lock table to record granted locks and pending requests
5. The lock table is usually implemented as an in-memory hash table, indexed on the name of the data item being locked.