1
00:00:03,073 --> 00:00:07,061
In this video, we're gonna talk a little
bit about concurrency in programming

2
00:00:07,061 --> 00:00:16,001
languages and in particular, Java's use of
threads. Java has concurrency built in

3
00:00:16,001 --> 00:00:21,067
through threads and I'm not going to
explain, what a thread is from first

4
00:00:21,067 --> 00:00:25,048
principles, in this video. So I'm going to
assume a little bit of background but

5
00:00:25,048 --> 00:00:30,015
we'll say a few words here about what
threads are. So a thread is like its own

6
00:00:30,015 --> 00:00:35,006
program. It has its own program counter,
meaning, it has an instruction that it's

7
00:00:35,006 --> 00:00:39,013
executing and it has its own set of local
variables and activation records. And a

8
00:00:39,013 --> 00:00:44,071
Java program, or any program written in
any language with threads may have

9
00:00:44,071 --> 00:00:49,040
multiple threads at the same time. So,
abstractly, we can think of threads as

10
00:00:49,040 --> 00:00:54,024
being a series of exec, of, of statements
that are executed. Each, one of these

11
00:00:54,024 --> 00:00:59,031
threads again, has its own set of local
variables. But the threads may refer to

12
00:00:59,031 --> 00:01:03,096
common data in the heap. So they could
refer to the same heap data structures.

13
00:01:03,096 --> 00:01:09,022
And, each thread is executing a particular
instruction, so let's say that the threads

14
00:01:09,022 --> 00:01:15,030
are all, here we have three threads, one,
two, and three. And they're each at some

15
00:01:15,030 --> 00:01:22,051
instruction or some, statement in the
program. And then there is a scheduler and

16
00:01:22,051 --> 00:01:32,003
at each step of execution, the scheduler
will pick one thread to execute. And it'll

17
00:01:32,003 --> 00:01:37,759
execute one statement. And this is
conceptual. Meaning, this isn't exactly

18
00:01:37,759 --> 00:01:44,045
the way it's usually implemented. And then
it will repeat this loop. So it'll pick a

19
00:01:44,045 --> 00:01:47,056
thread, it'll execute one statement of
that thread and it'll just keep doing that

20
00:01:47,056 --> 00:01:50,082
over and over again. So we might for
example, the schedule might pick thread

21
00:01:50,082 --> 00:01:55,094
one and execute this first statement. And
then it might pick thread two and execute

22
00:01:55,094 --> 00:01:59,087
this statement, and then it might pick
thread three and execute that statement.

23
00:01:59,087 --> 00:02:03,015
And then it might decide well to execute
another statement of thread two, and then

24
00:02:03,015 --> 00:02:06,025
it might execute several statements of
thread one. And then it might come back

25
00:02:06,025 --> 00:02:10,010
and execute a couple statements of thread
three, and then thread two might get to go

26
00:02:10,010 --> 00:02:17,049
again for a while, and so on. All right,
so, the threads execute in some order. And

27
00:02:17,049 --> 00:02:22,060
it's non-deterministic at each step of
execution which thread will execute, how

28
00:02:22,060 --> 00:02:27,046
many of its instructions will be executed.
And, and thus the threads may inter-lead,

29
00:02:27,046 --> 00:02:32,271
the instructions in the threads may
inter-lead in a relatively or, in fact,

30
00:02:32,271 --> 00:02:37,932
completely arbitrary order. Alright? Now,
coming back to how this is done in Java,

31
00:02:37,932 --> 00:02:42,100
thread objects in Java all have class
threads. So there's a special class that

32
00:02:42,100 --> 00:02:46,282
you have to inherit from in order to be a
thread. And what you get, when you inherit

33
00:02:46,282 --> 00:02:52,144
from the thread class is, you will have
start and stop methods for beginning and

34
00:02:52,144 --> 00:02:56,692
ending the thread. Alright? And there's
some other special properties of threads.

35
00:02:56,692 --> 00:03:05,384
And in particular, one thing that threads
can do is to synchronize on objects. So,

36
00:03:05,384 --> 00:03:10,651
a, a, a thread can, acquire a lock on an
object through the synchronized construct.

37
00:03:10,651 --> 00:03:19,050
And so if I say synchronized xe in Java,
what that means is, that the program will

38
00:03:19,050 --> 00:03:26,068
acquire a lock on x before it executes e.
So the procedure here will be to lock x,

39
00:03:26,068 --> 00:03:34,972
then evaluate e, and then unlock x,
alright? So it's a structured

40
00:03:34,972 --> 00:03:41,199
synchronization construct. And within,
while it is executing the expression e, it

41
00:03:41,199 --> 00:03:47,795
will hold a lock on x. And this is the
primary way, really almost the only way in

42
00:03:47,795 --> 00:03:53,112
Java, to get synchronization between,
multiple threads. So this is how we, one

43
00:03:53,112 --> 00:03:58,501
can control the set of interleavings
because while one thread is executing,

44
00:03:58,501 --> 00:04:04,145
this particular block of code, no other
thread can execute this block of code and

45
00:04:04,145 --> 00:04:08,946
also hold a lock on the same object x. Now
could, two threads could execute this same

46
00:04:08,946 --> 00:04:12,847
syntactic construct if they were locking,
if, if their local variables actually

47
00:04:12,847 --> 00:04:16,686
referred to different objects. But they're
guaranteed not to interfere with each

48
00:04:16,686 --> 00:04:22,037
other, not to interweave, if they tried to
lock the same object x, alright? Now

49
00:04:22,037 --> 00:04:27,503
there's one shorthand in Java which is
used more commonly than this form, the

50
00:04:27,503 --> 00:04:31,432
synchronized construct. And as the
synchronization can be put on methods. We

51
00:04:31,432 --> 00:04:40,438
can say, synchronized f, where this is a
method definition. Alright? An d what this

52
00:04:40,438 --> 00:04:45,159
means is that, when this method is called,
that this object will be locked. So here,

53
00:04:45,159 --> 00:04:49,015
the object that's going to be locked is
implicit. And when synchronized is

54
00:04:49,015 --> 00:04:53,834
attached to a method name, or a method
declaration, that always means that this

55
00:04:53,834 --> 00:04:59,711
parameter will be the synchronized or
locked object. Let's take a look at the

56
00:04:59,711 --> 00:05:03,447
simple example and think about what
happens if we have two methods, one of

57
00:05:03,447 --> 00:05:07,968
which calls the method two of the class
simple and one of which calls the method

58
00:05:07,968 --> 00:05:14,389
fro. So let's take a look at that, let's
say we have thread one and thread two. And

59
00:05:14,389 --> 00:05:20,636
now, thread one is going to invoke the
method two and thread two is going to

60
00:05:20,636 --> 00:05:25,788
invoke the method fro. All right? So one
possibility here, let's say that, that two

61
00:05:25,788 --> 00:05:31,873
gets to run all the way to completion
before fro executes anything. So then

62
00:05:31,873 --> 00:05:39,391
we'll have a = three and b = four, okay?
And then fro will run and it will print

63
00:05:39,391 --> 00:05:47,413
out the string a = three, b = four. Okay?
So that's a relatively simple straight

64
00:05:47,413 --> 00:05:55,271
forward case. You know another possibility
is that thread two gets to run before

65
00:05:55,271 --> 00:05:59,402
thread one ever does anything. So thread
two executes all of it's instructions

66
00:05:59,402 --> 00:06:04,661
before thread one executes anything at
all. In which case what will be printed.

67
00:06:04,661 --> 00:06:14,147
Well, the fro will print out a = one, b =
two, alright? And two will then run, and

68
00:06:14,147 --> 00:06:20,797
it will set after this executes. So, after
this, after fro finishes executing, it

69
00:06:20,797 --> 00:06:25,060
will then set a = three and b = four.
That's another possibility and both of

70
00:06:25,060 --> 00:06:29,236
those are fine, alright? But then there
are some other odd possibilities, and

71
00:06:29,236 --> 00:06:34,376
let's take a look at one of those. What
happens if the thread is actually enter

72
00:06:34,376 --> 00:06:38,845
leave in a non-trivial way. So let's
consider the following possibilities.

73
00:06:38,845 --> 00:06:44,805
Let's say that two executes these
assignment, a = three. And now fro

74
00:06:44,805 --> 00:06:54,448
executes the first part of the print. So,
it does the read of a and starts building

75
00:06:54,448 --> 00:07:00,491
up this output string, okay? So, it's
going to print out here, a = three,

76
00:07:00,493 --> 00:07:08,437
alright? And then, now lets say that fro
actually goes ahead and gets to run some

77
00:07:08,437 --> 00:07:13,322
more and also goes ahead and prints out
the rest of this. Okay? So, actually does

78
00:07:13,322 --> 00:07:20,208
the second read of b so the n it will
print b = two. All right? And then one

79
00:07:20,209 --> 00:07:28,442
will run, the rest of the way through,
excuse me, b = four. And so here we got an

80
00:07:28,442 --> 00:07:34,105
output that doesn't seem quite right. Here
we got, we were able to see an

81
00:07:34,105 --> 00:07:40,811
intermediate state where thread one had
only executed partially. And so, what came

82
00:07:40,811 --> 00:07:47,985
out over here, in fro show you know, just
a partial update of the variables a and b.

83
00:07:47,985 --> 00:07:52,529
So one had been written but not the other.
And if we didn't want to do that, if we

84
00:07:52,529 --> 00:07:56,576
thought this was wrong, we would have to
use synchronization in order to control

85
00:07:56,576 --> 00:08:01,569
that. So, let's take a look then at using
synchronization to try to prevent this

86
00:08:01,569 --> 00:08:06,643
from happening. And I'll tell you right
upfront that this piece of code or this

87
00:08:06,643 --> 00:08:11,479
attempt is incorrect and actually it
doesn't solve the problem at all. But it

88
00:08:11,479 --> 00:08:16,014
also illustrates probably the most common
thread programming error that Java

89
00:08:16,014 --> 00:08:20,044
programmers make. And lots of people,
including professional programmers make

90
00:08:20,044 --> 00:08:25,604
this mistake and lots of production Java
programs have this particular mistake in

91
00:08:25,604 --> 00:08:31,017
them. So it's a very instructive example,
I think. So let's take a look here. Let's

92
00:08:31,017 --> 00:08:35,766
assume we have the, the two threads again.
The thread is going to call two and the

93
00:08:35,766 --> 00:08:41,333
thread is going to call fro. And let's say
that, in our heap, there is only one

94
00:08:41,333 --> 00:08:47,175
object simple, and let's just call it s.
So this is globally, in the entire heap

95
00:08:47,175 --> 00:08:53,122
just one object, s, of the simple class.
Alright? So what is, let's say that thread

96
00:08:53,122 --> 00:08:58,494
one is going to go first, alright, and the
first that it's going to do, because it's,

97
00:08:58,494 --> 00:09:03,439
synchronized method, is it's going to lock
the this parameter of the call since

98
00:09:03,439 --> 00:09:08,185
there's only one simple, only one, object
of the simple class that has to be the

99
00:09:08,185 --> 00:09:11,860
object s, so it's going to lock s.
Alright, now we'll prevent any other

100
00:09:11,860 --> 00:09:17,088
thread from acquiring the lock on s while,
while thread one holds that lock. So then,

101
00:09:17,088 --> 00:09:22,433
thread one can go ahead and execute the
statement a = three. And now though, we

102
00:09:22,433 --> 00:09:28,219
could have interruption and thread two can
get to run. And notice here that thread

103
00:09:28,219 --> 00:09:33,575
two doesn't check the lock. It goes ahead
execute this code over here. In the f ro

104
00:09:33,575 --> 00:09:38,795
method but that's not synchronized, there
is no synchronize keyword there. And so

105
00:09:38,795 --> 00:09:44,609
just the fact that somebody else holds the
lock on a simple object doesn't prevent

106
00:09:44,609 --> 00:09:50,863
another method from accessing the fields
or the data of that object if that other

107
00:09:50,863 --> 00:09:57,008
method doesn't itself check the lock. So
if the other method is not synchronized,

108
00:09:57,008 --> 00:10:02,533
it will just go ahead and, and, and, and
execute ignoring the fact that another

109
00:10:02,533 --> 00:10:08,167
thread holds the lock on the object. So,
in this case, this will just, this can

110
00:10:08,167 --> 00:10:14,307
just run to completion. And we'll print
out, a = three, b = two. Okay? So we only

111
00:10:14,307 --> 00:10:24,039
see one of the two updates. And, and then
the scheduler can come back in. Let's the

112
00:10:24,039 --> 00:10:31,058
other thread run and it would run to
completion and unlock the object at the

113
00:10:31,058 --> 00:10:36,004
end. And you could see here that this
particular attempted fix has achieved

114
00:10:36,004 --> 00:10:41,661
nothing. Actually all the possible inter
leavings of the two methods that were,

115
00:10:41,661 --> 00:10:45,895
that existed without any synchronization
still exist if only one of the two methods

116
00:10:45,895 --> 00:10:51,080
is synchronized. And the reason this error
is common is because frequently people

117
00:10:51,080 --> 00:10:57,036
think well, I, you know if reads are okay
I can always read from things in parallel

118
00:10:57,036 --> 00:11:02,042
and that won't cause any problems because
I'm not altering any data. It's my writes

119
00:11:02,042 --> 00:11:07,029
that have to be synchronized, so if I'm
going to write to fields of objects well

120
00:11:07,029 --> 00:11:11,033
that needs to be coordinated with other
methods because writes are dangerous but

121
00:11:11,033 --> 00:11:16,001
reads somehow don't interfere. And the
point here is that if, having only one

122
00:11:16,001 --> 00:11:22,028
method, or only having one half of the
accesses to the, of two accesses to shared

123
00:11:22,028 --> 00:11:28,052
data be synchronized doesn't help because
synchronization only works if everybody is

124
00:11:28,052 --> 00:11:34,354
checking the lock. So both the reader and
the writer need to check the lock in order

125
00:11:34,354 --> 00:11:37,097
to restrict the set of possible
interleavings of these two methods. So,

126
00:11:37,097 --> 00:11:42,043
what would be a correct way to do it?
Well, is just to put the synchronized

127
00:11:42,043 --> 00:11:47,025
keyword on both methods. And now. It's not
possible to have the interleaving we saw

128
00:11:47,025 --> 00:11:52,075
before it's not just only two possible
outputs. One, there are only two possible

129
00:11:52,075 --> 00:11:58,983
strings that could be p rinted. One is
that a = one and b = two. So, in this

130
00:11:58,983 --> 00:12:05,461
case, the fro method executes before the
two method, so that's fro before two,

131
00:12:05,461 --> 00:12:13,030
okay? I mean, all of fro before all of the
two method. And the other possibility is a

132
00:12:13,030 --> 00:12:21,385
= three, b = four, alright? And that would
be the two method executing in its

133
00:12:21,385 --> 00:12:26,640
entirety before the fro method. And those
become the only two possible

134
00:12:26,640 --> 00:12:32,358
inter-leavings when both methods here are
synchronized. I'm going to conclude this

135
00:12:32,358 --> 00:12:37,785
video by making a couple of other comments
on Java's threads. So, one property we

136
00:12:37,785 --> 00:12:42,610
would like, is that even if there is no
synchronization, a variable should only

137
00:12:42,610 --> 00:12:46,870
hold values that were actually written by
some threads. So, what do I mean by that?

138
00:12:46,870 --> 00:12:51,671
Let's say that we have two assignments.
This is in thread one, where we're

139
00:12:51,671 --> 00:12:59,046
assigning a the value of 3.14, then in
thread two, we're assigning a the value

140
00:12:59,046 --> 00:13:03,003
2.78. And so after these assignments are
done, after they've executed in some

141
00:13:03,003 --> 00:13:09,095
order, what do we expect? Well, we expect
that a ends up being equal either to 3.14

142
00:13:09,095 --> 00:13:16,014
or 2.78, alright? Now what we don't want
is for a to wind up being some other

143
00:13:16,014 --> 00:13:21,867
value, okay? I mean what if a turned out
to be 3.78 for example, okay? This would

144
00:13:21,867 --> 00:13:29,096
be bad, we don't want this, right? Because
this value, 3.78, was never written by

145
00:13:29,096 --> 00:13:35,739
either thread. Okay, this value was
somehow manufactured. And I've chose 3.78,

146
00:13:35,739 --> 00:13:39,856
to kind of indicate what could potentially
go wrong. If we somehow wound up with a

147
00:13:39,856 --> 00:13:45,070
mix of the bits or the, the pieces of the
number from thread one and thread two. If

148
00:13:45,070 --> 00:13:50,078
they were re-combined in some strange way,
then we could create a number, that was

149
00:13:50,078 --> 00:13:55,088
assigned to a that didn't exist in either
thread. Okay, it was never actually

150
00:13:55,088 --> 00:14:01,021
written in either thread. Now, Java does
guarantee that the rights of values are

151
00:14:01,021 --> 00:14:05,081
atomic. Meaning that if I write to a
value, if I sign a primitive type to

152
00:14:05,081 --> 00:14:08,091
something, that is going to happen
atomically and won't be interfered with by

153
00:14:08,091 --> 00:14:14,001
another assignment to the same memory
location except for floating point

154
00:14:14,001 --> 00:14:20,046
doubles. So this does not hold writes to
doubles or not necessarily atomic. Now,

155
00:14:20,046 --> 00:14:25,025
why would that be? Well, a double is a
floating point number, but it consumes

156
00:14:25,025 --> 00:14:30,044
twice the memory. That's why it's called a
double, it consumes two words. Okay, and

157
00:14:30,044 --> 00:14:35,098
what that means is that if a here is a
double, so let's assume that a is a

158
00:14:35,098 --> 00:14:40,098
double. That means that this write of 3.14
actually translates into two machine

159
00:14:40,098 --> 00:14:48,031
instructions. We have to write the high
part of a equals something and then the

160
00:14:48,031 --> 00:14:53,024
lower part of a. So, the two machine
instructions to write both of the words

161
00:14:53,024 --> 00:14:57,098
that represent a after writing the high
half and the low half. Okay because there

162
00:14:57,098 --> 00:15:03,044
isn't a, a primitive double word write on
most machines. And the same thing would

163
00:15:03,044 --> 00:15:07,037
happen in thread two. This would get
broken up into two assignments to the two

164
00:15:07,037 --> 00:15:10,063
halves of a. And then, just from what we
discussed before, you can see that these

165
00:15:10,063 --> 00:15:15,050
could interleave in some way and you might
wind up with the unfortunate situation

166
00:15:15,050 --> 00:15:21,013
that the high half of the representation
of a is written by thread one, and the low

167
00:15:21,013 --> 00:15:25,252
half is written by thread two, and then
you can get a number like this, like you

168
00:15:25,252 --> 00:15:30,769
know, something not exactly 3.78, but some
mix of the bits from the write in thread

169
00:15:30,769 --> 00:15:38,968
one and the write at thread two, and you
would create what's called an out of thin

170
00:15:38,968 --> 00:15:44,860
air value. Okay, and clearly out of thin
air values are bad. Okay, you do not want

171
00:15:44,860 --> 00:15:48,740
those. And, and Java guarantees, again,
that the rights of almost all the

172
00:15:48,740 --> 00:15:52,691
primitive data types are going to be
atomic so you can't get out of thin air

173
00:15:52,691 --> 00:15:57,809
values. But for performance reasons, this
is not the case for doubles. All right.

174
00:15:57,809 --> 00:16:02,678
So, so, so, for fro as a, what it says in
the manual is that as a concession, the

175
00:16:02,678 --> 00:16:09,472
current hardware, they do not require that
rights to doubles be atomic unless you the

176
00:16:09,472 --> 00:16:14,526
programmer go and mark the type as
volatile. So you have to declare doubles

177
00:16:14,526 --> 00:16:19,658
to be volatile, and if you do that, then
they're guaranteed to be atomic writes.

178
00:16:19,658 --> 00:16:24,267
Okay, so if you were writing Java programs
using Java threads, and you were

179
00:16:24,267 --> 00:16:29,737
programming threads that read and write
doubles concurrently, then you need to be

180
00:16:29,737 --> 00:16:34,327
careful to declare those double types
volatil e, at least currently, and this

181
00:16:34,327 --> 00:16:38,368
may change in the future, and I'm sure
they'd like to change it. But currently

182
00:16:38,368 --> 00:16:43,485
you have to declare the doubles volatile
to guarantee that the writes will be

183
00:16:43,485 --> 00:16:48,117
atomic. More generally, or actually
somewhat separately, this is actually a

184
00:16:48,117 --> 00:16:52,516
separate point here, Java concurrency
semantics are actually kind of hard to

185
00:16:52,516 --> 00:16:57,806
understand in detail. And this, this issue
around, out of thin air values, is, is one

186
00:16:57,806 --> 00:17:03,701
aspect of this. There are several other
aspects, of it. And, and, and this is

187
00:17:03,701 --> 00:17:09,479
really not Java's fault. It turns out the
concurrency semantics are hard and

188
00:17:09,479 --> 00:17:14,058
actually, this is kind of at the frontier
of research. We don't really understand

189
00:17:14,058 --> 00:17:20,319
exactly what we want or what the right
thing is to do, to specify the behavior of

190
00:17:20,319 --> 00:17:25,653
languages, in concurrent settings. And,
that's not to say that we don't understand

191
00:17:25,653 --> 00:17:29,695
anything. We do have some languages in
perfectly, concurrency semantics but in a

192
00:17:29,695 --> 00:17:35,345
language, flow in language, feature is
Java, there are a number of things that

193
00:17:35,345 --> 00:17:40,255
are not completely clear how they should
be implemented on certain machines. So

194
00:17:40,255 --> 00:17:44,892
this has been a huge amount of work done
on this problems specifically for Java and

195
00:17:44,892 --> 00:17:49,918
actually java was the first mainstream
language to have first class threads in it

196
00:17:49,918 --> 00:17:54,582
and then try to integrate that with all
other language features that all other

197
00:17:54,582 --> 00:17:58,932
modern languages features that we like. It
was so surprising actually that we have

198
00:17:58,932 --> 00:18:03,919
run into some trouble understanding how
they are supposed to work in all

199
00:18:03,919 --> 00:18:09,453
situations. So this is one area of Java
that I would say still under debate. And

200
00:18:09,453 --> 00:18:12,084
while for them, while I figure out
straight forward things with threads

201
00:18:12,084 --> 00:18:17,405
everything will work fine. If you are
doing, there are some areas of the

202
00:18:17,405 --> 00:18:22,598
language where if you try to use them with
threads, you can get into a little bit of

203
00:18:22,598 --> 00:18:27,572
trouble. Alright, so it surely pays to try
to understand. Java concurrency and the

204
00:18:27,572 --> 00:18:36,012
threads if you're writing significant
concurrency Java programs