通过实现网站访问计数器带你理解 轻量级锁CAS原理,还学不会算我输!!!(下)

二、什么是CAS算法


1、概念


CAS的英文单词Compare and Swap的缩写,翻译过来就是比较并替换。


2、原理


CAS机制中使用了3个基本操作数:内存地址V,旧的预期值A,要修改的新值B。当且仅当预期值A和内存值V相同时,才将内存值修改为B,否则什么都不做,最后返回现在的V值。


简单理解为这句话:我认为V的值应该是A,如果是A的话我就把他改成B,如果不是A的话(那就证明被别人修改过了),那我就不修改了,避免多人 同时修改导致数据出错。换句话说:要想修改成功,必须保证A和V中的值是一样的,修改前有个对比的过程。


比如:更新一个变量,只有当变量的预期值(A)和内存地址(V)的实际值相同时,才会将内存地址(V)对应的值修改为B。


我们看如下的原理图:


1、在内存地址V当中,存储着值为10的变量。


通过实现网站访问计数器带你理解 轻量级锁CAS原理,还学不会算我输!!!(下)


通过实现网站访问计数器带你理解 轻量级锁CAS原理,还学不会算我输!!!(下)


通过实现网站访问计数器带你理解 轻量级锁CAS原理,还学不会算我输!!!(下)


3、对比Synchronized


从思想上来讲,Synchronized属于悲观锁,悲观的认为程序中的并发情况严重,所以严防死守,高并发情况下效率低下。而CAS属于乐观锁,乐观的认为程序中的并发情况不那么严重,所以让线程不断去重试更新。但实际上Synchronized已经改造了,带有锁升级的功能。效率不亚于cas。


4、CAS缺点


(1)CPU开销可能过大


在并发比较大的时候,若多线程反复尝试更新某个变量,却又一直更新不成功,循环往复,会给CPU带来很大的压力。(因为是个死循环,下面分析底层实现就懂了。)


(2)不能保证代码块的原子性


CAS机制所保证的只是一个变量的原子操作,而不能保证整个代码块的原子性。比如需要保证三个变量共同进行原子性的更新,就不得不使用Synchronized或Lock等机制了。


(3)ABA问题。


下面会单独抽出一块地来详细讲解。这是CAS最大的漏洞。


三、CAS底层实现(Java)


1、概述


要说Java中CAS的案例,那么最属java.util.concurrent.atomic包下的原子类有发言权了。最经典、最简单。


2、讲解


比如我们这里随便找个AtomicInteger来讲解CAS算法底层实现。


public final int incrementAndGet() {
    for (;;) {
        int current = get();
        int next = current + 1;
        if (compareAndSet(current, next))
            return next;
    }
}
private volatile int value; 
public final int get() {
    return value;
}


  1. 获取当前值


  1. 当前值+1,计算出目标值


  1. 进行CAS操作,如果成功则跳出循环,如果失败则重复上述步骤


如何保证获取的当前值是内存中的最新值?很简单,用volatile关键字来保证(保证线程间的可见性)。



通过实现网站访问计数器带你理解 轻量级锁CAS原理,还学不会算我输!!!(下)


compareAndSet方法的实现很简单,只有一行代码。这里涉及到两个重要的对象,一个是unsafe,一个是valueOffset。


什么是unsafe呢?


3、Unsafe


Unsafe是CAS的核心类,Java语言不像C,C++那样可以直接访问底层操作系统,Java无法直接访问底层操作系统,但是JVM为我们提供了一个后门,这个后门就是unsafe。unsafe为我们提供了硬件级别的原子操作


而valueOffset是通过unsafe.objectFiledOffset方法得到,所代表的是AtomicInteger对象value成员变量在内存中的偏移量。我们可以简单的把valueOffset理解为value变量的内存地址。


我们上面说过,CAS机制中使用了3个基本操作数:内存地址V,旧的预期值A,要修改的新值B。


而unsafe的compareAndSwapInt方法的参数包括了这三个基本元素:valueOffset参数代表了V,expect参数代表了A,update参数代表了B。


正是unsafe的compareAndSwapInt方法保证了Compare和Swap操作之间的原子性操作。


四、ABA问题


1、演示


线程1准备用CAS将变量的值由A替换为B,在此之前,线程2将变量的值由A替换为C,又由C替换为A。然后线程1执行CAS时发现变量的值仍是A,所以CAS成功,这么看没毛病,但是如果操作的是个链表呢?那就炸了,因为虽然值一样,但是链表的位置不一样了。


例如:


(1)现有一个用单向链表实现的堆栈,栈顶为A,这时线程T1已经知道A.next为B,然后希望用CAS将栈顶替换为B:


head.compareAndSet(A,B);


通过实现网站访问计数器带你理解 轻量级锁CAS原理,还学不会算我输!!!(下)


导致了其中堆栈中只有B一个元素,C和D组成的链表不再存在于堆栈中,平白无故就把C、D丢掉了。


以上就是由于ABA问题带来的隐患,各种乐观锁的实现中通常都会用版本戳version来对记录或对象标记,避免并发操作带来的问题,在Java中,


AtomicStampedReference<E>也实现了这个作用,它通过包装[E,Integer]的元组来对对象标记版本戳stamp,从而避免ABA问题。


2、生活案例


你和你前任分手后她又回来了,但是你在这期间又和其他女人...,你表面还是你,但是本质的你已经变了。把这个例子带到代码里来就是:


你有个class,里面有个LinkedList属性,这个链表里有你和你前任,你先把它踹了,然后小苍进来跟你...,这时候你前任就回来了,但是这期间链表已经发生了无感知的变化。`


END

上一篇:正则表达式基本语法


下一篇:php session存数据库