Data Structure in Lock Manager
The data structure required for the implementation of locking is called a Lock table.
- It is a hash table where the names of data items are used as a hashing index.
- Each locked data item has a linked list associated with it.
- Every node in the linked list represents the transaction requested for lock, the mode of lock requested (mutual/exclusive), and the current status of the request (granted/waiting).
- Every new lock request for the data item will be added to the end of the linked list as a new node.
- Collisions in the hash table are handled by the technique of separate chaining.
Consider the following example of a lock table:
Explanation: In the above figure, the locked data items present in the lock table are 5, 47, 167, and 15. The transactions which have requested for lock have been represented by a linked list shown below them using a downward arrow. Each node in the linked list has the name of the transaction which has requested the data item like T33, T1, T27, etc. The color of the node represents the status i.e. whether the lock has been granted or waiting. Note that a collision has occurred for data items 5 and 47. It has been resolved by separate chaining where each data item belongs to a linked list. The data item is acting as a header for a linked list containing the locking request.
Implementation of Locking in DBMS
Locking protocols are used in database management systems as a means of concurrency control. Multiple transactions may request a lock on a data item simultaneously. Hence, we require a mechanism to manage the locking requests made by transactions. Such a mechanism is called a Lock Manager. It relies on the process of message passing where transactions and lock manager exchange messages to handle the locking and unlocking of data items.