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.