6

Many people asked similar questions like this, but none of their answers satisfied me. The only two reordering rules that I am very sure of are as follows:

  1. Operations inside the synchronized block(or just call it critical section) are allowed to be reordered, as long as it confirms to the as-if-serial semantics.
  2. Operations(including both reads and writes) are disallowed to be moved(reordered) out of the critical section.

However, for those operations that are before or after the synchronized block, can they be moved into the critical section? For this problem, I found some contrary. For example, the cookbook said that the compiler will insert some barriers after the MonitorEnter and before the MonitorExit:

MonitorEnter
 (any other needed instructions go here )
[LoadLoad] <===MB1:Inserted memory barrier
[LoadStore] <===MB2:Inserted memory barrier
(Begin of critical section)

....
(end of critical section)
[LoadStore] <===MB3:Inserted memory barrier
[StoreStore] <===MB4:Inserted memory barrier
 (any other needed instructions go here )
MonitorExit

According to be above placement made by the compiler and given below pseudo code:

  Load a;
  Load b;
  Store 1;
  Store 2;
  MonitorEnter
     (any other needed instructions go here )
    [LoadLoad] <===MB1
    [LoadStore] <===MB2
    (Begin of critical section)

    ....
    (end of critical section)
    [LoadStore]  <===MB3
    [StoreStore]  <===MB4
     (any other needed instructions go here )
    MonitorExit
  Store 3;
  Store 4;
  Load c;
  Load d;

According to the cookbook and reordering prevention rules enforced by such XY(X is Load or Store,Y is Load or Store) memory barriers, it seems to me that valid/invalid reordering are as below:

Understanding 1: Any stores(Store 3 and Store 4 here) after the MonitorExit can NOT be moved up before MB3 and MB4, because of the existence of a LoadStore(MB3) followed by a StoreStore(MB4). That's to say stores after the MonitorExit cannot be moved into critical section. However, it can be moved up after MB4,namely the bracket area.

Understanding 2:Any loads(Load a and Load b here) before the MonitorEnter can NOT be moved down after MB2 and MB1, because of the existence of a LoadLoad(MB1) followed by a LoadLoad(MB2).That's to say loads before the MonitorEnter cannot be moved into critical sention. However, it can be moved down after MB2,namely the bracket area.

Understanding 3:Any loads(Load c and Load d here) after the MonitorExit can be moved up before the MonitorExit, including the critical section and the bracket area, but it cannot exceed the MonitorEnter.

Understanding 4: Any stores(Store 1 and Store 2 here) before the MonitorEnter can be moved down after the MonitorEnter, including the critical section and the bracket area, but it cannot exceed the MonitorExit.

However, all the above understanding or claim see to be contrary to what Jeremy Manson said in his blog, where he claimed that give below code:

x = 1;//Store
synchronized(o) {
z = z + 1;
}
y = 1//Store

Reordering that produce below code is allowed:

synchronized(o){
y = 1;//I added this comment:Store moved inside the critical section
z = z + 1;
x = 1;//I added this comment:Store moved inside the critical section
}

According to Understanding 1, "y=1" cannot be moved up inside the critical section, So I just was confused, which one is correct and complete?

Improve this question
1

1 Answer 1

Reset to default
1

Reordering do not care about memory barriers. Even if the compiler always inserts the strongest memory barrier between any two instructions, these reordering are still permitted regardless.

Now, given a sequence of instructions, possibly after being reordered from the the original sequence, the compiler needs to insert proper memory barriers between some instructions.

For example, given an original sequence of instructions

volatile store x
normal   store y

It does not need memory barrier between the two instructions.

However, the compiler may choose to reorder it to

normal   store y
volatile store x

then a StoreStore barrier is needed between the two instructions. The CPU only has a "store" instruction, no concept of normal/volatile store. And the CPU may have out-of-order stores. It is the Java semantics that requires that another CPU must not observe the effect of store x before the effect of volatile store y; so a StoreStore is used to tell the CPU to store them in order.

(If the compiler is smart enough, it'll remember that the original program does not require the ordering of y->x, therefore this barrier is not actually needed. But let's say the compiler isn't that smart.)

Roach Motel model --

The point of JMM is to establish some (partial) orders among instructions on different threads, so that effects of reads/writes can be defined. In the following example,

thread 1             thread 2

  a1                   a2
  |
 }b1       ----->      b2{
                       |
  c1                   c2

a synchronization order b1->b2 is established, which could be volatile store -> volatile load, or monitor exit -> monitor enter. This connects a1->b1->b2->c2 in happens-before order.

Since we need to guarantee the ordering of a1->c2, a1 must not be reordered with b1, and c2 must not be reordered with b2; that is, a roach cannot "check out".

On the other hand, JMM wants to be as weak as possible; it says nothing about the effects between c1 and a2,b2,c2; therefore, c1 can be freely reordered with b1. Similarly, a2 can be reordered with b2. That is, a roach can "check in".

Improve this answer
Sign up to request clarification or add additional context in comments.

4 Comments

Even if "the compiler is smart enough", according to my understanding, the compiler still needs to insert a StoreStore in your example, because it should prevent the processor from reordering between instructions that precedes the volatile store and the volatile store itself so as to enforce the semantics of a volatile store.
Thanks @bayou.io for your detailed explanation! My understanding is that, to sum it up, for reads and writes that precedes the MonitorEnter or followed the MonitorExit, they can be moved(reordered) into the critical section during compilation(JIT compilation).However, once the compilation is done, the moved reads/writes cannot be moved out by processor, due to the memory barriers inserted by the compiler which will be regarded by processor, am I right?
Suppose the original program is normal store A; volatile store B. JMM semantics is that, after another thread sees the effect of B, then it should also see the effect of A. Now, it's JVM's job to implement that semantics on a particular CPU architecture. A CPU may perform writes out-of-order by default; but it'll also support a barrier instruction to disable that. So on that CPU, JVM first will keep the order of A and B, i.e., no reordering by JVM; then JVM will insert StoreStore between A and B, i.e. no reordering by CPU.
Notice in the cookbook how similar the reordering table and the barrier table are. If instructions P;Q should not be reordered per JMM, the 1st table will forbid reordering by JVM, and the 2nd table will forbid reordering by CPU. The combined effect is that P;Q don't appear to be reordered when observed by other CPUs.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.