CODEWITHSUNDEEP
multithreadingconcurrencysynchronizationsemaphorebarrier
Siqi Liu
Siqi Liu

Reputation: 165

Why rendezvous with semaphore solution doesn't generalize (and we use barrier instead)?

For rendezvous problems we need to synchronize two threads, and here is a classic solution: 

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

Thread A:

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

Thread B:

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

This works well for two threads, but how about N threads? For N=3, we can implement something like this:

Thread A (other threads are symmetric):

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

All the sources that I've found just state that : "Consider again the Rendezvous problem from Section 3.2. A limitation of the solution we presented is that it does not work with more than two threads.", or "Solution presented previously doesn't work for more than two threads.".

(By the way, the generalized solution presented here is probably not optimal since it would use N semaphores for N threads... I'm just curious if anyone has a scenario that this solution doesn't work for N>2 threads?)

Upvotes: 4

Views: 1909

Answers (2)

OfNothing
OfNothing

Reputation: 600

The reason it does not generalize is because it does not work with 3 or more threads. Imagine there were 3 threads. One would need at least 6 semaphores. Each thread would have to wait on 2 semaphores - one from each other thread. Keeping track of which semaphore needs to get signaled would be a nightmare. How would you even do 100 threads?

One way to generalize a solution to this as an exercise, or if you really don't like CountDownLatch, would be for each thread to increment an AtomicInteger or an integer protected by a mutex. If the value of integer reaches N, release(N) permits on the semaphore, then wait on the semaphore. Each thread will wait until the last thread updates the count to N and N permits are released.

Upvotes: 0

John Vint
John Vint

Reputation: 40266

It would be very simple if you use a CyclicBarrier in Java as it does this sort of thing for you. But for the general case, how would you do this and write it yourself? You can do something similar to what a CountdownLatch or CyclicBarrier does.

Maintain a count of the number of parties expected, decrement it as they approach your barrier and then notify all once the decremented count is 0. For example: (this is incredibly simplified).

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

Then

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.

The same can be done in Java using 

CyclicBarrier#await();

or

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

Upvotes: 0

Related Questions