Peter is a senior software engineer for IBM and author of Practical Java Programming Language Guide (Addison-Wesley, 2000, ISBN 0-201-61646-7). He can be contacted at [email protected].
The Java Language Specification (JLS) guarantees that operations on 32 bits or less are atomic and therefore cannot be interrupted. To eliminate costly synchronization, some programmers try to achieve thread safety by relying on atomic operations. On 32-bit hardware, all primitive types except double and long are typically represented by 32 bits, with double and long typically represented by 64 bits. In addition, object references, implemented as native pointers, are typically 32 bits, too. I say "typically" because the "range of values" of primitive types is guaranteed by the language, not their storage size in the Java Virtual Machine (JVM). Therefore, an int always represents the same range of values on any compliant JVM implementation. Still, one JVM implementation might use 32 bits to represent an int, while another uses 64 bits. According to the JLS, this leads to two guarantees:
- The range of values represented by each primitive type is the same across all compliant JVM implementations.
- Operations on 32-bit, or smaller, values are atomic.
Given this, how can atomic operations not be threadsafe? The main point is that atomic operations can be threadsafe, but there is no guarantee that they are. The reason is that the JLS lets threads keep private working copies of variables separate from main memory. Therefore, main memory is not updated on each access to the variable, resulting in a performance optimization. For example, on a 32-bit machine, the class in Listing One contains two methods that set/return the clkID variable. The writing of the clkID variable in the setClockID method and the reading of it in the clockID method are both atomic operations. The clkID variable is an int, thus represented with 32 bits. Assuming Listing One is to be accessed by multiple threads concurrently and because of the atomic behavior of a 32-bit variable, you might leave out synchronization for performance benefits. However, consider Figure 1, which depicts one instance of the RealTimeClock class and two threads of execution (Thread 1 and Thread 2):
- Thread 1 calls the setClockID method passing 5.
- 5 is placed in the private working memory for Thread 1.
- Thread 1 is preempted by Thread 2.
- Thread 2 calls the setClockID method passing 10.
- 10 is placed in the private working memory for Thread 2.
- Thread 2 is preempted by Thread 1.
- Thread 1 calls the clockID method and returns 5 from its private working memory.
The call to clockID in Step 7 should return 10 since that is the last value set. However, 5 is returned because the read/writes were done to the private working memory of the thread. At no point was the variable in working memory reconciled with main memory. The read/writes of clkID are definitely atomic, but because of the allowance for this type of behavior in a JVM, not necessarily threadsafe. There is no guarantee that this problem will occur, but there is no guarantee it won't either.
Working copies of variables in threads are reconciled with main memory under two conditions:
- The variable is declared volatile.
- The variable is accessed within a synchronized method or block.
If a variable is declared volatile, it is reconciled with main memory on each access. In addition, if a variable is accessed within a synchronized method or block, it is reconciled when the lock is obtained at method or block entry, and when the lock is released at method or block exit. Therefore, either approach ensures this problem does not occur and guarantees that the call to clockID returns 10, the correct value.
The approach you choose can have performance implications depending on how often the variable is accessed. If concurrency is important and you are not updating many variables, consider using volatile. However, if you are updating many variables, volatile might be slower than synchronization. Remember that when variables are declared volatile, they are reconciled with main memory on every access. Conversely, when synchronized is used, the variables are reconciled with main memory only when the lock is obtained and released. However, synchronization makes the code less concurrent.
Consider using synchronized if you are updating many variables and don't want the cost of reconciling each of them with main memory on every access, or you want to eliminate concurrency for another reason.
The JLS states that the operations on 64-bit variables are guaranteed to be atomic if they are declared volatile. However, there is a bug in many JVM implementations with the volatile keyword and 64-bit variables.
Atomic Behavior, volatile, And 64-bit Variables
JVMs treat operations on nonvolatile 64-bit variables as two distinct 32-bit operations. This means that operations on double and long variables are not inherently atomic, as they are with 32-bit variables. However, the JLS proclaims that operations on 64-bit variables are atomic if they are declared volatile. Not only does this ensure atomicity, but it also ensures that private working copies of the variables are atomically reconciled with main memory on every access, and therefore do not need explicit synchronization. Unfortunately, many JVMs do not implement the semantics of the volatile keyword correctly. Therefore, relying on the proper behavior of 64-bit volatile variables is dangerous. Listing Two is a modified version of a program found on Bill Pugh's web site (http://www.cs.umd.edu/~pugh/java/memoryModel/) that demonstrates this problem.
The comments in Listing Two show the values for the variables for Thread 1 for all iterations of the loop except the first. On the first iteration of the loop, val is equal to 0, its initial value, and is set to the value of variable key at the bottom. To demonstrate the problem with volatile, Listing Two creates nine AtomicLong objects on nine different threads. Each object initializes its 64-bit key variable to a unique value. 00000001 00000001 is the value for Thread 1, 00000002 00000002 for Thread 2, and so on. When each thread enters its run method, it begins a loop that is set to execute 10 million times. The only variable shared between all nine threads is the static volatile variable val. This is a 64-bit value that should, after the first loop iteration, always equal its initial key value.
The code in the loop takes the 64-bit variable, val, and converts it into two 64-bit variables, temp1 and temp2. The variable temp1 only holds the high 32 bits of val, and temp2 only holds the low 32 bits of val. The code breaks apart the 64-bit variable into its two 32-bit halves. Each half should be identical, ensuring the consistency of the value. The code does this by taking val and assigning it to a temporary 64-bit long variable temp. It then shifts the bits in temp 32 places to the right, filling with zeros, and stores the result in temp1. Then it shifts the bits held in temp 32 places to the left, filling with zeros, and stores the result in temp2. Finally, it takes the bits held in temp2 and shifts them 32 places to the right, filling with zeros, and stores the result in temp2. Now, temp1 and temp2 should be equal. If they aren't, one of the two assignments involving the 64-bit variable val — temp =val; at the top of the loop and val=key; at the bottom — was not performed atomically as guaranteed by the language.
Since nine threads are executing this code concurrently and variable val is shared among all nine threads (because it is static), these assignments must be atomic to avoid the problem. Remember that 64-bit variables are normally treated as two separate 32-bit operations. However, because val is declared volatile, these assignments are supposed to be atomic. If temp1 and temp2 are not equal, their values are printed and the program stops. If volatile is implemented correctly, the program never displays any output. Running this code on a variety of JVMs shows that volatile does not guarantee atomic operations on 64-bit variables. Typical output of this code is something like this:
Saw: 100000003 <br> temp1 is:1<br> temp2 is:3<br>
This output means that when val was assigned to temp at the top of the loop, or key was assigned to val at the bottom, the lower 32 bits were written by Thread 3 and the upper 32 bits by Thread 1. When temp1 and temp2 are calculated, it proves that the reading/writing of the 64-bit variable val is not done atomically. This could happen because: For Thread 1, variable key equals 00000001 00000001 and for Thread 3, key equals 00000003 00000003. Then, consider the following sequence for the assignment val=key;:
- Thread 3 assigns 00000003 to the high 32 bits of variable val.
- Thread 1 preempts Thread 3 before it can write the low 32 bits.
- Thread 1 performs two 32-bit writes and assigns 00000001 00000001 to variable val.
- Thread 1 is preempted by Thread 3.
- Thread 3 completes its write by writing 00000003 to the low 32 bits of variable val.
- Variable val now equals 00000001 00000003 and the program stops.
Even if val=key; occurs atomically, there is still a problem at the top of the loop with temp=val;. Assume that for Thread 3 val is set to 00000003 00000003 with the assignment val=key; at the bottom. Then assume this sequence:
- Thread 3 begins to execute temp=val; at the top of the loop and reads the low 32 bits from val, 00000003, and writes it in the low 32 bits of temp.
- Thread 3 is then preempted by Thread 1.
- Thread 1 writes 64 bits, assigning 00000001 00000001 to val at the bottom of the loop.
- Thread 1 is preempted by Thread 3.
- Thread 3 completes its operation by reading the high 32 bits from val, 00000001, and writing them to the high 32 bits of variable temp.
- Variable temp now equals 00000001 00000003 and the program stops.
If volatile was implemented correctly, this scenario would not be possible. The 64-bit write operations would happen atomically and val would always be consistent. I tested the AtomicLong program on different JVMs with different run-time optimizers, each failing to implement the volatile semantics correctly. The JVMs I tested include the IBM JDK 1.3 for Windows, Sun JDK 1.2.1 for Windows, and Sun JDK 1.3 for Windows (classic, server, and hotspot VMs).
According to Bill Pugh's web site, there are other JVMs that do not implement the semantics of volatile correctly (this problem has been reported to JavaSoft as bug number 4023233). In fact, his testing reveals only one that does (the Sun Solaris JDK 1.2.2). Neither of us has tested every JVM, so this is not to say there are not other JVMs that implement the semantics of volatile correctly. Therefore, you should not rely on the stated semantics of volatile to access 64-bit variables in a threadsafe manner, unless you have tested your JVM.
64-Bit Variables & synchronized
Given that your JVM most likely does not implement volatile correctly, the only solution is to synchronize access to the shared 64-bit variables. This fixes the problem but is unfortunate because the use of synchronization reduces the concurrency of your code. Again, depending on your code, the use of synchronization to guarantee atomicity of 64-bit variables can be less desirable to the use of volatile. To work around the problem of volatile and guarantee atomicity with 64-bit variables, you need to add a synchronized block around both lines that access the 64-bit variable. The code at the top of the loop then looks like this:
// Place the assignment in a <br>
// synchronized block <br>
synchronized(AtomicLong.class)<br>
temp =val; <br>
//temp =00000001 00000001<br>
}</p>
while the code at the bottom of the loop then looks like this:
//Place the assignment in a <br>
// synchronized block <br>
synchronized(AtomicLong.class){<br>
val =key; //val should always = <br>
// 00000001 00000001 <br>
// for thread 1<br>
}</p>
This code synchronizes on the class literal, AtomicLong.class. The code does not synchronize on this, since that would let the different threads execute the assignment concurrently. Because there are nine threads, there are nine different objects represented by this. Synchronizing on the class literal, of which there is only one, ensures that only one thread executes the assignments in the synchronized block at a time. Running this code with the same JVMs as before results in each of them working properly.
Conclusion
Java supports atomic operations, but because of the way many JVMs are implemented, atomic operations are not necessarily threadsafe. You need synchronized or volatile to guarantee the correctness of atomic operations on 32 bits or less. According to the JLS, the use of volatile and synchronized should guarantee correctness of atomic operations of 64-bit variables as well. However, many JVMs do not implement the volatile keyword correctly, requiring syncronized to be used instead.
DDJ
Listing One
class RealTimeClock
{
private int clkID;
public int clockID()
{
return clkID;
}
public void setClockID(int id)
{
clkID =id;
}
//...
}
Listing Two
public class AtomicLong extends Thread
{
static volatile long val;
static int count =10000000;
long key;
AtomicLong(int k)
{
long temp =k;
key =(temp<<32)|temp; //key =00000001 00000001 for thread 1
} //key =00000002 00000002 for thread 2 etc
public void run()
{
for(int i =0;i <count;i++)
{
//This 64 bit assignment is supposed to be atomic since val is declared
//atomic
long temp =val;//temp =00000001 00000001
long temp1 =temp>>>32;//temp1 =00000000 00000001
long temp2 =temp<<32;//temp2 =00000001 00000000
temp2 =temp2>>>32;//temp2 =00000000 00000001
if (temp1 !=temp2)
{
System.out.println("Saw:"+Long.toHexString(temp));
System.out.println("temp1 is:"+Long.toHexString(temp1));
System.out.println("temp2 is:"+Long.toHexString(temp2));
System.exit(1);
}
//This 64-bit assignment is supposed to be atomic since val is
//declared volatile.temp1 should always equal temp2.
val =key;//val should always =00000001 00000001 for thread 1
}
}
public static void main(String args [] )
{
for(int t =1;t <10;t++)
new AtomicLong(t).start();
}
}
