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

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

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.
Lock Based Protocol
2.8 (56.3%) 27 votes

2 thoughts on “Lock Based Protocol

  1. Reply popina Jan 8,2015 12:12 am

    This is a great site. It helped me a lot.
    Thank you a lot!

Leave a Reply