The main goal of this project is to describe compare and swap as a way of resolving concurrency problems and provide basic examples (using Atomic classes).
Reference: https://dzone.com/articles/how-cas-compare-and-swap-java
Reference: https://www.javaworld.com/article/2078848/java-concurrency/java-concurrency-java-101-the-next-generation-java-concurrency-without-the-pain-part-2.html?page=3
Reference: http://tutorials.jenkov.com/java-concurrency/compare-and-swap.html
Reference: WJUG #136 - java.util.concurrent.atomic - Tomasz Nurkiewicz
The compare-and-swap (CAS) instruction is an uninterruptible instruction that reads a memory location, compares the read value with an expected value, and stores a new value in the memory location when the read value matches the expected value. Otherwise, nothing is done. The actual microprocessor instruction may differ somewhat (e.g., return true if CAS succeeded or false otherwise instead of the read value).
- Read value v from address X.
- Perform a multistep computation to derive a new value v2.
- Use CAS to change the value of X from v to v2. CAS succeeds when X's value hasn't changed while performing these steps.
CAS offers better performance (and scalability) over synchronization.
Java's traditional synchronization mechanism (synchronized
keyword)
impacts hardware utilization and scalability:
- Multiple threads constantly competing for a lock = frequent context switching (can take many processor cycles).
- When a thread holding a lock is delayed (e.g., because of a scheduling delay), no thread that requires that lock makes any progress.
We want to make this code thread-safe
class MyLock {
private boolean locked = false;
boolean lock() {
if(!locked) {
locked = true;
return true;
}
return false;
}
}
We have two approaches:
- synchronization using synchronized
note that calling synchronized (instance) method will block all other calls of synchronized (instance) methods on a given object
class MyLock { private boolean locked = false; synchronized boolean lock() { if(!locked) { locked = true; return true; } return false; } }
- synchronization using CAS
class MyLock { private AtomicBoolean locked = new AtomicBoolean(false); boolean lock() { return locked.compareAndSet(false, true); } }
Java 5 introduced a synchronization alternative that offers mutual
exclusion combined with the performance of volatile. Atomic
variable alternative is based on a microprocessor's compare-and-swap
instruction and largely consists of the types in the
java.util.concurrent.atomic
package.
For more info about Atomic classes in java, please refer my other github project: https://github.com/mtumilowicz/java11-atomic
The easiest implementation in java will be:
class EmulatedCAS {
private int value;
public synchronized int getValue() {
return value;
}
public synchronized int compareAndSwap(int expectedValue, int newValue) {
int readValue = value;
if (readValue == expectedValue)
value = newValue;
return readValue;
}
}
class Counter {
private EmulatedCAS value = new EmulatedCAS();
public int getValue() {
return value.getValue();
}
public int increment() {
int readValue = value.getValue();
while (value.compareAndSwap(readValue, readValue + 1) != readValue)
readValue = value.getValue();
return readValue + 1;
}
}
Note that increment()
is not synchronized, but compareAndSwap is.
We provide three classes (based on Atomic variables):
CounterService
public final int getAndIncrement() { return unsafe.getAndAddInt(this, valueOffset, 1); } public final int getAndAddInt(Object var1, long var2, int var4) { int var5; do { var5 = this.getIntVolatile(var1, var2); } while(!this.compareAndSwapInt(var1, var2, var5, var5 + var4)); return var5; }
EvenService
public final int getAndUpdate(IntUnaryOperator updateFunction) { int prev, next; do { prev = get(); next = updateFunction.applyAsInt(prev); } while (!compareAndSet(prev, next)); return prev; }
FibonacciService
- we use
AtomicReference
public final class FibonacciService { private final AtomicReference<Fibonacci> fibonacci = new AtomicReference<>(Fibonacci.FIRST); public int next() { return fibonacci.getAndUpdate(Fibonacci::next).get(); } }
Fibonacci
class is (in fact) an immutable Tuplepublic final class Fibonacci { public static final Fibonacci FIRST = new Fibonacci(0, 1); private final int left; private final int right; private Fibonacci(int left, int right) { this.left = left; this.right = right; } public Fibonacci next() { return new Fibonacci(right, left + right); } public int get() { return right; } // equals, hashcode }
- we use
note that before java 8, to perform some function on atomic value (for example - double it)
we have to use compareAndSet
in an do-while loop
int prev;
do {
prev = atom.get();
} while (!atom.compareAndSet(prev, prev * 2));
now, we have dedicated methods in atomic classes: updateAndGet
and accumulateAndGet