And Dijkstra came up with this naming nomenclature. So, implementation of sum of
force. this idea is all well and good, but we still need some way to come up with
mutual exclusion. Believe it or not, you can actually do this with just loads and
stores. And we're going to be talking about that a little bit later in class.
But it's really pretty slow. and it's, it, there are some algorithms that can do this
with just loads and stores. But from an implementation perspective, people
typically try to go faster. So, if you want to go faster, it might be helpful for
your computer architecture, your instructions set architect, to come up
with a special instruction which will allow you to do something atomically. So,
when we say do something atomically, it means there's nothing else can be
interweaved in that, in the meantime. And the, the simple solution here is that you
add an atomic operation which can do a read, a modify, and a write. All
atomically if nothing else interleaving it. So going, going back to our locks and
sum of fours here. All inside of this, this P and all inside this V here, you
need to somehow, atomically modify S. You need to be able to read S you need to be
able to write S if you were able to implement this somehow with code inside of
the implementation of, of P and inside the implementation of V. So, the primitive
here that makes this faster is having some read modify write operation. And we're
going to look at a couple different choices of this. One of the most basic
ones is test and set. x86 has this instruction. This is the one of the most
basic operations on x86 for atomic operations. lots of other architectures
have an instructions which does this. So, we write here a piece a code. But in
reality, this is a piece of pseudo code, but in reality, this is an instruction
which we'll actually do this atomically relative to the whole rest of the system.
So, let's look at what test and set does. The basic idea of test and set is it, is
it's probably one of the most primitive atomic operations you can do. I've seen
something slightly simpler than this. there's like a test and clear which is a
little bit easier to implement. But, largely the idea is that, you're going to
look at a memory address. And if that memory address is what you expect it to
be, then write some value. And, implicit in this piece of code here is that, the
piece of code which executed the testing set needs to know whether it's exceeded
and was successfully able to write the value or not to, or to not write the
value. So, it's sort of a status code and that's returned in this register R here.
So, if we look at this piece of code, you pass into it a memory reference, a memory
address, which is the address of the sum of four or the address lock. And you pass
into it and, and, and a register name. We do a load into that register and that
happens unconditionally. This part here though, is the, is the, the test part. So
the test part here is we check whether the thing we just read from this memory
address is zero. And if so, we're going to write a one to the memory address.
Sometimes these test and set operations will actually allow you to write something
else besides just one. But, for right now, let's, this is sort of the more basic one
here. So, it writes a one to that memory address. And what's important here is the
architecture guarantees that all of this happens atomically. But what's interesting
is, if you think about our processors that we built, this requires a load and a
store. Hm. So, we will talk about how we implement this a little bit in, in a few
slides. But, you basically have to stop everything else, stop all other loads and
stores happening in the system. Do this load, do the test, and possibly do the
store in hardware. One of the more basic ways this is done or one of the original
way this was done actually on some of the SA-6 based architectures, is there is
something called the lock bit on the bus. So what they did is when one processor was
going to go execute a atomic operation like this, a testing set for instance. You
'd actually broadcast all of the other processors in the system saying, I'm about
to do this. Do not touch anything. Do not issue any memory instructions effectively,
or do not issue any bus, based memory instructions. It would, it would do the
load, it would do the test, and it would do the set, and then it would release the
broadcast bit. This is the wire on a multi-drop bus. that's a pretty big
hammer. things have gone a little bit better since then. But, just to give you
an idea of basic hardware implementation of this. things got a little more
sophisticated this sorta showed up in the, the 70s' here. These fancier operations or
the fancy atomic operations. So, this whole box here is still a atomic
operation. All the, the code in here happens atomically, and what this
basically does is it's going to take a memory address and add something to it.
So, we're going to add Rv to R and put that into memory at the same memory
address and, so we're going to do the load in the store here, atomically. So, it's a
read modified write operation also. And having it all the atomic. Note, this still
actually returns into register R here, the original value. And sometimes that's
actually very useful if you're trying to implement a semifor based on this you kind
of want to see what was there before. There's some, there's some jokes around
fetching at here, though. the atomic operation community kind of push this to
the extreme at some point and people started having sort of fetch and insert
something here. So, fetch and multiply, fetch and divide or, or things like that
and people started building some stranger machines that had fetch and something
else. There's this old joke that someone was going to implement instruction called
fetch and FFT. So, it would be atomic Fourier Transform. I don't think it ever
got to that point. But, in the, in the microcoded days and the, and the early
microprocessor microcoded days, there was some pretty sophisticated atomic
operations. That's largely been decided to not be a good direction t o go.
You want to have a little bit of complexity in your atomic operations. so
maybe test and set is a little too simple. But, some of these fancier fetching FFTs
is probably a little bit too complex. Here's another interesting operation that
is atomic. And this one you can actually build some pretty interesting semaphores
out of. It's called swap. So, it takes a register value and a memory location, and
it'll take what's in the memory location and what's in the register and swap the
two things. And note, we need to use we use a temporary here because you can't
actually swap two things without a temporary. This is actually not very
common because it's kind of hard to use. so what's a little bit more common to
something called compare and swap which is something between kind of a test and set,
and a swap operation. And that's, that's what commonly used and we'll talk about
that in a second. Okay, so now we go back to the multiple consumers problems that we
have, where multiple people were trying to DQ from a, a Q. And let's introduce test
and set, and we'll look at our critical section here. We're going to use this term
mutex to basically mean a sum of four that only one thing can enter at a time. So,
what happens at the beginning here is there is a tight loop, and this tight loop
will read from a relocation of mutex into a temporary register, and will compare it
to zero. Note, we define test and set as writing one to memory if it succeeds. So
if it was zero, that means that it was not able to actually modify memory. The test
failed. So if the test failed, it's just going to sit and spin here. And we'll call
this busy waiting or spin attritional spinlock, it's called. If it acquired the
lock, this read value would have been a one. So, it would not be equal to, or
excuse me, if there, if it acquired the lock through the, the, the, you just
write, if it's one, it's zero. Okay, sorry we did this wrong. If, if the memory
address was a, if it was a one coming into here, that means someone else already
locked it. If it's a zero coming into here, that means no one locked it, but we
locked it and set it to a one now. So if we acquired the lock, we're going to
atomically set it to a one, and we're going to read a zero. So, we'll drop into
our critical section and start executing our critical section. And it, under the
critical section, we can do stores, we can do loads, we can do whatever we want cuz
we're guaranteeing that no other op, no other processor, no other thread is doing
anything to it. And then at some point, we need to do the, the release here. And that
we actually don't need a test and set for, we just need a store. A store is just
going to clear that in a real location, and some other thread is safe to go and
fall into the critical section here. Okay. So, this can be done with lots of
different implementations. We showed here of test and set, but this can be done with
swap, it can be done with fetch and add. The code gets a little bit more complex.
But, one of the interesting questions that comes up is, what do you, what happens if
you running along some threat acquires the critical or acquires the law falls into
the critical section and let's say, terminates or gets swapped out for very
long period of time? What's, what's going to happen here? Well, system crash. I
mean, we, we don't reference bad memory here. This is more, more of a hang. So,
it's going to freeze. So this is actually pretty common in the old, for instance, if
you look at like non-preemptive operating systems. So, back in the day of like the
original Mac OS before Mac OS became Mac OSX, so versions sort of nine and earlier.
That was a cooperative operating system. And if someone went and grabbed a lock,
and then died or took an error case, the whole machine would crash, crash. if
you're pre-emptive, I mean, there's like a timer going off, it's possible you still
you won't be able to make forward progress. But at least, the OS can
interrupt your process and try and do something about it. It can detect that one
process is hung. But in a cooperativ e multi-threading environment, if one
process, let's say, just hogs the processor and never gives back the
processor or just dies, and you have some other process, which say, which, or, or,
let's say, you, you grab the lock and one process and die. And then, another process
is running along and tries to acquire the lock, but it's just sitting there spinning
in this little spin section here for forever. You're basically just going to
hang the processor. You're not going to see anything else here. So, you've got to
be pretty careful especially in cooperative multi-threading environments.
So, one of the tricks to this actually is, if you're in a cooperative multi-threaded
environment, they'll typically put inside the spin loop here something which will
yield to a different thread. So, someone else can try to do something in that time.
Cuz if you just sit there spinning, it's very possible that you won't be fair or no
one else can ever go to unlock the lock, for instance. So, you've got to be a
little careful there. Okay. So, we're going to move forward here. And look at
how to do a slightly different version of the same piece of code, but now with
compare and swap. So, before we do that, let's talk about the, the semantics of
compare and swap. Compare and swap takes memory and two registers here. And it's
going to compare memory with one of the registers. If it's equal, then its going
to take the other register, put it in memory, and effectively swap them in
return of status. If the compare operation fails, and we come to this L station
statement here, we don't do any swap. So this would be effectively taking a
register and a memory location and swapping them, dependent on another
register. So, it's a little bit more powerful than just swap. It's a little
harder to implement, as you might imagine. it's probably not as hard to implement as
something like fetch and app. The reason for this is, if you want to do this
operation out of the memory system, you can basically send it as atomic sort of
operation. Go to main memory, compare this, put a comparitor there and swap the
two things. If you try to have these sort of increments or arbitrary instructions or
adds, you need to put a adder out there for sure. This only needs a comparator out
there. Still, still, still painful to go implement. But, it might a little bit
better than putting a full adder in your memory controller cuz that's almost like
duplicating your ALU out in your memory sub-system which doesn't make a whole lot
of sense. But, that's, that's why people used to talk about the fetching FFT. But,
okay. So, let's take a look at the same piece of the same case here of a
multi-reader piece of code. But instead, what we're going to do is we're not going
to have a spin lock at the beginning. Instead, we're going to have a critical
section, but we can concurrently execute critical sections from different threads
here which we're not going to call it a critical section then. We're going to say,
we'll concurrently execute what was in the other thread's critical section, and then
we're going to atomically try to swap out the head pointer and replace it. So, we're
inspectively doing speculative work here, and this is called non-blockive,
non-blocking synchronization. So, the synchronization primitive we're going to
do the loads, we talked about that before. We checked to make sure there's at least
something available. We'll pull the, the head pointer off. This is all speculative
work at this point cuz we have not check to make sure that we can validly pull off
the head of the queue. We're going to increment the head pointer into a
temporary here that we're going to call new head or registered new head. And then,
we're going to do a, try to swap the new head with the old head atomically. So,
it's going to take the register that we think is the new head and memory location
where the head pointer is. We're going to try to swap these two things. And the
thing that we're dependent on here is that what we think is the old head, still is
the old head. And if, if something bad hap pens here, we can, we can try again. so,
so the idea here is that we're going to spin actually in this effectively bigger
loop, trying to speculatively try to go and change the, the head. So, one, one
question that comes up here is, what if the head was DQ'd from, added back on to,
and, and it just so happens that we have some sort of, it's called an ABA problem?
The headpointer was a, was changed to be, and later changed back to a, all in, this
short period of time. Yeah. That, that might be a problem here in this piece of
code. You might need to think about that and carefully reason about that. Usually,
you can protect that in some other way sort of, when the, the pointer wraps
around, maybe. if you think about a normal ray, when it wraps around, you put
something which is not a compare and swap. You put like more spin lock, or a spin
loop sort of lock on it. So, you only have to worry about that in these sort of
circular buffers when something wraps around. Cuz otherwise, there's no, no
other way that the head pointer can go back to where it was before. But, you do
need to worry about that, that you wrapped all the way around the array in this very
short period of time. So, there's some, there's some race conditions that happen
if these non-blocking synchronizations operations. Another non-blocking
synchronization primitive that is actually really cool, I think, is, goes by lots of
different names. it goes by load locked, load linked, load reserve, and store
conditional. So, you take your ISA, you take your instruction set, and you add two
new instructions. Something which checks to make sure or something which doesn't
load, and what you then do is store conditional checks to make sure that no
one else did a load. Or a special load link to that same address in the
inter-meeting time. I can explain that one more time, it's a little confusing. But
the, basically the idea is a flag register here. And in hardware, you do a load link.
Just load the value into your register and its sort of on the side, somewhere n ext
to the register. It may not be architecturally visible, or shouldn't be
architecturally visible likely. It will set a bit. You execute your critical
section. And when you come back to it, to go do the store, we say, for this sort of
read modified write operations. When you go to the store, the store checks to make
sure the flag is still set to one. The flag is one. If it's still one, that means
no one did any memory, memory operations to that address or did at least any load
links or store initials to that address in the inter meeting time. Actually, sorry.
We'll say that in a more completely. No one else did a store conditional during
that time. So, no one else tried to do a store update. Other people may have tried
to do a load. But, no one else could of store at that address, or store
conditional at that address. Because if someone else did a store conditional,
what'll happen is that it'll actually cancel the other processor's reservation,
so set their flag bits to zero atomically. This is a pretty primitive, this is a
pretty powerful primitive here such that you can basically do a load. Try to do a
store later in the future. If no one else try to do a store to that same address in
the meantime, or a store conditional to that address in the meantime, your store
goes through and everybody else's loads. If they do a load in the meantime, will
get invalidated or they'll know that it gets invalidated when they go to do a
store conditional. So, if we take the same example here and we implement with load
link and store conditional, we're going to look at the headpointer here where we
normally do the update. And we're going to do a load into this register. And, when we
go into a store conditional, if we, someone else had changed this value in the
meantime, we're going to get a fail and we're going to jump back around and have
to redo the load link. And this actually gets rid of the ABA problem, also. Because
if you did have that sort of race, someone else would have done a store conditional
to that address, and the wrap around cases and all that stuff would actually, and it
would even validate your flag on that bit, if you will. We're flagging that memory
address. One of the reasons that people like this is, when you go to do load link
or load reserve in store conditional, you can, a lot of times sort of piggy back
this over a memory coherence protocol. Such that, you do a load link and it will
add an extra bit in your memory, we'll say. So, if you're doing some sort of
memory coherence protocol, it'll pull it in your cache and you can sort of tag this
little loop line as special, or that's the flag bit here effectively cuz this whole
line was load linked. And then, if no one else pushes it out of your cache or
fetches it from your cache in the meantime, so would mean no one else did a
load link on it. By the time you go to do the store, you know that no one did
anything. And what's really nice about this is there is no communication that has
to happen between the processors on the common case with an uncontained lock.
Versus the spin locks are, are generating memory traffic all the time. They are
saying, they're doing loads, doing stores and trying to like grab the lock, trying
to grab lock, trying to grab lock, trying to grab lock and they just generating all
this traffic all over the place versus this is very quiet. You just pull in your
local cash. And if by the time you get back to it, it was still in your cache and
it still has it's bitset. That's great. You get to do it. In the contendant case
though, you may actually get traffic ping ponging here, but you can still guarantee
correctness. So, this brings us to performance. As I said, some of these
blocking atomic operations can generate a lot of memory traffic. So, they'll say
they're spinning on memory and they'll at least be doing lots of loads. And those
lots of loads may be going out to main memory. Non-walking atomic operations, so
like these compare and swamp operations or load link store conditional. And the load
link store conditional, as I was alludin g to many times you can, you can do it
against your own cashe. also these, these things can have sometimes a better
performance because you don't have to sit there sort of spinning in type loops. You
can try to do stuff in, in the mean time. The down side to, at least the compare and
swamp implementation is you have to sort of speculative work in the meantime.
You're sitting there redoing some work and if you didn't get the lock, that
performance can be bad. There's also, as I alluded to at the beginning of class,
there are things that use ordinary loads and stores, or algorithms that do allow
blocking with just loads and stores. Their performance is, is not, not very good and
we're going to look at an example of that called Dekker's Algorithm today. Finally,
the performance of these isn't just dependent on the operations themselves.
So, of the, these primitives, harbor primitives, have better performance or
worse performance depending on how highly they are contended. So, what I mean by
contended is I mean you have multiple threads trying to acquire the lock at the
same time. If you have lots of people trying to fight for the lock, that's high
contention. If you have a lock which there's almost never contention on, you go
to just go to get the lock and you just get it, and it's there for a really rare
case. other locking primitives have better, better protocols there. And, of
course, we're going to talk about this in a little bit of how do you make these
integrate well with caches, out-of-order processors, and out-of-order memory