馃攳
Atomic Operations - Georgia Tech - Advanced Operating Systems - YouTube
Channel: unknown
[0]
Let's look at a very simple implementation of a
[3]
mutual exclusion lock. In terms of the instructions that the
[7]
processor will execute in order to get this lock, will
[12]
be to come in and check if the lock is
[14]
currently available and that is done by this check.
[18]
And if it is available then we're going to set it
[20]
to one to indicate that, I've got the lock, nobody
[23]
can get it. All right? That's the idea behind this
[25]
check and then setting this to one. On the
[28]
other hand, if somebody already has the lock L is
[31]
going to be one and therefore I'm going to wait here
[34]
until some the the lock is released. And once the
[39]
lock is released, then I can go back and
[42]
check again, to make sure that the lock is available
[45]
and set it to one. So this is the basic
[47]
idea. Very simple implementation of this lock. And, and how
[51]
will I know that the lock has been released? Unlocking this is
[54]
a very simple operation again. All that you have to do is
[57]
reset this L to zero, and that'll indicate that the lock has
[62]
been released. So, if I am waiting here, and somebody else has
[65]
got the lock, they going to come and unlock it by setting it
[67]
to zero. And that way, I will know that it has been
[70]
released. I can go back. I double check to make sure it
[73]
is still zero, because somebody else could have gotten in the middle.
[76]
If nobody else has gotten it, then I can set it to one. So this is the idea of
[79]
a simple, very simple minor implementation of, a lock
[83]
algorithm. Is it possible to implement the simple minded implementation
[88]
of the lock using atomic reads and writes alone?
[92]
Let's talk thought this implementation here. Now, if you look
[95]
at this set of instructions that the processor has
[97]
to execute in order to acquire the lock. It has
[101]
to first read L from memory, and then check if it is 0. And store that new
[108]
value which is 1, into this memory location. That's
[111]
a group of three instructions that the processor has
[114]
to execute and the key thing is these three
[117]
instructions have to be executed atomically in order to
[120]
make sure that I got the lock and nobody
[123]
else is going to interfere with my getting the lock.
[126]
And as we know reads and writes instructions by
[129]
themselves are atomic, but a group of reads and
[132]
writes are not atomic and therefore. What we have
[135]
here is a group of tree instructions and we need
[138]
them to be atomic. What that means is we
[141]
cannot have just reads and writes as the only
[143]
atomic operations if we want to implement this lock
[147]
algorithm. And we need a new semantic for an atomic
[152]
instruction, and the semantic is what I call the read modify write operation.
[156]
Meaning that I'm going to read from memory Modify the value and write it back to
[161]
memory. So that's the kind of instruction that is needed in order to ensure that
[166]
we can implement a lock algorithm. Now several flavors of
[171]
read-modify-write instructions have been. Proposed, and
[177]
or have been implemented in processor architectures. And
[180]
we will look at a couple of them. The
[182]
first one is what is called a test and
[185]
set instruction. The idea here is, the test and
[188]
set instruction takes on a memory location as an
[192]
argument. And, what it does is, it returns the
[196]
current value that is in this particular memory location.
[199]
And also sets the memory location to a one.
[202]
So, these two things that are being done.
[205]
That is, getting the current value from memory
[208]
and setting it to one, is being done
[210]
atomically. That's the key thing. That it is
[213]
testing the old value and setting it to this new value, atomically.
[219]
Another atomic Read Modify Write instruction that has been imposed and/or
[224]
implemented is what is called a fetch and increment instruction.
[229]
And this takes on again, a memory location of an argument,
[232]
and what it is gong to do is, it is going
[234]
to fetch the old value of what was in the memory...
[238]
And then incriment the current value that is in the emmory by
[241]
one or whatever value. So it could be that this may
[244]
take on an extra argument to indicate how much it is
[247]
going to change it by. But in the simple version it
[250]
might simply imple, increment, in the simple version it might simply incriment
[255]
the current value that is in the memory location
[257]
by one. As I said before, there have been
[259]
several flavors of read modify write instructions that have
[262]
been proposed in the literature. And often generically these
[268]
read modify instructions are called fetch and phi instructions.
[272]
Meaning that it is going to fetch an old
[274]
value from memory. And do some operation on that
[277]
fetched value and write it back to memory. So,
[279]
for instance, fetch an increment is one flavor
[281]
of that. There are other flavours like fetch
[284]
and store, fetch and decrement compare and swap
[288]
and so on. And you can read about that
[290]
in the papers that we've identified for you.
[294]
Okay, now that we have an atomic read modify
[297]
write instruction available from the architecture, we can
[301]
start looking at how to implement the mutual exclusion
[305]
lock algorithems. Now, I gave you, of course,
[308]
a very simple version of it, we'll talk
[310]
more about that in a minute. And, and
[312]
I'm sure that in the first project, when you
[315]
implemented the mutual exclusion lock, you did not
[319]
care too much about the scalability of your
[322]
locking implementation. Now if you are implementing your
[325]
mutual exclusion algorithm on a large scale shared memory
[330]
multi-processor, let's say with 1000's of processes.
[333]
You'll be very worried about making sure that,
[337]
that your synchronization algorithm scale and scalability
[340]
issues fundamental to the implementation of synchronization algorithms.
Most Recent Videos:
You can go back to the homepage right here: Homepage