wood burning stoves 2.0*
The moose likes Threads and Synchronization and the fly likes Java memory model Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Android Security Essentials Live Lessons this week in the Android forum!
JavaRanch » Java Forums » Java » Threads and Synchronization
Bookmark "Java memory model" Watch "Java memory model" New topic
Author

Java memory model

David Spades
Ranch Hand

Joined: Feb 01, 2014
Posts: 194
there's one aspect in JMM that is really really confusing to me : reordering. what does this mean?
let's use some analogy. Threads are students, servlet container is librarian and objects are (sets of instructions/books, methods are pages of the book and lines of code in a method are lines in that book). when a student comes to the library, the librarian will determine that this student needs ("has been mapped") to a certain book. so the librarian will display the appropriate page (method) of that book for the student to see what to do. and if another student also wants to do what's written in that exact same page of the same book, he's free to look to do whatever instruction written in it. they're also free to rewrite the contents of that page. Now where does reordering fit in this story? thanks
Raymond Tong
Ranch Hand

Joined: Aug 15, 2010
Posts: 230
    
    2

David Spades wrote:there's one aspect in JMM that is really really confusing to me : reordering. what does this mean?
let's use some analogy. Threads are students, servlet container is librarian and objects are (sets of instructions/books, methods are pages of the book and lines of code in a method are lines in that book). when a student comes to the library, the librarian will determine that this student needs ("has been mapped") to a certain book. so the librarian will display the appropriate page (method) of that book for the student to see what to do. and if another student also wants to do what's written in that exact same page of the same book, he's free to look to do whatever instruction written in it. they're also free to rewrite the contents of that page. Now where does reordering fit in this story? thanks

Lets say Student-1(Thread-001) need to perform following
1) read Chapter-1 of Book-1 (statement-001)
2) read Chapter-1 of Book-2 (statement-002)
3) read Chapter-2 of Book-1 (statement-003)

JVM determine statement-002 does not have dependency on statement-001 and statement-003, so JVM can re-order the execution of statement (to optimize code)
which becomes 1 -> 3 -> 2
or 2 -> 1 -> 3
David Spades
Ranch Hand

Joined: Feb 01, 2014
Posts: 194
lets say I have the following:


lets say thread 1 runs the code, after thread1 reaches the System.out.println(one), thread2 also invokes the code and at the same time, JVM in its infinite wisdom decides to:
1. swap line 8 and 9 so that variable "two" will be assigned before "one"
2. swap line 12 and 14 so that variable "three" will be assigned before printing value of variabel "one" to console

so now,
1. since reordering has happened, thread1 will assign the value "Three" before printing the value of "one" and both reordering will be visible by thread2 since the code has been reordered before thread2 ever reached line 8. Is this correct?
2. With each reordering, JVM will guarantee that line 9 will be executed before line 12, so JVM is still allowed to swap line 9 and 8 because by doing so, it still honors hb(9, 12). is this correct?
thanks
Raymond Tong
Ranch Hand

Joined: Aug 15, 2010
Posts: 230
    
    2

To my understanding, you are correct.
JVM may or may not re-order the code based on the statement dependencies.

Since those variables are local variables, they would not be visible to other threads.
Even those variables are declared as instance variables, memory visibility come to play. (which may need to use volatile)

I suggest to read Java Concurrency In Practice few times.
Henry Wong
author
Sheriff

Joined: Sep 28, 2004
Posts: 18545
    
  40

David Spades wrote:
lets say thread 1 runs the code, after thread1 reaches the System.out.println(one), thread2 also invokes the code and at the same time, JVM in its infinite wisdom decides to:
1. swap line 8 and 9 so that variable "two" will be assigned before "one"
2. swap line 12 and 14 so that variable "three" will be assigned before printing value of variabel "one" to console

so now,
1. since reordering has happened, thread1 will assign the value "Three" before printing the value of "one" and both reordering will be visible by thread2 since the code has been reordered before thread2 ever reached line 8. Is this correct?
2. With each reordering, JVM will guarantee that line 9 will be executed before line 12, so JVM is still allowed to swap line 9 and 8 because by doing so, it still honors hb(9, 12). is this correct?
thanks


First. the one, two, and three variables are local variables -- so none of the points about changes from thread1 being visible to thread2 applies. The threads have separate reference variables -- and changing a reference variable in one thread doesn't change a completely different reference variable in another thread.

Second, the second reordering will never happen. Reordering must keep the integrity of the algorithm -- the compiler can't just reorder any two lines. In this case, it can't move any code from one side of a method call to the other side of a method call, because it can't determine if the method call will have an indirect affect on the variable whose code is being moved.


And third, just because the compiler can move code doesn't mean that it will. There is generally a reason for it -- for example, for optimization purposes. And admittedly, code motion discussions generally go over my head, so won't be able to give any more examples than that.

Henry


Books: Java Threads, 3rd Edition, Jini in a Nutshell, and Java Gems (contributor)
David Spades
Ranch Hand

Joined: Feb 01, 2014
Posts: 194
tried that, but I find that book a bit too advanced to me.
that's why I end up asking question here, to simplify things a bit. and now about visibility


thread1 and thread2 invokes the method at the same time. thread1 passes a=3 and b=7 while thread 2 a=6 and b=11.
Here are my assumptions:
1. JVM may put line 7 to wherever it wants since it's independent. is this correct?
2. there are only two possibilities : thread1 reaches if block first or thread2 reaches it first. is this correct?
3. if thread1 assigns "a" to "x" before thread2 reaches if block, then thread2 would only print "abcdef". right?
4. if both thread2 enters the if block before thread1 assigns "a" to "x", then both threads will print value of y. right?
5. it's possible that the second println would print "3" or "6" for both threads, right?

number 4 and 5 is memory visibility problem right?

thanks
Heena Agarwal
Ranch Hand

Joined: Dec 25, 2013
Posts: 261
    
    4
David Spades wrote:



Try writing that swap method and then print the values of a and b using just one thread. You'd notice the swap did not happen ( a is still what it was and b is what it was before the swap) obviously cause a and b are local primitives and swap is a method call. Let us consider that the swap method assigns those values to x and y and then swaps them cause that is possible.

You have not created any memory barriers in your code. In the absence of a memory barrier, the compiler is free to be creative ( optimize ) the execution order of the instructions so long as all the happens before
relations among the statements that applied before the reorder are still intact and such a reorder does not change the way that thread would behave in isolation. So to assess whether a certain reordering can happen, you need to check if there exists a happens before relationship between two statements in your code. I don't think the statements you have in your code have any happens before relationships except the parts in the if block ( the if block condition will be executed before any of the statements in the if block are executed). Also within the if block there is a happens before between the assignment to y and the print of y.

I think since the swap method can't change the value of local variables a and b, there is no happens before relationship between that if block and the swap call. So I think the swap method can be executed even after the if block is executed. But I'm not sure about that.

Personally I don't trust the reordering and hence I would always employ a memory barrier.
David Spades
Ranch Hand

Joined: Feb 01, 2014
Posts: 194
in that case, can anybody give me an example of happen before relationship?
the concept of this is still vague to me.
thanks
Heena Agarwal
Ranch Hand

Joined: Dec 25, 2013
Posts: 261
    
    4
David Spades wrote:Here are my assumptions:
1. JVM may put line 7 to wherever it wants since it's independent. is this correct?
2. there are only two possibilities : thread1 reaches if block first or thread2 reaches it first. is this correct?
3. if thread1 assigns "a" to "x" before thread2 reaches if block, then thread2 would only print "abcdef". right?
4. if both thread2 enters the if block before thread1 assigns "a" to "x", then both threads will print value of y. right?
5. it's possible that the second println would print "3" or "6" for both threads, right?


1. Right
2. Right
3. Wrong ( cause that is not a guaranteed behavior) - Thread 2 might use a cached value of x.
4. Right
5. Wrong I think ( but I'm not sure ) My reason is this - I am not sure what the method swap does but a and b will not have changed after the swap call. And y =b will always be executed before system.out.println(y) is executed. So there is no way the two println can print the same values.
Heena Agarwal
Ranch Hand

Joined: Dec 25, 2013
Posts: 261
    
    4
David Spades wrote:in that case, can anybody give me an example of happen before relationship?
the concept of this is still vague to me.
thanks


You might want to go through the relevant jls parts.

The happens before part is explained in section 17.4.5.
Heena Agarwal
Ranch Hand

Joined: Dec 25, 2013
Posts: 261
    
    4
Heena Agarwal wrote:[quote=David Spades.......
5. it's possible that the second println would print "3" or "6" for both threads, right?



5. Wrong I think ( but I'm not sure ) My reason is this - I am not sure what the method swap does but a and b will not have changed after the swap call. And y =b will always be executed before system.out.println(y) is executed. So there is no way the two println can print the same values.

My answer for 5 should be this.

5. Wrong cause the value of b does not change after the swap call. So b can never have what a had.

If your question was if the two threads can print the same value ( 7 or 11 not 3 or 6 ), my answer would be no still cause I think there is a happens before between the assignment to y and the print of y.

Sorry, too many responses. But I think this one was worth mentioning.
Steve Luke
Bartender

Joined: Jan 28, 2003
Posts: 4167
    
  21

If we modify the code so the swap will occur, it might look something like this:


Then your questions become these:
David Spades wrote:1. JVM may put line 7 to wherever it wants since it's independent. is this correct?
2. there are only two possibilities : thread1 reaches if block first or thread2 reaches it first. is this correct?
3. if thread1 assigns "a" to "x" before thread2 reaches if block, then thread2 would only print "abcdef". right?
4. if both thread2 enters the if block before thread1 assigns "a" to "x", then both threads will print value of y. right?
5. it's possible that the second println would print "3" or "6" for both threads, right?

1. See Henry's second point in his previous response.
2. Incorrect. If the threads are running truly parallel, then they can reach the block at exactly the same time, however unlikely that is, it is still a possibility.
3. As Heena said, no. There is no memory barrier so there is no guarantee that one thread sees the value a different thread assigns to a shared (non-volatile) variable. So even if thread1 assigns a non-0 value to x before thread2 executes the code, thread2 may not see the effects of that assignment.
4. Yes, once a thread is in the if {} it will complete the if {} unless an exception occurs.
5. True, with the reposted code I gave, since the swap can actually have an effect on the objects used in the calling thread. In this case, all of the following are possible output:
(a) Both threads print 3
(b) Both threads print 6
(c) Thread1 prints 3 and thread2 prints 6
I think the following is a possibility, but I am not positive:
(d) Thread1 prints 6 and thread2 prints 3

You asked for some examples for happens-before. Happens-before is rather simple. If there is only one thread involved, then any single writing of a variable (assignment) will happen-before a reading of that variable (using it in an expression) as long as the writing is before the reading in programming order (the line of code which assigns the variable comes before the line of code with the expression that uses it). When multiple threads are concerned there is no happens-before relationship at all. Unless at least one of a few 'memory barriers' are in place to enforce the happens-before relationship. Heena previously posted a link which explain the relevant memory barriers. But the code you (and I) posted doesn't have any memory barriers and we are talking about multiple threads so happens-before is not guaranteed - definitely not between between threads and not about which value is visible at any time in a single thread.


Steve
Heena Agarwal
Ranch Hand

Joined: Dec 25, 2013
Posts: 261
    
    4
Steve Luke wrote:1. See Henry's second point in his previous response.
2. Incorrect. If the threads are running truly parallel, then they can reach the block at exactly the same time, however unlikely that is, it is still a possibility.


Steve, thanks for the correction and the other pointers you've provided in your response. I used to know these things till a few days back but I realize that I need to revise some of this stuff again. I didn't realize that the first println in the OP's code could not be placed anywhere else like he said cause there was another println in his code that would write to the same stream. So if the compiler could place that instruction anywhere, it would have made the output inconsistent even if those instructions were executed by a single thread in isolation.

About point 2, yeah I realize that I missed the part that these days systems are capable of executing multiple threads in parallel. We have multi-core processors. And with multi-core processors and multi processors, we'd get true concurrency and in such a case it could be possible that both of those threads would execute the if condition at the same time.
David Spades
Ranch Hand

Joined: Feb 01, 2014
Posts: 194
okay, so in multi-threaded env, no such thing as happens before would exist? because as of now, what I understand i the only rule the JVM follows to perform reordering is:
1. If the reordering can improve performance (why JVM thinks the reordering may improve performance is out of the scope of this question)
2. If criterion 1 is fulfilled, then JVM will check if reordering would violate happens before relationship. If it satisfies both criteria (may improve performance and not violate hb), then reordering will take place.

1. is this the correct understanding about hb and reordering?
2. reordering simply means the JVM swapping the position of one line of code with another right? and that's it, no other activities involved?
3. lets say JVM wants to perform reordering by swapping line 3 and line 8, that would mean JVM needs to evaluate if there's no hb between line 3 and line 4 to 8. is this correct?
thanks
Heena Agarwal
Ranch Hand

Joined: Dec 25, 2013
Posts: 261
    
    4
Have you gone through that link I suggested in my previous post?
Steve Luke
Bartender

Joined: Jan 28, 2003
Posts: 4167
    
  21

When you are talking about multiple threads it is not just about code reordering. It is also about value visibility. Unless you put memory barriers in place you have no guarantee about what value will be visible when a read happens. And there is no guarantee that values will be made visible in the order they are set.
Chris Hurst
Ranch Hand

Joined: Oct 26, 2003
Posts: 412
    
    2

I'll avoid going over the examples as so much has been written its hard to see where to start as so much has been commented on but 2 points ...


1) I think I have commented on this in previous threads ...

I would expect System.out.println to synchronize , looking at the the implementation/java source in my JDK download it's a PrintStream that is fully synchronized.
There is a lock in your example so if two threads synchronize on this lock e.g. call System.out.println we have hb (you have memory barriers in your example) at this point which gives us visibility / prevents reordering , some of the previous posts seemed to contradict this.


2) Hi Henry, I was interested in what you said about not being able reorder over method calls, I'd expect the JVM to struggle in such scenario but wasn't aware it was explicitly prohibited. I'm very interested in this can you point me at the relevant section of the Java Memory Model ? I always assumed as an example for a simple method that could be effectively inlined the JVM would be capable of reordering over it, for instance a NO-OP (though I wouldn't be surprised to find out no existing JVM currently took advantage of this).

"Eagles may soar but weasels don't get sucked into jet engines" SCJP 1.6, SCWCD 1.4, SCJD 1.5,SCBCD 5
Henry Wong
author
Sheriff

Joined: Sep 28, 2004
Posts: 18545
    
  40

Chris Hurst wrote:
2) Hi Henry, I was interested in what you said about not being able reorder over method calls, I'd expect the JVM to struggle in such scenario but wasn't aware it was explicitly prohibited. I'm very interested in this can you point me at the relevant section of the Java Memory Model ? I always assumed as an example for a simple method that could be effectively inlined the JVM would be capable of reordering over it, for instance a NO-OP (though I wouldn't be surprised to find out no existing JVM currently took advantage of this).


Sorry, I was talking from experience (and using the current example, which I guess I shouldn't have). Also, if the litmus test for this discussion is via the JVM specification, then I can't be involved as I have (so far) had no desire to read that document. Sorry for the confusion.


However, you are correct. It is possible to inline a method, and then do a code motion that can move that method. I had completely forgotten about that. On the other hand, I have never seen the inlining of anything that complex; certainly nothing that has I/O (such as a println()). I believe that the JVM can eliminate tail recursion though -- so that may be a case of eliminating (or arguably inlining) a complex method call.

Furthermore, assuming that the method is inlined, there are no loops, switches, or even combination usage of floats and ints, which are generally what is being optimized that may cause code motion.

Again, sorry for the confusion,
Henry
David Spades
Ranch Hand

Joined: Feb 01, 2014
Posts: 194
so, what criteria do the JVM must check before it determines that it's allowed to reorder lines of code? thanks
Heena Agarwal
Ranch Hand

Joined: Dec 25, 2013
Posts: 261
    
    4
David Spades wrote:so, what criteria do the JVM must check before it determines that it's allowed to reorder lines of code? thanks


There is no one criterion. I think it depends upon the JVM implementation. JLS specifies general rules that it expects the JVMs to adhere to.

I think people have already explained the important parts-- the importance of memory barriers in a multi-threaded environment, the counter intuitive behavior that can result in unsynchronized or incorrectly synchronized contexts, etc. I think the earlier responses have addressed your question already.

For more details you might want to go through the specifications in the JLS yourself. Let us know the specific part you could not understand.

But I'd suggest to go through things like reordering and stuff only after you have understood the basics. Like the race conditions that can exist, the ways to avoid them, the ways to employ different types of memory barriers, pros and cons... If you are past that stage, ignore this part.

Heena Agarwal
Ranch Hand

Joined: Dec 25, 2013
Posts: 261
    
    4
Actually the JLS states this.

JLS wrote:This is an extremely strong guarantee for programmers. Programmers do not need to reason about reorderings to determine that their code contains data races. Therefore they do not need to reason about reorderings when determining whether their code is correctly synchronized. Once the determination that the code is correctly synchronized is made, the programmer does not need to worry that reorderings will affect his or her code.

A program must be correctly synchronized to avoid the kinds of counterintuitive behaviors that can be observed when code is reordered. The use of correct synchronization does not ensure that the overall behavior of a program is correct. However, its use does allow a programmer to reason about the possible behaviors of a program in a simple way; the behavior of a correctly synchronized program is much less dependent on possible reorderings. Without correct synchronization, very strange, confusing and counterintuitive behaviors are possible.




 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Java memory model
 
Similar Threads
please help me
new to write code, pls help!
Learn to Program with Java by John Smiley
Modeling Classes
My latch experiment