Automatic Fine-Grain Locking Using Shape Properties
The authors present a technique for automatically adding fine-grain locking to an abstract data type that is implemented using a dynamic forest - i.e., the data structures may be mutated, even to the point of violating forestness temporarily during the execution of a method of the ADT. Their automatic technique is based on Domination Locking, a novel locking protocol. Domination locking is designed specifically for software concurrency control, and in particular is designed for object-oriented software with destructive pointer updates. Domination locking is a strict generalization of existing locking protocols for dynamically changing graphs.