Implementing a Barrier: The Counter Approach

Core Idea
Count arriving threads with a protected counter. When count reaches N, release everyone through a turnstile.
The Components
count: Tracks how many threads have arrived. Starts at 0.
mutex: Protects the counter from concurrent updates.
barrier semaphore: Initialized to 0 (locked). Blocks threads until all arrive.
The Algorithm
Each thread: (1) Lock mutex, increment count, unlock mutex. (2) If count equals N, signal the barrier. (3) Wait on barrier. (4) Signal barrier (let next thread through).
Barrier Flow (N=3)
T1 arrivescount = 11 != 3wait()BLOCKEDT2 arrivescount = 22 != 3wait()BLOCKEDT3 arrivescount = 33 == 3!signal()RELEASE!TurnstileEach thread:wait()signal()pass through
The Turnstile Pattern
After waiting, each thread immediately signals. This creates a chain reaction: thread wakes, signals, next thread wakes, signals, and so on. All N threads pass through one at a time in rapid succession.
Why Signal After Wait?
Without it, only one thread passes. The Nth thread signals once, one blocked thread wakes, but the others remain stuck. The turnstile (wait-then-signal) propagates the release to all waiting threads.
Key Pattern: wait() then signal() creates a turnstile. One thread unlocks it, then each passing thread keeps it open for the next. All N threads flow through.

💡 Key Takeaways

✓Use a counter (protected by mutex) to track arrivals. When count equals N, release the barrier.

✓Barrier semaphore starts at 0 (locked). The Nth thread signals it, releasing one blocked thread.

✓Turnstile pattern: each thread does wait() then signal(). Creates chain reaction releasing all threads.

✓Without the post-wait signal, only one thread escapes. The turnstile propagates the unlock to everyone.

✓Counter + mutex + semaphore + turnstile = complete barrier implementation.

📌 Interview Tips

13-thread barrier: T1 arrives (count=1, blocks), T2 arrives (count=2, blocks), T3 arrives (count=3, signals, all proceed).

2Turnstile in action: T3 signals, T1 wakes and signals, T2 wakes and signals. All three now past barrier.

3Missing turnstile bug: T3 signals, T1 wakes, T2 stays blocked forever. Common implementation mistake.

← Back to Barrier Synchronization Overview