Wait-free Dynamic Transactions for Linked Data Structures
Wait-free Dynamic Transactions for Linked Data Structures
复制标题
链接数据结构的无等待动态事务
DOI：
10.1145/3303084.3309491
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Dechev, Damian
中科院分区：
文献类型：
--
作者：
LaBorde, Pierre;Lebanoff, Lance;Peterson, Christina;Zhang, Deli;Dechev, Damian
transmitting数据结构支持线程以原子方式执行一系列操作。动态事务允许动态生成操作数，并允许线程在事务的操作之间执行代码，这与需要提前知道操作数的静态事务相反。一个名为无锁事务转换（LFTT）的框架允许数据结构运行高性能事务，但它只支持静态事务。我们扩展了LFTT，以增加对动态事务和无等待进度的支持，同时保持其速度。LFTT的线程帮助方案对动态事务提出了独特的挑战。我们通过将LFTT的输入从操作列表更改为函数来克服这一挑战，强制帮助线程始终在事务开始时启动，并允许线程通过使用返回值列表跳过已完成的操作。我们彻底评估了支持动态事务和无等待进度的性能影响，发现这些功能不会损害LFTT的性能。
Transactional data structures support threads executing a sequence of operations atomically. Dynamic transactions allow operands to be generated on the fly and allows threads to execute code in between the operations of a transaction, in contrast to static transactions which need to know the operands in advance. A framework called Lock-free Transactional Transformation (LFTT) allows data structures to run high-performance transactions, but it only supports static transactions. We extend LFTT to add support for dynamic transactions and wait-free progress while retaining its speed. The thread-helping scheme of LFTT presents a unique challenge to dynamic transactions. We overcome this challenge by changing the input of LFTT from a list of operations to a function, forcing helping threads to always start at the beginning of the transaction, and allowing threads to skip completed operations through the use of a list of return values. We thoroughly evaluate the performance impact of support for dynamic transactions and wait-free progress and find that these features do not hurt the performance of LFTT for our test cases.
登录
查看更多内容
事务预测：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：
--
发表时间：
2016
期刊：
IEEE International Conference on Distributed Computing Systems
影响因子：
--
作者：
Deli Zhang;D. Dechev
通讯作者：
D. Dechev
协作应用程序从可序列化事务到因果事务
DOI：
--
发表时间：
1997
期刊：
EUROMICRO 97. Proceedings of the 23rd EUROMICRO Conference: New Frontiers of Information Technology (Cat. No.97TB100167)
影响因子：
--
作者：
M. Raynal;G. Thia;M. Ahamad
通讯作者：
M. Ahamad
抽象数据类型的事务正确性工具
影响因子：
1.6
作者：
Peterson, Christina;Dechev, Damian
通讯作者：
Dechev, Damian