提问人：Ignorant 提问时间：6/23/2019 更新时间：6/26/2019 访问量：3178
使用测试和设置原子操作实现互斥锁：它是否适用于超过 2 个线程？
Implementing a mutex with test-and-set atomic operation: will it work for more than 2 threads?
问：
我正在阅读维基百科上关于测试和设置原子操作的文章。它说实现互斥的一种方法是使用基于测试和设置的锁。
然而，根据同一篇文章，测试和设置操作具有有限的共识数，最多可以解决两个并发进程的无等待共识问题。
那么，基于测试和设置操作的互斥锁是否只适用于两个线程？如果是这样，“实际”互斥锁是如何实现的？
答：
5赞
Dinei
6/24/2019
#1
需要注意的一点是，互斥本质上等同于 2 个线程的共识。换言之，实现互斥不需要有n线程共识。-- @Eric的评论
我强烈建议您阅读 Maurice Herlihy 和 Nir Shavit 合著的《The Art of Multiprocessor Programming》。实际上，测试和设置维基百科页面引用了 Herlihy 的一篇文章，指出“测试和设置有一个有限的共识数，可以解决最多两个并发进程的无等待共识问题”。
本书的第 5 章讨论了使用原始同步操作的共识，但我相信第 7 章会引起您的兴趣：它们讨论了如何使用 TAS（测试和设置）指令在 Java 中实现锁。 第145页剧透：
public class TASLock implements Lock {
AtomicBoolean state = new AtomicBoolean(false);
public void lock() {
while (state.getAndSet(true)) {}
}
public void unlock() {
state.set(false);
}
}
那么，基于测试和设置操作的互斥锁是否只适用于两个线程？
简单的答案是：不，它们适用于两个以上的线程。
如果是这样，“实际”互斥锁是如何实现的？
同一维基百科页面引用CAS（比较和交换）作为TAS的更强大的替代品，但该书对此事进行了广泛的讨论。 此外，这在 SO 中已经问过了，所以我建议通读互斥锁是如何实现的答案？
评论
1赞
Eric
6/24/2019
我想你的意思是写“它可以为两个以上的线程提供共识，但不是以无等待的方式。使用 TAS 绝对可以以无等待的方式解决 2 个以上的线程的互斥问题，因为解决互斥问题相当于解决 2 个线程的共识（我是否进入临界部分？
0赞
Dinei
6/26/2019
你说得对@Eric。我犯了一个错误，试图把事情简单化。为了简单起见，我删除了这部分答案，并在问题中复制了您的评论。关于这个主题的更详细的解释可以在答案中提到的 Herlihy 的文章中找到。
1赞
Hari Amoor
6/26/2019
#2
“正确”的解决方案是具有以下属性的“不间断模式”标志：
- 原子读取和写入（您可以使用 test-and-set 运算符）;
- 在设置此项时，应用程序在任何条件下（线程重新调度等）都不能中断。
您在互斥锁下有一个持有线程和 n 个等待线程，它们被放置在队列中（任何类型的列表，但我更喜欢队列。在互斥锁上，您可以通过原子测试/设置标志（在设置标志时旋转或休眠）进入不间断模式，然后获取互斥锁或进入队列以执行此操作（在后一种情况下，当前线程无法重新进入调度程序的就绪队列。解锁时，您将进入不间断模式，并将互斥锁交给队列中的下一个线程（如果有）。
我认为 libpthread 等以这种方式实现互斥锁。这本身并不是一件难事，但解决方案要么是绝对正确的，要么是不正确的。
希望这是有道理的！
评论
test-and-set当然可以用于实现 2 个以上线程的互斥。看起来他们的观点是，线程数越高，就不能再“无等待”（即在有限的步骤数内）完成