Why this program runs in infinite loop? Mutual exclusion

Question

Below is the java program with which i started learning about mutual exclusion.

class MutexVar{
    public static int Turn = 1;
}

class CriticalSection{
    private static int modelNumber =0;
    public static void setModelNumber(int number){
        modelNumber = number;
    }

    public static int getModelNumber(){
        return modelNumber;
    }
}

public class MutualExclusion{
    public static void main(String[] args){
        Thread threadObjRef = new Thread(new Runnable(){
            public void run(){
                int autoVar = 1;
                int newModelNumber = -1;
                while(true){
                    /*                               Non - critical section - start   */
                    System.out.println("\n" + "In  run() thread");
                    /*                               Non - critical section - end     */
                    while(MutexVar.Turn == 2){
                        //System.out.println("loop-run"); //infinite loop problem is here
                    }
                    /*                               Critical Section -start          */
                    CriticalSection.setModelNumber(autoVar);
                    newModelNumber = CriticalSection.getModelNumber();
                    MutexVar.Turn = 2;
                    /*                               Critical Section -end            */

                    /*                               Non - critical section - start   */
                    System.out.println("run() thread: " + newModelNumber + "\n");
                    autoVar = autoVar + 2;
                    /*                               Non - critical section - end     */
                }
            }
        });
        threadObjRef.start();
        int autoVar = 0;
        int newModelNumber = -1;
        while(true){

            /*                                       Non - critical section - start    */
            System.out.println("\n" + "In  main thread");
            /*                                       Non - critical section - end      */
            while(MutexVar.Turn == 1){
                //System.out.println("loop-main"); //infinite loop problem is here
            }
            /*                                       Critical Section -start           */
            CriticalSection.setModelNumber(autoVar);
            newModelNumber = CriticalSection.getModelNumber();
            MutexVar.Turn = 1;
            /*                                       Critical Section -end             */

            /*                                       Non - critical section - start    */
            System.out.println("main- thread: " + newModelNumber + "\n");
            autoVar = autoVar + 2;
            /*                                       Non - critical section - end      */
        }
    }
}

My question:

1) Is there a data race between two threads to set MutexVar.Turn?

2) If no, then this program looks good to me, But my program loops infinitely with below output. why infinite loop loop-run or loop-main?

In  main thread

In  run() thread
run() thread: 1


In  run() thread

My observation:

This looks like a Thread scheduling issue. I learnt that java threads are visible to windows OS because they are created internally using CreateThread() api of kernel32.dll and scheduled by OS as 1-1 threading model in windows. java program runs using java jdk 1.6 on windows 7 multi core OS.

Why OS is not interleaving between two threads? I think that is the point I would like to understand. program written in some specific language could not be the issue. — overexchange, Jan 16 '15 at 15:19

NESPowerGlove · Answer 1 · 2015-01-16T15:23:44.167

4

Read your code wrong at first. Looks like you have a stale value.

MutexVar.Turns value is never flushed for other threads to see the latest change. If you changed Turn to be declared as volatile or synchronized on some common lock when you read and write to the common variable shared between threads then you'll probably find MutexVar.Turns value to change.

edited Jan 16 '15 at 15:23

answered Jan 16 '15 at 14:33

NESPowerGlove

5,496
17
28

Yes it is working with `volatile`, but what exactly is happening under the hood when we declare volatile. Because byte code of `main(){}` looks similar to me with/without volatile keyword. Does this problem arise, if this program is written in C/C++? – overexchange Jan 16 '15 at 16:10
@overexchange Well the Java programming language specifies that without the proper synchronization tools used to share mutable state between threads that the JVM is free to make optimizations from caching values for a while before flushing them to RAM to reordering statements as it assumes that the data is not being shared between threads if it's marked somehow using volatile/synchronized. The byte code might not change that much, maybe a flag or two here and there, the real difference you'll see is the actual assembly when the JVM compiles (JITs) your bytecode. – NESPowerGlove Jan 16 '15 at 16:19
@overexchange You can use the compiler flags mentioned in this question to see the assembly output for when the JVM compiles your bytecode: http://stackoverflow.com/questions/1503479/how-to-see-jit-compiled-code-in-jvm. I'm not too familiar with c/C++ but my understanding is that those language specs don't specify how shared state between threads should behave and so it probably depends on the compiler implementation and what threading libraries you use (you probably still have to do some sort of flush/lock combo). – NESPowerGlove Jan 16 '15 at 16:20
@overexchange It may help to also use the flag -Xcomp which ensures that the JVM compiles your bytecode on first use so you can see that output. – NESPowerGlove Jan 16 '15 at 16:31
As per your answer: `Looks like you have a stale value`, Why does not JVM provide up to date value, if we do not use `volatile` keyword? Is it a bug in JVM? – overexchange Jan 20 '15 at 06:02
1

@overexchange It's a feature. Essentially, if you don't mark a value as being potentially used by more than one thread (by reading it and writing to it with a common synchronized lock or declaring it as volatile), the JVM is allowed to make optimizations from reordering your statements to keeping a value in a CPU cache and modifying it there if it's used often (as opposed to writing the latest value back to main memory every time. If the latest value stays in some sort of cache for a while that other threads can't see, then it's considered to be a stale value for those threads). – NESPowerGlove Jan 20 '15 at 14:25
Bit difficult to understand your English, Are you saying that, variable(`Turn`) that is being used by more than one thread are placed in CPU cache. To update this variable(`Turn`) `thread1` performs read/write with CPU cache and thread2 performs read/write from RAM but CPU cache? Is that what you are saying? – overexchange Jan 21 '15 at 09:51
@overexchange Yes that combination is possible, and something along those lines is probably what has happened in your case. You wrote code that used two threads that depend on each other, but didn't tell the compiler about their dependencies on each other, and so the compiler compiled and executed each thread's code as if only one thread required to see any of the work, or listen to the work done in any specific order (statements could be reordered to have single threaded logic remain correct but not multi-threaded logic). May help to look into what it means to have thread-safe code in Java. – NESPowerGlove Jan 21 '15 at 14:32
I feel, compiler knows that code is multithreaded because JVM internally uses kernel32.dll thread api's(in windows), if u go thru `../os/` directory of jdk code. – overexchange Jan 21 '15 at 14:45
@overexchange It knows the program overall has multiple threads and real threads are used, but it doesn't know what exact logic internally is multithreaded or how when and where another thread interacts with another thread. Without helping the compiler out with the required syntax, it assumes there is no shared state between threads and only ensures single threaded logic remains consistent and not the multithreaded logic (because it doesn't know what that logic is, the programmer never described it). – NESPowerGlove Jan 21 '15 at 15:00
OK fine, compiler does not know that a variable `Turn` is shared between two threads, which make sense. BUT when `thread1` gets pre-empted with `thread2` to acquire a CPU cycle, Does it make sense to say that `thread1`'s state has to be pushed from CPU cache to RAM before `thread2` starts her work? – overexchange Jan 21 '15 at 15:05
@overexchange Yes, it at least needs to push that to ram after the latest write for thread2 to see the latest value or on a single core processor at least before it's pre-empted I'd imagine. But that only happens for sure if you code it to happen. The Java language spec talks about this in a more abstract manner, it doesn't even mention the word RAM and only mentions "main memory" just once, so it may be easier to not think about this at a low implementation based level, but just as the rules of the language. [Threading spec part](http://docs.oracle.com/javase/specs/jls/se8/html/jls-17.html). – NESPowerGlove Jan 21 '15 at 15:45
i think here is the same reason why `java` uses volatile keyword as mentioned in this [link](http://www.geeksforgeeks.org/understanding-volatile-qualifier-in-c/). Now i understood. – overexchange Jan 21 '15 at 16:38

John Vint · Accepted Answer · 2015-01-16T15:14:25.377

3

Always synchronize access to shared mutable data. It's not exactly obvious what the JIT/CPU is doing but you are almost certainly running into thread-caching issues by using a non-volatile Turn. Declare MutrexVar as

static class MutexVar {
    public static volatile int Turn = 1;
}

Volatile on a keyword says, Each thread that reads this value will have the most up-to-date value and prohibits compiler reorderings.

A bit more detail of compiler re-orderings. The JIT compiler is able to take your code and hoist the read of Turn. For example it can transform

while(MutexVar.Turn == 1){
    //System.out.println("loop-main"); //infinite loop problem is here
}

into

if(MutexVar.Turn == 1) {
    while(true) {
        //System.out.println("loop-main"); //infinite loop problem is here
    }
 }

This in no way violates Java's compiler contract and can improve performance dramatically. Declaring the field volatile prevents this type or re-ordering.

edited Jan 16 '15 at 15:14

answered Jan 16 '15 at 15:08

John Vint

39,695
7
78
108

Under the hood, Java is allowed to cache the value so long as it doesn't violate intra-thread semantics (program-order). The OS is doing exactly what the JIT is compiling the code into. – John Vint Jan 16 '15 at 15:20
Yes it is working after setting as `volatile`. but, If i compare the bytecode, It is same in both cases. In run() thread it is: `Line #31 getstatic 41; /* MutexVar.Turn */` and in main() thread it is : `Line #47 putstatic 41; /* MutexVar.Turn */` despite i use `volatile` keyword – overexchange Jan 16 '15 at 16:07
Yes! The bytecode is generated once initially by compiling the source. What you want to see is the assembly generated while it's running. The initial compile is usually un-opotmized. The JIT needs more information during runtime on how to change it. – John Vint Jan 16 '15 at 16:28
Look at enabling assembly output it via `-XX:+UnlockDiagnosticVMOptions -XX:+PrintAssembly` – John Vint Jan 16 '15 at 16:29
I thought, `.java` gets compiled to `.class` and then JVM interprets `.class` instruction by instruction. Is it not the case? In which phase JIT comes into picture? – overexchange Jan 16 '15 at 17:09
JIT comes into the picture while interpreting. There can be more than one JIT pass against the code. For instance, your above code could have two different outputs for the machine code during runtime. The first one is how it turns the bytecode as is to machine then the second pass is how it will try and optimize it – John Vint Jan 16 '15 at 17:30
This is why it works for the first second or two than later goes into a for-ever-loop. It is the product of the JIT and the CPU optimizing the program. – John Vint Jan 16 '15 at 17:30
As per the definition of volatile keyword mentioned above: `will have the most up-to-date value `, why are we getting into this situation that using `volatile` keyword will only provide up to date value? Is it a bug in JVM? – overexchange Jan 20 '15 at 06:01
@overexchange No it is not. There are huge performance gains by not always pushing changes to memory when not needed. Just imagine a single-threaded application. If it never needs to push immediately to memory then it shouldn't. – John Vint Jan 20 '15 at 14:25
In my case, Is `Turn` being read by both `thread1` and `thread2` from CPU cache or from memory? – overexchange Jan 21 '15 at 09:52
I would have to look at the assembly out putted but I would guess Turn is being hoisted outside of the loop – John Vint Jan 21 '15 at 13:48
My point is, when `thread1` has done her job and gets pre-empted with `thread2` the `thread1` state has to be pushed from CPU-cache to memory before `thread2` starts her work? so, how did `thread2` get stale value of `Turn` variable? It is not evident to say that assembly code is executed as single threaded ): May be, JVM has overcome a bug by introducing `volatile` keyword. – overexchange Jan 21 '15 at 14:52
`My point is, when thread1 has done her job and gets pre-empted with thread2 the thread1 state has to be pushed from CPU-cache to memory before thread2 starts her work?` When a thread get pre-empted the JIT can cache the value and use it forever. It may not try to read from memory again. `May be, JVM has overcome a bug by introducing volatile keyword.` That is incredibly doubtful. – John Vint Jan 21 '15 at 15:04
I guess, JIT is a compiler that converts non-native byte-code language to native machine code language, so where does JIT come into picture during runtime to cache the value? – overexchange Jan 21 '15 at 15:09
Yes that's right. You can take a look at an answer I give here http://stackoverflow.com/questions/10620680/why-volatile-in-java-5-doesnt-synchronize-cached-copies-of-variables-with-main/10621390#10621390. At the front of the method it will store to the local variable and use that store later on instead of reading from memory. The JIT can do something similar here and appears to be. – John Vint Jan 21 '15 at 15:27
In that case, there was actually a bug in the VM, but those are very rare to see. In your case everything appears to be working as intended. – John Vint Jan 21 '15 at 15:28

Why this program runs in infinite loop? Mutual exclusion

2 Answers2