6

Regarding JLS ch17 Threads and Locks, it says "if one action happens-before another, then the first is visible to and ordered before the second"; I wonder:

(1) What does it really mean by saying "ordered before"? Because even if action_a happens-before action_b, action_a can be executed after action_b in some implementation, right?

(2) If action_a happens-before action_b, does it mean action_a MUST NOT see action_b? Or action_a may see or may not see action_b?

(3) If action_a does NOT happen-before action_b, and action_b does NOT happen-before action_a, does it mean action_a may see or may not see action_b?

(4) There could not be any cyclic happens-before, right?

Any answer would be appreciated :)

pbespechnyi
  • 2,251
  • 1
  • 19
  • 29
Kurtt.Lin
  • 289
  • 1
  • 8
  • The best explanation I ever read is Leslie Lamports original paper: http://research.microsoft.com/en-us/um/people/lamport/pubs/time-clocks.pdf – midor Dec 24 '14 at 12:48
  • @midor Great paper indeed; but here we're talking about Java Memory Model, not distributed system :-p – Kurtt.Lin Dec 24 '14 at 13:11
  • Yes, we do talk about Java, but the happened-before relation is something that spans pretty much all sections of CS where concurrent operation takes place. Afaik it is not redefined for Java, and I would be very surprised if it was so. Pretty much all of his questions are about the happened-before relation, so I would still consider Lamport's paper the best reference. – midor Dec 24 '14 at 13:46
  • @midor If you look carefully at what is being asked, you'll see that OP does not seek clarification of what *happens-before* means, but rather how the specific rules of the JLS prevent unnatural outcomes such as circular causality. – Marko Topolnik Dec 24 '14 at 16:53

2 Answers2

6

(1) What does it really mean by saying "ordered before"? Because even if action_a happens-before action_b, action_a can be executed after action_b in some implementation, right?

Happens-before is a causal, not a temporal relationship. action_a is causally ordered before action_b, whether or not it actually executes before it. In practice, however, a runtime would have a really hard time maintaning the causality without temporal order. Check out my earlier question which goes into some detail on the subject of causality.

(2) If action_a happens-before action_b, does it mean action_a MUST NOT see action_b? Or action_a may see or may not see action_b?

There is a definite overall order of the visibility of actions to one other. This is dealt with by the section specifying well-formed executions. Therefore, for any two actions a and b, either a is visible to b, or b to a, or none of the above. A good read to understand the notion of well-formed executions is Java Memory Model Examples: Good, Bad, and Ugly.

(3) If action_a does NOT happen-before action_b, and action_b does NOT happen-before action_a, does it mean action_a may see or may not see action_b?

Yes, either is possible. There is no guarantee either way.

(4) There could not be any cyclic happens-before, right?

Happens-before must impose a partial ordering, and the key property of ordering is no loops.

Community
  • 1
  • 1
Marko Topolnik
  • 195,646
  • 29
  • 319
  • 436
  • For point-2. If action-a happens before action-b, then the changes done by action-a should be visible to action-b right?. Else, how does the *Happens before* relationship hold? – TheLostMind Dec 24 '14 at 13:36
  • Of course, that's the definition of *happens-before*. – Marko Topolnik Dec 24 '14 at 13:52
  • I got confused because you say - *Therefore, for any two actions a and b, either a is visible to b, or b to a, or none of the above.* :) – TheLostMind Dec 24 '14 at 13:53
  • Yes, I'm making a general statement about any two actions. Applied to our case it implies the answer to OP's question: "correct, action_a MUST NOT see action_b". – Marko Topolnik Dec 24 '14 at 14:14
  • great points for (1)(3)(4); they really help; I'd appreciated that :) Regarding point-2, it's clear that if action_a happens-before action_b then action_a MUST be visible to action_b; however, I wonder, is there a guarantee that action_b MUST not be visible to action_a when action_a happens-before action_b? I could not find any explicit statement that says so; even in the _well-formed executions_ you mentioned, I could not find any. – Kurtt.Lin Dec 25 '14 at 02:08
  • Section 17.4.8, *Executions and Causality Requirements*, is all about the prevention of "out-of-thin-air" values, which could happen exactly if two actions were allowed to be visible to another. – Marko Topolnik Dec 25 '14 at 08:44
  • A great read to understand the notion of well-formed executions is this one: [*Java Memory Model Examples: Good, Bad and Ugly*](http://groups.inf.ed.ac.uk/request/jmmexamples.pdf). – Marko Topolnik Dec 25 '14 at 12:14
  • @MarkoTopolnik thanks for sharing this _Java Memory Model Examples_; I'm gonna dig into that. :) – Kurtt.Lin Dec 26 '14 at 03:28
2

What does it really mean by saying "ordered before"? Because even if action_a happens-before action_b, action_a can be executed after action_b in some implementation, right?

A Happens before relationship creates a memory barrier which prevents the execution of action-b before action-a. Thus some underlying JVM optimizations cannot be applied. So, NO action-a cannot be executed after or along with action-b.

If action_a happens-before action_b, does it mean action_a MUST NOT see action_b? Or action_a may see or may not see action_b?

It means action-b must see all the changes brought about by action-a.

If action_a does NOT happen-before action_b, and action_b does NOT happen-before action_a, does it mean action_a may see or may not see action_b?

Happens-before is a transitive relationship. So, if action-a happens before action-b which happens before action-c ... so on upto action-y, and action-y happens before action-z, then action-a happens before action-z.

A happens before relationship ensures that the actions which follow the current action, will see the changes made by the current action. If the changes are not seen, then a happens before doesn't exist.

There could not be any cyclic happens-before, right?

Right, If action-a happens before action-b,action-c, action-d, then none among b,c,d can happen before action-a.

Edit :

The JLS says It should be noted that the presence of a happens-before relationship between two actions does not necessarily imply that they have to take place in that order in an implementation. If the reordering produces results consistent with a legal execution, it is not illegal.. So, if action-a has a happens before relationship with action-b, then action-b can execute first provided the final is equivalent to the sate if action a had executed before action b. This is implementation specific. The JIT might decide to run action-b earlier than action a provided this change in order does not affect the final result.

  1. Well, action-a is independent of action-b. atleast theoretically :)

  2. Happens before specifies, sequential actions. If the actions are parallel, then a happens before doesn't exist.

Note : All this confusion is because of the removal of happens before by the the JIT if there is no dependency between two actions. Please read about Escape analysis.

Community
  • 1
  • 1
TheLostMind
  • 35,966
  • 12
  • 68
  • 104
  • Thanks for your quick reply. But, for (1), please see [this post](http://stackoverflow.com/questions/10439527/java-reordering-and-memory-model); for (2) what about action_b's impact on action_a? for (3) transitive is great, but what about "parallel" actions (no happens-before relations)? – Kurtt.Lin Dec 24 '14 at 13:18
  • @Kurtt.Lin - Check my edit. Also, check *Marko Toplonik's* answer. He is the one who taught me *Escape Analysis* :P – TheLostMind Dec 24 '14 at 13:49
  • 1
    I wouldn't view any actions by the JITC as a "removal of *happens-before*" because it is a *conceptual* relationhsip whose semantic consequences must always be obeyed. Lock elision (I guess that's what you have in mind where you mention Escape Analysis) does not remove any *happens-before* relationships---the JITC just concludes that it can satisfy them without any memory barriers. – Marko Topolnik Dec 24 '14 at 16:41