Lock-free locks revisited
Lock-free locks revisited
复制标题
重温无锁锁
DOI：
10.1145/3503221.3508433
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Wei, Yuanhao
中科院分区：
文献类型：
--
作者：
Ben-David, Naama;Blelloch, Guy E.;Wei, Yuanhao
本文提出了一种基于帮助的无锁锁的新方法，它允许用户使用细粒度的锁编写代码，但以无锁的方式运行代码。虽然无锁锁在过去已经被提出，但它们被广泛认为是不切实际的，有一些关键的限制，并且据我们所知，从未实现过。本文介绍了使无锁锁实用化和通用化的一些关键技术。最重要的技术是一种相同的方法-也就是说，使运行多次的代码看起来就像运行一次一样。这个想法是基于在运行相同受保护代码的进程之间使用共享日志。重要的是，这种方法可以是基于库的，只需要对标准代码做很少的修改--代码只需要使用内存操作的幂等版本（加载，存储，LL/SC，分配，释放）。Flock允许基于锁的数据结构以无锁或阻塞（传统锁）模式运行。我们使用Flock实现了各种基于树和列表的数据结构，并在各种工作负载下比较了无锁模式和阻塞模式的性能。在几乎所有工作负载下，无锁模式几乎与阻塞模式一样快，并且在线程超额订阅（线程比处理器多）时速度明显更快。我们还比较了几个现有的基于锁和无锁的替代品。
This paper presents a new and practical approach to lock-free locks based on helping, which allows the user to write code using fine-grained locks, but run it in a lock-free manner. Although lock-free locks have been suggested in the past, they are widely viewed as impractical, have some key limitations, and, as far as we know, have never been implemented. The paper presents some key techniques that make lock-free locks practical and more general. The most important technique is an approach to idempotence---i.e. making code that runs multiple times appear as if it ran once. The idea is based on using a shared log among processes running the same protected code. Importantly, the approach can be library based, requiring very little if any change to standard code---code just needs to use the idempotent versions of memory operations (load, store, LL/SC, allocation, free).We have implemented a C++ library called Flock based on the ideas. Flock allows lock-based data structures to run in either lock-free or blocking (traditional locks) mode. We implemented a variety of tree and list-based data structures with Flock and compare the performance of the lock-free and blocking modes under a variety of workloads. The lock-free mode is almost as fast as blocking mode under almost all workloads, and significantly faster when threads are over-subscribed (more threads than processors). We also compare with several existing lock-based and lock-free alternatives.
登录
查看更多内容
DOI：
10.1145/3460874
发表时间：
2018-07
期刊：
ACM Transactions on Parallel Computing (TOPC)
影响因子：
--
作者：
Kjell Winblad;Konstantinos Sagonas;B. Jonsson
通讯作者：
Kjell Winblad;Konstantinos Sagonas;B. Jonsson
高效的多字比较和交换
DOI：
10.4230/lipics.disc.2020.4
发表时间：
2020
期刊：
Proceedings of the 19th ACM SIGPLAN symposium on Principles and practice of parallel programming
影响因子：
--
作者：
R. Guerraoui;Alex Kogan;Virendra J. Marathe;I. Zablotchi
通讯作者：
I. Zablotchi
DOI：
10.1147/sj.472.0221
发表时间：
2008-04
期刊：
IBM Syst. J.
影响因子：
--
作者：
Dinakar Guniguntala;P. McKenney;J. Triplett;J. Walpole
通讯作者：
Dinakar Guniguntala;P. McKenney;J. Triplett;J. Walpole
影响因子：
0.6
作者：
R. Bayer;M. Schkolnick
通讯作者：
R. Bayer;M. Schkolnick
DOI：
10.1007/3-540-36108-1_18
发表时间：
2002-10
期刊：
--
影响因子：
--
作者：
T. Harris;K. Fraser;I. Pratt
通讯作者：
T. Harris;K. Fraser;I. Pratt