本文僅供學習，原文： https://www.jianshu.com/p/fe027772e156
顯式鎖ReentrantLock和同步工具類的實現基礎都是AQS，所以合起來一齊研究。
AQS即是AbstractQueuedSynchronizer，一個用來構建鎖和同步工具的框架，包括常用的ReentrantLock、CountDownLatch、Semaphore等。
AQS沒有鎖之類的概念，它有個state變數，是個int型別，在不同場合有着不同含義。本文研究的是鎖，爲了好理解，姑且先把state當成鎖。
AQS圍繞state提供兩種基本操作「獲取」和「釋放」，有條雙向佇列存放阻塞的等待執行緒，並提供一系列判斷和處理方法，簡單說幾點：
至於執行緒是否可以獲得state，如何釋放state，就不是AQS關心的了，要由子類具體實現。
直接分析AQS的程式碼會比較難明白，所以結合子類ReentrantLock來分析。AQS的功能可以分爲獨佔和共用，ReentrantLock實現了獨佔功能，是本文分析的目標。
Lock lock = new ReentranLock();
lock.lock();
try{
//do something
}finally{
lock.unlock();
}
ReentrantLock實現了Lock介面，加鎖和解鎖都需要顯式寫出，注意一定要在適當時候unlock。
和synchronized相比，ReentrantLock用起來會複雜一些。在基本的加鎖和解鎖上，兩者是一樣的，所以無特殊情況下，推薦使用synchronized。ReentrantLock的優勢在於它更靈活、更強大，除了常規的lock()、unlock()之外，還有lockInterruptibly()、tryLock()方法，支援中斷、超時。
public ReentrantLock() {
sync = new NonfairSync();
}
public ReentrantLock(boolean fair) {
sync = fair ? new FairSync() : new NonfairSync();
}
ReentrantLock的內部類Sync繼承了AQS，分爲公平鎖FairSync和非公平鎖NonfairSync。
ReentrantLock預設使用非公平鎖是基於效能考慮，公平鎖爲了保證執行緒規規矩矩地排隊，需要增加阻塞和喚醒的時間開銷。如果直接插隊獲取非公平鎖，跳過了對佇列的處理，速度會更快。
final void lock() { acquire(1);}
public final void acquire(int arg) {
if (!tryAcquire(arg) &&
acquireQueued(addWaiter(Node.EXCLUSIVE), arg))
selfInterrupt();
}
先來看公平鎖的實現，lock方法很簡單的一句話呼叫AQS的acquire方法：
protected boolean tryAcquire(int arg) {
throw new UnsupportedOperationException();
}
噢，AQS的tryAcquire不能直接呼叫，因爲是否獲取鎖成功是由子類決定的，直接看ReentrantLock的tryAcquire的實現。
protected final boolean tryAcquire(int acquires) {
final Thread current = Thread.currentThread();
int c = getState();
if (c == 0) {
if (!hasQueuedPredecessors() &&
compareAndSetState(0, acquires)) {
setExclusiveOwnerThread(current);
return true;
}
}
else if (current == getExclusiveOwnerThread()) {
int nextc = c + acquires;
if (nextc < 0)
throw new Error("Maximum lock count exceeded");
setState(nextc);
return true;
}
return false;
}
獲取鎖成功分爲兩種情況，第一個if判斷AQS的state是否等於0，表示鎖沒有人佔有。接着，hasQueuedPredecessors判斷佇列是否有排在前面的執行緒在等待鎖，沒有的話呼叫compareAndSetState使用cas的方式修改state，傳入的acquires寫死是1。最後執行緒獲取鎖成功，setExclusiveOwnerThread將執行緒記錄爲獨佔鎖的執行緒。
第二個if判斷當前執行緒是否爲獨佔鎖的執行緒，因爲ReentrantLock是可重入的，執行緒可以不停地lock來增加state的值，對應地需要unlock來解鎖，直到state爲零。
如果最後獲取鎖失敗，下一步需要將執行緒加入到等待佇列。
AQS內部有一條雙向的佇列存放等待執行緒，節點是Node物件。每個Node維護了執行緒、前後Node的指針和等待狀態等參數。
執行緒在加入佇列之前，需要包裝進Node，呼叫方法是addWaiter：
private Node addWaiter(Node mode) {
Node node = new Node(Thread.currentThread(), mode);
// Try the fast path of enq; backup to full enq on failure
Node pred = tail;
if (pred != null) {
node.prev = pred;
if (compareAndSetTail(pred, node)) {
pred.next = node;
return node;
}
}
enq(node);
return node;
}
每個Node需要標記是獨佔的還是共用的，由傳入的mode決定，ReentrantLock自然是使用獨佔模式Node.EXCLUSIVE。
建立好Node後，如果佇列不爲空，使用cas的方式將Node加入到佇列尾。注意，這裏只執行了一次修改操作，並且可能因爲併發的原因失敗。因此修改失敗的情況和佇列爲空的情況，需要進入enq。
private Node enq(final Node node) {
for (;;) {
Node t = tail;
if (t == null) { // Must initialize
if (compareAndSetHead(new Node()))
tail = head;
} else {
node.prev = t;
if (compareAndSetTail(t, node)) {
t.next = node;
return t;
}
}
}
}
enq是個死回圈，保證Node一定能插入佇列。注意到，當佇列爲空時，會先爲頭節點建立一個空的Node，因爲頭節點代表獲取了鎖的執行緒，現在還沒有，所以先空着。
執行緒加入佇列後，下一步是呼叫acquireQueued阻塞執行緒。
final boolean acquireQueued(final Node node, int arg) {
boolean failed = true;
try {
boolean interrupted = false;
for (;;) {
//1
final Node p = node.predecessor();
if (p == head && tryAcquire(arg)) {
setHead(node);
p.next = null; // help GC
failed = false;
return interrupted;
}
//2
if (shouldParkAfterFailedAcquire(p, node) &&
parkAndCheckInterrupt())
interrupted = true;
}
} finally {
if (failed)
cancelAcquire(node);
}
}
標記1是執行緒喚醒後嘗試獲取鎖的過程。如果前一個節點正好是head，表示自己排在第一位，可以馬上呼叫tryAcquire嘗試。如果獲取成功就簡單了，直接修改自己爲head。這步是實現公平鎖的核心，保證釋放鎖時，由下個排隊執行緒獲取鎖。（看到執行緒解鎖時，再看回這裏啦）
標記2是執行緒獲取鎖失敗的處理。這個時候，執行緒可能等着下一次獲取，也可能不想要了，Node變數waitState描述了執行緒的等待狀態，一共四種情況：
static final int CANCELLED = 1; //取消
static final int SIGNAL = -1; //下個節點需要被喚醒
static final int CONDITION = -2; //執行緒在等待條件觸發
static final int PROPAGATE = -3; //（共用鎖）狀態需要向後傳播
shouldParkAfterFailedAcquire傳入當前節點和前節點，根據前節點的狀態，判斷執行緒是否需要阻塞。
private static boolean shouldParkAfterFailedAcquire(Node pred, Node node) {
int ws = pred.waitStatus;
if (ws == Node.SIGNAL)
return true;
if (ws > 0) {
do {
node.prev = pred = pred.prev;
} while (pred.waitStatus > 0);
pred.next = node;
} else {
compareAndSetWaitStatus(pred, ws, Node.SIGNAL);
}
return false;
}
如果執行緒需要阻塞，由parkAndCheckInterrupt方法進行操作。
private final boolean parkAndCheckInterrupt() {
LockSupport.park(this);
return Thread.interrupted();
}
parkAndCheckInterrupt使用了LockSupport，和cas一樣，最終使用UNSAFE呼叫Native方法實現執行緒阻塞（以後有機會就分析下LockSupport的原理，park和unpark方法作用類似於wait和notify）。最後返回執行緒喚醒後的中斷狀態，關於中斷，後文會分析。
到這裏總結一下獲取鎖的過程：執行緒去競爭一個鎖，可能成功也可能失敗。成功就直接持有資源，不需要進入佇列；失敗的話進入佇列阻塞，等待喚醒後再嘗試競爭鎖。
通過上面詳細的獲取鎖過程分析，釋放鎖過程大概可以猜到：頭節點是獲取鎖的執行緒，先移出佇列，再通知後面的節點獲取鎖。
public void unlock() {
sync.release(1);
}
ReentrantLock的unlock方法很簡單地呼叫了AQS的release：
public final boolean release(int arg) {
if (tryRelease(arg)) {
Node h = head;
if (h != null && h.waitStatus != 0)
unparkSuccessor(h);
return true;
}
return false;
}
和lock的tryAcquire一樣，unlock的tryRelease同樣由ReentrantLock實現：
protected final boolean tryRelease(int releases) {
int c = getState() - releases;
if (Thread.currentThread() != getExclusiveOwnerThread())
throw new IllegalMonitorStateException();
boolean free = false;
if (c == 0) {
free = true;
setExclusiveOwnerThread(null);
}
setState(c);
return free;
}
因爲鎖是可以重入的，所以每次lock會讓state加1，對應地每次unlock要讓state減1，直到爲0時將獨佔執行緒變數設定爲空，返回標記是否徹底釋放鎖。
最後，呼叫unparkSuccessor將頭節點的下個節點喚醒：
private void unparkSuccessor(Node node) {
int ws = node.waitStatus;
if (ws < 0)
compareAndSetWaitStatus(node, ws, 0);
Node s = node.next;
if (s == null || s.waitStatus > 0) {
s = null;
for (Node t = tail; t != null && t != node; t = t.prev)
if (t.waitStatus <= 0)
s = t;
}
if (s != null)
LockSupport.unpark(s.thread);
}
尋找下個待喚醒的執行緒是從佇列尾向前查詢的，找到執行緒後呼叫LockSupport的unpark方法喚醒執行緒。被喚醒的執行緒重新執行acquireQueued裡的回圈，就是上文關於acquireQueued標記1部分，執行緒重新嘗試獲取鎖。
static void selfInterrupt() {
Thread.currentThread().interrupt();
}
在acquire裡還有最後一句程式碼呼叫了selfInterrupt，功能很簡單，對當前執行緒產生一箇中斷請求。
爲什麼要這樣操作呢？因爲LockSupport.park阻塞執行緒後，有兩種可能被喚醒。
第一種情況，前節點是頭節點，釋放鎖後，會呼叫LockSupport.unpark喚醒當前執行緒。整個過程沒有涉及到中斷，最終acquireQueued返回false時，不需要呼叫selfInterrupt。
第二種情況，LockSupport.park支援響應中斷請求，能夠被其他執行緒通過interrupt()喚醒。但這種喚醒並沒有用，因爲執行緒前面可能還有等待執行緒，在acquireQueued的回圈裡，執行緒會再次被阻塞。parkAndCheckInterrupt返回的是Thread.interrupted()，不僅返回中斷狀態，還會清除中斷狀態，保證阻塞執行緒忽略中斷。最終acquireQueued返回true時，真正的中斷狀態已經被清除，需要呼叫selfInterrupt維持中斷狀態。
因此普通的lock方法並不能被其他執行緒中斷，ReentrantLock是可以支援中斷，需要使用lockInterruptibly。
兩者的邏輯基本一樣，不同之處是parkAndCheckInterrupt返回true時，lockInterruptibly直接throw new InterruptedException()。
分析完公平鎖的實現，還剩下非公平鎖，主要區別是獲取鎖的過程不同。
final void lock() {
if (compareAndSetState(0, 1))
setExclusiveOwnerThread(Thread.currentThread());
else
acquire(1);
}
在NonfairSync的lock方法裡，第一步直接嘗試將state修改爲1，很明顯，這是搶先獲取鎖的過程。如果修改state失敗，則和公平鎖一樣，呼叫acquire。
final boolean nonfairTryAcquire(int acquires) {
final Thread current = Thread.currentThread();
int c = getState();
if (c == 0) {
if (compareAndSetState(0, acquires)) {
setExclusiveOwnerThread(current);
return true;
}
}
else if (current == getExclusiveOwnerThread()) {
int nextc = c + acquires;
if (nextc < 0) // overflow
throw new Error("Maximum lock count exceeded");
setState(nextc);
return true;
}
return false;
}
nonfairTryAcquire和tryAcquire乍一看幾乎一樣，差異只是缺少呼叫hasQueuedPredecessors。這點體驗出公平鎖和非公平鎖的不同，公平鎖會關注佇列裡排隊的情況，老老實實按照FIFO的次序；非公平鎖只要有機會就搶佔，纔不管排隊的事。
總結：
1）AQS lock時加入佇列，unlock時移除佇列；
2）LockSupport park時阻塞進程，unpark時喚醒進程。