CAS

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

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

前言概述

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

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

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

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

參考

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

CAS 概述

舉個例子，如 i++，它是分三步的

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

再將 i 加上 1

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

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

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

原理

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

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

舊期望值 - 操作前的值

新值 - 操作后的值

CAS 的操作簡而言之就是 compare and swap

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

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

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

ABA 問題

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

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

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

缺點(diǎn)

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

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)硬件級別的原子操作，底層是用匯編實(shí)現(xiàn)的

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

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

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

CPU

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

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

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

使用總線鎖保證原子性

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

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

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

使用緩存鎖保證原子性

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