A barrier keeps a fixed group of threads from passing a synchronization point until every member has arrived. It is reusable: after releasing the group, it starts a new cycle. Each thread arrives once per cycle. A latch differs because it becomes ready permanently when its counter reaches zero, and one thread may decrement that counter multiple times. section 4.4.7
Picture a roller coaster that cannot leave until every seat is filled. The barrier’s participant count is its number of seats. Threads that arrive early wait for the last arrival; then all may continue. Repeating this in a loop keeps cooperating threads from running ahead into the next step. section 8.5.3
Listing 8.12. A simple barrier class
class barrier
{
unsigned const count;
std::atomic<unsigned> spaces;
std::atomic<unsigned> generation;
public:
explicit barrier(unsigned count_): #1
count(count_),spaces(count),generation(0)
{}
void wait()
{
unsigned const my_generation=generation; #2
if(!--spaces) #3
{
spaces=count; #4
++generation; #5
}
else
{
while(generation==my_generation) #6
std::this_thread::yield(); #7
}
}
};
!@%STYLE%@!
{"css":"{\"css\": \"font-weight: bold;\"}","target":"[[{\"line\":6,\"ch\":51},{\"line\":6,\"ch\":53}],[{\"line\":11,\"ch\":51},{\"line\":11,\"ch\":53}],[{\"line\":12,\"ch\":51},{\"line\":12,\"ch\":53}],[{\"line\":14,\"ch\":51},{\"line\":14,\"ch\":53}],[{\"line\":15,\"ch\":51},{\"line\":15,\"ch\":53}],[{\"line\":19,\"ch\":51},{\"line\":19,\"ch\":53}],[{\"line\":20,\"ch\":51},{\"line\":20,\"ch\":53}]]"}
!@%STYLE%@!
In this C++11 implementation, `spaces` counts arrivals still needed and `generation` identifies the current cycle. Each call to `wait()` records its generation and decrements `spaces`. The last arrival restores `spaces` and advances `generation`; earlier arrivals repeatedly check for that change, yielding between checks. Thus the code waits by checking an atomic value rather than using a direct C++11 library barrier. section 8.5.3
Synchronizing parallel partial sums
In a parallel partial-sum calculation, threads update values in successive steps. Without synchronization at each step, a thread could modify a value another thread still needs, or read one that has not yet been updated. A barrier makes each step wait for the other participants before work continues. section 8.5.3
Listing 8.13. A parallel implementation of partial_sum by pairwise updates
struct barrier
{
std::atomic<unsigned> count;
std::atomic<unsigned> spaces;
std::atomic<unsigned> generation;
barrier(unsigned count_):
count(count_),spaces(count_),generation(0)
{}
void wait()
{
unsigned const gen=generation.load();
if(!--spaces)
{
spaces=count.load();
++generation;
}
else
{
while(generation.load()==gen)
{
std::this_thread::yield();
}
}
}
void done_waiting()
{
--count;
if(!--spaces)
{
spaces=count.load();
++generation;
}
}
};
template<typename Iterator>
void parallel_partial_sum(Iterator first,Iterator last)
{
typedef typename Iterator::value_type value_type;
struct process_element #1
{
void operator()(Iterator first,Iterator last,
std::vector<value_type>& buffer,
unsigned i,barrier& b)
{
value_type& ith_element=*(first+i);
bool update_source=false;
for(unsigned step=0,stride=1;stride<=i;++step,stride*=2)
{
value_type const& source=(step%2)? #2
buffer[i]:ith_element;
value_type& dest=(step%2)?
ith_element:buffer[i];
value_type const& addend=(step%2)? #3
buffer[i-stride]:*(first+i-stride);
dest=source+addend; #4
update_source=!(step%2);
b.wait(); #5
}
if(update_source) #6
{
ith_element=buffer[i];
}
b.done_waiting(); #7
}
};
unsigned long const length=std::distance(first,last);
if(length<=1)
return;
std::vector<value_type> buffer(length);
barrier b(length);
std::vector<std::thread> threads(length-1); #8
join_threads joiner(threads);
Iterator block_start=first;
for(unsigned long i=0;i<(length-1);++i)
{
threads[i]=std::thread(process_element(),first,last, #9
std::ref(buffer),i,std::ref(b));
}
process_element()(first,last,buffer,length-1,b); #10
}
!@%STYLE%@!
{"css":"{\"css\": \"font-weight: bold;\"}","target":"[[{\"line\":38,\"ch\":63},{\"line\":38,\"ch\":65}],[{\"line\":79,\"ch\":63},{\"line\":79,\"ch\":65}],[{\"line\":49,\"ch\":63},{\"line\":49,\"ch\":65}],[{\"line\":53,\"ch\":63},{\"line\":53,\"ch\":65}],[{\"line\":55,\"ch\":63},{\"line\":55,\"ch\":65}],[{\"line\":57,\"ch\":63},{\"line\":57,\"ch\":65}],[{\"line\":59,\"ch\":63},{\"line\":59,\"ch\":65}],[{\"line\":63,\"ch\":63},{\"line\":63,\"ch\":65}],[{\"line\":71,\"ch\":63},{\"line\":71,\"ch\":65}],[{\"line\":76,\"ch\":63},{\"line\":76,\"ch\":65}],[{\"line\":79,\"ch\":63},{\"line\":79,\"ch\":66}]]"}
!@%STYLE%@!
The pairwise-update partial-sum implementation includes a barrier whose `count` can change. Its `done_waiting()` operation reduces the participant count and updates the remaining spaces when needed, so later cycles need not wait for a participant that has finished. section 8.5.3
Choose a barrier when the same participating threads must meet repeatedly. Set the count to match those participants: a cycle cannot release until its required arrivals occur. The C++11 Thread Library does not directly provide this facility; the Concurrency TS adds barriers alongside latches. section 4.4.7 section 8.5.3
