CAS乐观锁

1.达观锁CAS和失望锁synchronized

Compare and Swap，简称CAS，是一种经过达观锁确保变量操作原子性的机制。

咱们一般了解的加锁办法是经过synchronized关键字，能够很便利地给实例办法、静态办法和代码块加锁，确保操作的原子性。

synchronized锁是是失望的，是同步锁，它假定更新很或许抵触，所以先获取锁，得到锁后才更新。

synchronized代表一种堵塞式算法，得不到锁的时分，进入锁等候行列，等候其他线程唤醒，有上下文切换开支。原子变量的更新逻辑对错堵塞式的，更新抵触的时分，它就重试，不会堵塞，不会有上下文切换开支。

与synchronized锁相比，CAS原子更新办法代表一种不同的思维办法。

失望锁更新的思维办法认为，在更新数据的时分大概率会有其他线程去抢夺共享资源，所以失望锁的做法是，第一个获取资源的线程会将资源确定起来，其他没抢夺到资源的线程只能进入堵塞行列，等第一个获取资源的线程释放锁之后，这些线程才能有机会从头抢夺资源。

synchronized便是java中失望锁的典型完成，synchronized的长处是运用起来十分简略便利，但缺陷是会使没争抢到资源的线程进入堵塞状况，线程在堵塞状况和Runnable状况之间切换效率较低（比较慢）。

在更新操作十分快的情况下，仍然用synchronized将其他线程都锁住，现场状况切换的成本就变得十分高，线程从Blocked状况切换回Runnable花费的时刻或许比更新操作的时刻还要长。

达观锁更新的思维办法认为，在更新数据的时分其他线程争抢这个共享变量的概率十分小，所以更新数据的时分不会对共享数据加锁，但在正式更新数据之前会检查数据是否被其他线程改变过，假如未被其他线程改变过就将共享变量更新成最新值，假如发现共享变量已经被其他线程更新过了就重试，直到成功为止。CAS机制便是达观锁的典型完成。在并发量不是很高的情况下，或许线程对共享资源的占用时刻不是很长，因为避免了频频切换线程状况，因而运用CAS机制的效率会比synchronized锁更高。

2.原子变量CAS原理

Java的原子变量内部便是经过CAS指令来完成的。

原子变量的更新逻辑是达观的，它假定抵触比较少，但运用CAS更新，也便是进行抵触检测，假如确实抵触了，那也不要紧，持续测验就好了。

关于大部分比较简略的操作，无论是在低并发仍是高并发情况下，这种达观非堵塞办法的性能都远高于失望堵塞式办法。

Java并发包中的根本原子变量类型有以下几种。

• AtomicBoolean：原子Boolean类型，常用来在程序中表明一个标志位。

• AtomicInteger：原子Integer类型。

• AtomicLong：原子Long类型，常用来在程序中生成仅有序列号。

• AtomicReference：原子引证类型，用来以原子办法更新杂乱类型。

• LongAdder、LongAccumulator、Double-Adder和DoubleAccumulator：Java 8增加，适合高并发统计汇总的场景。

原子变量相对比较简略，但关于杂乱一些的数据结构和算法，非堵塞办法往往难于完成和了解，幸运的是，Java并发包中已经供给了一些非堵塞容器，咱们只需求会运用就能够了，比方：

• ConcurrentLinkedQueue和ConcurrentLinkedDeque：非堵塞并发行列。

• ConcurrentSkipListMap和ConcurrentSkipListSet：非堵塞并发Map和Set。

• AtomicLongArray、AtomicReferenceArray：如针对数组类型的类。

• AtomicIntegerFieldUpdater、AtomicReferenceFieldUpdater：原子办法更新目标中的字段。

AtomicInteger包括一些以原子办法完成组合操作的办法，部分办法如下：

//以原子办法获取旧值并设置新值
public final int getAndSet(int newValue) 
//以原子办法获取旧值并给当时值加1
public final int getAndIncrement()
//以原子办法获取旧值并给当时值减1
public final int getAndDecrement()
//以原子办法获取旧值并给当时值加delta
public final int getAndAdd(int delta)
//以原子办法给当时值加1并获取新值
public final int incrementAndGet()
//以原子办法给当时值减1并获取新值
public final int decrementAndGet()
//以原子办法给当时值加delta并获取新值public final int
addAndGet(int delta)
//compareAndSet是一个十分重要的办法，比较并设置，咱们以后将简称为CAS。
//该办法有两个参数expect和update，以原子办法完成了如下功能：
// 假如当时值等于expect，则更新为update，不然不更新，
// 假如更新成功，返回true，不然返回false。
public final boolean compareAndSet(int expect, int update)

以incrementAndGet办法为例，代码主体是个死循环，先获取当时值current，核算期望的值next，然后调用CAS办法进行更新，假如更新没有成功，说明value被别的线程改了，则再去取最新值并测验更新直到成功为止。源码如下：

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

synchronized是失望的，它假定更新很或许抵触，所以先获取锁，得到锁后才更新。

原子变量的更新逻辑是达观的，它假定抵触比较少，但运用CAS更新，也便是进行抵触检测，假如确实抵触了，那也不要紧，持续测验就好了。

synchronized代表一种堵塞式算法，得不到锁的时分，进入锁等候行列，等候其他线程唤醒，有上下文切换开支。

原子变量的更新逻辑对错堵塞式的，更新抵触的时分，它就重试，不会堵塞，不会有上下文切换开支。关于大部分比较简略的操作，无论是在低并发仍是高并发情况下，这种达观非堵塞办法的性能都远高于失望堵塞式办法。

原子变量相对比较简略，但关于杂乱一些的数据结构和算法，非堵塞办法往往难于完成和了解，幸运的是，Java并发包中已经供给了一些非堵塞容器，咱们只需求会运用就能够了，比方：

ConcurrentLinkedQueue和ConcurrentLinkedDeque：非堵塞并发行列。 ConcurrentSkipListMap和ConcurrentSkipListSet：非堵塞并发Map和Set。

compareAndSet是怎样完成的呢？咱们看代码：

public final boolean compareAndSet(int expect, int update) {
    return unsafe.compareAndSwapInt(this, valueOffset, expect, update);
}

它调用了unsafe的compareAndSwapInt办法。

unsafe是什么呢？它的类型为sun.misc.Unsafe，界说为：

private static final Unsafe unsafe = Unsafe.getUnsafe();

它是Sun的私有完成，从姓名看，表明的也是“不安全”，一般应用程序不应该直接运用。

原理上，一般的核算机体系都在硬件层次上直接支撑CAS指令，而Java的完成都会利用这些特别指令。

从程序的角度看，能够将compareAndSet视为核算机的根本操作，直接接收就好。

根据CAS，除了能够完成达观非堵塞算法之外，还能够完成失望堵塞式算法，比方锁。

实际上，Java并发包中的所有堵塞式工具、容器、算法也都是根据CAS的（不过，也需求一些别的支撑）。用AtomicInteger完成一个锁MyLock：

public class MyLock {
    private Atomicinteger status = new AtomicInteger(0);
    public void lock() {
        while(!status.compareAndSet(0, 1)) {
            Thread.yield();
        }
    }
    public void unlock() {
        status.compareAndSet(1, 0);
    }
}

在MyLock中，运用status表明锁的状况，0表明未确定，1表明确定，lock（）、unlock（）运用CAS办法更新，lock（）只要在更新成功后才退出，完成了堵塞的效果，不过一般而言，这种堵塞办法过于耗费CPU，MyLock仅仅用于演示根本概念，实际开发中应该运用Java并发包中的类，如ReentrantLock。

3.CAS的问题与处理

CAS比失望锁的效率高，从堵塞机制变成了非堵塞机制，减少了线程之间等候的时刻，有一个条件，便是并发量不大。

因为在线程之间竞争程度大的时分，假如运用CAS，每次都有很多的线程在竞争，也便是说CAS机制不能更新成功。这种情况下CAS机制会一直重试，这样就会比较耗费CPU。

因而能够看出，假如线程之间竞争程度小，运用CAS是一个很好的选择；但是假如竞争很大，运用锁或许是个更好的选择。

在并发量十分高的环境中，假如仍然想经过原子类来更新的话，能够运用AtomicLong的替代类：LongAdder。

除了在高并发场景下耗费CPU的问题，运用CAS办法更新还有一个ABA问题。

该问题是指，假设当时值为A，假如另一个线程先将A修正成B，再修正回成A，当时线程的CAS操作无法分辩当时值发生过变化。

ABA是不是一个问题与程序的逻辑有关，即B之前的A和B之后的A不影响程序逻辑，ABA也就不是问题。

而假如确实有问题，处理办法是运用AtomicStampedReference，在修正值的同时附加一个时刻戳，只要值和时刻戳都相同才进行修正，其CAS办法声明为：

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

AtomicStampedReference在compareAndSet中要同时修正两个值：一个是引证，另一个是时刻戳。

它怎样完成原子性呢？实际上，内部AtomicStampedReference会将两个值组合为一个目标，修正的是一个值，咱们看代码：

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

这个Pair是AtomicStampedReference的一个内部类，成员包括引证和时刻戳，具体界说为：

private static class Pair<T> {
final T reference;    
final int stamp;    
private Pair(T reference,int stamp) {       
this.reference = reference;        
this.stamp = stamp;    
}    
static <T> Pair<T> of(T reference, int stamp) {        
return new Pair<T>(reference, stamp);    
}
}

AtomicStampedReference将对引证值和时刻戳的组合比较和修正转化为了对这个内部类Pair单个值的比较和修正。

关于并发环境中的计数、发生序列号等需求，应该运用原子变量而非锁，CAS是Java并发包的根底，根据它能够完成高效的、达观、非堵塞式数据结构和算法，它也是并发包中锁、同步工具和各种容器的根底。

4.参考资料

• 《并发编程的基石——CAS机制》 www.cnblogs.com/54chensongx…
• 《synchronized详解 》www.cnblogs.com/three-fight…
• 《Java编程的逻辑》豆瓣：book.douban.com/subject/301…