Okay. So now, we're going to talk about
how to implement mutual exclusion without
atomic operations. So, I shall ask here,
how many people here have seen mutual
exclusion without atomic operations
before? Okay, few. People probably taken
an operating systems class might have seen
this before. but it's all tricky and good
to refresh anyway. so we're going to throw
out test in site, we're going to throw out
other things. We're going to look how you
have locks and mutual exclusion without
any ordering or without having special
instructions added to our instruction set.
So, let's, let's take a look at a basic
piece of code here that is wrapping around
a critical section, trying to implement a
p and a v. And we're going to, we're going
to look at the case where we only have two
threads. The n, the n threaded case gets a
lot more complicated. So, in this simple
case here, an easy way to go about doing
this is, or, or one way to think about
doing this is process one sets its
variable here to one. Then, it checks to
see if the other process, process has
written it's lock variable. And these are
two different variables, c1 and c2. And
we're assuming sequential consen,
consistency for this. If it sees that the
other process wrote that value to two, or
to one, c2 to one, it says, oh, process
two already won here. It's going to go
execute its critical section. So, it will
sit here and loop until c2 is set to zero
at the end of the critical section. Okay,
any one see any problems here? Yeah. So,
if they both set their variables to one,
so if we interleave this instruction and
this instruction, and then both do the
checks, c1 and c2 are both going to be
equal to one. They're both going to check
if, and they're going to say, okay. Yeah,
c2 is equal to one, c1 is equal to one.
It's been forever. None of them will ever
get to the release of the sum before, and
all of the sudden you have deadlock.
that's not great. So, this is why this
stuff is really hard to do. So, let's look
at our second attempt here. let's try to,
to make th at better by adding a little
more checking in here. So, same thing. c1
is equal to one, c2 is equal to one. It
does the same checks to see if the other
person, the other thread set the, the
variable. And if it doesn't win, it clears
its own. So, it sets c1 back to zero for,
if it fails, and moves back up here. This
looks, looks a lot better. Yeah. We're not
getting any deadlocks here, I don't think.
Cuz, let's say we're trying to interleave
these things, c1 sets to one, c2 sets to
one, they both do the check at the same
time. They both say, oh, the other person
grabbed it, I'll release my variable, set
it to zero, and loop back around. So, we
don't deadlock here. And if you perturb
the system a little bit, at some point,
one of them's going to fall through we'll
say. But what happens if the system's not
perturbed? Well, you can actually hit
livelock here. Because they can just sit
there and in lock step if you interleave
these three instructions with these three
instructions here they're going to just
keep going through the loops, clearing the
variables, setting the variables, clearing
the variables, setting the variables,
testing. And none of them, neither of
these two processes are ever going to fall
into the critical section. So, livelock
here is just as bad as deadlock, in this
case. And, another bad thing here is, we
have no guarantees of fairness. So, you
could actually have a case where one
process grabs this lock, we'll say. The
other one sits here's in, in loops and
it's able to execute its critical section,
clear c1, get back around set c1 before
process two is actually able to go around
this loop. then you're going to say
processors probably not running at
different speeds. Well, that's true but
maybe this one has to take more cache
processes than this one or who knows, you
know, you don't have a strong guarantee.
You can't prove that one thread is not
going to starve. So, this is a fail. We
can't, we can't have mutual exclusion this
way. So instead, we go and we say well,
let's make it more complica ted and this
came up, was made by Decker, and is
largely called Decker's Algorithm. And
this is actually a protocol from mutual
exclusion which works. We're just using
those in stores. And we're introducing
another variable here, and this is a
shared variable between process one and
process two and we call this the turn
variable. So, this looks pretty similar to
what we had in the previous slide. But
now, the turn variable is shared between
the two. And what this is really going to
act as is this is going to act as a
tiebreaker in the case where they both set
c1 effectively at the same time. And the
tiebreaker is interesting here because,
actually it's those two things, it's
tiebreaker and we'll see how it, it's able
to solve some problems around starvation.
But the turn variable, one of the two
threads here, because its a shared
variable, and were sequentially
consistent, is going to execute last,
we'll say. Either through the left side or
the right side. so, when you come down to
here and do this check, whoever raced and
actually set that turn variable last, the
other thread is going to execute. So,
let's say, process two, if we interleave
these and these, process two now sets
process two turns equal two happen last.
And when this goes to execute here, we'll
see that c1 is set and turn is equal to
two. So, we're just going to sit here and
spin. The other thread is going to see
turn equal to two, and c2 is set. But we
have a logical end here, so both of these
are not going to be true. So, it's going
to fall through and execute its critical
section at this point. At the end, c1 is
going to get cleared. And what happens
here is, that's going to allow this other
process to enter into its critical
section. So, why is this nice from a
starvation perspective is, at least for
two processes, it's going to allow you to
alternate here. Because one of them is
going to enter in, and when the other one
goes to clear this variable, you're
guaranteed that the other one can go
execute that point. So, you're not going
to have starvation. Now, the reason you
don't get starvation is actually kind of
subtle. Okay. So, let's look at the
starvation case. So, let's say possible
it's really fast. They just loop around
and they came, get around this loop and
come to this point before process two can
basically loop around here once. That's,
is that the case you want to look at?
Yeah. So, what's going to happen at that
point is. Well, two, two things are going
to happen. When c1 gets up to zero, what's
going to happen here is, process two will
actually see c1 zero is, is what we're
saying here. This is going to set to zero,
and then it's going to set to one, before
this track can happen. But, what is
interesting here is that at some point,
but c2 is still set to one. Cuz this, this
one sitting here waiting. Okay. So, tc2
set to one, and turn gets set to one.
That's going to block process two from
entering, at this point. Or rather this
being one and that being one is going to
block it from executing. And when turn
gets set to one, or, or rather, let's,
let's hold off and look at this. That's
going to allow this process one, and its
going to force this process one to sit
here and spin forever. And its not going
to be able to race around this second
time. Process two on the other hand, c's
going to be set to one. Now, in the mean
time, c was one and then it was zeroc and
then it was one again. But, turn is no
longer equal to two, at this point. Which
is going to allow process two to fall
through, and act as it's critical section.
So, it's the shared turn variable here,
which actually allows us to garauntee if
you have a contended case such that,
you're basically going to have a round
robin between the two. Okay. So, I think
we went through that. [LAUGH] I wanted to
finish all today, talking about one, one
last idea here in the last two minutes.
you can, to do Decker's actually with end
processes more than two gets pretty
tricky. Dijkstra shows a proof of that
there's something that's simpler to reason
about called the Leslie Lamport's Bakery
Alg orithm.
And the bakery, I thought is kind of
interesting because the idea is, have you
ever gone into a bakery or gone into a
deli, there's the little tickets. And you
go in, you take a ticket, and then you
wait for them to either call your number
or the little number on the screen to tick
up one. And then, once it ticks up, you go
and you like get your bread or get your
sliced cheese, or something. Well, it
could use, which is loads and stores. You
don't need locks to go implement something
like that. and I don't want to go into
complete detail here, but the, the,
basically the idea here is you set a you
set that you want to, you want to take the
lock. And then, what you do is you check
if all of the people below you are waiting
in the lock, also, in, in order. So, its
kind of like you're, you're checking to
see if the number has incremented up to
you at this point. And if everyone below
you is, if there is no one below you is
waiting for a lock, then your number came
up and you can go execute. When someone
is, you, you can't, you can't go execute
this and you, you wait for the, everyone
else to release their, their receptive
variables to one effectively, until the
point that it's yours and then you can go
and buy your bread or order your, you
cheese. Now, that's not enough to actually
work. there are things called ticket
taking locks which is actually a more
general class of this sort of idea here.
But, you also need a sort of second matrix
here to prevent sort of AVA problems or
things running around. But, I don't want
to go into full detail about that. I just
wanted to give you an idea that one way to
go implement sort of fast locks is, or
ticket taking locks. You walk in and take
a ticket. This prevents multiple people
from hoarding up to the front of the
bakery and all trying to order at exactly
the same time. and in the bakery, it's a
little bit easier because on the wall,
there's like a number and someone tick the
number each up time. If you don't have a
central arbiter to go tick the number up,
you ne ed to somehow make the last person
who had to lock increase the number. And
that's what this algorithm's actually
doing. Okay. Let's stop here for today.
next time we are going to talk about
symmetric multiprocessor. We're running a
little bit behind where we were supposed
to be from the syllabus perceptive. We're
about a half a class behind. But, I think
we'll be able to pick up most of that.