Now let's look at how we can exploit the caches
available. Now, it is a fact that a tested set
instruction has to necessarily go to memory when we want
to acquire the lock, we have to execute a tested
set instructions so that we can atomically make sure that
exactly one processor gets the lock. But on the other
hand, the guys that don't have the lock. Could, in
fact, exploit the caches in order to wait for the lock.
And that's why this particular algorithm that I'm going to
describe to you is what is called spin on read,
and the assumption here is that you have a
shared memory machine in which the architecture is providing cache
coherence, or in other words, through the system bus
or interconnection network, The hardware is ensuring that the caches
are kept coherent. Well that gives us an idea
as to how we can exploit the caches. The waiters,
instead of executive a test [INAUDIBLE] instruction that has
to go to memory, they can spin locally on the
cached value of the lock. because when you are
spinning on the local cached value of the lock. If
that value changes in memory, these guys are going
to notice that. That's the principle behind the cache coherence
that is implemented in hardware. And so we can exploit
that fact in implementing a more efficient way of spinning.
Which is called spin on read. The idea is that the
lock algorithm, the first thing it's going to do is go and
do a check on the, the memory location to see if
it is locked. So this is a, a normal atomic read operation
that is being done, not a test and spin operation, so
if it is not in the cache, you're going to go to memory
and bring it in, and once you bring it in, so
long as this value doesn't change, we're going to basically looking at the
value that is in that cache in order to do
the checking And I'm not going to go to the
bus and therefore, I'm not producing any contention on the
network. And there could be any number of processes waiting on
the lock simultaneously. No problem with that because all of
them are going to be spinning on the local value of
L in their respective caches. And so if there is
one processor that's actually doing useful work and it has to
go to memory, it's not going to find that
to be a problem. No contention on the network
from the waiting processors because of this. Now,
if the one processor that was having the lock
eventually releases it, they go, everybody's going to notice
that. And so if I'm waiting for the lock,
and I've been spinning here locally in my
cache, when the, the lock is released, I'll notice
that through the cache coherence mechanism as I'll, I'll
break out of this spin loop. But immediately, I
want to check, I want check if the lock
is available by doing this test and set and
get it uniquely for myself. So multiple processors are
trying to execute this testing set simultaneously. It's possible
somebody else is going to beat me to the punch
and if that happens, I simply go back and, and,
and do the grouping on my private copy of L and wait for the guy who beat me
to the punch to release a lock eventually. So
that I can get it. So that's the idea.
The idea is you spin locally. When you notice
that the lock has been released you try and
do a test and set. If you get lucky you win, if you lose you go back and spin
again locally. So that's the idea behind spinning on
read. The unlock operation of course is pretty straightforward. The
guy that wants to unlock is simply going to change the
memory location to indicate that L is no longer locked.
So that's all it has to do. And then, and
then the other processes can observe it through the cache
coherence mechanism, and be able to acquire the lock. But
note what happens when the lock is released. When the
lock is released, all the processes that are stuck here
in the spin loop, they are going to go and
try to do this test and operation at the same
time, and we know that test and set has to
bypass the cache, everyone is hitting on the bus, right?
Everybody is hitting on the bus, trying to go to
memory, in order to do this test and operation. And
so that essentially means that, in a right invalidate this
cache coherence mechanism is going to result
in order of n squared bus transactions.
For all of these guys to stop chattering on the bus, because everyone of
these test and set instructions is going to
result in invalidating the caches, and as
a result, you have an order of n squared operation that is going to result
when a lock is released, where n is the number
of processors that are simultaneously trying to get the lock.
And, obviously, this is impeding that one guy that got
the lock and can actually get some useful work done.
And this is clearly disruptive. And earlier one of the
things that we said is that we want to avoid
or limit the amount of disruption to useful work that
can be done by the process that acquired the lock.