The idea: nobody moves on until all arrive
Many parallel programs work in phases: each thread computes its part of step 1, and step 2 needs the results of all of step 1. A simulation updates its grid one time step at a time; a parallel sort merges only after every chunk is sorted. A barrier is the meeting point between two phases. A thread that reaches it waits until all N threads have reached it; the last one to arrive releases everybody.
How to use the animation
Each thread runs its listing in a loop. A coloured marker shows the line it runs next, and every step runs one line atomically. Pick a thread and press Step Thread, let the round-robin or random scheduler choose, or run a demo. A sleeping thread moves into the queue of what it waits on. The phase grid fills a cell when a worker finishes a phase; the red lines between the columns are the barrier. The check under the grid turns red if a thread ever runs ahead.
Building a barrier from a mutex and a condition variable
A barrier needs a counter, a lock that protects it, and a place to sleep:
mutex m; int count = 0, gen = 0; condition allHere;
barrier_wait():
lock(m)
my = gen; count++ // I have arrived
if (count == N) // the last one
count = 0; gen++ // ready for the next phase
broadcast(allHere) // wake every waiter
else
while (gen == my) // until this generation is over
wait(allHere, m)
unlock(m)
The last thread must use broadcast, not signal: all N − 1 waiters have to wake up. As with any condition variable, a woken thread first has to take m back, so the threads leave one at a time (Demo: three workers meet at the barrier). The waiters test a condition in a while loop, which also covers spurious wake-ups. The same barrier is used again for phase 2, 3 and so on (Demo: the barrier is reused, phase after phase), and no schedule can make a thread run ahead (Demo: random schedule, nobody runs ahead).
Why a reusable barrier needs a generation
The obvious version waits on while (count < N). It works once. To be reusable, the last thread must reset count to 0 for the next phase, and that is exactly what breaks it: the woken threads re-test count < N, see 0 and go back to sleep. The last thread goes on to the next phase, arrives, and sleeps too. Every thread is asleep and nobody is left to broadcast: a deadlock (Bug: barrier without generation, Demo: no generation, the reset strands the waiters).
The fix is to wait for an event that cannot be undone. Each thread remembers my = gen when it arrives and sleeps while gen == my. The last thread's gen++ stays changed whatever happens to count afterwards. This generation (or sense-reversal flag, in the spin-based version) is how pthread_barrier_wait, Java's CyclicBarrier and C++20's std::barrier are written.
Countdown latch: one-way and one-shot
A countdown latch (Java CountDownLatch, C++20 std::latch, Go's sync.WaitGroup is close) splits the two roles. It starts at N. Workers call countDown() and go straight on: they never wait. Another thread calls await() and sleeps until the count reaches 0 (Countdown latch, Demo: main waits on a countdown latch). It is the right tool for "wait until these N tasks are done" or "start all threads at once".
A latch never resets. Once it is 0 it stays open, further countDown()s do nothing, and every later await() returns at once. Reusing it for a second round lets the waiter go ahead before the round is done (Demo: a latch is one-shot). Make a new latch per round, or use a barrier.
| Barrier | Countdown latch | |
|---|---|---|
| Who waits | all N participants, for each other | the thread(s) calling await() |
| Who counts | each arrival | countDown(), from any thread, without waiting |
| After it opens | resets for the next phase | stays open for good |
| Typical API | pthread_barrier_wait, CyclicBarrier, std::barrier, OpenMP #pragma omp barrier | CountDownLatch, std::latch, sync.WaitGroup |
Where you meet them
- Data-parallel loops. OpenMP puts an implicit barrier at the end of every parallel loop; MPI has
MPI_Barrier. - GPUs.
__syncthreads()is a barrier for the threads of one CUDA block, between writing and reading shared memory. - Bulk-synchronous systems. Graph engines such as Pregel run in supersteps separated by a global barrier.
- Tests and start-up. A latch lets a test start many threads at the same moment, or lets a server wait until all its components are ready.
See also Monitor & Condition Variables for the lock, wait and broadcast used here, Semaphore and Semaphore vs Condition Variable for the other basic tools, and Thread Pool for work that is handed out rather than split into phases.
What the page leaves out
The threads run one atomic line at a time on a single CPU, so there are no memory-ordering effects; a real barrier also acts as a memory fence, so the next phase sees the previous phase's writes. The page leaves out spinning barriers with sense reversal, tree and dissemination barriers that scale to many cores, timeouts and broken barriers (BrokenBarrierException), the barrier action that CyclicBarrier runs in the last thread, and Phaser, whose number of parties can change between phases.