Happens-Before relation in Java Memory Model

Question

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 :)

End

The best explanation I ever read is Leslie Lamports original paper: research.microsoft.com/en-us/um/people/lamport/pubs/… – Sundin

@Sundin Great paper indeed; but here we're talking about Java Memory Model, not distributed system :-p – End

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. – Sundin

@Sundin 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. – Physical

Answer 1

(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.

Physical

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? – Ribbing

Of course, that's the definition of happens-before. – Physical

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. :) – Ribbing

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". – Physical

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. – End

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. – Physical

A great read to understand the notion of well-formed executions is this one: Java Memory Model Examples: Good, Bad and Ugly. – Physical

@MarkoTopolnik thanks for sharing this Java Memory Model Examples; I'm gonna dig into that. :) – End

Answer 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.

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

3. 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.

Ribbing

Thanks for your quick reply. But, for (1), please see this post; 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)? – End

@End - Check my edit. Also, check Marko Toplonik's answer. He is the one who taught me Escape Analysis :P – Ribbing

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. – Physical