NWEN303 Concurrent Programming
6 Java memory model
Marco Servetto VUW
●
Just Writing parallel programs is bad, but if there is no communication at all between running processes, we can rely on good libraries and our programs can become more verbose, but not exponentially more complicated. Life with non-communicating tasks is not simple, but is still a job that normal humans can hope to bring to completion.
Now we will go down in hell.
●
Communication between processes is bad
●
No wait… why do we have to go?
Short lived tasks usually can have a functional interface, take some input and produce an output
(input is either immutable or defensively cloned)
●
–
●
–
The only common reason to talk with a short living task is to kill it!
see Future.cancel(), is a near safe operation! Longer tasks may have more stuff to say/share
●
●
I have long living social tasks
I need them to talk with each others to coordinate their work!
I want to create a population of active workers, that interact with each others to share resources and to dynamically and cooperatively react to changes in the environment.
Thus, I have to go trough that door! Ok then, welcome to NWEN303
●
●
while(true){ print(a)
a4
b … c3● d …
Scenario:
First tread 1 starts
After a while, thread 2 starts
print(c) }
… …
●
a=a+c; c=c+1;
…
… … … …
Thread1
Global memory
Thread2
What is printed? a series of 4 and 3, followed by a series of 7 and 4, right?
while(true){ print(a)
a4
b … c3● d …
Scenario:
First tread 1 starts
After a while, thread 2 starts
print(c) }
… …
●
a=a+c; c=c+1;
…
… … … …
Thread1
Global memory
Thread2
What is printed? a series of 4 and 3, followed by a series of 7 and 4, right?
while(true){ print(a)
print(c) }
a4
b … c3● d …
… …
Scenario:
First tread 1 starts
After a while, thread 2 starts
a=a+c; c=c+1;
…
… … … …
Thread1
Cache 1
Global memory
Thread2
Cache 2
What is printed? a series of 4 and 3, followed by a series of 7 and 4, right?
●
while(true){ print(a)
print(c) }
a4
b … c3● d …
… …
Scenario:
First tread 1 starts
After a while, thread 2 starts
a=a+c; c=c+1;
… … …
Thread1
Cache 1
a4
c3 … …
Thread2
Cache 2
Global memory
… …
… …
… … … …
What is printed? a series of 4 and 3, followed by a series of 7 and 4, right?
●
while(true){ print(a)
print(c) }
a4
b … c3● d …
… …
Scenario:
First tread 1 starts
After a while, thread 2 starts
a=a+c; c=c+1;
a4 … … … … …
Thread1
Cache 1
a4
c3 … …
Thread2
Cache 2
Global memory
… …
… …
What is printed? a series of 4 and 3, followed by a series of 7 and 4, right?
●
while(true){ print(a)
print(c) }
a4
b … c3● d …
… …
Scenario:
First tread 1 starts
After a while, thread 2 starts
a=a+c; c=c+1;
a4 … c 3 … …
Thread1
Cache 1
a4
c3 … …
Thread2
Cache 2
Global memory
… …
… …
What is printed? a series of 4 and 3, followed by a series of 7 and 4, right?
●
while(true){ print(a)
print(c) }
●
a=a+c; c=c+1;
a7 … c 3 … …
Thread1
Cache 1
a4
c3 … …
Thread2
Cache 2
Global memory
… …
… …
What is printed? a series of 4 and 3, followed by a series of 7 and 4, right?
a
b c3● d …
… …
7 or 4 …
Scenario:
First tread 1 starts
After a while, thread 2 starts
while(true){ print(a)
print(c) }
●
a=a+c; c=c+1;
a7 … c 4 … …
Thread1
Cache 1
a4
c3 … …
Thread2
Cache 2
Global memory
… …
… …
What is printed? a series of 4 and 3. Forever,… you see? thread1 never refresh its cache… and we are unsure is tread2 ever commit its own…
a
b
c 4or3 ● d …
… …
7 or 4 …
Scenario:
First tread 1 starts
After a while, thread 2 starts
● ●
●
●
Cache issues? is this for real?
Yep, and is just the first of the issues we will meet…
Nearly every real machine suffers from these issues
Nearly every real programming language needs to take them into account.
Nearly every real programming language and library just delegates the burden on the programmer.
Solutions Java offers volatile keyword
private static volatile int mySharedState = 0;
You can just declare all the fields that are supposed to be seen by multiple threads volatile.
Volatile just ignores the cache and goes straight to the memory.
However it is slower that a normal variable.
– This is good, right? Since writing efficient programs is bad.
What if you want to understand when you can avoid volatile? well, then you have to understand the happens-before relation in the Java memory model.
http://docs.oracle.com/javase/specs/jls/se8/html/jls-17.html#jls-17.4
●
●
● ●
●
Volatile vs long/double
On 32 bit machines, writing on a 64 bit var is/was two operations.
From the Java specification:
17.7 Non-atomic Treatment of double and long […]
For the purposes of the Java programming language memory model, a single write to a non-volatile long or double value is treated as two separate writes: one to each 32-bit half. This can result in a situation where a thread sees the first 32 bits of a 64 bit value from one write, and the second 32 bits from another write. Writes and reads of volatile long and double values are always atomic. Writes to and reads of references are always atomic, regardless of whether they are implemented as 32 or 64 bit values.
●
●
● ●
●
Understand Atomic Operations
private static volatile int mySharedState = 0; ….
mySharedState = mySharedState +1;
Is this a safe operation?
Any operation can be interrupted, so if two thread was to execute that code “at the same time” we could lose some information.
Let’s consider the following code
Understand Atomic Operations
class SimpleThread2 extends Thread { private static volatile int v = 0;
public void run() {
SimpleThread2.v = SimpleThread2.v + 1; System.out.println(“v = ” + SimpleThread2.v);
}
public static void main(String args[]) {
Thread t1 = new SimpleThread2(); Thread t2 = new SimpleThread2(); Thread t3 = new SimpleThread2(); t1.start();
t2.start();
t3.start();
}
v =1 v =2 v =3
v= 1 v= 2 v= 2
v= 1 v= 1 v= 1
v= 1 v=1 v= 3 v=2 v= 2 v=1
v= 2 v= 2 v= 1 v= 2 v= 2 v= 1
v= 3 v= 2 v= 3 v= 3 v= 3 v= 3
class ST extends Thread{
private static volatile int v = 0;
public void run() { ST.v = ST.v + 1;
…println(“v=”+ST.v); }
public static void main(…) { Thread t1 = new ST(); Thread t2 = new ST(); Thread t3 = new ST(); t1.start();
t2.start();
t3.start();
}
Usual Bank account example
private volatile int myMoney = 0;
….
//at the same time a creditor is taking money out myMoney = myMoney -300;
…
//and a debitor is paying you
myMoney = myMoney +100;
● What is wrong here?
● From the multithreading perspective, depending on how the timeslices
work out, you may get more or less money in the end.
● But a reality check is the most important thing here: This is not how banks manage translations
● All the information is preserved and safely saved in a nice list, so you can get your total balance *recomputed* every time. Transparent to bug!
● They do not use int, long, float or double to store money. Never do it please, use BigInteger to get unlimited precision numbers.
●
●
Contention of resources
(1) We need to understand what chunks of data are accessed by multiple threads at the same time.
It is hard, very hard. Especially in case of complex reachable object graphs.
The worst thing is that sort of all of the resources/guides of correct multithreading programming sort of assumes that every one has a clear idea of what thread accedes what object and when.
It is a real problem. We are developing better programming languages to handle it, but they are still not ready for real world usage.
●
●
●
●
●
Contention of resources
(2) Just understanding that a certain chunk of data is accessed by multiple threads/workers is not enough. we need to distinguish between different access/contention patterns.
Many reads Zero writes — no problem here Many reads One write — volatile may be enough
Many reads Many writes — pure hell, more later Zero reads Many writes — volatile may be enough,
however it is a very rare case.
may
may
●
●
●
●
Example of Many reads one write
We have a game, there is a Dragon and a Hero, they have x and y coordinates.
They are the only ones that modify their position.
However, their position can be read by the other.
Let see it with a code example
public class LongLivingTasks {
public static final Dragon dragon=new Dragon(); public static final Hero hero=new Hero(); public static void main(String[]a){
hero.start(); dragon.start(); }
public double distance(int x1,int x2,int y1, int y2){ int d1=x1-y1; int d2=x2-y2;
return Math.sqrt(d1*d1+d2*d2); }
static class Dragon extends Thread{ volatile int x=5; volatile int y=5; public void run(){
while(true){ if(distance(x,hero.x,y,hero.y)<200d){/**/} else{/**/}
}}}
static class Hero extends Thread{ volatile int x=10; volatile int y=10; public void run(){while(true){/**/}} }}
●
Well, when they move they will necessary update x and y in two different moments, so there is a moment where x and y would make no sense.
Distance is always correct?
●
What is the right thing to do, using only the instruments we already know?
static class Point{ ... }
static class Dragon extends Thread{
volatile Point p;
...
p=new Point(p.x+10,p.y+3);//example movement ok p.x=p.x+10; p.y=p.y+3//example movement *WRONG*
●
It is often wrong to put information that is meaningful together in two different variables and then update it one piece at the time.
Remember, always commit only self contained meaningful information.
●
Solutions?
●
This is correct only under the assumption that the contention over the position was on the form many read, one write.
static class Point{ ... }
static class Dragon extends Thread{
volatile Point p;
...
p=new Point(p.x+10,p.y+3);//example movement ok
●
● ●
Under that assumption, the two consecutive reads “p.x+10,p.y+3” are guaranteed to be correct, since the only task able to modify p is busy reading.
So, no “commit of the position is lost” or, if you prefer, There is no contention over the writing of the resource.
Solutions?
●
Well, the new solution requires to create a new object and that is expensive, right? What if I need to write an efficient program!
Well, first, writing an efficient program is bad.
Second, the just in time compiler would probably optimize your code so that no new object is created.
However, if you really want to hurt yourself, just come for the next lecture: “Critical section”
● ●
●
Solutions?
●
●
Next time, we will see how to handle Many reads Many writes
That is, pure hell!
Next time