Fast and Fair Randomized Wait-Free Locks
Fast and Fair Randomized Wait-Free Locks
复制标题
快速公平的随机无等待锁
DOI：
10.1145/3519270.3538448
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Blelloch, Guy E.
中科院分区：
文献类型：
--
作者：
Ben-David, Naama;Blelloch, Guy E.
我们提出了一种随机化的无等待锁方法，该方法在任何进程都可以任意延迟的上下文中具有强的时间和公平性界限。我们的方法支持提供一组锁的tryLock操作，以及在获得所有锁时运行的代码。如果锁上存在争用，则tryLock操作或尝试可能会失败，在这种情况下，代码不会运行。给定算法在任何锁的点争用上已知的上限k，以及在一个try- lock集合中的锁数已知的上限L，一个tryLock将成功获取它的锁并以至少1/(kL)的概率运行代码。这是公平的。此外，如果任何锁中代码的最大步复杂度为T，则无论成功还是失败，该尝试将需要O（k2L2T）步。这些尝试是独立的，因此，如果在失败时反复重试tryLock，它将在0 （k3L3T）个预期步骤内成功，并且很可能不会更多。
We present a randomized approach for wait-free locks with strong bounds on time and fairness in a context in which any process can be arbitrarily delayed. Our approach supports a tryLock operation that is given a set of locks, and code to run when all the locks are acquired. A tryLock operation, or attempt, may fail if there is contention on the locks, in which case the code is not run. Given an upper bound k known to the algorithm on the point contention of any lock, and an upper bound L on the number of locks in a try- Lock's set, a tryLock will succeed in acquiring its locks and running the code with probability at least 1/(kL). It is thus fair. Furthermore, if the maximum step complexity for the code in any lock is T , the attempt will take O(k2L2T ) steps, regardless of whether it succeeds or fails. The attempts are independent, thus if the tryLock is repeatedly retried on failure, it will succeed in O(k3L3T ) expected steps, and with high probability in not much more.
登录
查看更多内容
DOI：
10.1145/3503221.3508433
发表时间：
2022
期刊：
Proceedings of the 27th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming
影响因子：
--
作者：
Ben-David, Naama;Blelloch, Guy E.;Wei, Yuanhao
通讯作者：
Wei, Yuanhao
使用异步硬件的无等待共识
DOI：
--
发表时间：
1994
期刊：
SIAM journal on computing (Print)
影响因子：
--
作者：
B. Chor;A. Israeli;Ming Li
通讯作者：
Ming Li
具有恒定时间开销的并发延迟引用计数
DOI：
10.1145/3453483.3454060
发表时间：
2021
期刊：
ACM/SIGPLAN Internaltional Conference on Programming Language Design and Implementation (PLDI
影响因子：
--
作者：
Anderson, Daniel;Blelloch, Guy E.;Wei, Yuanhao
通讯作者：
Wei, Yuanhao
影响因子：
0.6
作者：
R. Bayer;M. Schkolnick
通讯作者：
R. Bayer;M. Schkolnick
DOI：
10.1145/135419.135468
发表时间：
1992
期刊：
J. ACM
影响因子：
--
作者：
E. Kushilevitz;M. Rabin
通讯作者：
M. Rabin