synchronized和LOCK的實現(xiàn)原理-深入JVM鎖機制-比較好

JVM底層又是如何實現(xiàn)synchronized的？目前在Java中存在兩種鎖機制：synchronized和Lock，Lock接口及其實現(xiàn)類是JDK5增加的內容，其作者是大名鼎鼎的并發(fā)專家DougLea。本文并不比較synchronized與Lock孰優(yōu)孰劣，只是介紹二者的實現(xiàn)原理。數(shù)據(jù)同步需要依賴鎖，那鎖的同步又依賴誰？synchronized給出的答案是在軟件層面依賴JVM，而Lock給出的方案是在硬件層面依賴特殊的CPU指令，大家可能會進一步追問：JVM底層又是如何實現(xiàn)synchronized的？本文所指說的JVM是指Hotspot的6u23版本，下面首先介紹synchronized的實現(xiàn)：synrhronized關鍵字簡潔、清晰、語義明確，因此即使有了Lock接口，使用的還是非常廣泛。其應用層的語義是可以把任何一個非null對象作為"鎖"，當synchronized作用在方法上時，鎖住的便是對象實例（this）；當作用在靜態(tài)方法時鎖住的便是對象對應的Class實例，因為Class數(shù)據(jù)存在于永久帶，因此靜態(tài)方法鎖相當于該類的一個全局鎖；當synchronized作用于某一個對象實例時，鎖住的便是對應的代碼塊。在HotSpotJVM實現(xiàn)中，鎖有個專門的名字：對象監(jiān)視器。1.線程狀態(tài)及狀態(tài)轉換當多個線程同時請求某個對象監(jiān)視器時，對象監(jiān)視器會設置幾種狀態(tài)用來區(qū)分請求的線程：ContentionList：所有請求鎖的線程將被首先放置到該競爭隊列EntryList：ContentionList中那些有資格成為候選人的線程被移到EntryListWaitSet：那些調用wait方法被阻塞的線程被放置到WaitSetOnDeck：任何時刻最多只能有一個線程正在競爭鎖，該線程稱為OnDeckOwner：獲得鎖的線程稱為Owner!Owner：釋放鎖的線程下圖反映了個狀態(tài)轉換關系：新請求鎖的線程將首先被加入到ConetentionList中，當某個擁有鎖的線程（Owner狀態(tài)）調用unlock之后，如果發(fā)現(xiàn)EntryList為空則從ContentionList中移動線程到EntryList，下面說明下ContentionList和EntryList的實現(xiàn)方式：1.1ContentionList虛擬隊列ContentionList并不是一個真正的Queue，而只是一個虛擬隊列，原因在于ContentionList是由Node及其next指針邏輯構成，并不存在一個Queue的數(shù)據(jù)結構。ContentionList是一個后進先出（LIFO）的隊列，每次新加入Node時都會在隊頭進行，通過CAS改變第一個節(jié)點的的指針為新增節(jié)點，同時設置新增節(jié)點的next指向后續(xù)節(jié)點，而取得操作則發(fā)生在隊尾。顯然，該結構其實是個Lock-Free的隊列。因為只有Owner線程才能從隊尾取元素，也即線程出列操作無爭用，當然也就避免了CAS的ABA問題。1.2EntryListEntryList與ContentionList邏輯上同屬等待隊列，ContentionList會被線程并發(fā)訪問，為了降低對ContentionList隊尾的爭用，而建立EntryList。Owner線程在unlock時會從ContentionList中遷移線程到EntryList，并會指定EntryList中的某個線程（一般為Head）為Ready（OnDeck）線程。Owner線程并不是把鎖傳遞給OnDeck線程，只是把競爭鎖的權利交給OnDeck，OnDeck線程需要重新競爭鎖。這樣做雖然犧牲了一定的公平性，但極大的提高了整體吞吐量，在Hotspot中把OnDeck的選擇行為稱之為“競爭切換”。OnDeck線程獲得鎖后即變?yōu)閛wner線程，無法獲得鎖則會依然留在EntryList中，考慮到公平性，在EntryList中的位置不發(fā)生變化（依然在隊頭）。如果Owner線程被wait方法阻塞，則轉移到WaitSet隊列；如果在某個時刻被notify/notifyAll喚醒，則再次轉移到EntryList。2.自旋鎖那些處于ContetionList、EntryList、WaitSet中的線程均處于阻塞狀態(tài)，阻塞操作由操作系統(tǒng)完成（在Linxu下通過pthread_mutex_lock函數(shù)）。線程被阻塞后便進入內核（Linux）調度狀態(tài)，這個會導致系統(tǒng)在用戶態(tài)與內核態(tài)之間來回切換，嚴重影響鎖的性能緩解上述問題的辦法便是自旋，其原理是：當發(fā)生爭用時，若Owner線程能在很短的時間內釋放鎖，則那些正在爭用線程可以稍微等一等（自旋），在Owner線程釋放鎖后，爭用線程可能會立即得到鎖，從而避免了系統(tǒng)阻塞。但Owner運行的時間可能會超出了臨界值，爭用線程自旋一段時間后還是無法獲得鎖，這時爭用線程則會停止自旋進入阻塞狀態(tài)（后退）?；舅悸肪褪亲孕?，不成功再阻塞，盡量降低阻塞的可能性，這對那些執(zhí)行時間很短的代碼塊來說有非常重要的性能提高。自旋鎖有個更貼切的名字：自旋-指數(shù)后退鎖，也即復合鎖。很顯然，自旋在多處理器上才有意義。還有個問題是，線程自旋時做些啥？其實啥都不做，可以執(zhí)行幾次for循環(huán)，可以執(zhí)行幾條空的匯編指令，目的是占著CPU不放，等待獲取鎖的機會。所以說，自旋是把雙刃劍，如果旋的時間過長會影響整體性能，時間過短又達不到延遲阻塞的目的。顯然，自旋的周期選擇顯得非常重要，但這與操作系統(tǒng)、硬件體系、系統(tǒng)的負載等諸多場景相關，很難選擇，如果選擇不當，不但性能得不到提高，可能還會下降，因此大家普遍認為自旋鎖不具有擴展性。自旋優(yōu)化策略對自旋鎖周期的選擇上，HotSpot認為最佳時間應是一個線程上下文切換的時間，但目前并沒有做到。經(jīng)過調查，目前只是通過匯編暫停了幾個CPU周期，除了自旋周期選擇，HotSpot還進行許多其他的自旋優(yōu)化策略，具體如下：如果平均負載小于CPUs則一直自旋如果有超過(CPUs/2)個線程正在自旋，則后來線程直接阻塞如果正在自旋的線程發(fā)現(xiàn)Owner發(fā)生了變化則延遲自旋時間（自旋計數(shù)）或進入阻塞如果CPU處于節(jié)電模式則停止自旋自旋時間的最壞情況是CPU的存儲延遲（CPUA存儲了一個數(shù)據(jù)，到CPUB得知這個數(shù)據(jù)直接的時間差）自旋時會適當放棄線程優(yōu)先級之間的差異那synchronized實現(xiàn)何時使用了自旋鎖？答案是在線程進入ContentionList時，也即第一步操作前。線程在進入等待隊列時首先進行自旋嘗試獲得鎖，如果不成功再進入等待隊列。這對那些已經(jīng)在等待隊列中的線程來說，稍微顯得不公平。還有一個不公平的地方是自旋線程可能會搶占了Ready線程的鎖。自旋鎖由每個監(jiān)視對象維護，每個監(jiān)視對象一個。3.JVM1.6偏向鎖在JVM1.6中引入了偏向鎖，偏向鎖主要解決無競爭下的鎖性能問題，首先我們看下無競爭下鎖存在什么問題：現(xiàn)在幾乎所有的鎖都是可重入的，也即已經(jīng)獲得鎖的線程可以多次鎖住/解鎖監(jiān)視對象，按照之前的HotSpot設計，每次加鎖/解鎖都會涉及到一些CAS操作（比如對等待隊列的CAS操作），CAS操作會延遲本地調用，因此偏向鎖的想法是一旦線程第一次獲得了監(jiān)視對象，之后讓監(jiān)視對象“偏向”這個線程，之后的多次調用則可以避免CAS操作，說白了就是置個變量，如果發(fā)現(xiàn)為true則無需再走各種加鎖/解鎖流程。但還有很多概念需要解釋、很多引入的問題需要解決：3.1CAS及SMP架構CAS為什么會引入本地延遲？這要從SMP（對稱多處理器）架構說起，下圖大概表明了SMP的結構：其意思是所有的CPU會共享一條系統(tǒng)總線（BUS），靠此總線連接主存。每個核都有自己的一級緩存，各核相對于BUS對稱分布，因此這種結構稱為“對稱多處理器”。而CAS的全稱為Compare-And-Swap，是一條CPU的原子指令，其作用是讓CPU比較后原子地更新某個位置的值，經(jīng)過調查發(fā)現(xiàn)，其實現(xiàn)方式是基于硬件平臺的匯編指令，就是說CAS是靠硬件實現(xiàn)的，JVM只是封裝了匯編調用，那些AtomicInteger類便是使用了這些封裝后的接口。Core1和Core2可能會同時把主存中某個位置的值Load到自己的L1Cache中，當Core1在自己的L1Cache中修改這個位置的值時，會通過總線，使Core2中L1Cache對應的值“失效”，而Core2一旦發(fā)現(xiàn)自己L1Cache中的值失效（稱為Cache命中缺失）則會通過總線從內存中加載該地址最新的值，大家通過總線的來回通信稱為“Cache一致性流量”，因為總線被設計為固定的“通信能力”，如果Cache一致性流量過大，總線將成為瓶頸。而當Core1和Core2中的值再次一致時，稱為“Cache一致性”，從這個層面來說，鎖設計的終極目標便是減少Cache一致性流量。而CAS恰好會導致Cache一致性流量，如果有很多線程都共享同一個對象，當某個CoreCAS成功時必然會引起總線風暴，這就是所謂的本地延遲，本質上偏向鎖就是為了消除CAS，降低Cache一致性流量。Cache一致性：上面提到Cache一致性，其實是有協(xié)議支持的，現(xiàn)在通用的協(xié)議是MESI（最早由Intel開始支持），具體參考：，以后會仔細講解這部分。Cache一致性流量的例外情況：其實也不是所有的CAS都會導致總線風暴，這跟Cache一致性協(xié)議有關，具體參考：NUMA(NonUniformMemoryAccessAchitecture）架構：與SMP對應還有非對稱多處理器架構，現(xiàn)在主要應用在一些高端處理器上，主要特點是沒有總線，沒有公用主存，每個Core有自己的內存，針對這種結構此處不做討論。3.2偏向解除偏向鎖引入的一個重要問題是，在多爭用的場景下，如果另外一個線程爭用偏向對象，擁有者需要釋放偏向鎖，而釋放的過程會帶來一些性能開銷，但總體說來偏向鎖帶來的好處還是大于CAS代價的。4.總結關于鎖，JVM中還引入了一些其他技術比如鎖膨脹等，這些與自旋鎖、偏向鎖相比影響不是很大，這里就不做介紹。通過上面的介紹可以看出，synchronized的底層實現(xiàn)主要依靠Lock-Free的隊列，基本思路是自旋后阻塞，競爭切換后繼續(xù)競爭鎖，稍微犧牲了公平性，但獲得了高吞吐量。JVM中的另一種鎖Lock的實現(xiàn)前文（深入JVM鎖機制-synchronized）分析了JVM中的synchronized實現(xiàn)，本文繼續(xù)分析JVM中的另一種鎖Lock的實現(xiàn)。與synchronized不同的是，Lock完全用Java寫成，在java這個層面是無關JVM實現(xiàn)的。在java.util.concurrent.locks包中有很多Lock的實現(xiàn)類，常用的有ReentrantLock、ReadWriteLock（實現(xiàn)類ReentrantReadWriteLock），其實現(xiàn)都依賴java.util.concurrent.AbstractQueuedSynchronizer類，實現(xiàn)思路都大同小異，因此我們以ReentrantLock作為講解切入點。1.ReentrantLock的調用過程經(jīng)過觀察ReentrantLock把所有Lock接口的操作都委派到一個Sync類上，該類繼承了AbstractQueuedSynchronizer：viewplainstaticabstractclassSyncextendsAbstractQueuedSynchronizerSync又有兩個子類：viewplainfinalstaticclassNonfairSyncextendsSyncviewplainfinalstaticclassFairSyncextendsSync顯然是為了支持公平鎖和非公平鎖而定義，默認情況下為非公平鎖。先理一下Reentrant.lock()方法的調用過程（默認非公平鎖）：這些討厭的Template模式導致很難直觀的看到整個調用過程，其實通過上面調用過程及AbstractQueuedSynchronizer的注釋可以發(fā)現(xiàn)，AbstractQueuedSynchronizer中抽象了絕大多數(shù)Lock的功能，而只把tryAcquire方法延遲到子類中實現(xiàn)。tryAcquire方法的語義在于用具體子類判斷請求線程是否可以獲得鎖，無論成功與否AbstractQueuedSynchronizer都將處理后面的流程。2.鎖實現(xiàn)（加鎖）簡單說來，AbstractQueuedSynchronizer會把所有的請求線程構成一個CLH隊列，當一個線程執(zhí)行完畢（lock.unlock()）時會激活自己的后繼節(jié)點，但正在執(zhí)行的線程并不在隊列中，而那些等待執(zhí)行的線程全部處于阻塞狀態(tài)，經(jīng)過調查線程的顯式阻塞是通過調用LockSupport.park()完成，而LockSupport.park()則調用sun.misc.Unsafe.park()本地方法，再進一步，HotSpot在Linux中中通過調用pthread_mutex_lock函數(shù)把線程交給系統(tǒng)內核進行阻塞。該隊列如圖：與synchronized相同的是，這也是一個虛擬隊列，不存在隊列實例，僅存在節(jié)點之間的前后關系。令人疑惑的是為什么采用CLH隊列呢？原生的CLH隊列是用于自旋鎖，但DougLea把其改造為阻塞鎖。當有線程競爭鎖時，該線程會首先嘗試獲得鎖，這對于那些已經(jīng)在隊列中排隊的線程來說顯得不公平，這也是非公平鎖的由來，與synchronized實現(xiàn)類似，這樣會極大提高吞吐量。如果已經(jīng)存在Running線程，則新的競爭線程會被追加到隊尾，具體是采用基于CAS的Lock-Free算法，因為線程并發(fā)對Tail調用CAS可能會導致其他線程CAS失敗，解決辦法是循環(huán)CAS直至成功。AbstractQueuedSynchronizer的實現(xiàn)非常精巧，令人嘆為觀止，不入細節(jié)難以完全領會其精髓，下面詳細說明實現(xiàn)過程：2.1Sync.nonfairTryAcquirenonfairTryAcquire方法將是lock方法間接調用的第一個方法，每次請求鎖時都會首先調用該方法。viewplainfinalbooleannonfairTryAcquire(intacquires){finalThreadcurrent=Thread.currentThread();intc=getState();if(c==0){if(compareAndSetState(0,acquires)){setExclusiveOwnerThread(current);returntrue;}}elseif(current==getExclusiveOwnerThread()){intnextc=c+acquires;if(nextc<0)//overflowthrownewError("Maximumlockcountexceeded");setState(nextc);returntrue;}returnfalse;}該方法會首先判斷當前狀態(tài)，如果c==0說明沒有線程正在競爭該鎖，如果不c!=0說明有線程正擁有了該鎖。如果發(fā)現(xiàn)c==0，則通過CAS設置該狀態(tài)值為acquires,acquires的初始調用值為1，每次線程重入該鎖都會+1，每次unlock都會-1，但為0時釋放鎖。如果CAS設置成功，則可以預計其他任何線程調用CAS都不會再成功，也就認為當前線程得到了該鎖，也作為Running線程，很顯然這個Running線程并未進入等待隊列。如果c!=0但發(fā)現(xiàn)自己已經(jīng)擁有鎖，只是簡單地++acquires，并修改status值，但因為沒有競爭，所以通過setStatus修改，而非CAS，也就是說這段代碼實現(xiàn)了偏向鎖的功能，并且實現(xiàn)的非常漂亮。2.2AbstractQueuedSynchronizer.addWaiteraddWaiter方法負責把當前無法獲得鎖的線程包裝為一個Node添加到隊尾：viewplainprivateNodeaddWaiter(Nodemode){Nodenode=newNode(Thread.currentThread(),mode);//Trythefastpathofenq;backuptofullenqonfailureNodepred=tail;if(pred!=null){node.prev=pred;if(compareAndSetTail(pred,node)){pred.next=node;returnnode;}}enq(node);returnnode;}其中參數(shù)mode是獨占鎖還是共享鎖，默認為null，獨占鎖。追加到隊尾的動作分兩步：如果當前隊尾已經(jīng)存在(tail!=null)，則使用CAS把當前線程更新為Tail如果當前Tail為null或則線程調用CAS設置隊尾失敗，則通過enq方法繼續(xù)設置Tail下面是enq方法：viewplainprivateNodeenq(finalNodenode){for(;;){Nodet=tail;if(t==null){//MustinitializeNodeh=newNode();//Dummyheaderh.next=node;node.prev=h;if(compareAndSetHead(h)){tail=node;returnh;}}else{node.prev=t;if(compareAndSetTail(t,node)){t.next=node;returnt;}}}}該方法就是循環(huán)調用CAS，即使有高并發(fā)的場景，無限循環(huán)將會最終成功把當前線程追加到隊尾（或設置隊頭）。總而言之，addWaiter的目的就是通過CAS把當前現(xiàn)在追加到隊尾，并返回包裝后的Node實例。把線程要包裝為Node對象的主要原因，除了用Node構造供虛擬隊列外，還用Node包裝了各種線程狀態(tài)，這些狀態(tài)被精心設計為一些數(shù)字值：SIGNAL(-1)：線程的后繼線程正/已被阻塞，當該線程release或cancel時要重新這個后繼線程(unpark)CANCELLED(1)：因為超時或中斷，該線程已經(jīng)被取消CONDITION(-2)：表明該線程被處于條件隊列，就是因為調用了Condition.await而被阻塞PROPAGATE(-3)：傳播共享鎖0：0代表無狀態(tài)2.3AbstractQueuedSynchronizer.acquireQueuedacquireQueued的主要作用是把已經(jīng)追加到隊列的線程節(jié)點（addWaiter方法返回值）進行阻塞，但阻塞前又通過tryAccquire重試是否能獲得鎖，如果重試成功能則無需阻塞，直接返回viewplainfinalbooleanacquireQueued(finalNodenode,intarg){try{booleaninterrupted=false;for(;;){finalNodep=node.predecessor();if(p==head&&tryAcquire(arg)){setHead(node);p.next=null;//helpGCreturninterrupted;}if(shouldParkAfterFailedAcquire(p,node)&&parkAndCheckInterrupt())interrupted=true;}}catch(RuntimeExceptionex){cancelAcquire(node);throwex;}}仔細看看這個方法是個無限循環(huán)，感覺如果p==head&&tryAcquire(arg)條件不滿足循環(huán)將永遠無法結束，當然不會出現(xiàn)死循環(huán)，奧秘在于第12行的parkAndCheckInterrupt會把當前線程掛起，從而阻塞住線程的調用棧。viewplainprivatefinalbooleanparkAndCheckInterrupt(){LockSupport.park(this);returnTerrupted();}如前面所述，LockSupport.park最終把線程交給系統(tǒng)（Linux）內核進行阻塞。當然也不是馬上把請求不到鎖的線程進行阻塞，還要檢查該線程的狀態(tài)，比如如果該線程處于Cancel狀態(tài)則沒有必要，具體的檢查在shouldParkAfterFailedAcquire中：viewplainprivatestaticbooleanshouldParkAfterFailedAcquire(Nodepred,Nodenode){intws=pred.waitStatus;if(ws==Node.SIGNAL)/**Thisnodehasalreadysetstatusaskingarelease*tosignalit,soitcansafelypark*/returntrue;if(ws>0){/**Predecessorwascancelled.Skipoverpredecessorsand*indicateretry.*/do{node.prev=pred=pred.prev;}while(pred.waitStatus>0);pred.next=node;}else{/**waitStatusmustbe0orPROPAGATE.Indicatethatwe*needasignal,butdon'tparkyet.Callerwillneedto*retrytomakesureitcannotacquirebeforeparking.*/compareAndSetWaitStatus(pred,ws,Node.SIGNAL);}returnfalse;}檢查原則在于：規(guī)則1：如果前繼的節(jié)點狀態(tài)為SIGNAL，表明當前節(jié)點需要unpark，則返回成功，此時acquireQueued方法的第12行（parkAndCheckInterrupt）將導致線程阻塞規(guī)則2：如果前繼節(jié)點狀態(tài)為CANCELLED(ws>0)，說明前置節(jié)點已經(jīng)被放棄，則回溯到一個非取消的前繼節(jié)點，返回false，acquireQueued方法的無限循環(huán)將遞歸調用該方法，直至規(guī)則1返回true，導致線程阻塞規(guī)則3：如果前繼節(jié)點狀態(tài)為非SIGNAL、非CANCELLED，則設置前繼的狀態(tài)為SIGNAL，返回false后進入acquireQueued的無限循環(huán)，與規(guī)則2同總體看來，shouldParkAfterFailedAcquire就是靠前繼節(jié)點判斷當前線程是否應該被阻塞，如果前繼節(jié)點處于CANCELLED狀態(tài)，則順便刪除這些節(jié)點重新構造隊列。至此，鎖住線程的邏輯已經(jīng)完成，下面討論解鎖的過程。3.解鎖請求鎖不成功的線程會被掛起在acquireQueued方法的第12行，12行以后的代碼必須等線程被解鎖鎖才能執(zhí)行，假如被阻塞的線程得到解鎖，則執(zhí)行第13行，即設置interrupted=true，之后又進入無限循環(huán)。從無限循環(huán)的代碼可以看出，并不是得到解鎖的線程一定能獲得鎖，必須在第6行中調用tryAccquire重新競爭，因為鎖是非公平的，有可能被新加入的線程獲得，從而導致剛被喚醒的線程再次被阻塞，這個細節(jié)充分體現(xiàn)了“非公平”的精髓。通過之后將要介紹的解鎖機制會看到，第一個被解鎖的線程就是Head，因此p==head的判斷基本都會成功。至此可以看到，把tryAcquire方法延遲到子類中實現(xiàn)的做法非常精妙并具有極強的可擴展性，令人嘆為觀止！當然精妙的不是這個Templae設計模式，而是DougLea對鎖結構的精心布局。解鎖代碼相對簡單，主要體現(xiàn)在AbstractQueuedSynchronizer.release和Sync.tryRelease方法中：classAbstractQueuedSynchronizerviewplainpublicfinalbooleanrelease(intarg){if(tryRelease(arg)){Nodeh=head;if(h!=null&&h.waitStatus!=0)unparkSuccessor(h);returntrue;}returnfalse;}classSyncviewplainprotectedfinalbooleantryRelease(intreleases){intc=getState()-releases;if(Thread.currentThread()!=getExclusiveOwnerThread())thrownewIllegalMonitorStateException();booleanfree=false;if(c==0){free=true;setExclusiveOwnerThread(null);}setState(c);returnfree;}tryRelease與tryAcquire語義相同，把如何釋放的邏輯延遲到子類中。tryRelease語義很明確：如果線程多次鎖定，則進行多次釋放，直至status==0則真正釋放鎖，所謂釋放鎖即設置status為0，因為無競爭所以沒有使用CAS。release的語義在于：如果可以釋放鎖，則喚醒隊列第一個線程（Head），具體喚醒代碼如下：viewplainprivatevoidunparkSuccessor(Nodenode){/**Ifstatusisnegative(i.e.,possiblyneedingsignal)try*toclearinanticipationofsignalling.ItisOKifthis