In this video, we're gonna talk a little
bit about concurrency in programming
languages and in particular, Java's use of
threads. Java has concurrency built in
through threads and I'm not going to
explain, what a thread is from first
principles, in this video. So I'm going to
assume a little bit of background but
we'll say a few words here about what
threads are. So a thread is like its own
program. It has its own program counter,
meaning, it has an instruction that it's
executing and it has its own set of local
variables and activation records. And a
Java program, or any program written in
any language with threads may have
multiple threads at the same time. So,
abstractly, we can think of threads as
being a series of exec, of, of statements
that are executed. Each, one of these
threads again, has its own set of local
variables. But the threads may refer to
common data in the heap. So they could
refer to the same heap data structures.
And, each thread is executing a particular
instruction, so let's say that the threads
are all, here we have three threads, one,
two, and three. And they're each at some
instruction or some, statement in the
program. And then there is a scheduler and
at each step of execution, the scheduler
will pick one thread to execute. And it'll
execute one statement. And this is
conceptual. Meaning, this isn't exactly
the way it's usually implemented. And then
it will repeat this loop. So it'll pick a
thread, it'll execute one statement of
that thread and it'll just keep doing that
over and over again. So we might for
example, the schedule might pick thread
one and execute this first statement. And
then it might pick thread two and execute
this statement, and then it might pick
thread three and execute that statement.
And then it might decide well to execute
another statement of thread two, and then
it might execute several statements of
thread one. And then it might come back
and execute a couple statements of thread
three, and then thread two might get to go
again for a while, and so on. All right,
so, the threads execute in some order. And
it's non-deterministic at each step of
execution which thread will execute, how
many of its instructions will be executed.
And, and thus the threads may inter-lead,
the instructions in the threads may
inter-lead in a relatively or, in fact,
completely arbitrary order. Alright? Now,
coming back to how this is done in Java,
thread objects in Java all have class
threads. So there's a special class that
you have to inherit from in order to be a
thread. And what you get, when you inherit
from the thread class is, you will have
start and stop methods for beginning and
ending the thread. Alright? And there's
some other special properties of threads.
And in particular, one thing that threads
can do is to synchronize on objects. So,
a, a, a thread can, acquire a lock on an
object through the synchronized construct.
And so if I say synchronized xe in Java,
what that means is, that the program will
acquire a lock on x before it executes e.
So the procedure here will be to lock x,
then evaluate e, and then unlock x,
alright? So it's a structured
synchronization construct. And within,
while it is executing the expression e, it
will hold a lock on x. And this is the
primary way, really almost the only way in
Java, to get synchronization between,
multiple threads. So this is how we, one
can control the set of interleavings
because while one thread is executing,
this particular block of code, no other
thread can execute this block of code and
also hold a lock on the same object x. Now
could, two threads could execute this same
syntactic construct if they were locking,
if, if their local variables actually
referred to different objects. But they're
guaranteed not to interfere with each
other, not to interweave, if they tried to
lock the same object x, alright? Now
there's one shorthand in Java which is
used more commonly than this form, the
synchronized construct. And as the
synchronization can be put on methods. We
can say, synchronized f, where this is a
method definition. Alright? An d what this
means is that, when this method is called,
that this object will be locked. So here,
the object that's going to be locked is
implicit. And when synchronized is
attached to a method name, or a method
declaration, that always means that this
parameter will be the synchronized or
locked object. Let's take a look at the
simple example and think about what
happens if we have two methods, one of
which calls the method two of the class
simple and one of which calls the method
fro. So let's take a look at that, let's
say we have thread one and thread two. And
now, thread one is going to invoke the
method two and thread two is going to
invoke the method fro. All right? So one
possibility here, let's say that, that two
gets to run all the way to completion
before fro executes anything. So then
we'll have a = three and b = four, okay?
And then fro will run and it will print
out the string a = three, b = four. Okay?
So that's a relatively simple straight
forward case. You know another possibility
is that thread two gets to run before
thread one ever does anything. So thread
two executes all of it's instructions
before thread one executes anything at
all. In which case what will be printed.
Well, the fro will print out a = one, b =
two, alright? And two will then run, and
it will set after this executes. So, after
this, after fro finishes executing, it
will then set a = three and b = four.
That's another possibility and both of
those are fine, alright? But then there
are some other odd possibilities, and
let's take a look at one of those. What
happens if the thread is actually enter
leave in a non-trivial way. So let's
consider the following possibilities.
Let's say that two executes these
assignment, a = three. And now fro
executes the first part of the print. So,
it does the read of a and starts building
up this output string, okay? So, it's
going to print out here, a = three,
alright? And then, now lets say that fro
actually goes ahead and gets to run some
more and also goes ahead and prints out
the rest of this. Okay? So, actually does
the second read of b so the n it will
print b = two. All right? And then one
will run, the rest of the way through,
excuse me, b = four. And so here we got an
output that doesn't seem quite right. Here
we got, we were able to see an
intermediate state where thread one had
only executed partially. And so, what came
out over here, in fro show you know, just
a partial update of the variables a and b.
So one had been written but not the other.
And if we didn't want to do that, if we
thought this was wrong, we would have to
use synchronization in order to control
that. So, let's take a look then at using
synchronization to try to prevent this
from happening. And I'll tell you right
upfront that this piece of code or this
attempt is incorrect and actually it
doesn't solve the problem at all. But it
also illustrates probably the most common
thread programming error that Java
programmers make. And lots of people,
including professional programmers make
this mistake and lots of production Java
programs have this particular mistake in
them. So it's a very instructive example,
I think. So let's take a look here. Let's
assume we have the, the two threads again.
The thread is going to call two and the
thread is going to call fro. And let's say
that, in our heap, there is only one
object simple, and let's just call it s.
So this is globally, in the entire heap
just one object, s, of the simple class.
Alright? So what is, let's say that thread
one is going to go first, alright, and the
first that it's going to do, because it's,
synchronized method, is it's going to lock
the this parameter of the call since
there's only one simple, only one, object
of the simple class that has to be the
object s, so it's going to lock s.
Alright, now we'll prevent any other
thread from acquiring the lock on s while,
while thread one holds that lock. So then,
thread one can go ahead and execute the
statement a = three. And now though, we
could have interruption and thread two can
get to run. And notice here that thread
two doesn't check the lock. It goes ahead
execute this code over here. In the f ro
method but that's not synchronized, there
is no synchronize keyword there. And so
just the fact that somebody else holds the
lock on a simple object doesn't prevent
another method from accessing the fields
or the data of that object if that other
method doesn't itself check the lock. So
if the other method is not synchronized,
it will just go ahead and, and, and, and
execute ignoring the fact that another
thread holds the lock on the object. So,
in this case, this will just, this can
just run to completion. And we'll print
out, a = three, b = two. Okay? So we only
see one of the two updates. And, and then
the scheduler can come back in. Let's the
other thread run and it would run to
completion and unlock the object at the
end. And you could see here that this
particular attempted fix has achieved
nothing. Actually all the possible inter
leavings of the two methods that were,
that existed without any synchronization
still exist if only one of the two methods
is synchronized. And the reason this error
is common is because frequently people
think well, I, you know if reads are okay
I can always read from things in parallel
and that won't cause any problems because
I'm not altering any data. It's my writes
that have to be synchronized, so if I'm
going to write to fields of objects well
that needs to be coordinated with other
methods because writes are dangerous but
reads somehow don't interfere. And the
point here is that if, having only one
method, or only having one half of the
accesses to the, of two accesses to shared
data be synchronized doesn't help because
synchronization only works if everybody is
checking the lock. So both the reader and
the writer need to check the lock in order
to restrict the set of possible
interleavings of these two methods. So,
what would be a correct way to do it?
Well, is just to put the synchronized
keyword on both methods. And now. It's not
possible to have the interleaving we saw
before it's not just only two possible
outputs. One, there are only two possible
strings that could be p rinted. One is
that a = one and b = two. So, in this
case, the fro method executes before the
two method, so that's fro before two,
okay? I mean, all of fro before all of the
two method. And the other possibility is a
= three, b = four, alright? And that would
be the two method executing in its
entirety before the fro method. And those
become the only two possible
inter-leavings when both methods here are
synchronized. I'm going to conclude this
video by making a couple of other comments
on Java's threads. So, one property we
would like, is that even if there is no
synchronization, a variable should only
hold values that were actually written by
some threads. So, what do I mean by that?
Let's say that we have two assignments.
This is in thread one, where we're
assigning a the value of 3.14, then in
thread two, we're assigning a the value
2.78. And so after these assignments are
done, after they've executed in some
order, what do we expect? Well, we expect
that a ends up being equal either to 3.14
or 2.78, alright? Now what we don't want
is for a to wind up being some other
value, okay? I mean what if a turned out
to be 3.78 for example, okay? This would
be bad, we don't want this, right? Because
this value, 3.78, was never written by
either thread. Okay, this value was
somehow manufactured. And I've chose 3.78,
to kind of indicate what could potentially
go wrong. If we somehow wound up with a
mix of the bits or the, the pieces of the
number from thread one and thread two. If
they were re-combined in some strange way,
then we could create a number, that was
assigned to a that didn't exist in either
thread. Okay, it was never actually
written in either thread. Now, Java does
guarantee that the rights of values are
atomic. Meaning that if I write to a
value, if I sign a primitive type to
something, that is going to happen
atomically and won't be interfered with by
another assignment to the same memory
location except for floating point
doubles. So this does not hold writes to
doubles or not necessarily atomic. Now,
why would that be? Well, a double is a
floating point number, but it consumes
twice the memory. That's why it's called a
double, it consumes two words. Okay, and
what that means is that if a here is a
double, so let's assume that a is a
double. That means that this write of 3.14
actually translates into two machine
instructions. We have to write the high
part of a equals something and then the
lower part of a. So, the two machine
instructions to write both of the words
that represent a after writing the high
half and the low half. Okay because there
isn't a, a primitive double word write on
most machines. And the same thing would
happen in thread two. This would get
broken up into two assignments to the two
halves of a. And then, just from what we
discussed before, you can see that these
could interleave in some way and you might
wind up with the unfortunate situation
that the high half of the representation
of a is written by thread one, and the low
half is written by thread two, and then
you can get a number like this, like you
know, something not exactly 3.78, but some
mix of the bits from the write in thread
one and the write at thread two, and you
would create what's called an out of thin
air value. Okay, and clearly out of thin
air values are bad. Okay, you do not want
those. And, and Java guarantees, again,
that the rights of almost all the
primitive data types are going to be
atomic so you can't get out of thin air
values. But for performance reasons, this
is not the case for doubles. All right.
So, so, so, for fro as a, what it says in
the manual is that as a concession, the
current hardware, they do not require that
rights to doubles be atomic unless you the
programmer go and mark the type as
volatile. So you have to declare doubles
to be volatile, and if you do that, then
they're guaranteed to be atomic writes.
Okay, so if you were writing Java programs
using Java threads, and you were
programming threads that read and write
doubles concurrently, then you need to be
careful to declare those double types
volatil e, at least currently, and this
may change in the future, and I'm sure
they'd like to change it. But currently
you have to declare the doubles volatile
to guarantee that the writes will be
atomic. More generally, or actually
somewhat separately, this is actually a
separate point here, Java concurrency
semantics are actually kind of hard to
understand in detail. And this, this issue
around, out of thin air values, is, is one
aspect of this. There are several other
aspects, of it. And, and, and this is
really not Java's fault. It turns out the
concurrency semantics are hard and
actually, this is kind of at the frontier
of research. We don't really understand
exactly what we want or what the right
thing is to do, to specify the behavior of
languages, in concurrent settings. And,
that's not to say that we don't understand
anything. We do have some languages in
perfectly, concurrency semantics but in a
language, flow in language, feature is
Java, there are a number of things that
are not completely clear how they should
be implemented on certain machines. So
this has been a huge amount of work done
on this problems specifically for Java and
actually java was the first mainstream
language to have first class threads in it
and then try to integrate that with all
other language features that all other
modern languages features that we like. It
was so surprising actually that we have
run into some trouble understanding how
they are supposed to work in all
situations. So this is one area of Java
that I would say still under debate. And
while for them, while I figure out
straight forward things with threads
everything will work fine. If you are
doing, there are some areas of the
language where if you try to use them with
threads, you can get into a little bit of
trouble. Alright, so it surely pays to try
to understand. Java concurrency and the
threads if you're writing significant
concurrency Java programs