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
Ref:
>> http://howtodoinjava.com/2014/06/13/compare-and-swap-cas-algorithm/
>> http://java.boot.by/ocpjp7-upgrade/ch04s03.html
