ACM Transactions on Parallel Computing · 2018 · 14 citations · 35 references
ComputingComputer EngineeringComputer ScienceData ManagementData StructuresParallel ComputingConcurrency ControlData SynchronizationTransaction ManagementTransaction Processing SystemsLock-free SynchronizationShared-memory Data StructuresSynchronizationThread-safe Data StructuresTransaction ProcessingTransactional Data StructuresTransactional MemoryTransactional Synchronization
Nonblocking data structures allow scalable and thread-safe access to shared data. They provide individual operations that appear to execute atomically. However, it is often desirable to execute multiple operations atomically in a transactional manner. Previous solutions, such as Software Transactional Memory (STM) and transactional boosting, manage transaction synchronization separately from the underlying data structure’s thread synchronization. Although this reduces programming effort, it leads to overhead associated with additional synchronization and the need to rollback aborted transactions. In this work, we present a new methodology for transforming high-performance lock-free linked data structures into high-performance lock-free transactional linked data structures without revamping the data structures’ original synchronization design. Our approach leverages the semantic knowledge of the data structure to eliminate the overhead of false conflicts and rollbacks. We encapsulate all operations, operands, and transaction status in a transaction descriptor, which is shared among the nodes accessed by the same transaction. We coordinate threads to help finish the remaining operations of delayed transactions based on their transaction descriptors. When a transaction fails, we recover the correct abstract state by reversely interpreting the logical status of a node. We also present an obstruction-free version of our algorithm that can be applied to dynamic execution scenarios and an example of our approach applied to a hash map. In our experimental evaluation using transactions with randomly generated operations, our lock-free transactional data structures outperform the transactional boosted ones by 70% on average. They also outperform the alternative STM-based approaches by a factor of 2 to 13 across all scenarios. More importantly, we achieve 4,700 to 915,000 times fewer spurious aborts than the alternatives.
35
Maurice Herlihy, J. Eliot B. Moss · 1993 · 2.2K citations
Software transactional memory for dynamic-sized data structures
Maurice Herlihy, Victor Luchangco, Mark Moir et al. · 2003 · 999 citations
Bratin Saha, Ali-Reza Adl-Tabatabai, Richard L. Hudson et al. · 2006 · 493 citations