Adaptive Locks: Combining Transactions and Locks for Efficient Concurrency

Takayuki Usui, Yannis Smaragdakis and Reimer Behrends

Transactional memory is being advanced as an alternativeto traditional lock-based synchronization for concurrent programming.Transactional memory simplifies the programmingmodel and maximizes concurrency. At the same time,transactions can suffer from interference that causes them tooften abort, from heavy overheads for memory accesses, andfrom expressiveness limitations (e.g., for I/O operations). Inthis paper we propose an adaptive locking technique that dynamicallyobserves whether a critical section would be bestexecuted transactionally or while holding a mutex lock. Thecritical new elements of our approach include the adaptivitylogic and cost-benefit analysis, a low-overhead implementationof statistics collection and adaptive locking in a full Ccompiler, and an exposition of the effects on the programmingmodel. In experiments with both micro- and macrobenchmarkswe found adaptive locks to consistently matchor outperform the better of the two component mechanisms(mutexes or transactions). Compared to either mechanismalone, adaptive locks often provide 3-to-10x speedups. Additionally,adaptive locks simplify the programming modelby reducing the need for fine-grained locking: with adaptivelocks, the programmer can specify coarse-grained lockingannotations and often achieve fine-grained locking performancedue to the transactional memory mechanisms.

Back to Program