Let's look at a very simple implementation of a
mutual exclusion lock. In terms of the instructions that the
processor will execute in order to get this lock, will
be to come in and check if the lock is
currently available and that is done by this check.
And if it is available then we're going to set it
to one to indicate that, I've got the lock, nobody
can get it. All right? That's the idea behind this
check and then setting this to one. On the
other hand, if somebody already has the lock L is
going to be one and therefore I'm going to wait here
until some the the lock is released. And once the
lock is released, then I can go back and
check again, to make sure that the lock is available
and set it to one. So this is the basic
idea. Very simple implementation of this lock. And, and how
will I know that the lock has been released? Unlocking this is
a very simple operation again. All that you have to do is
reset this L to zero, and that'll indicate that the lock has
been released. So, if I am waiting here, and somebody else has
got the lock, they going to come and unlock it by setting it
to zero. And that way, I will know that it has been
released. I can go back. I double check to make sure it
is still zero, because somebody else could have gotten in the middle.
If nobody else has gotten it, then I can set it to one. So this is the idea of
a simple, very simple minor implementation of, a lock
algorithm. Is it possible to implement the simple minded implementation
of the lock using atomic reads and writes alone?
Let's talk thought this implementation here. Now, if you look
at this set of instructions that the processor has
to execute in order to acquire the lock. It has
to first read L from memory, and then check if it is 0. And store that new
value which is 1, into this memory location. That's
a group of three instructions that the processor has
to execute and the key thing is these three
instructions have to be executed atomically in order to
make sure that I got the lock and nobody
else is going to interfere with my getting the lock.
And as we know reads and writes instructions by
themselves are atomic, but a group of reads and
writes are not atomic and therefore. What we have
here is a group of tree instructions and we need
them to be atomic. What that means is we
cannot have just reads and writes as the only
atomic operations if we want to implement this lock
algorithm. And we need a new semantic for an atomic
instruction, and the semantic is what I call the read modify write operation.
Meaning that I'm going to read from memory Modify the value and write it back to
memory. So that's the kind of instruction that is needed in order to ensure that
we can implement a lock algorithm. Now several flavors of
read-modify-write instructions have been. Proposed, and
or have been implemented in processor architectures. And
we will look at a couple of them. The
first one is what is called a test and
set instruction. The idea here is, the test and
set instruction takes on a memory location as an
argument. And, what it does is, it returns the
current value that is in this particular memory location.
And also sets the memory location to a one.
So, these two things that are being done.
That is, getting the current value from memory
and setting it to one, is being done
atomically. That's the key thing. That it is
testing the old value and setting it to this new value, atomically.
Another atomic Read Modify Write instruction that has been imposed and/or
implemented is what is called a fetch and increment instruction.
And this takes on again, a memory location of an argument,
and what it is gong to do is, it is going
to fetch the old value of what was in the memory...
And then incriment the current value that is in the emmory by
one or whatever value. So it could be that this may
take on an extra argument to indicate how much it is
going to change it by. But in the simple version it
might simply imple, increment, in the simple version it might simply incriment
the current value that is in the memory location
by one. As I said before, there have been
several flavors of read modify write instructions that have
been proposed in the literature. And often generically these
read modify instructions are called fetch and phi instructions.
Meaning that it is going to fetch an old
value from memory. And do some operation on that
fetched value and write it back to memory. So,
for instance, fetch an increment is one flavor
of that. There are other flavours like fetch
and store, fetch and decrement compare and swap
and so on. And you can read about that
in the papers that we've identified for you.
Okay, now that we have an atomic read modify
write instruction available from the architecture, we can
start looking at how to implement the mutual exclusion
lock algorithems. Now, I gave you, of course,
a very simple version of it, we'll talk
more about that in a minute. And, and
I'm sure that in the first project, when you
implemented the mutual exclusion lock, you did not
care too much about the scalability of your
locking implementation. Now if you are implementing your
mutual exclusion algorithm on a large scale shared memory
multi-processor, let's say with 1000's of processes.
You'll be very worried about making sure that,
that your synchronization algorithm scale and scalability
issues fundamental to the implementation of synchronization algorithms.