本文將從happens-before關係出發，結合ReentranLock源碼，如何用記憶體屏障、CAS操作、LOCK指令實現鎖的功能。 ...

鎖在多線程中是必不可少的，他給多線程提供了同步的功能，讓多線程可以互斥的執行同步塊，並具有可見性。

本文將從happens-before關係出發，結合ReentranLock源碼，如何用記憶體屏障、CAS操作、LOCK指令實現鎖的功能。

鎖的happens-before關係

happens-before規則

程式順序規則：在一個線程中，前面的操作happens-before後面的操作

鎖規則：對同一個鎖，解鎖happens-before加鎖。

傳遞性規則：A happens-before B，B happens-before C，則A happens-before C

從這段代碼看看happens-before關係，線程A先執行store()，線程B後執行load()

int value = 0;
boolean finish = 0;

//線程A
void store(){
    //A：加鎖前的操作
    synchronized(this){ //B：加鎖
        value = 1;      //C：寫value
        finish = true;  //D：寫finish
    }                   //E：解鎖
    //F：解鎖後的操作
}

//線程B
void load(){
    //G：加鎖前的操作
    synchronized(this){ //H：加鎖
        if(finish){     //I：讀finish
            assert value == 1; //J：讀value
        }
    }                   //K：解鎖
    //L：解鎖後的操作
}

這裡有13個happens-before關係。①～⑤是線程A的程式順序關係，⑥~⑩是線程B的程式順序關係，⑪是鎖規則關係，⑫～⑬是傳遞性關係

鎖happens-before關係

從happens-before關係分析可見性

①~⑩根據程式順序規則，只要不重排序數據依賴的指令，執行結果就是正確的，就可以保證在單線程內的可見性。

⑪根據鎖規則，E happens-before H，也就是線程A解鎖 happens-before 線程B加鎖。

⑫根據傳遞性規則，線程A解鎖前的操作都需要對線程B加鎖可見，ABCDE happens-before H，也就是線程A解鎖及其先前操作 happens-before 線程B加鎖。

⑬再根據傳遞性規則，線程A解鎖前的操作都需要對線程B加鎖之後的操作可見，ABCDE happens-before HIJKL，最終得出線程A解鎖及其先前操作 happens-before 線程B加鎖及其後續操作。

這樣來看，為了保證解鎖及其之前操作的可見性，需要把解鎖線程的本地記憶體刷新到主記憶體去。同時為了保證加鎖線程讀到最新的值，需要將本地記憶體的共用變數設為無效，重新從主記憶體中讀取。

實現鎖的原理

前面得出來的鎖的可見性：線程A解鎖及其先前操作 happens-before 線程B加鎖及其後續操作

將前面得出的可見性分解為三個等級：

線程A解鎖 happens-before 線程B加鎖
線程A解鎖及其先前操作 happens-before 線程B加鎖
線程A解鎖及其先前操作 happens-before 線程B加鎖及其後續操作

由於這是在多線程間實現可見性，那麼就要考慮本地記憶體和主記憶體的緩存不一致問題，需要用到JMM的記憶體屏障：

記憶體屏障

逐級的實現可見性：

1) 對於第一級可見性，線程A解鎖需要對線程B加鎖可見，在多線程間的，會引發緩存不一致，所以要把線程A的本地記憶體刷新到主記憶體去。所以在解鎖、加鎖之間需要加寫讀記憶體屏障，這裡有兩種實現方式：

線上程A解鎖後加StoreLoad Barrier
線上程B加鎖前，加StoreLoad Barrier。

在常用的開發模式中，常常是一個線程負責寫，多個線程負責讀，典型的像生產者-消費者模式。所以相較後者，前者的記憶體屏障執行次數少，性能高。採用第一種實現方式比較好。

2) 對於第二級可見性，線程A解鎖前的操作需要對加鎖可見，也就是線程A解鎖前的操作不能被重排序到解鎖後。由於只有寫操作會對改變共用變數，所以需要在解鎖前加上StoreStore Barrier。

3) 對於第三級可見性，線程B加鎖之後的讀寫操作不能重排序到加鎖前，否則線程B可能讀不到線程A的操作結果，以及線程B可能線上程A之前修改了共用變數。所以需要線上程B加鎖後加上LoadLoad Barrier 和 LoadStore Barrier。

綜上所述：

解鎖前加StoreStore Barrier
解鎖後加StoreLoad Barrier
加鎖後加LoadLoad Barrier 和LoadStore Barrier

加上記憶體屏障後的程式：

int value = 0;
boolean finish = 0;

//線程A
void store(){
    //A：加鎖前的操作
    synchronized(this){ //B：加鎖
        loadLoadBarrier();
        loadStoreBarrier();
        value = 1;      //C：寫value
        finish = true;  //D：寫finish
        storeStoreBarrier();
                        //E：解鎖
        storeLoadBarrier();
    }                   
    //F：解鎖後的操作
}

//線程B
void load(){
    //G：加鎖前的操作
    synchronized(this){ //H：加鎖
        loadLoadBarrier();
        loadStoreBarrier();
        if(finish){     //I：讀finish
            assert value == 1; //J：讀value
        }
        storeStoreBarrier();
                        //K：解鎖
        storeLoadBarrier();
    }
    //L：解鎖後的操作
}

分析鎖的源碼

Java提供的鎖可以分為兩種：隱形鎖和顯性鎖。隱形鎖就是常用的synchronized語句，是由Java語法提供的，語法的源碼比較難找。在這裡用顯性鎖的源碼去分析，顯性鎖實際上是Java中的一個工具類，允許以調用函數的形式去加鎖解鎖。從功能上看顯性鎖的功能更強大，因為其能通過繼承實現不同演算法的鎖，以便根據實際情況選擇合適的鎖。這裡使用ReentrantLock去分析源碼。

在前面實現鎖的原理中，得出實現可見性的原理是在加鎖解鎖前後加上記憶體屏障。乍一看這不是和volatile的原理是一模一樣的嗎，連使用的記憶體屏障種類順序都一樣。所以在ReentrantLock中，他復用了volatile提供的可見性，並沒有再去寫記憶體屏障。

在ReentrantLock中，他有一個變數state是volatile的（繼承自AbstractQueuedSynchorinizer）。解鎖-加鎖分別是由寫-讀state這個volatile變數去實現的。這個state變數可以理解成所被重入的次數（ReentrantLock是可重入鎖），0表示沒有線程擁有該鎖，2表示被擁有者連續擁有了兩次且沒有釋放。

ReentranLoack分為公平鎖和不公平鎖，下麵分別看看這兩種鎖在解鎖加鎖的源碼。

解鎖的實現

公平鎖和不公平鎖的對於解鎖的實現都是一樣的，都是寫state變數。最後都是調用ReentranLock.Sync.tryRelease()

//在java.util.concurrent.locks.ReentranLock.Sync.tryRelease()
protected final boolean tryRelease(int releases) {
    int c = getState() - releases;
    if (Thread.currentThread() != getExclusiveOwnerThread())//如果當前線程不是該鎖的擁有者則拋出異常
        throw new IllegalMonitorStateException();
    boolean free = false;//鎖是否可用
    if (c == 0) {//state=0 表示該持有線程完全釋放該鎖，需要設置free為可用狀態以及擁有者線程置空
        free = true;
        setExclusiveOwnerThread(null);
    }
    setState(c);//在釋放鎖的最後，寫state
    return free;
}

根據volatile原理知道，寫state這個volatile變數也就相當於

storeStoreBarrier();
解鎖;
storeLoadBarrier();

這樣的記憶體屏障和前面鎖原理分析的是一樣的，所以寫volatile與解鎖有一樣的功能，也就能使用寫volatile的方式實現解鎖。

加鎖的實現

加鎖中，公平鎖和不公平鎖實現的方式就有很大的不同了。公平鎖使用的是讀volatile，不公平鎖使用的是CompareAndSet(CAS)。

公平鎖的加鎖實現

先看公平鎖的讀state加鎖實現，核心代碼在ReentranLock.FairSync.tryAcquire()。

//在java.util.concurrent.locks.ReentranLock.FairSync.tryAcquire()
protected final boolean tryAcquire(int acquires) {
    final Thread current = Thread.currentThread();
    int c = getState();//在加鎖的一開始，讀state
    if (c == 0) {//鎖處於可用狀態
        if (!hasQueuedPredecessors() &&
            compareAndSetState(0, acquires)) {
            setExclusiveOwnerThread(current);//設置鎖被當前線程擁有
            return true;
        }
    }
    else if (current == getExclusiveOwnerThread()) {//state>0，重入了
        int nextc = c + acquires;
        if (nextc < 0)
            throw new Error("Maximum lock count exceeded");//超過最大重入次數2147483648（最大的int）
        setState(nextc);//更新state
        return true;
    }
    return false;
}

根據volatile原理知道，讀state這個volatile變數也就相當於

加鎖;
loadLoadBarrier();
loadStoreBarrier();

這樣的記憶體屏障和前面鎖原理分析的是一樣的，所以讀volatile與加鎖有一樣的功能，也就能使用讀volatile的方式實現加鎖。

不公平鎖的加鎖實現

//在java.util.concurrent.locks.ReentranLock.NoFairSync.lock()
final void lock() {
    if (compareAndSetState(0, 1))//如果該鎖可用，則占有
        setExclusiveOwnerThread(Thread.currentThread());
    else//嘗試重入
        acquire(1);
}
//在java.util.concurrent.locks.AbstractQueuedSynchronizer.compareAndSetState()
protected final boolean compareAndSetState(int expect, int update) {
    return unsafe.compareAndSwapInt(this, stateOffset, expect, update);
}

如果該鎖沒占用的時候，調用的是unsafe.compareAndSwapInt()，這是一個CAS操作。如果該鎖已經被占有了，嘗試重入，這部分的代碼是使用和公平鎖一樣的讀state方式實現的。

unsafe.compareAndSwapInt()這是一個native方法，是用JNI調用C++或者彙編的，需要到openjdk看，位置在：openjdk-7-fcs-src-b147-
27_jun_2011\openjdk\hotspot\src\os_cpu\windows_x86\vm\atomic_windows_x86.inline.hpp

//CAS源碼：
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           //要修改的地址，也就是state變數
        mov ecx, exchange_value //新值值
        mov eax, compare_value  //期待值
        LOCK_IF_MP(mp)          //如果是多處理器，在下麵指令前加上LOCK首碼
        cmpxchg dword ptr [edx], ecx//[edx]與eax對比，相同則[edx]=ecx，否則不操作
    }
}

這裡看到有一個LOCK_IF_MP，作用是如果是多處理器，在指令前加上LOCK首碼，因為在單處理器中，是不會存在緩存不一致的問題的，所有線程都在一個CPU上跑，使用同一個緩存區，也就不存在本地記憶體與主記憶體不一致的問題，不會造成可見性問題。然而在多核處理器中，共用記憶體需要從寫緩存中刷新到主記憶體中去，並遵循緩存一致性協議通知其他處理器更新緩存。
Lock在這裡的作用：

在cmpxchg執行期間，鎖住記憶體地址[edx]，其他處理器不能訪問該記憶體，保證原子性。即使是在32位機器上修改64位的記憶體也可以保證原子性。
將本處理器上寫緩存全部強制寫回主存中去，也就是寫屏障，保證每個線程的本地記憶體與主存一致。
禁止cmpxchg與前後任何指令重排序，防止指令重排序。

可見CAS操作具有與讀寫volatile變數一致的作用，都能保證可見性。

鎖的實現原理