使用测试和设置原子操作实现互斥锁：它适用于 2 个以上的线程吗？

Question

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

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

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

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

我强烈建议阅读 Herlihy 的 The Art of Multiprocessor Programming, from Maurice Herlihy and Nir Shavit. Actually, the test-and-set Wikipedia page cite an article 以说明 "test-and-set has a finite consensus number and can solve the wait-free consensus problem for at-most two concurrent processes"。

本书的第 5 章讨论了使用原始同步操作的共识，但我相信第 7 章会引起您的兴趣：他们讨论了如何使用 TAS (test-and-set) 指令在 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?

的答案

Answer 2

"correct" 解决方案是使用具有以下属性的 "uninterruptible mode" 标志：

原子读写（你有 test-and-set 运算符）；
设置后，您的应用程序在任何情况下（线程重新安排等）都不能中断。

你有一个在互斥锁下的保持线程和 n 个等待线程，它们被放置在一个队列中（任何一种列表，但我更喜欢队列。）在互斥锁上，你通过原子方式进入不间断模式 test/setting 你的标志（在设置标志时自旋或睡眠，）并获取互斥锁或进入队列来这样做（在后一种情况下，当前线程无法重新进入调度程序的就绪队列。）解锁时，你去进入不间断模式并将互斥锁交给队列中的下一个线程（如果有）。

我认为 libpthread 等以这种方式实现互斥体。这本身并不难，但解决方案要么绝对正确，要么不正确。

希望这是有道理的！

使用测试和设置原子操作实现互斥锁：它适用于 2 个以上的线程吗？

Implementing a mutex with test-and-set atomic operation: will it work for more than 2 threads?

language-agnostic

concurrency

multithreading

atomic

test-and-set