Skip to Main content Skip to Navigation
Conference papers

Grasping the Gap between Blocking and Non-Blocking Transactional Memories

Abstract : Transactional memory (TM) is an inherently optimistic synchronization abstraction: it allows concurrent processes to execute sequences of shared-data accesses (transactions) speculatively, with an op- tion of aborting them in the future. Early TM designs avoided using locks and relied on non-blocking synchronization to ensure obstruction- freedom: a transaction that encounters no step contention is not allowed to abort. However, it was later observed that obstruction-free TMs per- form poorly and, as a result, state-of-the-art TM implementations are nowadays blocking, allowing aborts because of data conflicts rather than step contention. In this paper, we explain this shift in the TM practice theoretically, via complexity bounds. We prove a few important lower bounds on obstruction-free TMs. Then we present a lock-based TM implementation that beats all of these lower bounds. In sum, our results exhibit a considerable complexity gap between non-blocking and blocking TM implementations.
Complete list of metadata

Cited literature [25 references]  Display  Hide  Download

https://hal.archives-ouvertes.fr/hal-01206451
Contributor : Matthieu Roy Connect in order to contact the contributor
Submitted on : Tuesday, September 29, 2015 - 10:08:41 AM
Last modification on : Friday, April 9, 2021 - 4:28:05 PM
Long-term archiving on: : Wednesday, December 30, 2015 - 10:22:59 AM

File

22.pdf
Files produced by the author(s)

Identifiers

Citation

Petr Kuznetsov, Srivatsan Ravi. Grasping the Gap between Blocking and Non-Blocking Transactional Memories . DISC 2015, Toshimitsu Masuzawa; Koichi Wada, Oct 2015, Tokyo, Japan. ⟨10.1007/978-3-662-48653-5_16⟩. ⟨hal-01206451⟩

Share

Metrics

Record views

56

Files downloads

168