高并发编程 -- Java中CAS详解_cas 自旋转 竞争激烈模拟

目录

锁机制存在以下问题：

volatile机制

什么是CAS

模拟CAS算法 :

CAS的用处：

处理器是如何实现原子操作

1.处理器自动保证基本内存操作的原子性

2. 总线锁定

3. 缓存锁定

CAS优缺点

使用乐观锁还是悲观锁

CAS应用

concurrent包的实现

---

 

在JDK 5之前Java语言主要依靠synchronized关键字保证同步，这会导致有锁。

一、锁机制存在以下问题：

（1）在多线程竞争下，加锁、释放锁会导致比较多的上下文切换和调度延时，引起性能问题。

（2）一个线程持有锁会导致其它所有需要此锁的线程挂起。

（3）如果一个优先级高的线程等待一个优先级低的线程释放锁会导致优先级倒置，引起性能风险。

 

二、volatile机制

volatile到底如何保证可见性和禁止指令重排序的。

“观察加入volatile关键字和没有加入volatile关键字时所生成的汇编代码发现，加入volatile关键字时，会多出一个lock前缀指令”

0x000000011214bb49: mov    %rdi,%rax
  0x000000011214bb4c: dec    %eax
  0x000000011214bb4e: mov    %eax,0x10(%rsi)
  0x000000011214bb51: lock addl $0x0,(%rsp)     ;*putfield v1
                                                ; - com.earnfish.VolatileBarrierExample::readAndWrite@21 (line 35)
 
  0x000000011214bb56: imul   %edi,%ebx
  0x000000011214bb59: mov    %ebx,0x14(%rsi)
  0x000000011214bb5c: lock addl $0x0,(%rsp)     ;*putfield v2
                                                ; - com.earnfish.VolatileBarrierExample::readAndWrite@28 (line 36)

lock前缀指令实际上相当于一个内存屏障（也成内存栅栏），内存屏障会提供3个功能：

1）它确保指令重排序时不会把其后面的指令排到内存屏障之前的位置，也不会把前面的指令排到内存屏障的后面；即在执行到内存屏障这句指令时，在它前面的操作已经全部完成；

2）它会强制将对缓存的修改操作立即写入主存；

3）如果是写操作，它会导致其他CPU中对应的缓存行无效。

 

但是volatile不能保证原子性。因此对于同步最终还是要回到锁机制上来。

独占锁是一种悲观锁，synchronized就是一种独占锁，会导致其它所有需要锁的线程挂起，等待持有锁的线程释放锁。而另一个更加有效的锁就是乐观锁。所谓乐观锁就是，每次不加锁而是假设没有冲突而去完成某项操作，如果因为冲突失败就重试，直到成功为止。乐观锁用到的机制就是CAS，Compare and Swap。

来看一段代码：

代码证明volatile不能保证原子性

package org.hcgao.common.blog.AQS;
 
import java.util.concurrent.CountDownLatch;
 
public class Test_Volatile implements Runnable {
	
	CountDownLatch cdOrder;
	
	public Test_Volatile(CountDownLatch cdOrder) {
		this.cdOrder = cdOrder;
	}
	
	private volatile int count = 0;
	
	public void add() {
		count += 1;
	}
	
	public void add2() {
		count = count + 1;
	}
	
	@Override
	public void run() {
		try {
			//System.out.println("准备："+count);
			cdOrder.await();
		} catch (InterruptedException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		// TODO Auto-generated method stub
		add();
		System.out.println(count);
	}
	
	public static void main(String[] args) throws InterruptedException {
		
		final CountDownLatch cdOrder = new CountDownLatch(1);
	    Test_Volatile test = new Test_Volatile(cdOrder); 
	    for (int i = 0; i < 10000; i++) {
	    Thread th1 = new Thread(test); th1.start(); }
	    Thread.sleep(5000);
	    cdOrder.countDown();
		
	}
	
}

//add()方法的执行结果
2
2
3
5
4
6
10
9
8
7
11
14
13
12
15
19
18
17
16
20
......
9993
9994
9995
9996
9997
9998
9999
10000

//add2()方法的执行结果
3
3
3
4
6
5
7
8
12
......
9729
9725
9724
9723
9719
9716
9715
9714
9704
9696
9695

volatile变量自身具有下列特性。

❑ 可见性。对一个volatile变量的读，总是能看到（任意线程）对这个volatile变量最后的写入。

❑ 原子性：对任意单个volatile变量的读/写具有原子性，但类似于volatile++这种复合操作不具有原子性。

 

什么是CAS

CAS,compare and swap的缩写，中文:比较并交换。

我们都知道，在java语言之前，并发就已经广泛存在并在服务器领域得到了大量的应用。所以硬件厂商老早就在芯片中加入了大量直至并发操作的原语，从而在硬件层面提升效率。在intel的CPU中，使用cmpxchg指令。

 

在Java发展初期，java语言是不能够利用硬件提供的这些便利来提升系统的性能的。而随着java不断的发展,Java本地方法(JNI)的出现，使得java程序越过JVM直接调用本地方法提供了一种便捷的方式，因而java在并发的手段上也多了起来。而在Doug Lea提供的cucurenct包中，CAS理论是它实现整个java包的基石。

 

CAS 操作包含三个操作数 —— 内存位置（V）、预期原值（A）和新值(B)。 如果内存位置的值与预期原值相匹配，那么处理器会自动将该位置值更新为新值 。否则，处理器不做任何操作。无论哪种情况，它都会在 CAS 指令之前返回该 位置的值。（在 CAS 的一些特殊情况下将仅返回 CAS 是否成功，而不提取当前 值。）CAS 有效地说明了“我认为位置 V 应该包含值 A；如果包含该值，则将 B 放到这个位置；否则，不要更改该位置，只告诉我这个位置现在的值即可。”

通常将 CAS 用于同步的方式是从地址 V 读取值 A，执行多步计算来获得新 值 B，然后使用 CAS 将 V 的值从 A 改为 B。如果 V 处的值尚未同时更改，则 CAS 操作成功。

类似于 CAS 的指令允许算法执行读-修改-写操作，而无需害怕其他线程同时 修改变量，因为如果其他线程修改变量，那么 CAS 会检测它（并失败），算法 可以对该操作重新计算。

CPU指令对CAS的支持

或许我们可能会有这样的疑问，假设存在多个线程执行CAS操作并且CAS的步骤很多，有没有可能在判断V和E相同后，正要赋值时，切换了线程，更改了值。造成了数据不一致呢？答案是否定的，因为CAS是一种系统原语，原语属于操作系统用语范畴，是由若干条指令组成的，用于完成某个功能的一个过程，并且原语的执行必须是连续的，在执行过程中不允许被中断，也就是说CAS是一条CPU的原子指令，不会造成所谓的数据不一致问题。

compareAndSet利用JNI来完成CPU指令的操作。   
 public final boolean compareAndSet(int expect, int update) { 
        //compareAndSwapInt就是借助C来调用CPU底层指令实现的。  
        return unsafe.compareAndSwapInt(this, valueOffset, expect, update);
    }
 
 
 
intel x86处理器的源代码的片段：
 
// Adding a lock prefix to an instruction on MP machine
// VC++ doesn't like the lock prefix to be on a single line
// so we can't insert a label after the lock prefix.
// By emitting a lock prefix, we can define a label after it.
#define LOCK_IF_MP(mp) __asm cmp mp, 0  \
                       __asm je L0      \
                       __asm _emit 0xF0 \
                       __asm L0:
 
inline jint     Atomic::cmpxchg    (jint     exchange_value, volatile jint*     dest, jint     compare_value) {
  // alternative for InterlockedCompareExchange
  int mp = os::is_MP();
  __asm {
    mov edx, dest
    mov ecx, exchange_value
    mov eax, compare_value
    LOCK_IF_MP(mp)
    cmpxchg dword ptr [edx], ecx
  }
}

根据CPU处理器源代码所示，程序会根据当前处理器的类型来决定是否为cmpxchg指令添加lock前缀。如果程序是在多处理器上运行，就为cmpxchg指令加上lock前缀（lock cmpxchg）。反之，如果程序是在单处理器上运行，就省略lock前缀（单处理器自身会维护单处理器内的顺序一致性，不需要lock前缀提供的内存屏障效果）。

 

 

内存值 V 
预估值 A 
更新值 B
 
当且仅当，V==A 时，才将 B 的只值赋给 A，否则，将不做任何操作。  //(CAS算法的一个特性)

模拟CAS算法 :

CAS的流程：获取 —> 比较 —> 设置

public class TestCompareAndSwap {
    public static void main(String[] args) {
        final CompareAndSwap cas=new CompareAndSwap();
 
        for(int i=0;i<10;i++){
            new Thread(new Runnable(){
                @Override
                public void run() { 
                    int expectedValue=cas.get(); //每次执行前先获取内存中的值
                    boolean isTrue=cas.compareAndSet(expectedValue, (int)(Math.random()*101));
                    System.out.println(isTrue);
                }
            }).start();
        }
    }
}
 
class CompareAndSwap{
    //内存值
    private int value;
 
    //获取内存值
    public synchronized int get(){
        return value;
    }
 
    //比较
    public synchronized boolean compareAndSwap(int expectedValue,int newValue){
        int oldValue=value;//线程读取内存值，与预估值比较
        if(oldValue==expectedValue){
            this.value=newValue;
            return true;
        }
        return false;
    }
  
  	//设置
  	public synchronized boolean compareAndSet(int expectedValue,int newValue){
    	return expectedValue == compareAndSwap(expectedValue,newValue);
  	}
}

 

CAS的用处：

原子类例如AtomicInteger里的方法都很简单，我们看一下getAndIncrement方法：

//该方法功能是Interger类型加1
public final int getAndIncrement() {
        //主要看这个getAndAddInt方法
        return unsafe.getAndAddInt(this, valueOffset, 1);
    }
 
//var1 是this指针
//var2 是地址偏移量
//var4 是自增的数值，是自增1还是自增N
public final int getAndAddInt(Object var1, long var2, int var4) {
        int var5;
        do {
            //获取内存值，这是内存值已经是旧的，假设我们称作期望值E
            var5 = this.getIntVolatile(var1, var2);
            //compareAndSwapInt方法是重点，
            //var5是期望值，var5 + var4是要更新的值
            //这个操作就是调用CAS的JNI,每个线程将自己内存里的内存值M
            //与var5期望值E作比较，如果相同将内存值M更新为var5 + var4,否则做自旋操作
        } while(!this.compareAndSwapInt(var1, var2, var5, var5 + var4));
 
        return var5;
    }

 

处理器是如何实现原子操作

32位IA-32处理器使用基于对缓存加锁或总线加锁的方式来实现多处理器之间的原子操作。首先处理器会自动保证基本的内存操作的原子性。处理器保证从系统内存中读取或写入一个字节是原子的，意思是当一个处理器读取一个字节时，其他处理器不能访问这个字节的内存地址。

 

1.处理器自动保证基本内存操作的原子性

首先处理器会自动保证基本的内存操作的原子性。处理器保证从系统内存当中读取或者写入一个字节是原子的，意思是当一个处理器读取一个字节时，其他处理器不能访问这个字节的内存地址。奔腾6和最新的处理器能自动保证单处理器对同一个缓存行里进行16/32/64位的操作是原子的，但是复杂的内存操作处理器不能自动保证其原子性，比如跨总线宽度，跨多个缓存行，跨页表的访问。但是处理器提供总线锁定和缓存锁定两个机制来保证复杂内存操作的原子性。

 

2. 总线锁定

如果多个处理器一起对共享变量进行读改写操作（i++就是典型的读改写操作），这个读改写操作就不是原子的。如上图所示，各个处理器将i的值读入自己的处理器缓存中，各自对各自的缓存里的i值进行操作，然后分别写入系统内存从而导致了问题的产生。要想对共享变量的读改写操作也是原子性的，必须保证，CPU1读改写共享变量的时候，CPU2不能操作该共享变量内存地址的缓存行。

处理器的总线锁就是这么来保证原子性的，所谓总线锁就是使用处理器提供的一个LOCK #信号，当一个处理器在总线上输出此信号时，其他处理器的请求将会被阻塞住，那么该处理器可以独占共享内存。

3. 缓存锁定

在同一时刻我们只需要保证对某一个内存地址的操作是原子性就可以了，但是总线锁把CPU和内存之间的通信锁住了，这使得锁定期间，其他处理器不能操作其他内存地址的数据，所以总线锁定的开销比较大。

频繁使用的内存会缓存在处理器的L1，L2，L3高速缓存中，那么原子操作就可以直接在处理器内部缓存进行，并不需要声明总线锁。

缓存锁是：一个处理器的缓存写回到内存会导致其他处理器的缓存无效，在多核处理器中，例如在Pentium和P6 family处理中，如果通过嗅探一个处理器来检测到其他处理器打算写内存地址，而这个地址当前处于共享状态，那么正在嗅探的处理器将使它的缓存行无效，在下次访问相同内存地址时，强制执行缓存行填充。

但是有两种情况是不能使用缓存锁：一是不能缓存到处理器的数据以及跨多个缓存行的数据；而是有些处理器不支持缓存锁定。

 

CAS优缺点

• 优点

非阻塞的轻量级的乐观锁，通过CPU指令实现，在资源竞争不激烈的情况下性能高，相比synchronized重量锁，synchronized会进行比较复杂的加锁、解锁和唤醒操作。

• 缺点

CAS存在的问题

CAS虽然很高效的解决原子操作，但是CAS仍然存在三大问题。ABA问题，循环时间长开销大和只能保证一个共享变量的原子操作

1.  ABA问题。因为CAS需要在操作值的时候检查下值有没有发生变化，如果没有发生变化则更新，但是如果一个值原来是A，变成了B，又变成了A，那么使用CAS进行检查时会发现它的值没有发生变化，但是实际上却变化了。ABA问题的解决思路就是使用版本号。在变量前面追加上版本号，每次变量更新的时候把版本号加一，那么A－B－A 就会变成1A-2B－3A。

从Java1.5开始JDK的atomic包里提供了一个类AtomicStampedReference来解决ABA问题。这个类的compareAndSet方法作用是首先检查当前引用是否等于预期引用，并且当前标志是否等于预期标志，如果全部相等，则以原子方式将该引用和该标志的值设置为给定的更新值。

关于ABA问题参考文档: http://blog.hesey.net/2011/09/resolve-aba-by-atomicstampedreference.html

2. 循环时间长开销大。自旋时间过长，消耗CPU资源，如果资源竞争激烈，多线程自旋长时间消耗资源。自旋CAS如果长时间不成功，会给CPU带来非常大的执行开销。如果JVM能支持处理器提供的pause指令那么效率会有一定的提升，pause指令有两个作用，第一它可以延迟流水线执行指令（de-pipeline）,使CPU不会消耗过多的执行资源，延迟的时间取决于具体实现的版本，在一些处理器上延迟时间是零。第二它可以避免在退出循环的时候因内存顺序冲突（memory order violation）而引起CPU流水线被清空（CPU pipeline flush），从而提高CPU的执行效率。

3. 只能保证一个共享变量的原子操作。当对一个共享变量执行操作时，我们可以使用循环CAS的方式来保证原子操作，但是对多个共享变量操作时，循环CAS就无法保证操作的原子性，这个时候就可以用锁，或者有一个取巧的办法，就是把多个共享变量合并成一个共享变量来操作。比如有两个共享变量i＝2,j=a，合并一下ij=2a，然后用CAS来操作ij。从Java1.5开始JDK提供了AtomicReference类来保证引用对象之间的原子性，你可以把多个变量放在一个对象里来进行CAS操作。

 

使用乐观锁还是悲观锁

从上面对两种锁的介绍，我们知道两种锁各有优缺点，不可认为一种好于另一种，像乐观锁适用于写比较少的情况下（多读场景），即冲突真的很少发生的时候，这样可以省去了锁的开销，加大了系统的吞吐量。但如果是多写的情况，一般会经常发生冲突，这就会导致CAS算法会不断的进行retry，这样反倒是降低了性能，所以一般多写的场景下用悲观锁就比较合适。

 

CAS应用

由于CAS是CPU指令，我们只能通过JNI与操作系统交互，关于CAS的方法都在sun.misc包下Unsafe的类里，java.util.concurrent.atomic包下的原子类等通过CAS来实现原子操作。

 

concurrent包的实现

由于java的CAS同时具有 volatile 读和volatile写的内存语义，因此Java线程之间的通信现在有了下面四种方式：

1. A线程写volatile变量，随后B线程读这个volatile变量。
2. A线程写volatile变量，随后B线程用CAS更新这个volatile变量。
3. A线程用CAS更新一个volatile变量，随后B线程用CAS更新这个volatile变量。
4. A线程用CAS更新一个volatile变量，随后B线程读这个volatile变量。

 

对volatile写和volatile读的内存语义做个总结。

❑ 线程A写一个volatile变量，实质上是线程A向接下来将要读这个volatile变量的某个线程发出了（其对共享变量所做修改的）消息。

❑ 线程B读一个volatile变量，实质上是线程B接收了之前某个线程发出的（在写这个volatile变量之前对共享变量所做修改的）消息。

❑ 线程A写一个volatile变量，随后线程B读这个volatile变量，这个过程实质上是线程A通过主内存向线程B发送消息。

 

Java的CAS会使用现代处理器上提供的高效机器级别原子指令，这些原子指令以原子方式对内存执行读-改-写操作，这是在多处理器中实现同步的关键（从本质上来说，能够支持原子性读-改-写指令的计算机器，是顺序计算图灵机的异步等价机器，因此任何现代的多处理器都会去支持某种能对内存执行原子性读-改-写操作的原子指令）。同时，volatile变量的读/写和CAS可以实现线程之间的通信。把这些特性整合在一起，就形成了整个concurrent包得以实现的基石。如果我们仔细分析concurrent包的源代码实现，会发现一个通用化的实现模式：

1. 首先，声明共享变量为volatile；
2. 然后，使用CAS的原子条件更新来实现线程之间的同步；
3. 同时，配合以volatile的读/写和CAS所具有的volatile读和写的内存语义来实现线程之间的通信。

AQS，非阻塞数据结构和原子变量类（java.util.concurrent.atomic包中的类），这些concurrent包中的基础类都是使用这种模式来实现的，而concurrent包中的高层类又是依赖于这些基础类来实现的。从整体来看，concurrent包的实现示意图如下：