5.1 Can You Avoid Synchronization? - Java Threads, Third Edition

5.1 Can You Avoid Synchronization?

Developers of threaded programs are often paranoid about synchronization. There are many horror stories about programs that performed poorly because of excessive or incorrect synchronization. If there is a lot of contention for a particular lock, acquiring the lock becomes an expensive operation for two reasons:

• The code path in many virtual machine implementations is different for acquiring contended and uncontended locks. Acquiring a contended lock requires executing more code at the virtual machine level. The converse of this statement is also true, however: acquiring an uncontended lock is a fairly inexpensive operation.

• Before a contended lock can by acquired, its current holder must release it. A thread that wants to acquire a contended lock must always wait for the lock to be released.

Contended and Uncontended Locks The terms contended and uncontended refer to how many threads are operating on a particular lock. A lock that is not held by any thread is an uncontended lock: the first thread that attempts to acquire it immediately succeeds. When a thread attempts to acquire a lock that is already held by another thread, the lock becomes a contended lock. A contended lock has at least one thread waiting for it; it may have many more. Note that a contended lock becomes an uncontended one when threads are no longer waiting to acquire it.

In practical terms, the second point here is the most salient: if someone else holds the lock, you have to wait for it, which can greatly decrease the performance of your program. We discuss the performance of thread-related operations in Chapter 14.

This situation leads programmers to attempt to limit synchronization in their programs. This is a good idea; you certainly don't want to have unneeded synchronization in your program any more than you want to have unneeded calculations. But are there times when you can avoid synchronization altogether?

We've already seen that in one case the answer is yes: you can use the volatile keyword for an instance variable (other than a double or long). Those variables cannot be partially stored, so when you read them, you know that you're reading a valid value: the last value that was stored into the variable. Later in this chapter, we'll see another case where allowing unsychronized access to data is acceptable by certain classes.

But these are really the only cases in which you can avoid synchronization. In all other cases, if multiple threads access the same set of data, you must explicitly synchronize all access to that data in order to prevent various race conditions.

The reasons for this have to do with the way in which computers optimize programs. Computers perform two primary optimizations: creating registers to hold data and reordering statements.

5.1.1 The Effect of Registers

Your computer has a certain amount of main memory in which it stores the data associated with your program. When you declare a variable (such as the done flag used in several of our classes), the computer sets aside a particular memory location that holds the value of that variable.

Most CPUs are able to operate directly on the data that's held in main memory. Other CPUs can only read and write to main memory locations; these computers must read the data from main memory into a register, operate on that register, and then store the data to main memory. Yet even CPUs that can operate on data directly in main memory usually have a set of registers that can hold data, and operating on the data in the register is usually much faster than operating on the data in main memory. Consequently, register use is pervasive when the computer executes your code.

From a logical perspective, every thread has its own set of registers. When the operating system assigns a particular thread to a CPU, it loads the CPU registers with information specific to that thread; it saves the register information before it assigns a different thread to the CPU. So, threads never share data that is held in registers.

Let's see how this applies to a Java program. When we want to terminate a thread, we typically use a done flag. The thread (or runnable object) contains code, such as:

public void run( ) {

    while (!done) {

        foo( );

    }

}

public void setDone( ) {

    done = true;

}

Suppose we declare done as:

private boolean done = false;

This associates a particular memory location (e.g., 0xff12345) with the variable done and sets the value of that memory location to 0 (the machine representation of the value false).

The run() method is then compiled into a set of instructions:

Begin method run

Load register r1 with memory location 0Xff12345

Label L1:

Test if register r1 == 1

If true branch to L2

Call method foo

Branch to L1

Label L2:

End method run

Meanwhile, the setDone() method looks something like this:

Begin method setDone

Store 1 into memory location 0xff12345

End method setDone

You can see the problem: the run() method never reloads register r1 with the contents of memory location 0xff12345. Therefore, the run() method never terminates.

However, suppose we define done as:

private volatile boolean done = false;

Now the run() method logically looks like this:

Begin method run

Label L1:

Test if memory location 0xff12345 == 1

If true branch to L2

Call method foo

Branch to L1

Label L2:

End method

Using the volatile keyword ensures that the variable is never kept in a register. This guarantees that the variable is truly shared between threads.^[1]

^[1] The virtual machine can use registers for volatile variables as long as it obeys the semantics we've outlined. It's the principle that must be obeyed, not the actual implementation.

Remember that we might have implemented this code by synchronizing around access to the done flag (rather than making the done flag volatile). This works because synchronization boundaries signal to the virtual machine that it must invalidate its registers. When the virtual machine enters a synchronized method or block, it must reload data it has cached in its local registers. Before the virtual machine exits a synchronization method or block, it must store its l ocal registers to main memory.

5.1.2 The Effect of Reordering Statements

Developers often hope that they can avoid synchronization by depending on the order of execution of statements. Suppose that we decide to keep track of the total score among a number of runs of our typing game. We might then write the resetScore() method like this:

public int currentScore, totalScore, finalScore

public void resetScore(boolean done) {

    totalScore += currentScore;

    if (done) {

        finalScore = totalScore;

        currentScore = 0;

    }

}



public int getFinalScore( ) {

    if (currentScore == 0)

        return finalScore;

    return -1;

}

A race condition exists because we can have this order of execution by threads t1 and t2:

Thread1: Update total score

Thread2: See if currentScore == 0

Thread2: Return -1

Thread1: Update finalScore

Thread1: Set currentScore == 0

That's not necessarily fatal to our program logic. If we're periodically checking the score, we'll get -1 this time, but we'll get the correct answer next time. Depending on our program, that may be perfectly acceptable.

However, you cannot depend on the ordered execution of statements like this. The virtual machine may decide that it's more efficient to store 0 in currentScore before it assigns the final score. This decision is made at runtime based on the particular hardware running the program. In that case, we're left with this sequence:

Thread1: Update total score

Thread1: Set currentScore == 0

Thread2: See if currentScore == 0

Thread2: Return finalScore

Thread1: Update finalScore

Now the race condition has caused a problem: we've returned the wrong final score. Note that it doesn't make any difference whether the variables are defined as volatile: statements that include volatile variables can be reordered just like any other statements.

The only thing that can help us here is synchronization. If the resetScore() and getFinalScore() methods are synchronized, it doesn't matter whether the statements within methods are reordered since the synchronization prevents us from interleaving the thread execution of the methods.

Synchronized blocks also prevent the reordering of statements. The virtual machine cannot move a statement from inside a synchronized block to outside a synchronized block. Note, however, that the converse is not true: a statement before a synchronized block may be moved into the block, and a statement after a synchronized block may be moved into the block.

5.1.3 Double-Checked Locking

This design pattern gained a fair amount of attention when it was first proposed, but it has been pretty thoroughly discredited by now. Still, it pops up every now and then, so here are the details for the curious.

One case where developers are tempted to avoid synchronization deals with lazy initialization. In this paradigm, an object contains a reference that is time-consuming to construct, so the developer delays construction of the object:

Foo foo;

public void useFoo( ) {

    if (foo == null) {

        synchronized(this) {

            if (foo == null)

                foo = new Foo( );

        }

    }

    foo.invoke( );

}

The developer's goal here is to prevent synchronization once the foo object has been initialized. Unfortunately, this pattern is broken because of the reasons we've just examined. In particular, the value for foo can be stored before the constructor for foo is called; a second thread entering the useFoo() method would then call foo.invoke() before the constructor for foo has completed. If foo is a volatile primitive (but not a volatile object), this can be made to work if you don't mind the case where foo is initialized more than once (and where multiple initializations of foo are guaranteed to produce the same value).

For more information on the double-checked locking pattern as well as an extensive treatement of the Java memory model, see http://www.cs.umd.edu/~pugh/java/memoryModel/.