Since we've initialized this array with hl in the
first spot and mw in all of the other
spots of this array, to enable the queuing what
we will do is associate with each lock another
variable, which is called a queuelast variable. And this
queuelast variable is initialized to zero. And so these
two are the two data structures associated with every
lock. So every lock that you have in your program,
the operating system is going to assign two data structures
for you. One, which is the circular queue, represented
by the flags array. And the other is the
queuelast variable, which is saying, what is this part that
is available for you to queue yourself in this,
in this particular array? So as you can see, since
there is no lock request yet, we just initialized
the queue, the first guy that comes around to ask
for the lock will get it, and, and he
will queue himself here and he will get the lock
as well. So let's say some processor came along,
and, and made a lock request. It's going to get
it immediately because there's no locks request currently pending.
And so it's got this position and it's got the
lock and what will happen is that the queuelast
variable will advance to the next spot to indicate that
future requesters have to start queuing up from here. And
now this current lock holder has got the lock and he
can go off in the critical section and do whatever
he wants in terms of managing or messing up with the
data structure that is governed by this particular lock. Let's
say that at some point of time, I come along and
request the same lock. Now depending on who else got
ahead of me at the point that I made that lock
request, there may be some number of people that are
lined up ahead of me and where ever queuelast is
pointing is my place. And, and so this is where
I'm going to queue myself, waiting for that lock, and of
course queuelast will advance to the next open spot for future requesters that
come after me. Now the important point that I want you to notice is that since
that the array size is N and the number of processes
is N, nobody will be denied. [LAUGH] Everybody
can come and queue up waiting for this lock.
Because since there are N processes at most
N simultaneous requests can be there for the lock
and everybody will get their unique spot to
wait for if in fact the lock is currently
in use. Given the timing of my lock
request and the position of the current lock holder,
you can see that I have some waiting to do, because
there are a quite a few requests that are ahead of
me, and so I have some waiting to do before I
get my turn in in acquiring this particular lock. So now
I can tell you how the lock algorithm is going to look
like, pretty simple. When I make a lock request what I'm
going to do is mark my place in this flags array
and the way I do that is by calling fetch and increment
on the queuelast variable. And that ensures that I
get my unique spot due to the fetch operation
and I increment the queuelast to point to the
next spot which is available to the next spot for
future requesters. And since fetch-and-increment is an atomic operation,
remember that we have read modify write operations, fetch-and-increment is
one of those. And it's an atomic operation and
therefore, even though it's a multiprocessor there could be multiple
guys trying to get the same block at
the same time. They're all good to be sequenced
through this fetch-and-increment atomic operation, and so there is
no issue of any risk condition in that sense
So, I will get my spot and I'll increment
queuelast. And, of course, if the architecture does not
support this fancy fetch and increment read modify write
operation, then, you know, you have to simulate that
operation using, using test and increment instructions. So
once I've marked my position in this flags array,
then I'm going to basically wait for my turn. So what I do in order to wait is
I'm basically waiting for this spot that I've marked
myself, it is right now must wait, it has
to change to hl. Once it changes to hl,
I know I have the lock, and therefore I'm
going to do a spin on this particular
location. and, and I'm going to wait for this,
this location changing its value from mw to hl, so that's the spin loop that you
see here. So basically once I have marked
my position, I'm going to wait on my position
becoming hl to know that I have acquired
the lock. And, I will get it eventually,
because that's the way this algorithm is supposed to work.