CAS

meislzhua 發(fā)布于2019-08-15 10:37 / 3171人閱讀

摘要：如果程序是在多處理器上運(yùn)行，就為指令加上前綴。關(guān)于的鎖有如下種處理器自動(dòng)保證基本內(nèi)存操作的原子性首先處理器會(huì)自動(dòng)保證基本的內(nèi)存操作的原子性。使用緩存鎖保證原子性第二個(gè)機(jī)制是通過緩存鎖定保證原子性。

前言概述

與鎖不同的是， CAS 是一種無鎖操作，一種無阻塞的算法，它實(shí)質(zhì)上不能說是一種鎖，而是將 CPU 充分利用起來的一種算法

CAS 廣泛應(yīng)用在數(shù)據(jù)結(jié)構(gòu)中，JDK中的 java.util.concurrent 并發(fā)包就是在其操作下建立的

眾所周知，JAVA 作為一門高級(jí)語言，是不支持一些底層處理的，例如指針，內(nèi)存控制等等，但大家可以看看 sun.misc.Unsafe 類，也是在它的支持下，JAVA 具備了對(duì)硬件級(jí)別原子操作的支持，這個(gè)包有很多應(yīng)用，例如 java.util.concurrent.atomic 包下的原子類都是基于其實(shí)現(xiàn) CAS 操作的

我的測(cè)試下，當(dāng)線程數(shù)量不大時(shí)，CAS 要快于鎖，但線程數(shù)量很多很多時(shí)，CAS 卻更慢了

參考

http://blog.csdn.net/hsuxu/ar...
http://www.cnblogs.com/mickol...

CAS 概述

舉個(gè)例子，如 i++，它是分三步的

先取內(nèi)存中的 i

再將 i 加上 1

最后將加完后的值賦給內(nèi)存中的 i

但若在其賦值前，i 的內(nèi)存值已經(jīng)被其他線程修改，此處肯定會(huì)丟失數(shù)據(jù)，也就是說它是線程不安全的

如果給這個(gè)操作加上鎖，那代價(jià)未免也太大了，CAS 便可以更快地解決這個(gè)問題

原理

CAS 的原理其實(shí)很簡(jiǎn)單，主要分三個(gè)參數(shù)

內(nèi)存值 - 內(nèi)存里的實(shí)際值

舊期望值 - 操作前的值

新值 - 操作后的值

CAS 的操作簡(jiǎn)而言之就是 compare and swap

將內(nèi)存值與舊期望值比較

若相等，則說明此值在操作中沒有被其他線程改變過，并將新值賦給內(nèi)存值

若不等，則說明此值在操作中已經(jīng)被其他線程改變過，并一直自旋直到相等

ABA 問題

簡(jiǎn)而言之，ABA 問題就是，比如我取內(nèi)存值 A，在我比較之前，它被其他人改成了 B，然后又被其他人改回了 A，而我之后再做比較，相等成立，但是又會(huì)造成數(shù)據(jù)丟失的問題

CAS 真正比較的應(yīng)該是 值的狀態(tài)，而不是值的大小，我可以給值附帶一個(gè) 版本號(hào)，然后更新時(shí)對(duì)版本號(hào)進(jìn)行值大小的 CAS 操作，或者附帶一個(gè) 時(shí)間戳也是一樣的，像現(xiàn)在數(shù)據(jù)庫大部分都是采用附加版本號(hào)的方法

大家也可以看看 java.util.concurrent.atomic.AtomicStampedReference 是怎么解決 ABA 問題的，在這里就不講述了

缺點(diǎn)

如果每個(gè)人都在自旋，CPU 的開銷將是巨大的，關(guān)于本人的測(cè)試，當(dāng)線程數(shù)量很多很多時(shí)，CAS 會(huì)更慢就是這個(gè)原因

AtomicInteger

我們來看看 java.util.concurrent.atomic.AtomicInteger 是怎么實(shí)現(xiàn)原子操作的，其主要成員如下

// Unsafe 類實(shí)例，具體的在下一篇文章詳細(xì)講，這里先跳過
private static final Unsafe unsafe = Unsafe.getUnsafe();
// 值偏移量
private static final long valueOffset;
// 內(nèi)部封裝值
private volatile int value;
// unsafe 初始化
static {
    try {
        valueOffset = unsafe.objectFieldOffset
            (AtomicInteger.class.getDeclaredField("value"));
    } catch (Exception ex) { 
        throw new Error(ex); 
    }
}

我們常用的 incrementAndGet 方法如下，在這里是直接調(diào)用 Unsafe 的 native 方法，實(shí)現(xiàn)硬件級(jí)別的原子操作，底層是用匯編實(shí)現(xiàn)的

public final int incrementAndGet() {
    return unsafe.getAndAddInt(this, valueOffset, 1) + 1;
}

這個(gè)本地方法在openjdk中依次調(diào)用的c++代碼為：unsafe.cpp，atomic.cpp和atomicwindowsx86.inline.hpp。這個(gè)本地方法的最終實(shí)現(xiàn)在openjdk的如下位置：openjdk-7-fcs-src-b147-27jun2011openjdkhotspotsrcoscpuwindowsx86vm atomicwindowsx86.inline.hpp（對(duì)應(yīng)于windows操作系統(tǒng)，X86處理器）。下面是對(duì)應(yīng)于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
  }
}

如上面源代碼所示，程序會(huì)根據(jù)當(dāng)前處理器的類型來決定是否為cmpxchg指令添加lock前綴。如果程序是在多處理器上運(yùn)行，就為cmpxchg指令加上lock前綴（lock cmpxchg）。反之，如果程序是在單處理器上運(yùn)行，就省略lock前綴（單處理器自身會(huì)維護(hù)單處理器內(nèi)的順序一致性，不需要lock前綴提供的內(nèi)存屏障效果）。

CPU

關(guān)于CPU的鎖有如下3種：

處理器自動(dòng)保證基本內(nèi)存操作的原子性

首先處理器會(huì)自動(dòng)保證基本的內(nèi)存操作的原子性。處理器保證從系統(tǒng)內(nèi)存當(dāng)中讀取或者寫入一個(gè)字節(jié)是原子的，意思是當(dāng)一個(gè)處理器讀取一個(gè)字節(jié)時(shí)，其他處理器不能訪問這個(gè)字節(jié)的內(nèi)存地址。奔騰6和最新的處理器能自動(dòng)保證單處理器對(duì)同一個(gè)緩存行里進(jìn)行16/32/64位的操作是原子的，但是復(fù)雜的內(nèi)存操作處理器不能自動(dòng)保證其原子性，比如跨總線寬度，跨多個(gè)緩存行，跨頁表的訪問。但是處理器提供總線鎖定和緩存鎖定兩個(gè)機(jī)制來保證復(fù)雜內(nèi)存操作的原子性

使用總線鎖保證原子性

第一個(gè)機(jī)制是通過總線鎖保證原子性。如果多個(gè)處理器同時(shí)對(duì)共享變量進(jìn)行讀改寫（i++就是經(jīng)典的讀改寫操作）操作，那么共享變量就會(huì)被多個(gè)處理器同時(shí)進(jìn)行操作，這樣讀改寫操作就不是原子的，操作完之后共享變量的值會(huì)和期望的不一致，舉個(gè)例子：如果i=1,我們進(jìn)行兩次i++操作，我們期望的結(jié)果是3，但是有可能結(jié)果是2，如圖

原因是有可能多個(gè)處理器同時(shí)從各自的緩存中讀取變量i，分別進(jìn)行加一操作，然后分別寫入系統(tǒng)內(nèi)存當(dāng)中。那么想要保證讀改寫共享變量的操作是原子的，就必須保證CPU1讀改寫共享變量的時(shí)候，CPU2不能操作緩存了該共享變量內(nèi)存地址的緩存。

處理器使用總線鎖就是來解決這個(gè)問題的。所謂總線鎖就是使用處理器提供的一個(gè)LOCK＃信號(hào)，當(dāng)一個(gè)處理器在總線上輸出此信號(hào)時(shí)，其他處理器的請(qǐng)求將被阻塞住,那么該處理器可以獨(dú)占使用共享內(nèi)存。

使用緩存鎖保證原子性

第二個(gè)機(jī)制是通過緩存鎖定保證原子性。在同一時(shí)刻我們只需保證對(duì)某個(gè)內(nèi)存地址的操作是原子性即可，但總線鎖定把CPU和內(nèi)存之間通信鎖住了，這使得鎖定期間，其他處理器不能操作其他內(nèi)存地址的數(shù)據(jù)，所以總線鎖定的開銷比較大，最近的處理器在某些場(chǎng)合下使用緩存鎖定代替總線鎖定來進(jìn)行優(yōu)化。