Concurrent Programming - Barrier

From SwinBrain

A barrier is a utility that is used to provide a "meeting" point for a number of threads. When a Barrier is created, it is assigned a number of threads that will meet there. When a thread arrives it will wait until this number of threads have arrived, and then all threads will leave together, resetting the Barrier for the next group of threads.

As Barriers are used as a meeting point for a number of threads, there are issues if one of these threads is interrupted. The standard way of handling this is to break the barrier. Once the barrier is broken, the waiting threads are released with an exception (typically something like a Barrier Broken Exception). Additional threads that arrive will immediately throw this exception.

The Barrier's implementation has the following methods.

  • Arrive: Used to indicate that the thread has arrived a the barrier.
  • Reset: Used to reset the barrier after it has broken.

Illustration

When the Barrier is created it is designed as a "meeting point" for a set number of threads. The count is typically set in the constructor. The following image illustrates a Barrier designed for two threads to meet at.

A barrier for two threads too meet at.


When the first thread arrives at the barrier it will determine that there is not sufficient threads to continue. At this point the thread will wait for other threads to arrive. In this case the thread is waiting for one other thread to arrive (image 1). When the n'th thread arrives it gains access to the Barrier and can release the waiting threads (image 2). The two threads clear the Barrier making it available for the next group, and then return (image 3).

The 1st thread arrives and must wait for the others.
The n'th thread arrives and can release the waiting threads.
The two threads clear the Barrier, and return.


Timed Versions

The Arrive method may never return if insufficient threads make it to the Barrier. In some cases this may not be acceptable. To improve the usability of the Barrier, a TryArrive method can be added.

  • TryArrive: Provides a timed version of the Arrive method. This returns false if the arrive times out.

The TryArrive arrives at the Barrier, and must be released within a set time (image 1). Success works just the same as the Arrive, with the thread returning true (image 2). When the Try Arrive fails, the Barrier is broken and the method returns false (image 3). If other threads are waiting on the Barrier when the time-out occurs, they will return with a Barrier Broken Exception.

Thread performs a try arrive.
On success the try arrive returns true.
On failure the barrier is broken, and TryArrive returns false.
If other threads are waiting when the time-out occurs, they throw Barrier Broken Exceptions.
Once broken, arriving threads (and try arrive) will all return immediately with a Barrier Broken exception.


Pseudocode

The basic process for a barrier is:

lock
{
  while released
  {
    wait
  }
 
  increment arrived thread count
 
  if arrived thread count = number waiting for
  {
    released = true
    wake all waiting threads
  }
  else
  {
    while not released
      wait
  }
 
  decrement arrived thread count
 
  if arrived thread count = 0  #last exiting thread
  {
    released = false
    wake all waiting threads
  }
}