为什么使用信号量解决方案会合不能泛化（我们使用屏障代替）？

Question

对于集合点问题，我们需要同步两个线程，这是一个经典的解决方案：

aArrived = S(0);
bArrived = S(0);

线程A：

while(true) {
  doSomething();
  aArrived.signal();
  bArrived.wait();
}

线程B：

while(true) {
  doSomething();
  bArrived.signal();
  aArrived.wait();
}

这对于两个线程来说效果很好，但是对于 N 个线程呢？对于 N=3，我们可以实现如下所示：

螺纹A（其他螺纹对称）：

while(true) {
  doSomething();
  aArrived.signal();
  aArrived.signal();
  bArrived.wait();
  cArrived.wait();
}

我找到的所有消息来源都指出： “再次考虑第 3.2 节中的 Rendezvous 问题。我们提出的解决方案的一个限制是它不适用于两个以上的线程。”，或 “解决方案前面介绍的方法不适用于两个以上的线程。”.

（顺便说一句，这里提出的通用解决方案可能不是最佳的，因为它会为 N 个线程使用 N 个信号量......我只是好奇是否有人遇到这个解决方案不适用于 N>2 线程的情况？ )

Answer 1

如果你在 Java 中使用

CyclicBarrier

，那就非常简单了，因为它会为你做这样的事情。 但对于一般情况，你会如何做并自己编写呢？ 您可以执行类似于

CountdownLatch

或

CyclicBarrier

的操作。

维护预期参与方的数量，当他们接近你的障碍时减少它，然后在减少的计数为 0 时通知所有人。例如：（这非常简单）。

class CountdownBarrier {
   private int numberOfParties;
   private final Object lock = new Object();
   public CountdownBarrier(int numberOfParties){ this.numberOfParties = ..}

   public void arriveAndAwait(){  
      synchronized(lock){  
         if(--numberOfParties == 0)
            lock.notifyAll();  
         while(numberOfParties != 0)
            lock.wait();       
      }
   }
} 

然后

CountdownBarrier barrier = new CountdownBarrier(3);

Thread A:
   barrier.arriveAndAwait();
Thread B: 
   barrier.arriveAndAwait();
Thread C:
   barrier.arriveAndAwait(); // assuming time progresses downward, this arriveAndAwait will notify all threads to wake up and continue.

---

在 Java 中也可以使用

完成同样的操作

CyclicBarrier#await();

或

CountdownLatch#countDown(); // then
CountdownLatch#await();

Answer 2

它不能泛化的原因是它不能很好地处理 3 个或更多线程。假设有 3 个线程。一个信号量至少需要 6 个。每个线程都必须等待 2 个信号量——一个来自其他线程。跟踪哪个信号量需要发出信号将是一场噩梦。

将解决方案概括为练习的一种方法，或者如果您真的不喜欢 CountDownLatch，则可以为每个线程增加一个 AtomicInteger 或由互斥锁保护的整数。如果整数的值达到N，release(N)允许信号量，然后等待信号量。每个线程都会等待，直到最后一个线程更新计数一直到 N 并为所有线程释放足够的许可。

这是作业问题吗？其他人基本上问了同样的问题，所以我不会给出任何代码。