【JUC系列第三篇】-CAS算法详解

版权声明:本文为博主原创文章,未经博主允许不得转载。如需授权请联系微信:878799579 https://blog.csdn.net/qq_878799579/article/details/85636250

作者 : 毕来生
微信: 878799579


1、CAS是什么?

CAS是英文单词(Compare-And-Swap)的缩写,中文意思是:比较并替换。CAS需要有3个操作数:内存地址V,旧的预期值A,即将要更新的目标值B。

CAS指令执行时,当且仅当内存地址V的值与预期值A相等时,将内存地址V的值修改为B,否则就什么都不做。整个比较并替换的操作是一个原子操作。

Cas乐观锁算法演示
【JUC系列第三篇】-CAS算法详解

CAS优缺点

优点:

  1. 解决了部分情况下原子操作的问题
  2. 并发量不是很高时cas机制会提高效率。

缺点:

  1. 同一时间只能保证一个共享变量的原子操作(针对多个共享变量操作。循环CAS无法保证操作原子性,需要考虑通过加锁来保证原子性)

  2. 循环时间比较长,且开销时间比较大 : 如果尝试CAS失败,则会一直进行尝试。如果一直不成功。会对CPU带来较大负担

  3. 经典ABA问题

    如果内存地址V初次读取的值是A,并且在准备赋值的时候检查到它的值仍然为A,那我们就能说它的值没有被其他线程改变过了吗?

    如果在这段期间它的值曾经被改成了B,后来又被改回为A,那CAS操作就会误认为它从来没有被改变过。这个漏洞称为CAS操作的“ABA”问题。Java并发包为了解决这个问题,提供了一个带有标记的原子引用类“AtomicStampedReference”,它可以通过控制变量值的版本来保证CAS的正确性。因此,在使用CAS前要考虑清楚“ABA”问题是否会影响程序并发的正确性,如果需要解决ABA问题,改用传统的互斥同步可能会比原子类更高效。

如何解决经典ABA问题以及源码分析

通过JDK中自带的AtomicStampedReference类可以解决ABA问题。附上核心解决方法

	/**
     * Atomically sets the value of both the reference and stamp
     * to the given update values if the
     * current reference is {@code ==} to the expected reference
     * and the current stamp is equal to the expected stamp.
     *
     * @param expectedReference the expected value of the reference(期望值)
     * @param newReference the new value for the reference(写入新值)
     * @param expectedStamp the expected value of the stamp(期望的状态值)
     * @param newStamp the new value for the stamp(新的状态值)
     * @return {@code true} if successful
     */
    public boolean compareAndSet(V   expectedReference,
                                 V   newReference,
                                 int expectedStamp,
                                 int newStamp) {
        Pair<V> current = pair;
        return
            expectedReference == current.reference &&
            expectedStamp == current.stamp &&
            ((newReference == current.reference &&
              newStamp == current.stamp) ||
             casPair(current, Pair.of(newReference, newStamp)));
    }

    private boolean casPair(Pair<V> cmp, Pair<V> val) {
        return UNSAFE.compareAndSwapObject(this, pairOffset, cmp, val);
    }


因为casPair核心方法时通过native关键字修饰。故不能直接查看对应class源码。

public final native boolean compareAndSwapObject(Object var1, long var2, Object var4, Object var5)

不能查看源码就能难住我们了?不存在的。

我们下载好openjdk源码后,将其导入到idea里该project的lib中,全局搜索。直接附上对应源码供大家参考

UNSAFE_ENTRY(jboolean, Unsafe_CompareAndSwapObject(JNIEnv *env, jobject unsafe, jobject obj, jlong offset, jobject e_h, jobject x_h))
  UnsafeWrapper("Unsafe_CompareAndSwapObject");
  oop x = JNIHandles::resolve(x_h); // 新值
  oop e = JNIHandles::resolve(e_h); // 预期值
  oop p = JNIHandles::resolve(obj);
  HeapWord* addr = (HeapWord *)index_oop_from_field_offset_long(p, offset);// 在内存中的具体位置
  oop res = oopDesc::atomic_compare_exchange_oop(x, addr, e, true);// 调用了另一个方法
  jboolean success  = (res == e);  // 如果返回的res等于e,则判定满足compare条件(说明res应该为内存中的当前值),但实际上会有ABA的问题
  if (success) // success为true时,说明此时已经交换成功(调用的是最底层的cmpxchg指令)
    update_barrier_set((void*)addr, x); // 每次Reference类型数据写操作时,都会产生一个Write Barrier暂时中断操作,配合垃圾收集器
  return success;
UNSAFE_END
上一篇:键入任意整数,将之从小到大输出


下一篇:PowerShell 脚本执行策略