3

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

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

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

4

2 回答 2

5

需要注意的一点是，互斥本质上相当于 2 个线程的共识。换句话说，实现互斥并不一定要有n线程共识。-- @Eric的评论

我强烈推荐阅读Maurice Herlihy 和 Nir ​​Shavit的 The Art of Multiprocessor Programming。实际上，test-and-set 维基百科页面引用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);
  }
}

那么基于 test-and-set 操作的互斥锁是否只对两个线程有​​效？

简单的答案是：不，它们适用于两个以上的线程。

如果是这样，“实际”互斥锁是如何实现的？

同一个 Wikipedia 页面引用 CAS（比较和交换）作为 TAS 的更强大的替代方案，但该书对此事进行了广泛的讨论。此外，这已经在 SO 中被问过，所以我建议阅读如何实现互斥锁的答案？

于 2019-06-23T16:49:55.913 回答
1

“正确”的解决方案是拥有一个具有以下属性的“不间断模式”标志：

  1. 原子读写（你可以使用 test-and-set 操作符）；
  2. 设置后，您的应用程序在任何情况下都不能中断（线程重新调度等）。

您在互斥锁下有一个持有线程和 n 个等待线程，它们被放置在队列中（任何类型的列表，但我更喜欢队列。）在互斥锁上，您通过原子测试/设置标志（自旋）进入不间断模式或在设置标志时休眠）并获取互斥锁或进入队列以执行此操作（在后一种情况下，当前线程无法重新进入调度程序的就绪队列。）解锁时，您进入不间断模式并放弃互斥锁到队列中的下一个线程，如果有的话。

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

希望这是有道理的！

于 2019-06-25T23:15:04.680 回答