In the design of a locking-based concurrency control mechanism for a hierarchical structure, the granularity of locking must be determined. One simple, popular approach is to support coarse-grained concurrency control which allows only one user to execute commands.
In comparison to schemes that choose finer locking granularity, it is space efficient in that it stores only one lock per application, and time efficient in that it requires only one lock to be checked on each access. However, it limits the concurrency in the application when different components of an object can be manipulated independently.
It is sometimes useful to support a compromise between fine-grain and coarse-grain locking by offering variable-grained locking.
A simple method for supporting variable-grain locking is to allow transactions to lock both leaf and non-leaf nodes. A lock on a non-leaf node applies to all the leaf-level items in the subtree rooted by the node. We can define two types or modes of locks: shared locks and exclusive locks, which do not allow other transactions from writing and accessing, respectively, the locked data structure.
(In the discussion above, we assume that users operate only on leaf items. However, the solutions given above work for cases when the users can operate on non-leaf items.)
The variable-grained locking approach, as described above, has two related problems. First, it is inefficient in that when a transaction tries to lock a node, the system must check the lock status of all nodes in the subtree rooted by the node and the path from the node to the root. Second, it does not allow transactions to use exceptions in lock specifications such as lock all nodes in this tree with shared locks except this one in the exclusive mode. Transactions are forced to either take a conservative approach and lock the entire tree using a stronger lock than necessary or use a large number of locks.
Gray et al describe a scheme that addresses these problems. In addition to the basic or explicit locks, shared and exclusive, it associates non-leaf nodes with intention locks. An intention lock on a node served two purposes: First, it summarizes the locked status of its descendents, thereby reducing the need to check their individual locked status when the node is to be locked. Second, it allows exception-based specification. While a regular lock indicates that all descendent nodes are locked, an intention lock indicates that there exists a descendent node is locked. Thus these two kinds of locks essentially assert the universal and existential operators respectively.
Now a transaction is required to put intention locks on all ancestors of a node before it puts a basic or explicit (shared or exclusive) lock on the node. Three kinds of intention locks are defined:
Intention Shared (IS) - it is put on a node if some descendent of the node is to be locked in the shared mode.
Intention Exclusive (IX) - it is put on a node if some descendent of the node is to be locked in the exclusive mode.
Shared Intention Exclusive (SIX) - it is put one a node if all children of a node are to be locked in the shared mode except for some children that are to be explicitly locked in the exclusive mode.
Thus, before putting a shared (exclusive) lock on a node, a transaction must put an IS or SIX (IX or SIX) lock on all parents of the node. Conversely, it must release the locks in a leaf to root order. When releasing alock on a node it must ensure that the node lock status is restored, that is, the status reverts to the one it was before the transaction locked it. This can be done by keeping reference counts, checkpointing, or by keeping not one value but a list of values for a lock of a particular type.
The following compatibility matrix determines if a transaction can lock a node that is already locked by another transaction:
