![]() | |
|
Compare and swap (CAS)
The first processors that supported concurrency provided atomic test-and-set operations, which generally operated on
a single bit. The most common approach taken by current processors, including Intel and Sparc processors, is to implement
a primitive called compare-and-swap, or CAS. (On Intel processors, compare-and-swap is implemented by the cmpxchg
family
of instructions. PowerPC processors have a pair of instructions called "load and reserve" and "store conditional" that
accomplish the same goal; similar for MIPS, except the first is called "load linked.")
A CAS operation includes three operands - a memory location (V), the expected old value (A), and a new value (B). The processor will atomically update the location to the new value if the value that is there matches the expected old value, otherwise it will do nothing. In either case, it returns the value that was at that location prior to the CAS instruction. (Some flavors of CAS will instead simply return whether or not the CAS succeeded, rather than fetching the current value.) CAS effectively says "I think location V should have the value A; if it does, put B in it, otherwise, don't change it but tell me what value is there now."
The natural way to use CAS for synchronization is to read a value A from an address V, perform a multistep computation to derive a new value B, and then use CAS to change the value of V from A to B. The CAS succeeds if the value at V has not been changed in the meantime.
Instructions like CAS allow an algorithm to execute a read-modify-write sequence without fear of another thread modifying the variable in the meantime, because if another thread did modify the variable, the CAS would detect it (and fail) and the algorithm could retry the operation. Listing below illustrates the behavior (but not performance characteristics) of the CAS operation, but the value of CAS is that it is implemented in hardware and is extremely lightweight (on most processors):
public class SimulatedCAS { private int value; public synchronized int getValue() { return value; } public synchronized int compareAndSwap(int expectedValue, int newValue) { int oldValue = value; if (value == expectedValue) { value = newValue; } return oldValue; } }
Concurrent algorithms based on CAS are called lock-free, because threads do not ever have to wait for a lock (sometimes called a mutex or critical section, depending on the terminology of your threading platform). Either the CAS operation succeeds or it doesn't, but in either case, it completes in a predictable amount of time. If the CAS fails, the caller can retry the CAS operation or take other action as it sees fit. Listing below shows the counter class written to use CAS:
public class CASCounter { private SimulatedCAS value = new SimulatedCAS(); // starts with 0 public int getValue() { return value.getValue(); } public int increment() { int oldValue = value.getValue(); while (value.compareAndSwap(oldValue, oldValue + 1) != oldValue) { oldValue = value.getValue(); } return oldValue + 1; } }
Lock-free and wait-free algorithms
An algorithm is said to be wait-free if every thread will continue to make progress in the face of arbitrary delay (or even failure) of other threads. By contrast, a lock-free algorithm requires only that some thread always make progress.
Nonblocking algorithms are used extensively at the operating system and JVM level for tasks such as thread and process scheduling. While they are more complicated to implement, they have a number of advantages over lock-based alternatives - hazards like priority inversion and deadlock are avoided, contention is less expensive, and coordination occurs at a finer level of granularity, enabling a higher degree of parallelism.
Until Java SE 5, it was not possible to write wait-free, lock-free algorithms in the Java language without
using native code. With the addition of the atomic variables classes in the java.util.concurrent.atomic
package, that has changed. The atomic variable classes all expose a compare-and-set primitive (similar to
compare-and-swap), which is implemented using the fastest native construct available on the platform
(compare-and-swap, load linked/store conditional, or, in the worst case, spin locks). Nine flavors of
atomic variables are provided in the java.util.concurrent.atomic
package (AtomicInteger
;
AtomicLong
; AtomicReference
; AtomicBoolean
; array forms of atomic integer;
long; reference; and atomic marked reference and stamped reference classes, which atomically update a pair of values).
The atomic variable classes can be thought of as a generalization of volatile variables, extending the concept of volatile variables to support atomic conditional compare-and-set updates. Reads and writes of atomic variables have the same memory semantics as read and write access to volatile variables.
Operations on atomic variables get turned into the hardware primitives that the platform provides for concurrent access, such as compare-and-swap.
Java Atomic Operations
In Java the integer primitive increment operation is not an atomic operation. When an integer is incremented, the following logical steps are performed by the JVM:
Retrieve the value of the integer from memory
Increment the value
Assign the newly incremented value back to the appropriate memory location
Return the value to the caller
So while we write the increment operator in a single line of Java code, such as:
int n = i++;
Each one of the aforementioned steps occurs in the JVM. The danger is that if you have multiple threads that all try to increment the same value, there is a chance that two or more of the threads will get the same value (step #1), then increment it (step #2), and then assign the new value to it (step #3). If two threads increment the number 5 then you would expect to see 7 but instead both increment the number 5, yielding a result of 6, and then assign 6 back to the integer's memory location.
With the release of Java SE 5, Sun included a java.util.concurrent.atomic
package that addresses this
limitation. And specifically they added classes including the following:
AtomicBoolean
- A boolean
value that may be updated atomically. An AtomicBoolean
is used in applications such as atomically updated flags, and cannot be used as a replacement for a Boolean
.
AtomicInteger
- An int
value that may be updated atomically. An AtomicInteger
is
used in applications such as atomically incremented counters, and cannot be used as a replacement for an Integer
.
However, this class does extend Number
to allow uniform access by tools and utilities that deal with
numerically-based classes.
AtomicIntegerArray
- An int
array in which elements may be updated atomically.
AtomicLong
- A long
value that may be updated atomically. An AtomicLong
is used
in applications such as atomically incremented sequence numbers, and cannot be used as a replacement for a Long
.
However, this class does extend Number
to allow uniform access by tools and utilities that deal with
numerically-based classes.
AtomicLongArray
- A long
array in which elements may be updated atomically.
Each of these atomic classes provides methods to perform common operations, but each one is ensured to be performed as a single atomic operation. For example, rather than incrementing an integer using the standard increment operator, like the following:
int n = ++i;
You can ensure that the (1) get value, (2) increment value, (3) update memory, and (4) assign the new value to n
is
all accomplished without fear of another thread interrupting your operation by writing you code as follows:
AtomicInteger ai = new AtomicInteger(0); int n = ai.incrementAndGet();
In addition, the AtomicInteger
class provides the following operations:
int addAndGet(int delta)
- Add delta
to the integer and then return the new value.
int decrementAndGet()
- Decrement the integer and return its value.
int getAndAdd(int delta)
- Return the value and then add delta
to it.
int getAndDecrement()
- Return the value and then decrement.
int getAndIncrement()
- Return the value and then increment it.
int getAndSet(int newValue)
- Return the value and then set it to the newValue
Locks in Java
A lock is a thread synchronization mechanism like synchronized
blocks except locks can be more sophisticated
than Java's synchronized
blocks.
From Java SE 5 the package java.util.concurrent.locks
contains several lock implementations, so you may not have
to implement your own locks:
The Lock
interface supports locking disciplines that differ in semantics (reentrant, fair, etc),
and that can be used in non-block-structured contexts including hand-over-hand and lock reordering algorithms.
The main implementation is ReentrantLock
.
The ReadWriteLock
interface similarly defines locks that may be shared among readers but are exclusive to
writers. Only a single implementation, ReentrantReadWriteLock
, is provided, since it covers most standard
usage contexts. But programmers may create their own implementations to cover nonstandard requirements.
The Condition
interface describes condition variables that may be associated with Lock
s. These
are similar in usage to the implicit monitors accessed using Object.wait()
, but offer extended capabilities.
In particular, multiple Condition
objects may be associated with a single Lock
. To avoid
compatibility issues, the names of Condition
methods are different than the corresponding Object
versions.
The AbstractQueuedSynchronizer
class serves as a useful superclass for defining locks and other synchronizers that
rely on queuing blocked threads. The LockSupport
class provides lower-level blocking and unblocking support that is
useful for those developers implementing their own customized lock classes.
Let's start out by looking at a synchronized
block of Java code:
public class Counter {
private int count = 0;
public int inc() {
synchronized (this) {
return ++count;
}
}
}
Notice the synchronized(this)
block in the inc()
method. This block makes sure that only one thread can execute the
return ++count
at a time.
The purpose of the synchronized
keyword is to provide the ability to allow serialized entrance to synchronized
methods in an object. Although almost all the needs of data protection can be accomplished with this keyword, it is too
primitive when the need for complex synchronization arises. More complex cases can be handled by using classes that achieve
similar functionality as the synchronized
keyword. These classes are available beginning in Java SE 5.
The synchronization tools in Java SE 5 implement a common interface: the Lock
interface. For now, the two methods
of this interface that are important to us are lock()
and unlock()
. Using the Lock
interface
is similar to using the synchronized
keyword: we call the lock()
method at the start of the method and
call the unlock()
method at the end of the method, and we have effectively synchronized the method.
The lock()
method grabs the lock. The difference is that the lock can now be more easily envisioned: we now have an actual
object that represents the lock. This object can be stored, passed around, and even discarded. As before, if another thread owns the
lock, a thread that attempts to acquire the lock waits until the other thread calls the unlock()
method of the lock. Once
that happens, the waiting thread grabs the lock and returns from the lock()
method. If another thread then wants the
lock, it has to wait until the current thread calls the unlock()
method.
The Counter
class could have been written using a Lock
instead of a synchronized
block:
import java.util.concurrent.locks.Lock; import java.util.concurrent.locks.ReentrantLock; public class Counter { private Lock lock = new ReentrantLock(); private int count = 0; public int inc() { lock.lock(); try { return ++count; } finally { lock.unlock(); } } }
![]() ![]() ![]() |