Lock-Free Transactional Transformation for Linked Data Structures
Lock-Free Transactional Transformation for Linked Data Structures
复制标题
链接数据结构的无锁事务转换
DOI：
10.1145/3209690
复制
发表时间：
2018
影响因子：
1.6
通讯作者：
Dechev, Damian
中科院分区：
文献类型：
--
作者：
Zhang, Deli;Laborde, Pierre;Lebanoff, Lance;Dechev, Damian
非阻塞数据结构允许对共享数据进行可扩展且线程安全的访问。它们提供看似原子执行的单独操作。然而，通常希望以事务方式原子地执行多个操作。以前的解决方案，例如软件事务内存（STM）和事务提升，将事务同步与底层数据结构的线程同步分开管理。虽然这减少了编程工作量，但它会导致与额外同步相关的开销以及回滚中止事务的需要。在这项工作中，我们提出了一种新的方法，用于将高性能无锁链接数据结构转换为高性能无锁事务性链接数据结构，而无需修改数据结构的原始同步设计。我们的方法利用数据结构的语义知识来消除错误冲突和回滚的开销。我们将所有操作、操作数和事务状态封装在一个事务描述符中，该描述符在同一事务访问的节点之间共享。我们协调线程以根据事务描述符帮助完成延迟事务的剩余操作。当事务失败时，我们通过反向解释节点的逻辑状态来恢复正确的抽象状态。我们还提出了可应用于动态执行场景的算法的无阻塞版本，以及应用于哈希映射的方法的示例。在我们使用具有随机生成操作的事务的实验评估中，我们的无锁事务数据结构平均比事务提升数据结构高出 70%。在所有场景中，它们的性能均优于基于 STM 的替代方法 2 至 13 倍。更重要的是，与其他替代方案相比，我们实现的虚假中止次数减少了 4,700 至 915,000 倍。
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.
登录
查看更多内容
DOI：
--
发表时间：
2012-06
期刊：
--
影响因子：
--
作者：
M. Herlihy;N. Shavit
通讯作者：
M. Herlihy;N. Shavit
事务预测：STM 的高性能并发集和映射
DOI：
--
发表时间：
2010
期刊：
ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing
影响因子：
--
作者：
N. Bronson;J. Casper;Hassan Chafi;K. Olukotun
通讯作者：
K. Olukotun
编写宽松的交易
DOI：
--
发表时间：
2013
期刊：
2013 IEEE 27th International Symposium on Parallel and Distributed Processing
影响因子：
--
作者：
Vincent Gramoli;R. Guerraoui;Mihai Letia
通讯作者：
Mihai Letia
DOI：
--
发表时间：
2012
期刊：
European Conference on Object-Oriented Programming
影响因子：
--
作者：
Khilan Gudka;T. Harris;S. Eisenbach
通讯作者：
S. Eisenbach
一种基于多维链表的无锁优先级队列设计
影响因子：
5.3
作者：
Deli Zhang;D. Dechev
通讯作者：
D. Dechev