Home Tags Posts tagged with "ABA"

ABA

0 53

CAS及ABA的定义和实现

CAS思想(算法):对于内存中的某一个值data,提供一个旧值A一个新值B。如果提供的旧值V和A相等就把B写入V,这个过程是原子性的。

CAS执行结果要么成功要么失败,对于失败的情形下一般采用不断重试,或者放弃。

举例说明:

public class CAS{
    public static void main(String[] args) {
        /*乐观锁的实现CAS;*/
        String data = "123";//共享数据

        /*更新数据的线程会进行如下操作*/
        boolean flag=true;
        while(flag){
            oldValue = date;//保存原始数据
            newValue = doSomething(oldValue);
            //下面的部分为CAS操作,尝试更新出data值
            if(date == oldValue){//比较在更新之前原值有无更改,如没有
                //则更新:
                data = newValue;
                falg = false;//跳出循环
            }
            else{
                //什么也不做,循环重试
            }
        }
    }
}
/*
   很明显,这样的代码根本不是原子性的,
   因为真正的CAS利用了CPU指令,
   这里只是为了展示执行流程,本意是一样的。
*/

ABA问题

CAS实现的过程是先取出内存中某时刻的数据在下一时刻比较并替换,那么在这个时间差会导致数据的变化,此时就有可能出现ABA问题;

什么是ABA问题?

如果另一个线程修改V值,假设原来是A,先修改成B,再修改会A。当前线程的CAS操作无法分辨当前V值是否发生过变化。

举例说明:

在你非常渴的情况下发现一个盛满水的被子,你一饮而尽,之后再给杯子里面重新倒满水,然后你离开,当杯子的真正主人(当前执行CAS操作的线程)看到杯子还是盛满水的,他当然不知道是否被人喝完重新倒满。解决这个问题的方案的一个策略是 每一次倒水假设有一个自动记录仪记录下(Version版本号),这样主人回来就可以分辨在他离开后是否发生过重新倒满的情况。这也是解决ABA问题目前采用的策略。

解决办法:

1.加版本号

2.用AtomicStampedReference/AtomicMarkableReference解决ABA问题

 

补充:

洪山区最新新开了一家自助餐店,为迎接5-1劳动节,老板决定为每位消费卡余额低于20的用户卡里赠送20元,该活动每位顾客只可享受一次;

很简单就用cas技术,先去用户卡里的余额,然后包装成 AtomicInteger,写一个判断,开启10个线程,然后判断小于20的,一律加20,然后就很开心的交差了。可是过了一段时间,发现账面亏损的厉害,老板起先的预支是2000块,因为店里的会员总共也就100多个,就算每人都符合条件,最多也就2000啊,怎么预支了这么多。小王一下就懵逼了,赶紧debug,tail -f一下日志,这不看不知道,一看吓一跳,有个客户被充值了10次!

解释:

用户要给储值卡充值20元,用户卡内余额15元,A线程首先获取余额是15,然后准备加上20,A线程因为某种原因block超时,系统超时重试提交,B线程成功将余额加上20并且成功提交,此时余额为35。但是紧接着用户又消费了20,所以余额还是15,终于A线程获取到了时间片,它比对之后发现余额还是15,所以A线程就执行了。ABA的问题核心在于一个线程在提交的时候,如果只是根据要修改的值和之前是否一样,这样是无法证明这个值没有被其他线程改过因为在这段时间它的值可能被改为其他值,然后又改原来的,实际上如果避免重复提交就能避免ABA问题,而版本号控制可以避免重复提交