0粘招、引言
自J2SE1.5開始，java中的同步類（Lock嘉冒，Semphore等等）都基于AbstractQueuedSynchronizer（后文簡稱AQS）才睹。AQS提供了一種原子式管理同步狀態(tài)、阻塞和喚醒線程功能以及隊列模型的簡單框架淳梦。
本文主要是分析此框架的實現(xiàn)者Doug Lea寫的一篇介紹AQS的論文（→猛戳這里拿原文←）析砸，并沒有完全翻譯原文，所以想看原文的在上面拿原文爆袍。
1首繁、基本功能
同步器至少要有以下兩種類型的方法acquire和release
- acquire：至少要有一個操作能實現(xiàn)對調用線程的阻塞，直到同步器允許它進行操作陨囊。
- release：至少要有一個操作能用一種方式解鎖一個或者更多個已經(jīng)阻塞的線程改變同步狀態(tài)弦疮。
同時，同步器還需要支持以下幾種功能：
- 非阻塞式的同步過程嘗試(tryLock)
- 可選的超時機制蜘醋，可以允許程序放棄等待
- 可以通過中斷執(zhí)行取消
而為了適應不同的同步器胁塞，同步器要支持兩種模式
- 獨占式exclusive。要保證一次只有一個線程可以經(jīng)過阻塞點
- 共享式shared压语∠邢龋可以允許多個線程阻塞點
2、性能要求
AQS對性能改進的關注點不是主要在于減小空間的開銷和時間的開銷无蜂。
原因是：對于開發(fā)者來說，只在需要的時候構建同步器蒙谓，實在沒有必要為了這部分空間的消耗去壓縮空間斥季。與此同時，同步器大部分情況是用在多線程的情況下，產(chǎn)生一些競爭也是可以想象到的酣倾。
AQS的性能重點在于可擴展性
AQS的幾個改進目標：
- 可預見性的保證同步器的效率舵揭，甚至在其發(fā)生競爭的情形下。
- 減少那些已經(jīng)被允許通過阻塞點的線程但是沒有通過的消耗時間躁锡。
對比自旋鎖來說午绳，自旋鎖的響應速度很快，但是在線程競爭特別激烈的情況下映之，由于大量的內存讀取拦焚，會降低其響應的速度。
AQS的框架必須能夠提供一些監(jiān)視和檢查的基本操作杠输，以便用戶發(fā)現(xiàn)和緩解瓶頸赎败。例如：提供一個方式，決定多少個線程會被阻塞蠢甲。
3僵刮、設計與實現(xiàn)
acquire和release操作的偽代碼可以很容易的寫出來如下：
acquire{
while (同步狀態(tài)不允許獲取) {
若當前線程沒有入隊，那么就將其入隊鹦牛；
可能會阻塞當前線程搞糕；
}
如果它已經(jīng)入隊了，就將其出隊
}
release {
更新同步狀態(tài)
if(狀態(tài)表示允許一個阻塞的線程去acquire)
釋放一個或多個隊列中的線程
}
3.1曼追、同步狀態(tài)State
AQS采用了int（4個字節(jié)）的變量來持有同步狀態(tài)窍仰。使用getState， setState拉鹃， compareAndSetState方法來進行狀態(tài)的獲取和更新辈赋。
以上的方法，它們依賴于volatile這個機制來進行讀寫膏燕，compare-and-swap機制去實現(xiàn)compareAndSetState方法钥屈。（CAS操作如果不清楚的可以自行搜索相關的內容）
AQS是一個抽象類，它的tryAcquire和tryRelease方法都需要子類去實現(xiàn)坝辫。兩個方法都支持傳入一個int類型的參數(shù)篷就。這個參數(shù)主要用來實現(xiàn)不同子類功能的〗Γ【例如】：reentrant lock竭业，當在返回一個條件等待后重新去獲取鎖權限是，它會重新建立一個遞歸計數(shù)及舍。
3.2未辆、阻塞
AQS沒有采用Thread.suspend和Thread.resume這兩種方式，以上兩種方式都有嚴重的安全問題锯玛，容易造成死鎖等咐柜。
AQS采用了java.util.concurrent.locks包下的LockSupport類兼蜈。該類可以響應中斷操作，可以設置超時時間等拙友。此機制與Win32內的“消費事件”機制为狸，Linux NPTL線程庫的方式類似。
3.3遗契、核心隊列
AQS框架的核心是阻塞線程的隊列辐棒。也就是一個FIFO（先進先出）隊列。AQS不支持基于優(yōu)先級的同步器牍蜂。
AQS的鎖策略采用的CLH而不是MCS漾根，原因是CLH要比MCS更適合處理取消和超時。
CLH隊列的入隊和出隊操作是與它的鎖操作息息相關捷兰。它有兩個原子操作更新域立叛，head和taiil。初始化時贡茅，將指向一個虛假的節(jié)點秘蛇。
每個節(jié)點的release狀態(tài)都保存在它的前驅節(jié)點內，while (pred.status != RELEASED);后就可以開始自旋顶考。若持有前驅節(jié)點的域赁还，CLH鎖可以處理超時和其他形式的取消操作。
AQS對CLH機制有兩點修改
3.3.1驹沿、修改點1：增加后繼節(jié)點訪問域
AQS增加了節(jié)點node訪問其后繼節(jié)點的next域艘策。由于AQS隊列是雙向隊列，所以CAS操作也沒有很好的方式對兩個方向都做到完全的原子性更新渊季。后繼結點的更新就采用了
pred.next = node; 這種方式朋蔫。
當后繼結點可能出現(xiàn)退出的情形，AQS會通過pred域往前遍歷確定是否是真的退出了却汉。
3.3.2驯妄、修改點2：采用狀態(tài)域控制阻塞
CLH采用自旋進行線程的阻塞，AQS沒有采用這種方式合砂，而采用之前介紹過的State字段進行阻塞青扔。
AQS需要控制在頭節(jié)點調用tryAcquire方法適合才允許通過，其他情況acquire和block都會失敗翩伪。每次只需檢查當前節(jié)點的前驅節(jié)點是不是head微猖，這一點減少了CLH對內存的讀取競爭，同時還能避免不必要的阻塞和喚醒操作缘屹。
【原因】：在調用park方法前凛剥，線程會設置一個“SIGNAL”信號，然后重新檢查同步狀態(tài)轻姿，再確定是否需要再次調用park方法犁珠。
3.3.3傅瞻、修改點3：利用垃圾回收機制進行節(jié)點存儲管理
AQS主要使用在出隊的時候置null方式回收節(jié)點內存，這可以有效的避免復雜的處理和瓶頸盲憎。
這里我們可以給出更加具體的acquire方法
acquire {
if (!tryAcquire(arg)) {
node = 創(chuàng)建隊列并且新入隊節(jié)點;
pred = 節(jié)點的有效前驅節(jié)點;
while (pred 不是頭節(jié)點 || !tryAcquire(arg)) {
if (pred的狀態(tài)位是Signal信號)
park();
else
CAS操作設置pred的Signal信號;
pred = node節(jié)點的有效前驅節(jié)點;
}
head = node;
}
}
而release方法也可以得到如下：
release {
if (tryRelease(arg) && 頭節(jié)點的狀態(tài)是Signal) {
將頭節(jié)點的狀態(tài)設置為不是Signal;
如果頭節(jié)點的后繼結點存在，則將其喚醒胳挎。
}
}
【時間復雜度】acquire的循環(huán)次數(shù)由tryAcquire方法的性質決定饼疙。在不考慮線程等消耗，以及取消操作的情況下慕爬，它的時間復雜度是O(1)窑眯。在取消操作的情況下，確認前驅和后繼結點后重置同步狀態(tài)需要O(n)次遍歷（n為隊列的長度）医窿。
3.4磅甩、條件隊列
AQS中的ConditionObject提供一個能讓同步器使用的類。它既符合Lock接口姥卢，又能持有互斥的同步機制卷要。
ConditionObject類提供了類似await，signal独榴，signalAll操作的API僧叉。這些方法的作用與Object.wait方法是一樣的。ConditionObject使用與同步器同樣的內部隊列棺榔，不過與同步器存儲在分開的條件隊列中瓶堕。
3.4.1、基本操作流程
基本的await操作如下：
- 創(chuàng)建并添加新的節(jié)點到條件隊列中症歇；
- 釋放鎖郎笆；
- 阻塞直到節(jié)點在鎖隊列中
- 重新獲取鎖。
基本的signal操作如下：
- 傳遞條件隊列的第一個節(jié)點到鎖隊列中
3.4.2忘晤、取消流程
上述基本操作的實現(xiàn)并不困難宛蚓，而處理取消，超時和線程的中斷是實現(xiàn)的難點德频。
- 中斷發(fā)生在await操作之前苍息，此方法一定要拋出一個InterruptedException
- 中斷發(fā)生在await操作之后，此方法不拋出異常壹置，而是系統(tǒng)的中斷狀態(tài)集
條件隊列需要一個狀態(tài)位竞思，當出現(xiàn)Signal信號失敗，就將信號傳遞到隊列的下一個節(jié)點內钞护。而如果出現(xiàn)Cancel信號失敗盖喷，就取消傳遞操作，喚醒鎖的重新獲取操作难咕。
4课梳、用法
4.1距辆、控制公平性
AQS并不保證同步器一定是公平的。tryAcquire方法是在入隊操作前的一個檢驗暮刃，因此完全可以在入隊前跨算，“偷取”獲取的權限。
非公平的FIFO策略（獲取到鎖的順序不一定是隊列中的順序）椭懊，將tryAcquire方法中每次進入都會進行競爭诸蚕，無論當前線程是否是隊列的頭節(jié)點。只要進入的線程速度更快氧猬，那么隊列中的節(jié)點即使解除了阻塞背犯，依然會重新阻塞回去。
公平的FIFO策略盅抚，只需要將tryAcquire方法在當前線程不是隊列的頭節(jié)點時放回失敗就行漠魏。次之的方式，只需要判斷隊列是否為空妄均，空隊列就可以放回tryAcquire成功柱锹。
同步器的公平性設置主要是在多處理器情況下，才能發(fā)揮出其水平丛晦。多處理器往往會有更多的競爭奕纫，也就更有可能發(fā)生一個線程發(fā)現(xiàn)鎖現(xiàn)在被其他線程需要的情形。
4.2烫沙、同步器
- ReentrantLock
- ReentrantReadWriteLock
- Semaphore
- CountDownLatch
- FutureTask(1.5以后不再使用AQS)
- SynchronousQueue
自我總結
這里開始就不是論文中的內容了匹层。AQS的基本理解就在上述的文章中，后面我們再深入到AQS的源碼中看它具體的實現(xiàn)方式锌蓄。
AQS的核心內容就在于它處理阻塞和非阻塞的方式升筏，如何用隊列實現(xiàn)不同功能的同步器，如何控制同步器的性能瘸爽。
如果你對上述問題還不了解您访，可以再深入看看原文。
參考文章
- Doug Lea. The java.util.concurrent Synchronizer Framework.
如有翻譯不周到的地方剪决，歡迎批評指正灵汪！
