# Tree Barrier – Georgia Tech – Advanced Operating Systems

So I’m going to first describe to you a more scalable version of the sense reversal algorithm. And the basic idea is to use divide and conquer. I have a hierarchical solution. That is, limit the amount of sharing to a small number of processes. Let’s say a small number K of processes and, and in this example, k is equal to 2. So essentially, you know, what we are saying is, if you have n processors that the condition, break them up into small groups of k processors. And so we build the hierarchical solution and the hierarchical solution obviously leads to a tree solution. And so, since we have K processors competing and accomplishing a variable among themselves. If you have N processors, then you have a log, and the base K as a number of levels in the tree, in order to achieve the value. And in this case, what we have done is K is equal to 2. And so, the number of levels and with the eight processors The number of levels in the tree is going to be three. So let’s talk about what happens when we [UNKNOWN] a value. So, at a micro level algorithm works exactly like a sense reversing algorithm. And that is, these two processes if they’re sharing this data structure at count Variable and a locksense variable and you see that for every k processes and in this case k being two, every two processes you have issued two shared variables: account variable and a locksense variable. Count variable locksense variable, count and locksense. And, so what’s going to happen and you’ll see that you have this count and locksense variable. Replicated in every level of the tree, and we’ll talk about how these going to, are, variables are going to be used in the progression of this algorithm. So let’s first talk about arriving at a barrier. So let’s say that P1 has arrived at the barrier. What it is going to do is, it’s going to go and decrement this counter. Now, what is this counter going to be set to? Well, This counter is, is just for the key processes that are value syncing here and keeping two this counter is going to be two. And so, this guy is going to decrement the count and if the count is not zero it’s going to basically wait for the sense to reverse. Just like the sense reversal of algorithms. The same thing is going to happen that P1 comes here decrements the count and it waits for sense to reverse by spinning on this flag. Sometime later, P0 comes to the barrier and it decrements the count, count goes to zero, but you’re not done with the barrier yet, because the barrier is for all of the processes. So what P0 is going to say is okay, between the two of us I know that we both have reached the value because the count is zero. But I have to go up, and go to the next level up and here I’m going to decrement the count here, to indicate that I’ve arrived at the value. So P0’s the one that arrive up the tree, P1 is stuck here waiting for sense to diverse, P0 moves up. So remember that even though P0’s come here decremented the count and made it zero, that doesn’t flip the sense flag yet. Right? Because the value will be done only when everybody has arrived, and therefore all that P0 is going to do now is decrement the count, see that it is 0, then it is going to move up in the tree and go to the next level of the tree. And this data structure, which is now shared among this half of the tree this half of the tree is sharing this data structure, so P0 decrements this count. And what’ll this count be resized to? Again, 2, right? Because at every level, you have k processors, k being 2 in this case, arriving at a barrier. So P0 arrives here, decrements the count, count is not 0 yet, and so it waits. So P0 is going to wait on locksense to reverse here. P1 is waiting on locksense deliveries here P0 is not waiting on locksense deliveries here because it has arrived at the barrier but his partners are still stragglers, they have not arrived at the barrier yet.