Java并发编程之CAS

CAS（Compare and Swap，比较并交换）:

CAS 操作包含三个操作数 —— 内存位置（V）、预期原值（A）和新值(B)。
如果内存位置的值与预期原值相匹配，那么处理器会自动将该位置值更新为新值。否则，处理器不做任何操作。

利用CPU的CAS指令，同时借助JNI来完成Java的非阻塞算法。其它原子操作都是利用类似的特性完成的。而整个J.U.C都是建立在CAS之上的，因此对于synchronized阻塞算法，J.U.C在性能上有了很大的提升。

乐观锁避免了悲观锁独占对象的现象，同时也提高了并发性能，但它也有缺点：

① 不能保证代码块的原子性

乐观锁只能保证一个共享变量的原子操作。如上例子，自旋过程中只能保证value变量的原子性，这时如果多一个或几个变量，乐观锁将变得力不从心，但互斥锁能轻易解决，不管对象数量多少及对象颗粒度大小。

② CPU开销较大

长时间自旋可能导致开销大。假如CAS长时间不成功而一直自旋，会给CPU带来很大的开销。

③ ABA问题。

CAS的核心思想是通过比对内存值与预期值是否一样而判断内存值是否被改过，但这个判断逻辑不严谨，假如内存值原来是A，后来被一条线程改为B，最后又被改成了A，则CAS认为此内存值并没有发生改变，但实际上是有被其他线程改过的，这种情况对依赖过程值的情景的运算结果影响很大。解决的思路是引入版本号，每次变量更新都把版本号加一。

乐观锁是对悲观锁的改进，虽然它也有缺点，但它确实已经成为提高并发性能的主要手段，而且jdk中的并发包也大量使用基于CAS的乐观锁。

===================================

自旋锁：

跟互斥锁一样，一个执行单元要想访问被自旋锁保护的共享资源，必须先得到锁，在访问完共享资源后，必须释放锁。

如果在获取自旋锁时，没有任何执行单元保持该锁，那么将立即得到锁；如果在获取自旋锁时锁已经有保持者，那么获取锁操作将自旋在那里，直到该自旋锁的保持者释放了锁。

由此我们可以看出，自旋锁是一种比较低级的保护数据结构或代码片段的原始方式，

这种锁可能存在两个问题：

递归死锁：试图递归地获得自旋锁必然会引起死锁：递归程序的持有实例在第二个实例循环，以试图获得相同自旋锁时，不会释放此自旋锁。在递归程序中使用自旋锁应遵守下列策略：递归程序决不能在持有自旋锁时调用它自己，也决不能在递归调用时试图获得相同的自旋锁。此外如果一个进程已经将资源锁定，那么，即使其它申请这个资源的进程不停地疯狂“自旋”,也无法获得资源，从而进入死循环。
过多占用cpu资源。如果不加限制，由于申请者一直在循环等待，因此自旋锁在锁定的时候,如果不成功,不会睡眠,会持续的尝试,单cpu的时候自旋锁会让其它process动不了. 因此，一般自旋锁实现会有一个参数限定最多持续尝试次数. 超出后, 自旋锁放弃当前time slice. 等下一次机会

由此可见，自旋锁比较适用于锁使用者保持锁时间比较短的情况。正是由于自旋锁使用者一般保持锁时间非常短，因此选择自旋而不是睡眠是非常必要的，自旋锁的效率远高于互斥锁。

自旋锁在java中的应用：

Jdk1.5以后，提供了java.util.concurrent.atomic包，这个包里面提供了一组原子类。

其基本的特性就是在多线程环境下，当有多个线程同时执行这些类的实例包含的方法时，具有排他性，

即当某个线程进入方法，执行其中的指令时，不会被其他线程打断，而别的线程就像自旋锁一样，一直等到该方法执行完成，才由JVM从等待队列中选择一个另一个线程进入，

这只是一种逻辑上的理解。实际上是借助硬件的相关指令来实现的，不会阻塞线程(或者说只是在硬件级别上阻塞了)。

其中的类可以分成4组

AtomicBoolean，AtomicInteger，AtomicLong，AtomicReference
AtomicIntegerArray，AtomicLongArray
AtomicLongFieldUpdater，AtomicIntegerFieldUpdater，AtomicReferenceFieldUpdater
AtomicMarkableReference，AtomicStampedReference，AtomicReferenceArray

======================================================================

查看CAS，自旋锁的具体应用：

AtomicInteger中的自旋锁的代码：

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;
}

这段代码是一个无限循环，也就是CAS的自旋。循环体当中做了三件事：

1.获取当前值。
2.当前值+1，计算出目标值。
3.进行CAS操作，如果成功则跳出循环，如果失败则重复上述步骤。

这里需要注意的重点是 get 方法，这个方法的作用是获取变量的当前值，使用volicate可以获取变量的最新值。

compareAndSet方法的实现，以及方法所依赖对象的来历：

compareAndSet方法的实现很简单，只有一行代码。这里涉及到两个重要的对象，一个是unsafe，一个是valueOffset。
什么是unsafe呢？Java语言不像C，C++那样可以直接访问底层操作系统，但是JVM为我们提供了一个后门，这个后门就是unsafe。unsafe为我们提供了硬件级别的原子操作。
至于valueOffset对象，是通过unsafe.objectFieldOffset方法得到，所代表的是AtomicInteger对象value成员变量在内存中的偏移量。我们可以简单地把valueOffset理解为value变量的内存地址。
我们在上一期说过，CAS机制当中使用了3个基本操作数：内存地址V，旧的预期值A，要修改的新值B。
而unsafe的compareAndSwapInt方法参数包括了这三个基本元素：valueOffset参数代表了V，expect参数代表了A，update参数代表了B。
正是unsafe的compareAndSwapInt方法保证了Compare和Swap操作之间的原子性操作。

注意AtomicLong,Long是64位，会先写入前32位，再写入后32位，所以是线程不安全的。

AtomLong的缺点：

唯一会制约AtomicLong高效的原因是高并发，高并发意味着CAS的失败几率更高，重试次数更多，越多线程重试，CAS失败几率又越高，变成恶性循环，AtomicLong效率降低。

已经有新的更高效的类LongAdder,详细讲解链接：

http://www.liuinsect.com/2014/04/15/%E6%AF%94atomiclong%E8%BF%98%E9%AB%98%E6%95%88%E7%9A%84longadder-%E6%BA%90%E7%A0%81%E8%A7%A3%E6%9E%90/

1. Java语言CAS底层如何实现？
利用unsafe提供了原子性操作方法。

2. 什么是ABA问题？怎么解决？
当一个值从A更新成B，又更新回A，普通CAS机制会误判通过检测。
利用版本号比较可以有效解决ABA问题。

（具体使用中问题，比如小明卡里有100块，提款50，提款机发生故障，两个线程去执行扣款，线程1金额100到50，线程二阻塞，小明妈妈又打款50，金额50到100，线程二继续运行，金额100到50）

小明被多扣款50，两个扣款线程应该只能执行一个。

http://www.cnblogs.com/lintong/p/4373723.html

http://blog.csdn.net/hsuxu/article/details/9467651

http://www.mamicode.com/info-detail-334916.html