What is the CAS

(1) CAS(compare and swap) is a technique used in thread concurrency algorithms (2) CAS is an atomic operation that guarantees concurrent safety, not concurrent synchronization (3) CAS is an instruction of the CPU (4) CAS is a non-blocking, lightweight optimistic lock

Why is CAS an optimistic lock

Optimistic locks, which are not strictly locks, ensure data synchronization through atomicity, such as optimistic locks for databases, through version control, etc., so CAS does not guarantee thread synchronization. It is optimistic that no other threads will affect the data during the update

The CAS theory

CAS(compare and swap) is used to update the memory value to the required value, but the memory value must be the same as the expected value. For example, the expected value E, the memory value M, and the updated value U update M to U when E == M.

The CAS application

As the CAS is CPU instructions, we can only through the JNI interaction with the operating system, methods of CAS in the sun. The misc package under the Unsafe class in Java. Util. Concurrent. The atomic package under the atomic classes by CAS, such as atomic operations.

CAS, for example,

/**
 * Created by Dell on 2018/2/6.
 */
public class CasLock {
    private static final CountDownLatch latch = new CountDownLatch(5);
    private static AtomicInteger i = new AtomicInteger(0);
    private static int p = 0;

    public static void main(String[] args) throws InterruptedException {
        long time = System.currentTimeMillis();
        ExecutorService pool = Executors.newFixedThreadPool(5);
        for(int j = 0; j < 5; j++) {
            pool.execute(new Runnable() {
                public void run() {
                    for(int k = 0; k < 10000; k++) { p++; // not atomic operation i.getandincrement (); // Call the atomic class with 1} latch.countdown (); }}); } latch.await(); System.out.println(system.currentTimemillis () -time); System.out.println("p=" + p);
        System.out.println("i="+ i); pool.shutdown(); }}Copy the code

The output

"C: \ Program Files \ Java \ jdk1.8.0 _91 \ bin \ Java". 8 P =43204// The result is incorrectexit code 0
Copy the code

According to the result, we find that the result is incorrect due to multiple threads asynchronously performing p++ operation. Why is the demerit p++ incorrect? Let’s say two threads read that p is 1, add 1, p is 2, not 3 and the variable I is correct, thanks to CAS. Now let’s look at the atomic class.

CAS instruction and specific source code

Methods in atomic classes such as AtomicInteger are very simple, and you can understand them. Let’s look at getAndIncrement. Post the code below:

// This method is Interger plus 1 public final intgetAndIncrement() {// Focus on the getAndAddInt methodreturnunsafe.getAndAddInt(this, valueOffset, 1); } //var1 is this pointer //var2 is the address offset //var4 is the increment value, N Public Final int getAndAddInt(Object var1, Long var2, int var4) {int var5;do{// Get the memory value, which is already old, assuming we call the expected value E var5 = this.getIntVolatile(var1, var2); // Call the JNI of CAS. Each thread compares its memory value M with the expected value E of var5. Update M to var5 + var4 if the same, otherwise do spin}while(! this.compareAndSwapInt(var1, var2, var5, var5 + var4));return var5;
    }
Copy the code

The getAndAddInt method assumes the following scenario: 1. Two threads, A and B; 2. The main memory of the JVM is 1, and the working memory of A and B is 1 (the working memory copies the main memory value) 3. (1) thread A compares working memory (M) (var5 = 1, var4 = 1) (2) thread A compares working memory (M) (var5 = 1, var4 = 1) (2) thread A compares working memory (M) (M) (var5 = 1, var4 = 1) This pointer at this time, the sample value of the variable value is 2, the end of the cycle (3) if they are not the same thread B changes the value of the the main memory that thread B already done before A thread 1 operation, A thread didn’t updated the need to continue to cycle, note var5 updates for the new memory value right now, assuming that the current memory value is 2, If var5 = 2 and var5 + var4 = 3, repeat the above steps until successful

The following is the source of the compareAndSwapInt local method. You can see that CAS is implemented using the CMPXCHG directive, which has a good performance in efficiency.

UNSAFE_ENTRY(jboolean, Unsafe_CompareAndSwapInt(JNIEnv *env, jobject unsafe, jobject obj, jlong offset, jint e, jint x))
  UnsafeWrapper("Unsafe_CompareAndSwapInt");
  oop p = JNIHandles::resolve(obj);
  jint* addr = (jint *) index_oop_from_field_offset_long(p, offset);
  return (jint)(Atomic::cmpxchg(x, addr, e)) == e;
UNSAFE_END
Copy the code

CAS pros and cons

  • Advantages Non-blocking lightweight optimistic lock is implemented by CPU instructions and has high performance when resource competition is not fierce. Compared with synchronized weight lock, synchronized performs more complex locking, unlocking, and awakening operations.
  • (1) ABA problem Thread C, thread D, and thread D change Ato B and then to A, thread C thinks that A has not changed, and controls the version of the Java atom class AtomicStampedReference to ensure the correctness of CAS. (2) The spin time is too long, which consumes CPU resources. If the resource competition is fierce, the multi-thread spin will consume resources for a long time.

CAS summary

CAS is not only an optimistic locking, is a kind of thought, we can also in the daily project through similar CAS operation to ensure the safety of data, but not for all occasions, have seen post said, it can use synchronized don’t use the CAS, unless meet performance bottlenecks, because the CAS will make the code readability, these words do not see how you understand it.