Component-Based Lock Allocation

The choice of lock objects in concurrent programs can affect both performance and correctness, a burden of complexity for programmers. Recently, various automated lock allocation and assignment techniques have been proposed, each aiming primarily to minimize the number of conflicts between critical sections. However, practical performance depends on a number of important factors, including the nature of concurrent interaction, the accuracy of the program analyses used to support the lock allocation, and the underlying machine hardware. We introduce component-based lock allocation, which starts by analysing data dependences and automatically assigns lock objects with tunable granularity to groups of interfering critical sections. Our experimental results show that while a single global lock is usually suboptimal, high accuracy in program analysis is not always necessary to achieve generally good performance. Our work provides empirical evidence as to sufficient strategies for efficient lock allocation, and details the requirements of an adaptable implementation.