Multiple Granularity Locking | Database Management System (DBMS) - Computer Science Engineering (CSE) PDF Download

Multiple Granularity Locking in DBMS

In the various Concurrency Control schemes have used different methods and every individual Data item as the unit on which synchronization is performed. A certain drawback of this technique is if a transaction Ti needs to access the entire database, and a locking protocol is used, then Ti must lock each item in the database. It is less efficient, it would be more simpler if Ti could use a single lock to lock the entire database. But, if it consider the second proposal, this should not in fact overlook the certain flaw in the proposed method. Suppose another transaction just needs to access a few data items from a database, so locking the entire database seems to be unnecessary moreover it may cost us loss of Concurrency, which was our primary goal in the first place. To bargain between Efficiency and Concurrency. Use Granularity.
Let’s start by understanding what is meant by Granularity.

Granularity: It is the size of data item allowed to lock. Now Multiple Granularity means hierarchically breaking up the database into blocks which can be locked and can be track what need to lock and in what fashion. Such a hierarchy can be represented graphically as a tree.
For example, consider the tree, which consists of four levels of nodes. The highest level represents the entire database. Below it are nodes of type area; the database consists of exactly these areas. Area has children nodes which are called files. Every area has those files that are its child nodes. No file can span more than one area.
Finally, each file has child nodes called records. As before, the file consists of exactly those records that are its child nodes, and no record can be present in more than one file. Hence, the levels starting from the top level are:

• database
• area
• file
• record

Multi Granularity tree Hierarchy

Consider the above diagram for the example given, each node in the tree can be locked individually. As in the 2-phase locking protocol, it shall use shared and exclusive lock modes. When a transaction locks a node, in either shared or exclusive mode, the transaction also implicitly locks all the descendants of that node in the same lock mode. For example, if transaction Ti gets an explicit lock on file Fc in exclusive mode, then it has an implicit lock in exclusive mode on all the records belonging to that file. It does not need to lock the individual records of Fc explicitly. this is the main difference between Tree Based Locking and Hierarchical locking for multiple granularity.
Now, with locks on files and records made simple, how does the system determine if the root node can be locked? One possibility is for it to search the entire tree but the solution nullifies the whole purpose of the multiple-granularity locking scheme. A more efficient way to gain this knowledge is to introduce a new lock mode, called Intention lock mode.

Intention Mode Lock
In addition to S and X lock modes, there are three additional lock modes with multiple granularity:

• Intention-Shared (IS): explicit locking at a lower level of the tree but only with shared locks.
• Intention-Exclusive (IX): explicit locking at a lower level with exclusive or shared locks.
• Shared & Intention-Exclusive (SIX): the sub-tree rooted by that node is locked explicitly in shared mode and explicit locking is being done at a lower level with exclusive mode locks.

The compatibility matrix for these lock modes are described below:

Multi Granularity tree Hierarchy

The multiple-granularity locking protocol uses the intention lock modes to ensure serializability. It requires that a transaction Ti that attempts to lock a node must follow these protocols:

1. Transaction T_i must follow the lock-compatibility matrix.
2. Transaction T_i must lock the root of the tree first, and it can lock it in any mode.
3. Transaction T_i can lock a node in S or IS mode only if T_i currently has the parent of the node locked in either IX or IS mode.
4. Transaction T_i can lock a node in X, SIX, or IX mode only if T_i currently has the parent of the node locked in either IX or SIX mode.
5. Transaction T_i can lock a node only if T_i has not previously unlocked any node (i.e., T_i is two phase).
6. Transaction T_i can unlock a node only if T_i currently has none of the children of the node locked.

Observe that the multiple-granularity protocol requires that locks be acquired in top-down (root-to-leaf) order, whereas locks must be released in bottom-up (leaf to-root) order.

As an illustration of the protocol, consider the tree given above and the transactions:

• Say transaction T₁ reads record R_a2 in file F_a. Then, T₂ needs to lock the database, area A₁, and F_a in IS mode (and in that order), and finally to lock R_a2 in S mode.
• Say transaction T₂ modifies record Ra9 in file F_a . Then, T₂ needs to lock the database, area A₁, and file F_a (and in that order) in IX mode, and at last to lock Ra9 in X mode.
• Say transaction T₃ reads all the records in file F_a. Then, T₃ needs to lock the database and area A₁ (and in that order) in IS mode, and at last to lock F_a in S mode.
• Say transaction T₄ reads the entire database. It can do so after locking the database in S mode.

Note that transactions T₁, T₃ and T₄ can access the database concurrently. Transaction T₂ can execute concurrently with T₁, but not with either T₃ or T₄.
This protocol enhances concurrency and reduces lock overhead. Deadlock are still possible in the multiple-granularity protocol, as it is in the two-phase locking protocol. These can be eliminated by using certain deadlock elimination techniques.