轉自：http://blog.csdn.net/chen77716/article/details/6618779
目前在java中存在兩種鎖機制：synchronized和lock，lock接口及其實作類是jdk5增加的内容，其作者是大名鼎鼎的并發專家doug lea。本文并不比較synchronized與lock孰優孰劣，隻是介紹二者的實作原理。
資料同步需要依賴鎖，那鎖的同步又依賴誰？synchronized給出的答案是在軟體層面依賴jvm，而lock給出的方案是在硬體層面依賴特殊的cpu指令，大家可能會進一步追問：jvm底層又是如何實作synchronized的？
本文所指說的jvm是指hotspot的6u23版本，下面首先介紹synchronized的實作：
synrhronized關鍵字簡潔、清晰、語義明确，是以即使有了lock接口，使用的還是非常廣泛。其應用層的語義是可以把任何一個非null對象作為"鎖"，當synchronized作用在方法上時，鎖住的便是對象執行個體（this）；當作用在靜态方法時鎖住的便是對象對應的class執行個體，因為class資料存在于永久帶，是以靜态方法鎖相當于該類的一個全局鎖；當synchronized作用于某一個對象執行個體時，鎖住的便是對應的代碼塊。在hotspot jvm實作中，鎖有個專門的名字：對象螢幕。
當多個線程同時請求某個對象螢幕時，對象螢幕會設定幾種狀态用來區分請求的線程：
contention list：所有請求鎖的線程将被首先放置到該競争隊列
entry list：contention list中那些有資格成為候選人的線程被移到entry list
wait set：那些調用wait方法被阻塞的線程被放置到wait set
ondeck：任何時刻最多隻能有一個線程正在競争鎖，該線程稱為ondeck
owner：獲得鎖的線程稱為owner
!owner：釋放鎖的線程
下圖反映了個狀态轉換關系：
新請求鎖的線程将首先被加入到conetentionlist中，當某個擁有鎖的線程（owner狀态）調用unlock之後，如果發現entrylist為空則從contentionlist中移動線程到entrylist，下面說明下contentionlist和entrylist的實作方式：
contentionlist并不是一個真正的queue，而隻是一個虛拟隊列，原因在于contentionlist是由node及其next指針邏輯構成，并不存在一個queue的資料結構。contentionlist是一個後進先出（lifo）的隊列，每次新加入node時都會在隊頭進行，通過cas改變第一個節點的的指針為新增節點，同時設定新增節點的next指向後續節點，而取得操作則發生在隊尾。顯然，該結構其實是個lock-free的隊列。
因為隻有owner線程才能從隊尾取元素，也即線程出列操作無争用，當然也就避免了cas的aba問題。
entrylist與contentionlist邏輯上同屬等待隊列，contentionlist會被線程并發通路，為了降低對contentionlist隊尾的争用，而建立entrylist。owner線程在unlock時會從contentionlist中遷移線程到entrylist，并會指定entrylist中的某個線程（一般為head）為ready（ondeck）線程。owner線程并不是把鎖傳遞給ondeck線程，隻是把競争鎖的權利交給ondeck，ondeck線程需要重新競争鎖。這樣做雖然犧牲了一定的公平性，但極大的提高了整體吞吐量，在hotspot中把ondeck的選擇行為稱之為“競争切換”。
ondeck線程獲得鎖後即變為owner線程，無法獲得鎖則會依然留在entrylist中，考慮到公平性，在entrylist中的位置不發生變化（依然在隊頭）。如果owner線程被wait方法阻塞，則轉移到waitset隊列；如果在某個時刻被notify/notifyall喚醒，則再次轉移到entrylist。
那些處于contetionlist、entrylist、waitset中的線程均處于阻塞狀态，阻塞操作由作業系統完成（在linxu下通過pthread_mutex_lock函數）。線程被阻塞後便進入核心（linux）排程狀态，這個會導緻系統在使用者态與核心态之間來回切換，嚴重影響鎖的性能
緩解上述問題的辦法便是自旋，其原理是：當發生争用時，若owner線程能在很短的時間内釋放鎖，則那些正在争用線程可以稍微等一等（自旋），在owner線程釋放鎖後，争用線程可能會立即得到鎖，進而避免了系統阻塞。但owner運作的時間可能會超出了臨界值，争用線程自旋一段時間後還是無法獲得鎖，這時争用線程則會停止自旋進入阻塞狀态（後退）。基本思路就是自旋，不成功再阻塞，盡量降低阻塞的可能性，這對那些執行時間很短的代碼塊來說有非常重要的性能提高。自旋鎖有個更貼切的名字：自旋-指數後退鎖，也即複合鎖。很顯然，自旋在多處理器上才有意義。
還有個問題是，線程自旋時做些啥？其實啥都不做，可以執行幾次for循環，可以執行幾條空的彙編指令，目的是占着cpu不放，等待擷取鎖的機會。是以說，自旋是把雙刃劍，如果旋的時間過長會影響整體性能，時間過短又達不到延遲阻塞的目的。顯然，自旋的周期選擇顯得非常重要，但這與作業系統、硬體體系、系統的負載等諸多場景相關，很難選擇，如果選擇不當，不但性能得不到提高，可能還會下降，是以大家普遍認為自旋鎖不具有擴充性。
對自旋鎖周期的選擇上，hotspot認為最佳時間應是一個線程上下文切換的時間，但目前并沒有做到。經過調查，目前隻是通過彙編暫停了幾個cpu周期，除了自旋周期選擇，hotspot還進行許多其他的自旋優化政策，具體如下：
如果平均負載小于cpus則一直自旋
如果有超過(cpus/2)個線程正在自旋，則後來線程直接阻塞
如果正在自旋的線程發現owner發生了變化則延遲自旋時間（自旋計數）或進入阻塞
如果cpu處于節電模式則停止自旋
自旋時間的最壞情況是cpu的存儲延遲（cpu a存儲了一個資料，到cpu b得知這個資料直接的時間差）
自旋時會适當放棄線程優先級之間的差異
那synchronized實作何時使用了自旋鎖？答案是線上程進入contentionlist時，也即第一步操作前。線程在進入等待隊列時首先進行自旋嘗試獲得鎖，如果不成功再進入等待隊列。這對那些已經在等待隊列中的線程來說，稍微顯得不公平。還有一個不公平的地方是自旋線程可能會搶占了ready線程的鎖。自旋鎖由每個監視對象維護，每個監視對象一個。
在jvm1.6中引入了偏向鎖，偏向鎖主要解決無競争下的鎖性能問題，首先我們看下無競争下鎖存在什麼問題：
現在幾乎所有的鎖都是可重入的，也即已經獲得鎖的線程可以多次鎖住/解鎖監視對象，按照之前的hotspot設計，每次加鎖/解鎖都會涉及到一些cas操作（比如對等待隊列的cas操作），cas操作會延遲本地調用，是以偏向鎖的想法是一旦線程第一次獲得了監視對象，之後讓監視對象“偏向”這個線程，之後的多次調用則可以避免cas操作，說白了就是置個變量，如果發現為true則無需再走各種加鎖/解鎖流程。但還有很多概念需要解釋、很多引入的問題需要解決：
cas為什麼會引入本地延遲？這要從smp（對稱多處理器）架構說起，下圖大概表明了smp的結構：
其意思是所有的cpu會共享一條系統總線（bus），靠此總線連接配接主存。每個核都有自己的一級緩存，各核相對于bus對稱分布，是以這種結構稱為“對稱多處理器”。
而cas的全稱為compare-and-swap，是一條cpu的原子指令，其作用是讓cpu比較後原子地更新某個位置的值，經過調查發現，其實作方式是基于硬體平台的彙編指令，就是說cas是靠硬體實作的，jvm隻是封裝了彙編調用，那些atomicinteger類便是使用了這些封裝後的接口。
core1和core2可能會同時把主存中某個位置的值load到自己的l1 cache中，當core1在自己的l1 cache中修改這個位置的值時，會通過總線，使core2中l1 cache對應的值“失效”，而core2一旦發現自己l1 cache中的值失效（稱為cache命中缺失）則會通過總線從記憶體中加載該位址最新的值，大家通過總線的來回通信稱為“cache一緻性流量”，因為總線被設計為固定的“通信能力”，如果cache一緻性流量過大，總線将成為瓶頸。而當core1和core2中的值再次一緻時，稱為“cache一緻性”，從這個層面來說，鎖設計的終極目标便是減少cache一緻性流量。
而cas恰好會導緻cache一緻性流量，如果有很多線程都共享同一個對象，當某個core cas成功時必然會引起總線風暴，這就是所謂的本地延遲，本質上偏向鎖就是為了消除cas，降低cache一緻性流量。
cache一緻性：
cache一緻性流量的例外情況：
numa(non uniform memory access achitecture）架構：
與smp對應還有非對稱多處理器架構，現在主要應用在一些高端處理器上，主要特點是沒有總線，沒有公用主存，每個core有自己的記憶體，針對這種結構此處不做讨論。
偏向鎖引入的一個重要問題是，在多争用的場景下，如果另外一個線程争用偏向對象，擁有者需要釋放偏向鎖，而釋放的過程會帶來一些性能開銷，但總體說來偏向鎖帶來的好處還是大于cas代價的。
關于鎖，jvm中還引入了一些其他技術比如鎖膨脹等，這些與自旋鎖、偏向鎖相比影響不是很大，這裡就不做介紹。