为什么使用信号量解决方案无法推广（我们改用屏障）？

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节中的会面问题。我们提出的解决方案的局限性在于它无法处理超过两个线程。” 或者“之前提出的解决方案对于多于两个线程是无效的。”。

（顺便说一句，本文介绍的通用解决方案可能并不是最佳的，因为对于N个线程，它需要使用N个信号量……我只是好奇是否有人有一个关于N>2线程的情景使该解决方案无法工作？）

- Siqi Liu

---

什么语言？还是你是在一般意义上询问？我之所以这样问是因为在Java中有一种简单的方法可以做到这一点。 - John Vint

嗨，语言不是很重要。可能有更简单的方法来做这件事，但我只是想了解为什么泛化不起作用... 有什么想法吗？ :) - Siqi Liu

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();

- John Vint

---

嗨John，谢谢你的回答！但我的问题真正在于尝试理解为什么像“信号量小书”这样的书中，作者说会面的解决方案不适用于超过2个线程。你有任何想法为什么我提出的问题的解决方案不能推广吗？ - Siqi Liu