So let's see what happens when the current
lock-holder comes around to unlocking the lock. What he's
going to do is, he's going to execute the unlock
algorithm. And the unlock algorithm, the first thing that
it does, is it sets this position that the lockholder had from HL to MW. And the
reason for that is, is that this is a
circular queue and since it's a circular queue even
though queue last is here future requesters can, can come
around and then eventually somebody may come here and may want
to occupy this particular slot and they have to know that
they have to wait. And that's the reason, the first thing
that the current lock holder does, is to mark this
spot that he used to be at, as hl. The next
thing that the current lock holder is, is going to do is
signal the next guy in the circular queue. So, the current
lock holder was here, so you'd mark it as mw
for future requesters that may come and wait on his
spot. And the next request in the circular queue is
the guy next to him. And therefore what he is
doing is, he is saying you know, current plus one
mode N, is going to be set to hl. And so,
that guy would have been waiting in this position and
so he'll get the signal. And therefore he will be
getting ready to go. And he can get into the
critical section and do whatever he wants to do with
the Data structure that is protected by this particular lock.
Now this will go on, and eventually, my predecessor will become
the current lock holder. And when my predecessor is done
using the lock, he'll come around to do an unlock
and when the current lock holder who's my predecessor does
the unlock operation, that's going to be resulting in a signal for
me, because basically. He's going to set the flags array,
the next spot in the flags array, as hl. And
that's the spot I'm waiting on. So good news for
me. I've got my position marked as hl, and what
that means is that now I've got the lock. And
now I can go off into the critical section do
what I need to do in order to do the
code that is associated with the critical section protected by,
this particular lock out. Now that we understand that the
lock and the unlock algorithm works with this array-based queuing,
let's talk about some of the virtues of this algorithm.
The first thing that you notice is that there is
exactly one atomic operation that you have to carry out,
put, put critical sections so,every time you want to acquire a
lock you come in and do a fetch and increment
and that is all that you do in order to get
the lock. And so there's one atomic operation that
you do per critical section, that's good news. And
the other thing that you also notice is that,
the processes are all sequenced in other words there is
fairness uh, so whoever comes first. Gets into the
queue ahead of me and when I come in
if people are going to come after me they're going to
get queued up after me. So that's good news also.
And the spin variable we're going to mark my position
in this array my spin variable is distinct from
the spin variable of all the other guys that
may be waiting for the same lock. That's another good
thing. In other words, I'm completely unaffected by all
the signaling that it will happen when the guys that
are ahead of me were getting the lock and,
and signaling the next guy and so on. I'm completely
impervious to that because I'm spinning on my
own private variable. Waiting for the lock. And
of course correlating to what I just said
is that whenever a lock is erased, exactly one
guy is signaled to indicate that they've got
the lock. And, and that's another important virtue of
this particular algorithm. So, it is fair. And
it is also not nice, so these are two
things that very good things about this algorithm. And
those we saw were you know the deficiency of the
ticket log algorithm was exactly that where it is fair,
but it is noisy when the lock is released. So
that problem has gotten away with this queuing lock. Now
you might be wondering, are there any downside to this
array based queuing lock. I assure there is. The first
thing I'm sure that you've noticed already is the size
of the data structure is as big as the
number of processors in the multiprocessor. So the space
complexity [COUGH] for this algorithm is order of N
for every lock that you have in the multiprogram. So
if you have a large scale multiprocessor with dozens
of processors, that can start eating into the memory
space. So that's something that you have to watch
out for. So the space can be a big overhead.
And the reason I'm emphasizing that is because
in any well-structure multi-threaded program even though we may
have lots of threads executing in, in all
the processors. At any point of time for a
particular lock, they might not be in contention
but all the processors, only a subset of them
may be requesting the lock. But still, this
particular algorithm has to worry about the worst case.
Contention for a lock, and therefore it creates a data
structure that is as big as a number of processes
that you have in the multiprocessors. And that's the only
downside to this, but all the other things are good stuff
about this algorithm. And of course the reason why you
have that downside with the, with this particular Anderson's queueing
lock is the fact that the queue is being simulated
by a static data structure, an array. And since it is
a static data structure and you have to
worry about the worst case contention among requesters for
a lock we have to make this static array
as big as the number of processors. So that's
really the the catch in this particular algorithm.
Next we will look at another algorithm, a lock
algorithm that is also based on queuing, but it
doesn't have the space complexity of Anderson's queuing lock.