用AtomicStampedReference解决ABA问题
悲观锁,乐观锁CAS、原子操作类的应用与浅析及Java8对其的优化
CAS(Compare and swap),即比较并交换,也是实现我们平时所说的【自旋锁或乐观锁】的核心操作。
CAS有3个操作数,内存值V,旧的预期值A,要修改的新值B。当且仅当预期值A和内存值V相同时,将内存值V修改为B,否则什么都不做。
public final boolean compareAndSet(boolean expect, boolean update)
它的实现很简单,【就是用 一个预期的值 和内存值进行比较,如果两个值相等,就用预期的值替换内存值,并返回 true。否则,返回 false】。
保证原子操作
任何技术的出现都是为了解决某些特定的问题, CAS 要解决的问题就是保证原子操作。原子操作是什么,原子就是最小不可拆分的,原子操作就是最小不可拆分的操作,也就是说操作一旦开始,就不能被打断,知道操作完成。在多线程环境下,原子操作是保证线程安全的重要手段。举个例子来说,假设有两个线程在工作,都想对某个值做修改,就拿自增操作来说吧,要对一个整数 i 进行自增操作,需要基本的三个步骤:
1、读取 i 的当前值;
2、对 i 值进行加 1 操作;
3、将 i 值写回内存;
假设两个进程都读取了 i 的当前值,假设是 0,这时候 A 线程对 i 加 1 了,B 线程也 加 1,最后 i 的是 1 ,而不是 2。这就是因为自增操作不是原子操作,分成的这三个步骤可以被干扰。如下面这个例子,10个线程,每个线程都执行 10000 次 i++ 操作,我们期望的值是 100,000,但是很遗憾,结果总是小于 100,000 的。
static int i = 0; public static void add() { i++; } private static class Plus implements Runnable { @Override public void run() { for ( int k = 0; k < 10000; k++ ) { add(); } } } public static void main( String[] args ) throws InterruptedException { Thread[] threads = new Thread[10]; for ( int i = 0; i < 10; i++ ) { threads[i] = new Thread( new Plus() ); threads[i].start(); } for ( int i = 0; i < 10; i++ ) { threads[i].join(); } System.out.println( i ); }
既然这样,那怎么办。没错,也许你已经想到了,可以加锁或者利用 synchronized 实现,例如,将 add() 方法修改为如下这样:
public synchronized static void add(){ i++; }
或者,加锁操作,例如下面使用 ReentrantLock (可重入锁)实现。
private static Lock lock = new ReentrantLock(); public static void add(){ lock.lock(); i++; lock.unlock(); }
CAS 实现自旋锁
既然用锁或 synchronized 关键字可以实现原子操作,那么为什么还要用 CAS 呢,因为【加锁或使用 synchronized 关键字带来的性能损耗较大】,而用 【CAS 可以实现乐观锁】,它实际上是直接利用了 CPU 层面的指令,所以性能很高。
上面也说了,CAS 是实现自旋锁的基础,【CAS 利用 CPU 指令保证了操作的原子性,以达到锁的效果】,至于自旋呢,看字面意思也很明白,自己旋转,翻译成人话就是循环,【一般是用一个无限循环实现。这样一来,一个无限循环中,执行一个 CAS 操作,当操作成功,返回 true 时,循环结束;当返回 false 时,接着执行循环,继续尝试 CAS 操作,直到返回 true】。
其实 JDK 中有好多地方用到了 CAS ,尤其是java.util.concurrent包下,比如 CountDownLatch、Semaphore、ReentrantLock 中,再比如 java.util.concurrent.atomic 包下,相信大家都用到过 Atomic* ,比如 AtomicBoolean、AtomicInteger 等。
这里拿 AtomicBoolean 来举个例子,因为它足够简单。
public class AtomicBoolean implements java.io.Serializable { private static final long serialVersionUID = 4654671469794556979L; // setup to use Unsafe.compareAndSwapInt for updates private static final Unsafe unsafe = Unsafe.getUnsafe(); private static final long valueOffset; static { try { valueOffset = unsafe.objectFieldOffset(AtomicBoolean.class.getDeclaredField("value")); } catch (Exception ex) { throw new Error(ex); } } private volatile int value; public final boolean get() { return value != 0; } public final boolean compareAndSet(boolean expect, boolean update) { int e = expect ? 1 : 0; int u = update ? 1 : 0; return unsafe.compareAndSwapInt(this, valueOffset, e, u); } }
这里面又几个关键方法和属性。
1、使用了 sun.misc.Unsafe 对象,这个类提供了一系列直接操作内存对象的方法,只是在 jdk 内部使用,不建议开发者使用;
2、value 表示实际值,可以看到 get 方法实际是根据 value 是否等于0来判断布尔值的,这里的 value 定义为 volatile,因为 volatile 可以保证内存可见性,也就是 value 值只要发生变化,其他线程是马上可以看到变化后的值的;下一篇会讲一下 volatile 可见性问题,欢迎关注
3、valueOffset 是 value 值的内存偏移量,用 unsafe.objectFieldOffset 方法获得,用作后面的 compareAndSet 方法;
4、compareAndSet 方法,这就是实现 CAS 的核心方法了,在使用这个方法时,只需要传递期望值和待更新的值即可,而它里面调用了 unsafe.compareAndSwapInt(this, valueOffset, e, u) 方法,它是个 native 方法,用 c++ 实现,具体的代码就不贴了,总之是利用了 CPU 的 cmpxchg 指令完成比较并替换,当然根据具体的系统版本不同,实现起来也有所区别,感兴趣的可以自行搜一下相关文章。
使用场景
CAS 适合简单对象的操作,比如布尔值、整型值等;
CAS 适合冲突较少的情况,如果太多线程在同时自旋,那么长时间循环会导致 CPU 开销很大;
ABA问题:
线程1准备用CAS将变量的值由A替换为B,在此之前,线程2将变量的值由A替换为C,又由C替换为A,然后线程1执行CAS时发现变量的值仍然为A,所以CAS成功。但实际上这时的现场已经和最初不同了,尽管CAS成功,但可能存在潜藏的问题。
例如下面的例子:
现有一个用单向链表实现的堆栈,栈顶为A,这时线程T1已经知道A.next为B,然后希望用CAS将栈顶替换为B:
head.compareAndSet(A,B);
在T1执行上面这条指令之前,线程T2介入,将A、B出栈,再pushD、C、A,此时堆栈结构如下图,而对象B此时处于游离状态:
此时轮到线程T1执行CAS操作,检测发现栈顶仍为A,所以CAS成功,栈顶变为B,但实际上B.next为null,所以此时的情况变为:
其中堆栈中只有B一个元素,C和D组成的链表不再存在于堆栈中,平白无故就把C、D丢掉了。
以上就是由于ABA问题带来的隐患,各种乐观锁的实现中通常都会用版本戳version来对记录或对象标记,避免并发操作带来的问题,并发包下倒是有 AtomicStampedReference 提供了根据版本号判断的实现,可以解决一部分问题。它通过包装[E,Integer]的元组来对对象标记版本戳stamp,从而避免ABA问题,例如下面的代码分别用AtomicInteger和AtomicStampedReference来对初始值为100的原子整型变量进行更新,AtomicInteger会成功执行CAS操作,而加上版本戳的AtomicStampedReference对于ABA问题会执行CAS失败:
import java.util.concurrent.TimeUnit; import java.util.concurrent.atomic.AtomicInteger; import java.util.concurrent.atomic.AtomicStampedReference; public class ABA { private static AtomicInteger atomicInt = new AtomicInteger(100); private static AtomicStampedReference atomicStampedRef = new AtomicStampedReference(100, 0); public static void main(String[] args) throws InterruptedException { Thread intT1 = new Thread(new Runnable() { @Override public void run() { atomicInt.compareAndSet(100, 101); atomicInt.compareAndSet(101, 100); } }); Thread intT2 = new Thread(new Runnable() { @Override public void run() { try { TimeUnit.SECONDS.sleep(1); } catch (InterruptedException e) { } boolean c3 = atomicInt.compareAndSet(100, 101); System.out.println(c3); // true } }); intT1.start(); intT2.start(); intT1.join(); intT2.join(); Thread refT1 = new Thread(new Runnable() { @Override public void run() { try { TimeUnit.SECONDS.sleep(1); } catch (InterruptedException e) { } atomicStampedRef.compareAndSet(100, 101, atomicStampedRef.getStamp(), atomicStampedRef.getStamp() + 1); atomicStampedRef.compareAndSet(101, 100, atomicStampedRef.getStamp(), atomicStampedRef.getStamp() + 1); } }); Thread refT2 = new Thread(new Runnable() { @Override public void run() { int stamp = atomicStampedRef.getStamp(); try { TimeUnit.SECONDS.sleep(2); } catch (InterruptedException e) { } boolean c3 = atomicStampedRef.compareAndSet(100, 101, stamp, stamp + 1); System.out.println(c3); // false } }); refT1.start(); refT2.start(); } }
。。
相关推荐
主要给大家介绍了关于我们说的CAS自旋锁到底是什么的相关资料,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧
自旋锁SpinLock唉….刚写完了!别白嫖啊,点赞关注,给你们福利啊~~转载请标注! 好兄弟们,不会真有人看不懂CAS吧?反正我是没看懂… 一. CAS是什么? import java.util.concurrent.atomic.AtomicInteger; /** * 1. CAS...
一、自旋锁 自旋锁是一种基础的同步原语,用于保障对共享数据的互斥访问。与互斥锁的相比,在获取锁失败的时候不会使得线程阻塞而是一直自旋尝试获取锁。当线程等待自旋锁的时候,CPU不能做其他事情,而是一直处于...
为了效率,不使用C++语言提供的Mutex互斥量,而使用不使用线程被阻塞的方式,即所谓的自旋锁,这是自旋锁的一种实现方式,使用C++11的原子变量,不用锁机制,实现的一种无锁的自旋锁
相比于多线程防止CPU空转Quine 不通过读源文件的方式输出程序源代码本身Vertx 基于netty的NIO实现的小清新WebServer和HttpClientReentrantReadWriteLock的用例以及实现写锁降级为读锁实现三种自旋锁SpinLock直接基于...
自旋锁 Go和内联汇编程序中的Spinlock实现。 概述 程序包自旋锁提供了汇编中低级自旋锁的实现。 此外,它还提供了基于内置原子的实现的后备功能。 在我的私人笔记本电脑上,基准测试结果如下。 所测量的时间是墙上...
CAS是什么 CAS是指比较并交换(compy and set),底层...可以看到源码是一个自旋锁,如果循环长时间对cpu是一种很大消耗 2. 只能保证一个共享变量的原子操作,对多个共享变量操作时,循环CAS就无法保证操作的原子性,
偏向锁、轻量级锁和重量级锁不同的地方在于不是通过信号量机制(强制阻塞)而是通过自旋CAS实现互斥访问的,避免了强制阻塞时用户态与核心态之间切换带来的开销(系统调用),这里的开销主要是保存用户态的上下文...
1. 什么是线程 2. 什么是线程安全和线程不安全 3. 什么是自旋锁 4. 什么是CAS 5. 什么是乐观锁和悲观锁 6. 什么是AQS 7. 什么是原子操作
自旋锁 读写锁/独占/共享锁 Synchronized和Lock的区别 CountDownLatch/CyclicBarrier/Semaphore CountDownLatch 枚举类的使用 CyclicBarrier Semaphore 阻塞队列 SynchronousQueue Callable接口 阻塞队列的应用——...
自适应自旋锁 重量级锁 synchronized 可重入锁 土方法实现可重入锁 使用AQS类实现可重入锁 CAS MySQL 中的行级锁、表级锁和页级锁 java中的死锁 公平锁和非公平锁 锁的总结 锁的优化 .......... 还有好多,不想写了,...
##### 循环时间长开销大,自旋CAS如果长时间不成功,会给CPU带来非常大的执行开销。 ##### 只能保证一个共享变量的原子操作 解决方案:1.用锁 2.把多个共享变量合并成一个共享变量来操作。 ##### ABA...
codeceo 首页问答热门文章RSS订阅 文章首页 Java JavaScript ... iOS ...2018-07-25 分类:JAVA开发、编程开发、首页精华0人评论 来源:crossoverjie.top ...Map 这样的 Key Value 在软件开发中是非常经典的结构,常...
1. 目录 1. 2. 目录 .........................................................................................................................................................1 JVM .........................
1. 目录 1. 2. 目录 .........................................................................................................................................................1 JVM ........................