multithreading - 使用测试和设置原子操作 : will it work for more than 2 threads? 实现互斥锁

Question

我正在阅读有关 test-and-set 的维基百科文章原子操作。它说实现互斥的一种方法是使用基于测试和设置的锁。

然而，根据同一篇文章，test-and-set 操作具有有限的共识数，最多可以解决两个并发进程的无等待共识问题。

那么基于test-and-set操作的互斥量是否只对两个线程有​​效？如果是这样，“实际”互斥量是如何实现的？

Answer 1

One thing to note is that mutual exclusion is essentially the equivalent of consensus for 2 threads. In other words, it is not necessary to have n-thread consensus to implement mutual exclusion. -- @Eric's comment

强烈推荐阅读The Art of Multiprocessor Programming ，来自 Maurice Herlihy 和 Nir ​​Shavit。实际上，test-and-set Wikipedia page引用 an article Herlihy 指出，“test-and-set 具有有限的共识数，最多可以解决两个并发进程的无等待共识问题”。

本书的第 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);
  }
}

So does a mutex based on the test-and-set operation work only for two threads?

简单的回答是:不，它们为两个以上的线程工作。

If so, how are "actual" mutexes implemented?

同一个维基百科页面引用 CAS ( compare-and-swap ) 作为 TAS 的更强大替代品，但该书对此事进行了广泛的讨论。此外，这已经在 SO 中被问到，所以我建议通读 How are mutexes implemented? 的答案。