Locks Must Die: Composable Mutual Exclusion Implemented by Dynamic Resource Sharing on Task Graphs

Locks, the enduring de-facto standard for synchronization in parallel programs, suffer from non-composability and are conducive to a variety of hard-to-find bugs such as data races and deadlocks. In this paper, we propose a straightforward replacement of the traditional lock-based mutex with the Guard, a construct providing mutual exclusion through efficient, dynamic serialization of tasks in a dynamic task graph. Unlike with locks, programming with Guards is lock-free, composable, and immune to deadlock. Guards are compatible with arbitrary executor services, and can be implemented on any platform which supports atomic variables and compare-and-set operations. We will describe the general construction and API for Guards, introduce our reference implementation, and analyze through various benchmarks the performance of our reference implementation against the standard ReentrantLock class used in Java. The practice of writing multithreaded code will benefit from the safety, ease of use, and performance of Guards.