cas无锁队列实现的原理_cas无锁队列实现的原理

一、什么是CAS锁

概述

CAS的全称为Compare-And-Swap，直译就是对比交换。是一条CPU的原子指令，其作用是让CPU先进行比较两个值是否相等，然后原子地更新某个位置的值。经过调查发现，其实现方式是基于硬件平台的汇编指令，就是说CAS是靠硬件实现的，JVM只是封装了汇编调用，那些AtomicInteger类便是使用了这些封装后的接口。 简单解释：CAS操作需要输入两个数值，一个旧值(期望操作前的值)和一个新值，在操作期间先比较下在旧值有没有发生变化，如果没有发生变化，才交换成新值，发生了变化则不交换。

原理

CAS有3个操作数，位置内存值V，旧的预期值A，要修改的更新值B。

当且仅当旧的预期值A和内存值V相同时，将内存值V修改为B，否则什么都不做或重来 。

硬件级别保证

CAS是JDK提供的非阻塞原子性操作，它通过 硬件保证了比较-更新的原子性。

它是非阻塞的且自身原子性，也就是说这玩意效率更高且通过硬件保证，说明这玩意更可靠

示例代码

public class CASDemo { 
   
    public static void main(String[] args) { 
   
        AtomicInteger atomicInteger = new AtomicInteger(5);
        //期望时5，如果是5则改成2022
        System.out.println(atomicInteger.compareAndSet(5, 2022) + "\t" + atomicInteger.get());
        System.out.println(atomicInteger.compareAndSet(5, 2022) + "\t" + atomicInteger.get());
    }
}

输出结果

由于前面修改了，后面修改失败，故先true后false。

源码分析compareAndSet(int expect,int update)

compareAndSet()方法的源代码：

上面三个方法都是类似的，主要对4个参数做一下说明。

var1：表示要操作的对象

var2：表示要操作对象中属性地址的偏移量

var4：表示需要修改数据的期望的值

var5/var6：表示需要修改为的新值

引出来一个问题：UnSafe类是什么？

二、CAS底层原理

Unsafe

unsafe是CAS的核心类，由于Java方法无法直接访问底层系统，需要通过本地（native）方法来访问，Unsafe相当于一个后门，基于该类可以直接操作特定内存的数据。 Unsafe类存在于sun.misc包中 ，其内部方法操作可以像C的指针 一样直接操作内存，因为Java中CAS操作的执行依赖于Unsafe类的方法。

注意Unsafe类中的所有方法都是native修饰的，也就是说Unsafe类中的方法都直接调用操作系统底层资源执行相应任务

valueOffset

变量valueOffset，表示该变量值在内存中的 偏移地址 ，因为Unsafe就是根据内存偏移地址获取数据的

volatile

变量value用volatile修饰，保证了多线程之间的内存可见性。

源码分析

OpenJDK源码里面查看下 Unsafe.java

假设线程A和线程B两个线程同时执行getAndAddInt操作（分别跑在不同CPU上）：

1 AtomicInteger里面的value原始值为3，即主内存中AtomicInteger的value为3，根据JMM模型，线程A和线程B各自持有一份值为3的value的副本分别到各自的工作内存。

2 线程A通过getIntVolatile(var1, var2)拿到value值3，这时线程A被挂起。

3 线程B也通过getIntVolatile(var1, var2)方法获取到value值3，此时刚好线程B 没有被挂起 并执行compareAndSwapInt方法比较内存值也为3，成功修改内存值为4，线程B打完收工，一切OK。

4 这时线程A恢复，执行compareAndSwapInt方法比较，发现自己手里的值数字3和主内存的值数字4不一致，说明该值已经被其它线程抢先一步修改过了，那A线程本次修改失败， 只能重新读取重新来一遍了。

5 线程A重新获取value值，因为变量value被volatile修饰，所以其它线程对它的修改，线程A总是能够看到，线程A继续执行compareAndSwapInt进行比较替换，直到成功。

底层汇编

native修饰的方法代表是底层方法

Unsafe类中的compareAndSwapInt，是一个本地方法，该方法的实现位于unsafe.cpp中

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); 
// 先想办法拿到变量value在内存中的地址，根据偏移量valueOffset，计算 value 的地址 
  jint* addr = (jint *) index_oop_from_field_offset_long(p, offset); 
// 调用 Atomic 中的函数 cmpxchg来进行比较交换，其中参数x是即将更新的值，参数e是原内存的值 
  return (jint) (Atomic::cmpxchg(x, addr, e)) == e; 
UNSAFE_END 

(Atomic::cmpxchg(x, addr, e)) == e; （主要源码）

cmpxchg

调用 Atomic 中的函数 cmpxchg来进行比较交换，其中参数x是即将更新的值，参数e是原内存的值

return (jint) (Atomic::cmpxchg(x, addr, e)) == e;

unsigned Atomic:: cmpxchg (unsigned int exchange_value,volatile unsigned int* dest, unsigned int compare_value) {
    assert(sizeof(unsigned int) == sizeof(jint), "more work to do"); 
   /* 
   * 根据操作系统类型调用不同平台下的重载函数，这个在预编译期间编译器会决定调用哪个平台下的重载函数*/ 
    return (unsigned int)Atomic::cmpxchg((jint)exchange_value, (volatile jint*)dest, (jint)compare_value); 
} 

总结

你只需要记住：

• CAS是靠硬件实现的从而在硬件层面提升效率，最底层还是交给硬件来保证原子性和可见性
• 实现方式是基于硬件平台的汇编指令，在intel的CPU中(X86机器上)，使用的是汇编指令cmpxchg指令。

核心思想就是：比较要更新变量的值V和预期值E（compare），相等才会将V的值设为新值N（swap）如果不相等自旋再来。

三、原子引用

在上面我们知道AtomicInteger原子整型，那可否有其它原子类型呢？

比如说：AtomicBook、AtomicOrder

答案是肯定的。这里引入AtomicReference

AtomicReference示例

@Data
@AllArgsConstructor
class User{ 
   
    String username;
    int age;
}
public class AtomicReferenceDemo { 
   
    public static void main(String[] args) { 
   
        User z3 = new User("z3", 24);
        User li4 = new User("li4", 26);

        AtomicReference<User> atomicReferenceUser = new AtomicReference<>();

        atomicReferenceUser.set(z3);
        System.out.println(atomicReferenceUser.compareAndSet(z3, li4) + "\t" + atomicReferenceUser.get().toString());
        System.out.println(atomicReferenceUser.compareAndSet(z3, li4) + "\t" + atomicReferenceUser.get().toString());
    }
}

四、自旋锁，借鉴CAS思想

什么是自旋锁？

自旋锁是指尝试获取锁的线程不会立即阻塞，而是采用循环的方式 去尝试获取锁 ，

当线程发现锁被占用时，会不断循环判断锁的状态，直到获取。这样的好处是减少线程上下文切换的消耗，缺点是循环会消耗CPU 。

示例

题目：实现一个自旋锁
自旋锁好处：循环比较获取没有类似 wait 的阻塞。
通过 CAS 操作完成自旋锁。

public class SpinLockDemo { 
   
    AtomicReference<Thread> atomicReference = new AtomicReference<>();

    public void lock() { 
   
        Thread thread = Thread.currentThread();
        System.out.println(Thread.currentThread().getName() + "\t" + "---come in");
        while (!atomicReference.compareAndSet(null, thread)) { 
   

        }
    }

    public void unlock() { 
   
        Thread thread = Thread.currentThread();
        atomicReference.compareAndSet(thread, null);
        System.out.println(Thread.currentThread().getName() + "\t" + "---task over , unlock ...");
    }

    public static void main(String[] args) { 
   
        SpinLockDemo spinLockDemo = new SpinLockDemo();
        new Thread(() -> { 
   
            spinLockDemo.lock();
            try { 
   
                TimeUnit.MILLISECONDS.sleep(5000);
            } catch (Exception e) { 
   
                e.printStackTrace();
            }
            spinLockDemo.unlock();
        }, "A").start();

        new Thread(() -> { 
   
            spinLockDemo.lock();

            spinLockDemo.unlock();
        }, "B").start();

    }
}

输出结果

A线程先进，B线程后进。紧接着A线程等待，然后解锁，B线程在A线程解锁后才会解锁。

解析

A 线程先进来调用 myLock 方法自己持有锁 5 秒钟， B 随后进来后发现
当前有线程持有锁，不是 null ，所以只能通过自旋等待，直到 A 释放锁后 B 随后抢到。

这种自旋等待尝试的过程就是自旋锁。

五、CAS的缺点

循环时间长开销很大

我们可以看到getAndAddInt方法执行时，有个do while 。

如果CAS失败，会一直进行尝试。如果CAS长时间一直不成功，可能会给CPU带来很大的开销。

引出来ABA问题

ABA问题怎么产生的

CAS算法实现一个重要前提需要取出内存中某时刻的数据并在当下时刻比较并替换，那么在这个时间差类会导致数据的变化。

比如说一个线程one从内存位置V中取出A，这时候另一个线程two也从内存中取出A，并且线程two进行了一些操作将值变成了B，

然后线程two又将V位置的数据变成A，这时候线程one进行CAS操作发现内存中仍然是A，然后线程one操作成功。

尽管线程one的CAS操作成功，但是不代表这个过程就是没有问题的。

今天的文章cas无锁队列实现的原理_cas无锁队列实现的原理分享到此就结束了，感谢您的阅读。