In the previous lesson we looked at efficient
implementation of mutual exclusion lock algorithms. In this lesson
we're going to look at barrier synchronization how, how
to implement that efficiently in the operating system. And
just to refresh your memory about the barrier
the barrier synchronization works like this, that you have
a bunch of processors and they all need to
know where they are with respect to each other.
Where they want to, reach a barrier. And they want to
wait here until everybody has arrived at this barrier. So
if T1 arrives at the barrier, it's going to wait until
everybody else has come. So one of the guys, maybe
a straggler is going to come a little later, and in
that case, everybody has to wait until all the threads
that are part of this application have arrived at the
barrier, then they can move on. And, and I mentioned
to you that this kind of synchronization is very popular
in scientific applications and they go through these phases where
they execute code for a while, reach a barrier, and
then execute code for a while, reach another barrier, execute
four code for a while, reach a barrier and so
on and so forth. And, and I mentioned also that
in real life this happens quite often. When we go
to a dinner with with a bunch of our friends and
some of us show up early and others come
late. The usher is going to hold us all, ransom. Wait
'til everyone is here. Until, until then I cannot
seat you. So that same sort of this that's happening,
with the barrier that all of the threads have
to arrive at the barrier, only then they can proceed
on. So that's the semantic of the Barrier Synchronization. And
I'm going to describe to you a very simple implementation
of this barrier. The first algorithm I'm going to describe to
you as what is called a centralized barrier or also sometimes
called a counting barrier. So centralized barrier, counting barrier, that's a
name that, that's given to this. The idea is very, very
simple. You have a counter, that's why it's called a counting
barrier. You have a counter. And the counter is initialized to
N, where N is the number of threads that need to
synchronize at the barrier. And what is going to happen is that,
when a thread arrives at the barrier, it's going to atomically decrement
the count. A key thing is it has to be done
atomically. So once is it atomically decremented and the count then,
it's going to wait for the count to become zero. So long
as the count is not zero, it's going to wait. So if
the count is zero, we're going to do something else, but if
the count is not zero that means that, I've arrived at
the barrier, but I don't know where the others are yet.
So I'm going to wait. So they're, they're going to spin
and the spin is basically saying while count is greater
then zero, spin. And all the processors except the last
one are going to be doing this spinning on count
becoming zero. Now the last processor, the straggler may
be the T2's sta-, straggler. And the straggler arrives eventually.
And when he arrives, then what he's going to do is
he's going to decrement also. And when he decrements the count,
he'll see that the count has become zero. And so what
he will do is he'll reset the count back up to
N. And that is indication that everybody, so, so all of
these guys are waiting on count being greater than zero. So
as soon as the count becomes zero, then they can, they
can be released from the barrier. And the last processor to
arrive is going to reset the count to N to indicate that
when these guys go off, before they come to the next barrier,
the count has to be N. So that's the
idea behind that. So very simple algorithm. Decrement the count
atomically when you come to the barrier. If the count
is greater than zero, then you know that everybody has
not arrived, spin. And everybody except the last guy
will do the spin. And the last guy that comes
around decrements the counter for, and, and the counter becomes
zero. And once the counter becomes zero, all the guys
that are stuck here, they're going to be
released. And then the last processor will reset this
count to N so that you know, all these guys are now on their way to the
next barrier. So, it is resetting it to
N so that the barrier can be executed again
when all these guys get to the next
barrier. And that's the idea behind the centralized barrier.