Those of you who have studied multithreading have seen the concept of CAS, which stands for compact-and-swap, so what does it do? Why can synchorinzed be replaced?

CAS

CAS (compare-and-swap) is a common technique for designing concurrency algorithms. The USE of CAS operations can be used to guarantee atomicity of variable updates.

The CAS operation involves three values:

  • VCurrent value: The current value of the variable in memory
  • AExpected value: the current in-memory value of the expected variable
  • BUpdated value: Ready to assign a new value to a variable

The CAS operation logic is as follows: THE CAS compares the values of V and A. If the values are equal, the variable value is updated to B. Otherwise, no operation is performed. The diagram below:

If you first encounter the concept of CAS, you may be confused about its operation logic. Why do you do nothing when you assign when you are equal and not equal? Here’s an example of an increment operation:

/** * Atomically increments by one the current value. * * @return the updated value */ public final int incrementAndGet() { for (;;) {// Get the current value, which in this example is also the expected value of 'CAS' int current = get(); Int next = current + 1; If (compareAndSet(current, next)) {if (compareAndSet(current, next)) {if (compareAndSet(current, next)) { }}}Copy the code

We now have threads A and B. When thread A executes the CAS operation and gets the current value, expected value, and update value of 0, 0, and 1, thread A is suspended. Thread B enters the CAS operation and updates the value of the variable to 1 successfully. Thread A continues to perform the CAS operation. Because the current value of the variable has been modified at this time, the CAS execution fails.

CAS VS synchorinzed

From the above example, we know that CAS guarantees atomicity of variable updates, which in turn brings to mind the functional flaws of the volatile keyword.

The volatile keyword works as follows:

  • Order: prevent reordering;
  • Visibility: All threads can access the latest value of a variable when it is updated;
  • Atomicity: The atomicity of a single read and write operation is guaranteed.

The flaw with the volatile keyword is that it does not guarantee atomicity of variable operations, such as the unary operators ++, –, which involve both read and write operations. So it’s common to see volatile and synchorinzed keyword sharing to ensure atomicity of variable operations, and CAS to ensure atomicity of variable operations. Can CAS replace synchorinzed? In some cases, yes.

For example, in the example above, the internal source of AtomicInteger().getAndIncrement() is as follows:

/** * Atomically increments by one the current value. * * @return the previous value */ public final int getAndIncrement() { return U.getAndAddInt(this, VALUE, 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; }Copy the code

You can see that volatile + CAS is used to secure variable operations.

The following is a comparison of the use of CAS and synchorinzed from the following two aspects:

Functional limitations:

  • CASMore lightweight,synchorinzedThe upgrade to a weight lock affects system performance.
  • CASCan only guarantee atomicity for single variable operations,synchorinzedAtomicity is guaranteed for all variable operations within a code block.

Concurrency scale:

  • Low concurrency:CASMore advantageous,synchorinzedIn rare cases, it is still possible to upgrade to a weight lock and affect system performance.
  • High concurrency:synchorinzedMore advantageous becauseCASMany implementations of “spin” (described below) use spin operationsAtomic***Series) when in the case of a large number of threadsCASFrequent execution failures and frequent retries are wastefulCPUResources.

Conclusion: Volatile + CAS can be used instead of volatile + synchorinzed when there are a few threads and only a single variable is thread-safe.

Note: Volatile + CAS and volatile + synchorinzed should be used with an understanding of their respective roles and functions:

  • volatile: Ensure order and visibility;
  • CAS,synchorinzed: Ensures the atomicity of the operation.

Note: The correct use of CAS in a multithreaded environment must be accompanied by the volatile keyword. Because CAS guarantees atomicity, it does not guarantee the safety of variables in different thread memory Spaces, volatile is needed to ensure that variable updates are visible to different threads.

ABA problem

In addition to the two disadvantages of CAS mentioned above:

  • Only atomicity of single variable operations can be guaranteed;
  • In high concurrencyCASKeep failing will keep trying again, wasteCPUResource injection. One idea for this problem is to introduce an exit mechanism, such as a failed exit after the number of retries exceeds a certain threshold. Of course, it’s more important to avoid using it in high-concurrency environmentsCAS.

Another problem is the ABA problem, existing threads A and B:

  1. thread1Read data in memory asA;
  2. thread2Example Change memory data toB;
  3. thread2Example Change memory data toA;
  4. thread1Execute on dataCASOperation.

In the fourth step, the memory data is still A, but the data has been modified. That’s the ABA problem. To solve the ABA problem, the version number can be introduced. Each time the value in memory is modified, the version number is +1. When the CAS operation is performed, not only the value in memory but also the version number are compared. Java provided in Java. Util. Concurrent. Atomic. AtomicStampedReference is through the version number to solve the problem of ABA.

Use in Android

In Android we can also use volatile + CAS with the Atomic class.

  • AtomicFile
  • AtomicInteger
  • AtomicLong
  • AtomicBoolean
  • AtomicReferenceFieldUpdater
  • AtomicStampedReference

If the data is a String or of an unknown type, what can we do? If the data is a String or of an unknown type, what can we do? This time you can use the AtomicReferenceFieldUpdater (). In Kotlin. Lazy were used in the implementation of the AtomicReferenceFieldUpdater:

private class SafePublicationLazyImpl<out T>(initializer: () -> T) : Lazy<T>, Serializable { @Volatile private var initializer: (() -> T)? = initializer @Volatile private var _value: Any? = UNINITIALIZED_VALUE // this final field is required to enable safe initialization of the constructed instance private val final: Any = UNINITIALIZED_VALUE override val value: T get() { val value = _value if (value ! == UNINITIALIZED_VALUE) { @Suppress("UNCHECKED_CAST") return value as T } val initializerValue = initializer // if we see null in initializer here, it means that the value is already set by another thread if (initializerValue ! = null) { val newValue = initializerValue() if (valueUpdater.compareAndSet(this, UNINITIALIZED_VALUE, newValue)) { initializer = null return newValue } } @Suppress("UNCHECKED_CAST") return _value as T } ...... companion object { private val valueUpdater = java.util.concurrent.atomic.AtomicReferenceFieldUpdater.newUpdater( SafePublicationLazyImpl::class.java, Any::class.java, "_value" ) } }Copy the code

AtomicReferenceFieldUpdater by static newUpdater method () for instance objects. The newUpdater() method takes three arguments:

  • tclass: of the class where the target variable residesclassObject;
  • vclass: Specifies the type of the target variableclassObject;
  • fieldName: Specifies the name of the target variable.

The kotlin.lazy source code above ensures that only the first assignment is valid in a multithreaded environment by comparing the initial values:

valueUpdater.compareAndSet(this, UNINITIALIZED_VALUE, newValue)
Copy the code

The AtomicStampedReference is initialized as follows:

public AtomicStampedReference(V initialRef, int initialStamp) {
}
Copy the code

You can see that the initialization method takes two arguments:

  • The initial value
  • Think of it as the initial version number

The usage is as follows:

private val atomicObj: AtomicStampedReference<String> = AtomicStampedReference("A", 0)

val t1 = Thread {
    try {
        TimeUnit.SECONDS.sleep(1)
    } catch (e: InterruptedException) {
    }
    println("run thread1")
    atomicObj.compareAndSet("A", "B", atomicObj.stamp, atomicObj.stamp + 1)
    atomicObj.compareAndSet("B", "A", atomicObj.stamp, atomicObj.stamp + 1)
}

val t2 = Thread {
    val stamp: Int = atomicObj.stamp
    try {
        TimeUnit.SECONDS.sleep(2)
    } catch (e: InterruptedException) {
    }
    println("run thread2")
    val result: Boolean = atomicObj.compareAndSet("A", "B", stamp, stamp + 1)
    println(result) // false
}

t1.start()
t2.start()
Copy the code

As you can see, since Thread2 gets the version number in advance, even after Thread1 executes, the value is still A, but since the version number has changed, Thread2 will still execute false.