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

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

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.

Answer 2

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