Tree Barrier (cont) – Georgia Tech – Advanced Operating Systems

Tree Barrier (cont) – Georgia Tech – Advanced Operating Systems


Of course, multiple processors can arrive at the barrier at the same time and all of them are going to work with their local data structure. So, like, this guy will work with this local data structure. This guy with this local data structure. With this local data structure. And each of them is waiting for his partner to arrive so that he can move up the tree. So that’s what going on and so eventually, P3 is going to arrive and so when P3 arrives, he decrements the count, sees it as zero so he can move up the tree. When it comes here it says, oh the count is already one so I decrement it and the count becomes zero and remember P0 decremented the count and it is waiting on locksense. So P3, when it comes here, finds that the count is one, decrements it, becomes zero and it moves up the tree because the barrier is still not done until we know that everybody has arrived at the barrier. So in the meanwhile, on this half of the tree, what’s going on is that P4 has arrived, P5 is not there yet, P6 and P7 have arrived. And it turns out that P6 was the last guy to come to the barrier here, and therefore, he is the guy that has moved up. And he has decremented count. And he’s waiting for this half of the tree to arrive at the barrier. And you can guess which one is going to come up, right? Because P4 has already arrived here, and so if P4 has already arrived here, he’s decremented the count, and he’s waiting on locksense to flip. So the straggler in this whole seam, scheme of things, is this guy right here. He’s the guy who is, is still not arrived, but eventually he’ll also arrive. When he arrives, he will decrement the count, find that the count has become zero, move up the tree, and he’ll find that this count is already decremented also, and when he comes up here, he will decrement it to zero, and then he’ll say, oh, if we’re all done, so we can move up here. So, that’s what is going to happen. So we come here, P5 comes here and goes all the way up. And then when it comes up here, it sees that P3 has already decremented the count to one. And so when he comes up, he decrements it, and it becomes zero. And at this point, everybody has arrived at the barrier. So let’s understand what each processor does. When a processor arrives at a barrier it is going to decrement the count. If the count is not zero, it’s going to spin on this locksense flag. If a processor arrives at a barrier, decrements the count, finds that the count is zero, then what it’s going to do is one of two things. The first thing it’s going to do is, he’s going to say, do I have a parent? If I have a parent, what I have to do is, I have to recurse. Do the same thing to the next level. Right? So, so the algorithm is, decrement count and see if the count becomes zero. If the count has become zero, then you recurse. If end of the parent is there, you recurse. If the count does not become zero, then spin on the local locksense flag. And you continue this. So you continue this P0, that this came up here and informed this is another parent. So so this, you know, it, it is, it is, it is stuck here. But P3, when it came later on, it moves up. And when it came up here, this is the last part. So there’s no more recursing here. So when P5 finally arrives here, it finds that there is no more parent. This is the root of the tree. And since we reached the root of the tree, you know that if the count is zero now at the root of the tree, then everybody has arrived at the barrier. So count at the root of the tree becoming zero is indicative to the last arriving processor, P5 in this case, that everybody has arrived at the barrier, so it’s time now to wake up everyone.

Leave a Reply

Your email address will not be published. Required fields are marked *