前言：最近這段時比較忙，抽空寫的這篇總結(jié)，該篇文章是繼上一篇深入理解鎖的實(shí)現(xiàn)原理（一）的補(bǔ)充，希望能對大家有所幫助~

Reentrantlock鎖的實(shí)現(xiàn)原理：
基于AQS實(shí)現(xiàn)定義源碼：

public abstract class AbstractQueuedSynchronizer extends
    AbstractOwnableSynchronizer implements java.io.Serializable {  
    //等待隊(duì)列的頭節(jié)點(diǎn)    
    private transient volatile Node head;    
    //等待隊(duì)列的尾節(jié)點(diǎn)    
    private transient volatile Node tail;    
    //同步狀態(tài)    
    private volatile int state;    
    protected final int getState() { 
      return state;
    }    

  protected final void setState(int newState) { 
      state = newState;
    }    
  ...
}

AQS的實(shí)現(xiàn)原理：
隊(duì)列同步器AbstractQueueSynchronized，是用來構(gòu)建鎖或者其他同步組件的基礎(chǔ)架構(gòu)，內(nèi)部使用一個int成員變量表示同步狀態(tài)，通過內(nèi)置的FIFO隊(duì)列來完成資源獲取線程的排隊(duì)工作，其中內(nèi)部狀態(tài)state，等待隊(duì)列的頭結(jié)點(diǎn)head和尾節(jié)點(diǎn)tail都是通過volatile修飾來保證多線程之間的可見。子類重寫tryAcquire和tryRelease方法通過CAS指令修改狀態(tài)變量state

概述：AQS內(nèi)部會保存一個狀態(tài)變量state，通過CAS修改該變量的值，修改成功的線程表示獲取到該鎖，沒有修改成功，或者發(fā)現(xiàn)狀態(tài)state已經(jīng)是加鎖狀態(tài)，則通過一個Waiter對象封裝線程，添加到等待隊(duì)列中，并掛起等待被喚醒內(nèi)置FIFO隊(duì)列：
源碼如下：

static final class Node {        
    static final Node SHARED = new Node();        
    static final Node EXCLUSIVE = null;        
    static final int CANCELLED =  1;        
    static final int SIGNAL    = -1;        
    static final int CONDITION = -2;        
    static final int PROPAGATE = -3;        
    volatile int waitStatus;       
    volatile Node prev;        
    volatile Node next;        
    volatile Thread thread;        
    Node nextWaiter;       
     ...    
 }

解析：
第一個默認(rèn)是head節(jié)點(diǎn)，是一個空節(jié)點(diǎn)，可以理解成代表當(dāng)前持有鎖的線程，每當(dāng)有線程競爭失敗，都是插入到隊(duì)列的尾節(jié)點(diǎn)，tail節(jié)點(diǎn)始終指向隊(duì)列中的最后一個元素。每個節(jié)點(diǎn)中， 除了存儲了當(dāng)前線程，前后節(jié)點(diǎn)的引用以外，還有一個waitStatus變量，用于描述節(jié)點(diǎn)當(dāng)前的狀態(tài)。多線程并發(fā)執(zhí)行時，隊(duì)列中會有多個節(jié)點(diǎn)存在，這個waitStatus其實(shí)代表對應(yīng)線程的狀態(tài)：有的線程可能獲取鎖因?yàn)槟承┰蚍艞壐偁?；有的線程在等待滿足條件，滿足之后才能執(zhí)行等等。一共有4中狀態(tài)：

• CANCELLED 取消狀態(tài)
• SIGNAL 等待觸發(fā)狀態(tài)
• CONDITION 等待條件狀態(tài)
• PROPAGATE 狀態(tài)需要向后傳播

等待隊(duì)列是FIFO先進(jìn)先出，只有前一個節(jié)點(diǎn)的狀態(tài)為SIGNAL時，當(dāng)前節(jié)點(diǎn)的線程才能被掛起。

線程獲取鎖的過程：

1. 線程A執(zhí)行CAS執(zhí)行成功，state值被修改并返回true，線程A繼續(xù)執(zhí)行。
2. 線程A執(zhí)行CAS指令失敗，說明線程B也在執(zhí)行CAS指令且成功，這種情況下線程A會執(zhí)行步驟3。
3. 生成新Node節(jié)點(diǎn)node，并通過CAS指令插入到等待隊(duì)列的隊(duì)尾（同一時刻可能會有多個Node節(jié)點(diǎn)插入到等待隊(duì)列中），如果tail節(jié)點(diǎn)為空，則將head節(jié)點(diǎn)指向一個空節(jié)點(diǎn)（代表線程B）
4. node插入到隊(duì)尾后，該線程不會立馬掛起，會進(jìn)行自旋操作。因?yàn)樵趎ode的插入過程，線程B（即之前沒有阻塞的線程）可能已經(jīng)執(zhí)行完成，所以要判斷該node的前一個節(jié)點(diǎn)pred是否為head節(jié)點(diǎn)（代表線程B），如果pred == head，表明當(dāng)前節(jié)點(diǎn)是隊(duì)列中第一個“有效的”節(jié)點(diǎn)，因此再次嘗試tryAcquire獲取鎖，
   4.1 如果成功獲取到鎖，表明線程B已經(jīng)執(zhí)行完成，線程A不需要掛起。
   4.2. 如果獲取失敗，表示線程B還未完成，至少還未修改state值。進(jìn)行步驟5。
5. 前面我們已經(jīng)說過只有前一個節(jié)點(diǎn)pred的線程狀態(tài)為SIGNAL時，當(dāng)前節(jié)點(diǎn)的線程才能被掛起。
   5.1. 如果pred的waitStatus == 0，則通過CAS指令修改waitStatus為Node.SIGNAL。
   5.2. 如果pred的waitStatus > 0，表明pred的線程狀態(tài)CANCELLED，需從隊(duì)列中刪除。
   5.3. 如果pred的waitStatus為Node.SIGNAL，則通過LockSupport.park()方法把線程A掛起，并等待被喚醒，被喚醒后進(jìn)入步驟6
6. 線程每次被喚醒時，都要進(jìn)行中斷檢測，如果發(fā)現(xiàn)當(dāng)前線程被中斷，那么拋出InterruptedException并退出循環(huán)。從無限循環(huán)的代碼可以看出，并不是被喚醒的線程一定能獲得鎖，必須調(diào)用tryAccquire重新競爭，因?yàn)殒i是非公平的，有可能被新加入的線程獲得，從而導(dǎo)致剛被喚醒的線程再次被阻塞，這個細(xì)節(jié)充分體現(xiàn)了“非公平”的精髓

線程釋放鎖的過程：

1. 如果頭結(jié)點(diǎn)head的waitStatus值為-1，則用CAS指令重置為0；
2. 找到waitStatus值小于0的節(jié)點(diǎn)s，通過LockSupport.unpark(s.thread)喚醒線程。

CAS的實(shí)現(xiàn)原理：
Compare and Swap，比較并替換，通過unsafe類的compareAndSwap方法實(shí)現(xiàn)。

1. Unsafe，是CAS的核心類，由于Java方法無法直接訪問底層系統(tǒng)，需要通過本地（native）方法來訪問，Unsafe相當(dāng)于一個后門，基于該類可以直接操作特定內(nèi)存的數(shù)據(jù)。
2. Unsafe類中的compareAndSwap方法：

public final native boolean compareAndSwapInt(
  Object paramObject, long paramLong, int paramInt1, int paramInt2);

各參數(shù)的含義：

• paramObject：要修改的對象
• paramLong：對象中要修改變量的偏移量
• paramInt1：修改之前的值
• paramInt2：預(yù)想修改后的值

系統(tǒng)級別上的實(shí)現(xiàn)：

1. Linux x86：Atomin::cmpxchg方法源碼如下：

inline jint Atomic::cmpxchg (jint exchange_value, volatile jint* dest, 
  jint compare_value) {
  int mp = os::is_MP();
  __asm__ volatile (LOCK_IF_MP(%4) "cmpxchgl %1,(%3)"
                    : "=a" (exchange_value)
                    : "r" (exchange_value), "a" (compare_value), "r" (dest), "r" (mp)
                    : "cc", "memory");
  return exchange_value;
}

2. Windows x86：

inline jint Atomic::cmpxchg (jint exchange_value, volatile jint* dest, jint compare_value) {
    int mp = os::isMP(); //判斷是否是多處理器
    _asm {
        mov edx, dest
        mov ecx, exchange_value
        mov eax, compare_value
        LOCK_IF_MP(mp)
        cmpxchg dword ptr [edx], ecx
    }
}

// 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:

LOCK_IF_MP根據(jù)當(dāng)前系統(tǒng)是否為多核處理器決定是否為cmpxchg指令添加lock前綴。

• 如果是多處理器，為cmpxchg指令添加lock前綴。
• 反之，就省略lock前綴。（單處理器會不需要lock前綴提供的內(nèi)存屏障效果）

CAS存在的問題：ABA問題
問題：如果變量V初次讀取的時候是A，并且在準(zhǔn)備賦值的時候檢查到它仍然是A，那能說明它的值沒有被其他線程修改過了嗎？

如果在這段期間曾經(jīng)被改成B，然后又改回A，那CAS操作就會誤認(rèn)為它從來沒有被修改過。針對這種情況，java并發(fā)包中提供了一個帶有標(biāo)記的原子引用類AtomicStampedReference，它可以通過控制變量值的版本來保證CAS的正確性。

Reentrantlock非公平鎖的實(shí)現(xiàn)：
在非公平鎖中，每當(dāng)線程執(zhí)行l(wèi)ock方法時，都嘗試?yán)肅AS把state從0設(shè)置為1
競爭過程：

1. 線程A和B同時執(zhí)行CAS指令，假設(shè)線程A成功，線程B失敗，則表明線程A成功獲取鎖，并把同步器中的exclusiveOwnerThread設(shè)置為線程A。
2. 競爭失敗的線程B，在nonfairTryAcquire方法中，會再次嘗試獲取鎖，Doug lea會在多處嘗試重新獲取鎖，應(yīng)該是在這段時間如果線程A釋放鎖，線程B就可以直接獲取鎖而不用掛起。完

公平鎖的實(shí)現(xiàn)：
在公平鎖中，每當(dāng)線程執(zhí)行l(wèi)ock方法時，如果同步器的隊(duì)列中有線程在等待，則直接加入到隊(duì)列中.

條件變量Condition：
源碼如下：

public class ConditionObject implements Condition, java.io.Serializable {
    /** First node of condition queue. */
    private transient Node firstWaiter;
    /** Last node of condition queue. */
    private transient Node lastWaiter;
    public final void signal() {}
    public final void signalAll() {}
    public final void awaitUninterruptibly() {}  
    public final void await() throws InterruptedException {}
}

1. Synchronized中，所有的線程都在同一個object的條件隊(duì)列上等待。而ReentrantLock中，每個condition都維護(hù)了一個條件隊(duì)列。
2. 每一個Lock可以有任意數(shù)據(jù)的Condition對象，Condition是與Lock綁定的，所以就有Lock的公平性特性：如果是公平鎖，線程為按照FIFO的順序從Condition.await中釋放，如果是非公平鎖，那么后續(xù)的鎖競爭就不保證FIFO順序了。
3. Condition接口定義的方法，await對應(yīng)于Object.wait，signal對應(yīng)于Object.notify，signalAll對應(yīng)于Object.notifyAll。特別說明的是Condition的接口改變名稱就是為了避免與Object中的wait/notify/notifyAll的語義和使用上混淆。

await實(shí)現(xiàn)邏輯：

1. 將線程A加入到條件等待隊(duì)列中，如果最后一個節(jié)點(diǎn)是取消狀態(tài)，則從對列中刪除。
2. 線程A釋放鎖，實(shí)質(zhì)上是線程A修改AQS的狀態(tài)state為0，并喚醒AQS等待隊(duì)列中的線程B，線程B被喚醒后，嘗試獲取鎖，接下去的過程就不重復(fù)說明了。
3. 線程A釋放鎖并喚醒線程B之后，如果線程A不在AQS的同步隊(duì)列中，線程A將通過LockSupport.park進(jìn)行掛起操作。
4. 隨后，線程A等待被喚醒，當(dāng)線程A被喚醒時，會通過acquireQueued方法競爭鎖，如果失敗，繼續(xù)掛起。如果成功，線程A從await位置恢復(fù)。

signal實(shí)現(xiàn)邏輯：

1. 接著上述場景，線程B執(zhí)行了signal方法，取出條件隊(duì)列中的第一個非CANCELLED節(jié)點(diǎn)線程，即線程A。另外，signalAll就是喚醒條件隊(duì)列中所有非CANCELLED節(jié)點(diǎn)線程。遇到CANCELLED線程就需要將其從隊(duì)列中刪除。
2. 通過CAS修改線程A的waitStatus為0，表示該節(jié)點(diǎn)已經(jīng)不是等待條件狀態(tài)，并將線程A插入到AQS的等待隊(duì)列中。
3. 喚醒線程A，線程A和別的線程進(jìn)行鎖的競爭。

總結(jié)：

1. ReentrantLock提供了內(nèi)置鎖類似的功能和內(nèi)存語義。
2. 此外，ReetrantLock還提供了其它功能，包括定時的鎖等待、可中斷的鎖等待、公平性、以及實(shí)現(xiàn)非塊結(jié)構(gòu)的加鎖、Condition，對線程的等待和喚醒等操作更加靈活，一個ReentrantLock可以有多個Condition實(shí)例，所以更有擴(kuò)展性，不過ReetrantLock需要顯示的獲取鎖，并在finally中釋放鎖，否則后果很嚴(yán)重。
3. ReentrantLock在性能上似乎優(yōu)于Synchronized，其中在jdk1.6中略有勝出，在1.5中是遠(yuǎn)遠(yuǎn)勝出。那么為什么不放棄內(nèi)置鎖，并在新代碼中都使用ReetrantLock？
4. 在java1.5中， 內(nèi)置鎖與ReentrantLock相比有例外一個優(yōu)點(diǎn)：在線程轉(zhuǎn)儲中能給出在哪些調(diào)用幀中獲得了哪些鎖，并能夠檢測和識別發(fā)生死鎖的線程。Reentrant的非塊狀特性任然意味著，獲取鎖的操作不能與特定的棧幀關(guān)聯(lián)起來，而內(nèi)置鎖卻可以。
5. 因?yàn)閮?nèi)置鎖時JVM的內(nèi)置屬性，所以未來更可能提升synchronized而不是ReentrantLock的性能。例如對線程封閉的鎖對象消除優(yōu)化，通過增加鎖粒度來消除內(nèi)置鎖的同步。

參考資料：《并發(fā)編程的藝術(shù)》、博客