Two-phase locking

• Transaction is not allowed any new locks after it has released a lock.
• The first phase of each transaction is a ‘growing phase’, during which new locks are acquired.
• In the second phase, the locks are released (a ‘shrinking phase’). 

Strict two-phase locking

• Any locks applied during the progress of a transaction are held until the transaction commits or aborts. 
• When a transaction commits, to ensure recoverability, the locks must be held until all the objects it updated have been written to permanent storage. 

Concurrency control protocols are designed to cope with conflicts between operations in different transactions on the same object. 

Two types of locks are used: read locks and write locks.

All the transactions reading the same object share its read lock – read locks are sometimes called shared locks.

Figure 14: Transactions T and U with exclusive locks

Operation conflict rules

• If a transaction T has already performed a read operation on a particular object, then a concurrent transaction U must not write that object until T commits or aborts. 
• If a transaction T has already performed a write operation on a particular object, then a concurrent transaction U must not read or write that object until T commits or aborts. 

For the first condition: a request for a write lock on an object is delayed by the presence of a read lock belonging to another transaction.

For the second condition: a request for either a read lock or a write lock on an object is delayed by the presence of a write lock belonging to another transaction. 

Inconsistent retrievals: 

• Prevented by performing the retrieval transaction before or after the update transaction.
• If it comes first, its read lock delays the update transaction.
• It if comes second, its request for read locks causes it to be delayed until the update transaction has completed.
  

  
  Figure 15: Lock compatibility
  

Lost updates

• Prevented by making later transactions delay their reads until the earlier one have been completed.
• Achieved by each transaction setting a read lock when it reads an object and then promoting it to a write lock when it writes the same object – when a subsequent transaction requires a read lock it will be delayed until any current transaction has completed. 
• A transaction with a read lock that is shared with other transactions cannot promote its read lock to a write lock. 
• This transaction must request a write lock and wait for the other read locks to be released. 
  
  

  Figure 16: Use of locks in strict two-phase locking

Increasing concurrency in locking schemes

• Two-version locking
  • Allows one transaction to write tentative versions of objects while other transactions read from the committed versions of the same objects. 
  • Read operations only wait if another transaction is currently committing the same object.
  • Transactions cannot commit their write operations immediately if other uncompleted transactions have read the same objects. 
  • Must wait until the reading transactions have completed.
  • Deadlocks may occur
    • Transactions are waiting to commit
    • May need to abort some transactions when they are waiting to commit to resolve deadlocks.
  • 3 types of locks: read lock, write lock and commit lock.
• i. Read lock 
  • set before the transaction’s read operation on an object
  • Attempt to set will be successful unless the object has a commit lock.
• ii. Write lock
  • Set before a transaction’s write operation is performed on an object.
  • Attempt to set will be successful unless the object has a write lock or a commit lock
• When the transaction coordinator receives a request to commit a transaction, it attempts to convert all the transaction’s write locks to commit locks.
• If any of the objects have outstanding read locks, the transaction must wait until the other transactions have completed and the locks are released. 
  
  

  Figure 24: Lock compatibility (read, write and commit locks)
  

  
  

• iii. Hierarchic locks

  • In some applications, the granularity suitable for one operation is not appropriate for another operation.
  • Example:
    • Majority of the operations require locking at the granularity of an account.
    • But the branchTotal operation require a read lock on all of the accounts. 
• To reduce locking overheads, it would be useful to allow locks of mixed granularity to coexist. 
• At each level, the setting of a parent lock has the same effect as setting all the equivalent child locks. 
• Banking example: branch is parent and accounts are children.
• Also useful in a diary system.

Figure 25: Lock hierarchy for the banking example

Figure 26: Lock hierarchy for a diary