Making sense of the “sense reversing barrier” (synchronization)

What’s the deal with a sense reversing barrier? Even after watching the lectures on the topic, I was still confused as to how a single flag could toggle between two values (true and false) can communicate whether or not all processes (or threads) are running in the same critical section. This concept completely baffled me.

Trying to make sense of it all, I did some “research” (aka google search) and landed on a great article titled Implementing Barriers1.  The article contains source code written in C that helped demystify the topic.

Sense Reversal Barrier. Credit: (Nkindberg 2013)

 

The article explains how each process must maintain its own local sense variable and compare that variable against a shared flag. That was the key, the fact that each process maintains its own local variable, separate from the shared flag. That means, each time a process enters a barrier, the local sense toggles, switching from 1 to 0 (or from 0 to 1), depending on the variable’s last value. If the local sense variable and the shared flag differ, then the process (or thread) must wait before proceeding beyond the current barrier.

For example, let’s say process 0 initializes its local sense variable of 0. The process enters the barrier, flipping the local sense from 0 to 1. Once the process reaches the end of the critical section, the process compares the shared flag (also initialized to 0) with its local sense variable and since the two do not equal to one another, then that process waits until all other processes complete.

References

1. Nkindberg, Laine. 2013. “Implementing Barriers.” Retrieved September 17, 2020 (http://15418.courses.cs.cmu.edu/spring2013/article/43).