Composite Synchronization Constructs

• While the Pthreads API provides a basic set of synchronization constructs, often, there is a need for higher level constructs.
• These higher level constructs can be built using basic synchronization constructs.
• An important and often used construct in threaded (as well as other parallel) programs is a barrier.
• A barrier call is used to hold a thread until all other threads participating in the barrier have reached the barrier.
• Barriers can be implemented using a counter, a mutex and a condition variable.
• A single integer is used to keep track of the number of threads that have reached the barrier.
  • If the count is less than the total number of threads, the threads execute a condition wait.
  • The last thread entering (and setting the count to the number of threads) wakes up all the threads using a condition broadcast.

The code for accomplishing this is as follows:

• In the above implementation of a barrier, threads enter the barrier and stay until the broadcast signal releases them.
• The threads are released one by one since the mutex count_lock is passed among them one after the other.
• The trivial lower bound on execution time of this function is therefore $O(n)$ for $n$ threads.
• This implementation of a barrier can be speeded up using multiple barrier variables.