It happens before and the programming order in the Java Memory Model

Question

I have some regarding the order of the program and how this affects reordering in JMM.

In the Java memory model, program order (po) is defined as the general order of actions in each thread in the program. According to JLS , this leads to the occurrence-before (hb) edges:

If x and y are the actions of the same thread, and x is up to y in the programming order, then hb (x, y) (i.e., x occurs before y ).

So, for a simple P program:

  initially, x = y = 0 T1 | T2 -----------|----------- 1. r1 = x | 3. r2 = y 2. y = 1 | 4. x = r2 

I think po (1, 2) and po (3, 4). Thus, hb (1, 2) and hb (3, 4).

Now suppose I wanted to reorder some of these statements, giving me P ':

  initially, x = y = 0 T1 | T2 -----------|----------- 2. y = 1 | 3. r2 = y 1. r1 = x | 4. x = r2 

In accordance with this article, we can reorder any two neighboring operators (for example, 1 and 2), provided that reordering does not eliminate any transitive events - before edges in any real execution. However, since hb is determined (partially) by po, and po is the complete order over the actions of the stream, it seems to me that it would be impossible to reorder any two statements without breaking hb, so P 'is not a legal transformation.

My questions:

• Do I understand po and hb correctly, and have I correctly defined po and hb relative to the above program P?
• Where is my understanding about reordering regarding hb failure?

Answer 1

You are missing this part of JLS:

It should be noted that the presence of a relationship between two actions does not necessarily mean that they must be performed in this order in the implementation. If reordering leads to results that are consistent with legal execution, this is not illegal.

In your case, since 1 and 2 are not connected, they can be turned over. Now, if 2 was y = r1 , then 1 must happen before 2 for the correct result.

---

The real problem arises with multiprocessor execution. Without any consequences - in front of the boundaries, T2 can observe 2 to 1, regardless of the order of execution.

This is due to processor caching. Let them say that T1 holds 1 and 2, in any order. Since it does not happen - before the boundary exists, these actions are still in the CPU cache, and depending on other needs, the part of the cache containing the result 2 can be cleared to the part of the cache that contains the result 1.

If T2 is executed between these two cache flush events, then 2 will be observed, and 1 will not occur, that is, 2 will occur before 1, as far as T2 is known.

If this is not allowed, then T1 should set the limit to 1: 2.

There are different ways to do this in Java. The old style should be to put 1 and 2 in separate synchronized blocks, because the beginning and end of the synchronized block occurs before the border, that is, any action in front of the block occurs before actions inside the block, and any action inside the block occurs before the actions following behind the block.

Answer 2

What you described as P 'is actually not a different program, but a trace of the execution of the same program P. It may be a different program, but then it will have different po and, therefore, different hb.

A case-to-relationship relationship restricts reordering of operators with respect to their observed effect, rather than their execution order. Action 1 occurs before 2, but they do not observe each other, so they can be reordered. hb ensures that you notice that two actions were performed in order, but only from a synchronous context (i.e. from other actions forming hb with 1 and 2). You might think of words 1 and 2: "Swap." No one is watching!

Here is a good example from JLS that reflects what happens before the idea is pretty good:

For example, writing a default value for each field of an object constructed by a stream does not have to precede the beginning of this stream, unless the reading notices this fact.

In practice, it is rarely possible to order default entries for all objects built by a stream before it starts, even if they form a synchronization with the edge with every action in that stream. The initial thread may not know what and how many objects it will create at runtime. But as soon as you access the object, you will notice that the default entries have already occurred. The default ordering of an object not yet built (or known for building it) can often not be reflected in execution, but it still does not violate the action-up relationship, because it is associated with the observed effect.

Answer 3

I think the key problem is with your P' construct. This means that the reordering method is that the reordering is global - the entire program is reordered unilaterally (with each execution), which obeys the memory model. Then you try to reason about this P' and find out that there are no interesting reorders!

What actually happens is that there is no definite global order for operators that are not related by the hb relation, so different threads can see different visible orders at the same execution. In your example, there are no edges between the {1,2} and {3,4} operators in one set, which can be seen in the other set in any order. For example, it is possible that T2 observes 2 to 1 , but then T3 , which is identical to T2 (with its own variables), notices the opposite! Thus, there is no single P 'reordering - each thread can observe its own reordering if they are consistent with the JMM rules.