Compilers are our friends…right? So tell me: why would a friend change your software to create an infinite loop in your code without you knowing? Such an action would no doubt create potential havoc for someone using your software. Heavens knows how many headache pills would need to be ingested as you debug that gem!

I am not making this scenario up. It could actually happen.

I was reading a section in the excellent tome Java Concurrency in Practice by Brian Goetz, Tim Peierls, Joshua Bloch, Joseph Bowbeer, David Holmes and Doug Lea on why a volatile variable should be used for a status flag in a while loop for a section of code that may be accessed by multiple threads. This is the example that they describe in the book:


volatile boolean asleep;
...
while (!asleep) {
 	countSomeSheep();
}


(By the way, if you think that you know something about thread programming in Java then read this book and let's have a conversation!)

So our software will count sheep until the variable asleep is set to the value true by some other thread. At some point, our loop will pick up this change and exit.

Simple enough. However, the authors indicate that if the boolean variable asleep were not declared volatile, then an update to its value by another thread may not be read at all by the loop. The authors give an excellent explanation as to why this could occur.



Perhaps more surprisingly, the authors also indicate that a compiler (as an optimization) could move the test for the value of the variable asleep out of the while loop and create an infinite loop!!!

What the authors did not describe is the "why" in this case. I would like to explain that "why" in this posting and clarify a few things in this example. Without the "why" we may be inclined to anthropomorphism our good complier friends as schizophrenic psychopaths.

The first thing to note in how the example is written in the book, is that the variable asleep is not a local (or automatic) variable. Local variables are per thread variables i.e. not shared across threads. Local variables cannot be declared to be volatile so, by implication, asleep is obviously an instance variable. A small point no doubt, and perhaps no need for clarification here, but, just to be totally explicit. The other thing to note is that the method countSomeSheep() does not (and should not for this example to be true) make any modifications to the variable asleep. This way, asleep is loop invariant.

Cool. To explain why this optimization occurs, we have to look at how compilers optimize loops.

We are probably very familiar with how compilers optimize loops through code motion techniques. I will go over one technique briefly. What we are interested in here for our particular example is called loop-invariant code motion or hoisting. Simply put, a compiler may move a variable out of a loop that is not modified in the processing of the loop. A sensible thing no doubt. Why keep checking a variable or repeating a calculation that does not change? Provided that the hoisting does not change the semantics of the loop, this is perfectly fine. To illustrate, consider the following loop:


for (int i=0; i < count; ++i) {
 	c = a + b; // c does not change in the loop it is always a + b. Neither a nor b changes in the loop
 	d = i + 2 * c; // Since c does not change, neither does 2 * c
 }
 


This loop could be optimized via the following restructuring by a compiler to move the components that do not change out of the loop and calculate them just one time, up front before looping:

c = a + b;
_t1 = 2 * c;
for (int i=0; i < count; ++i) {
 	d = i + _t1;
 }
 

Code motion causes the loop-invariants to be move out loop and our two pieces of software are identical in the result that they generate. The example gives the gist of what occurs but what about our example?

Let us assume that we have a snippet of program that does the following:


private boolean flag; // An instance variable for this class
...
	processSomeData();
	flag = true;
	while(flag) {
	  // Do something that does not change the value of flag
	}
	flag = false;
	processSomeMoreData();



As an aside, bear in mind that the operation of a while loop like while(flag){} breaks down approximately into the following memory operations:

  • Check (or compare) the value of the variable flag
  • If the value is true, execute the loop and repeat from the first statement above
  • If the value is false, do not execute the loop

  • We all know this but, for perfect clarity, it is useful to break down what instructions the compiler would actually generate from our higher level syntax to illustrate the point.

    Our program segment (directly above) calls a method to process some data. It then sets flag to true and enters a loop with checks for the condition of flag. After the loop, we set flag to false and then process some more data. But the last two statements never get executed!! This is because by the time that we get to the while loop with flag set to true, we never get past this statement. We loop infinitely because the value of flag never gets modified by the loop. Each time the loop processes and we compare the value of flag, it is the same: true. So what is my point here? Let us rewrite the example, with the same semantics (or meaning) but different statements. Here we go:


    private boolean flag; // An instance variable for this class
    ...
    	processSomeData();
    	flag = true;
    
    	if (flag) {
    		while(true) {
    		  // Do something that does not change the value of flag
    		}
    	}
    
    	flag = false;
    	processSomeMoreData();
    


    For this example, we check the value of flag once up front. If the value is true then we just loop infinitely. The two programs have exactly the same semantics or same meaning and do exactly the same thing!!! The difference is that the first snippet of code does a check of the status of flag every time through the loop even though the value does not change and the second checks the value of flag one time and just loops forever without having to compare the value of flag over and over since it does not change. OK, so it is true that for the read of variable flag in the loop of the first snippet that the variable will likely be in the processor's cache at this point. It may even be in level one cache or it may be cached in a register. You will most likely not have to go to main memory to compare the value of flag each time with modern processors. So, comparing (or checking) the value of the variable flag in a loop is pretty fast... but not as fast as not comparing it at all if you know that the compare is unnecessary! The compiler can generate an unconditional jump to repeat the loop rather than a conditional one.

    The point is that the second code snippet is more efficient than the first but has exactly the same programmatic meaning! Therefore, your compiler is justified in changing the first code snippet into the second snippet as an optimization. In general, your compiler is free to reorder your code in efficient ways so long as the semantics of your program are not changed. A compiler can hoist a variable out of a loop and check it only once, then put in place an infinite loop if the semantics justify such an action.

    So back to our original problem because all this code motion stuff is cool but I do not need unexpected infinite loops popping up. This is all fine and good for single-threaded sequential processing and if I wrote my single-threaded programs the way I described in the examples, then I would deserve infinite loops because I am creating them. I would no doubt expect them too! But what if I am doing multi-threaded programming? I may want my loop-invariant flag not to be loop-invariant because, even though the initial value of the flag is set by one thread and a particular snippet of code, I may update the flag with a different thread and a different snippet of code but want the results to be reflected in how the loop of the first thread and first snippet of code executes. To this end, we write the following snippet of code:


    public static void main(String[] args) {
    
    	processSomeData();
    
    	ANewThread newThread = new ANewThread();
    
    	new Thread(newThread).start();
    
    	...
    
    	newThread.stopThread(); // Done with thread so stop it!
    
    	processSomeMoreData();
    
    }
    


    And to it we add the implementation of class ANewThread:


    public class ANewThread implements Runnable {
    
    	private boolean flag = true; // Our old flag friend!
    
    	public void stopThread() {
    		flag = false;
    	}
    
    	@Override
    	public void run() {
    		while(flag) {
    			// do something
    		}
    	}
    
    }
    


    We then say to ourselves, "Look! I have the main thread, I create an object and I spawn another thread with that object, then I stop the thread using the same object! Everything is cool...right?"

    To this I say, "Regrettably, no. Everything is not cool." For the reasons mentioned above and in the book, the while loop of the run method of class ANewThread may reasonably be turned into and infinite loop by a conversion similar to the previous example, or, the newly spawned thread may never read the update to the flag variable in the call to stopThread() made in the main method. To this you say, "Dude, are you crazy? I could see the compiler turning the loop for the thread into an infinite one if I did not make a call to stopThread(). If I did not make the call this would be a cool optimization. When I call stopThread() I mean for the value of the flag variable to be updated and consequently for the loop to stop. Heck, the fact that I created the stopThread() method indicates that I want the loop to stop based on the variable flag. Can you not see the context?"

    To these points I say, "I feel ya. I definitely get the context and what you intended. Don't talk to me talk to the compiler. If you were writing your own language and compiler then maybe you could figure out the context any way that you wished. However, this is Java and Java has a clearly defined way to indicate your context. Therefore, you would need to declare the flag variable in the ANewThread class to be volatile." You are now dealing with two separate threads, the main thread and the one from class ANewThread so some indication has to be made as to your intentions i.e. how one thread can influence the other. This is not the only way that context can be communitated of course. There is also synchronization etc but I am not dealing with that here.

    For this sort of thing we have the Java Memory Model (JMM) and the semantics of the volatile keyword. In the JMM, a variable declared volatile has the following implications which are germane to this discussion:

  • The compiler is not allowed to reorder the instructions on a volatile variables with respect to other memory operations (yep! no code motion for you var!).
  • A variable of type volatile being read by one thread will see the latest update of its value by writes that occur by other threads.
  • These two facts mean that the memory operations involving a volatile variable that you use as a flag in a loop will not be reorder by hoisting it out of the loop and reading it once. The loop will read the latest value of the variable each time the loop executes to see if there are updates to the value. The compiler becomes aware of a new multi threaded context in with the statements are being used. In more formal terms, we say that the use of the volatile keyword introduces a partial ordering between actions of one thread and another. In the JMM parlance, this partial ordering is termed "happens-before". This topic is well covered elsewhere so I need not go into details. The aforementioned book is an excellent resource for an exposition on this.

    In other words, you signal to the compiler that you mean for your loop flag variables to be written to and read by multiple threads by declaring them to be volatile. You are saying that the single-threaded context where the reordering is semantically correct is no longer valid. This way, you and your friend the complier communicate clearly, you know that he ain't crazy and it is all good!

    Perhaps the last thing to mention is that this sort of behavior (threads not seeing updates and hoisting) occurs under the following circumstances respectively:

  • A multiprocessor environment where each thread can run on a different processor and there may one cache per processor with one shared main memory (the common model these days).
  • If you turn on optimizations with the -server command line option when invoking the JVM.
  • That being said, write your threading code as if it were going to run on a multiprocessor machine with the -server option invoked for the JVM!

    Now isn't all of that really cool?

    0 votes, average: 0.00 out of 50 votes, average: 0.00 out of 50 votes, average: 0.00 out of 50 votes, average: 0.00 out of 50 votes, average: 0.00 out of 5 (0 votes, average: 0.00 out of 5)
    You need to be a registered member to rate this post.
    Loading...Loading...
    Tags:
    Categories: Technical Solutions

    Disclaimer: As with everything else at NetIQ Cool Solutions, this content is definitely not supported by NetIQ, so Customer Support will not be able to help you if it has any adverse effect on your environment.  It just worked for at least one person, and perhaps it will be useful for you too.  Be sure to test in a non-production environment.

    Leave a Reply

    No Comments
    By: dcthorpe
    Oct 19, 2010
    3:01 pm
    Reads:
    1,801
    Score:
    Unrated