鎖的開銷是巨大的，特别是對于多核多處理來講。
引入多處理，本身就是為了将并行化處理以提高性能，然而由于存在共享臨界區，而這個臨界區同時隻能有一個線程通路(特别是對于寫操作)，那麼本來并行的執 行流在這裡被串行化了，形象地看，這裡好像是寬闊馬路上的一個瓶頸，由于串行化是本質上存在的，是以該瓶頸就是不可消除的。問題是線程執行流如何度過這個 瓶頸，很顯然，它們誰都繞不開，現在問題是是它們到達這個瓶頸時該怎麼辦。
很顯然，鬥毆搶先是一種不合理但實用的簡單方案，樸素的自旋鎖就是這麼設計的。然而，更加紳士的做法就是，既然暫時得不到通行權，那麼自己先讓出道 路，sleep一會兒，這種方式就是sleep-wait方式，與之對應的就是持續spin-wait方式。問題是線程本身如何對這二者做出明智的選擇。 事實上，這種選擇權交給了程式，而不是執行中的線程。
不要試圖比較sleep-wait和spin-wait的性能，它們都是損耗了性能-因為串行化。其中，sleep-wait的開銷在切換(涉及到程序， 線程的切換比較，比如寄存器上下文，堆棧，某些處理器上cache重新整理，MMU tlb重新整理等)，而spin-wait的開銷很顯然，就是持續浪費CPU周期，雖然沒有切換的開銷，但事實上，它這段時間什麼也做不了。
為什麼要引入spin-wait這種方式呢？因為如果始終是sleep-wait，那麼sleep線程A切換到别的線程B後，鎖被釋放了，系統不一定能保 證sleep的那個線程可以獲得CPU進而切回來，即便如此，付出巨大的切換代價，有時間隔很短，線程B并沒有由于線程A的紳士行為獲得收益，這種姿态顯 然是不值得的，還不如保留本質，持續鬥毆。
和中斷相比，鎖的開銷更加巨大，如果可以通過關中斷的方式換取無鎖操作，那麼這是值得的，但是(最讨厭且永恒的“但是”)，你要考慮關中斷的副作用，比如增加了處理延遲，然後你必須拿這種新的代價和鎖的開銷進行對比，權衡這種交易是否值得。
要開始本文了，為了簡便起見，我不會給出太多的和處理器相關的細節，而是集中針對自旋鎖本身。這些細節比如CPU cache機制，緩存一緻性協定，記憶體屏障，Intel的pause指令，流水線，總線鎖等，還好，這些概念都是可以很友善baidu出來的，不用去牆 外。
Linux核心一開始就引入了自旋鎖，所謂的自旋鎖在等待鎖過程中的行為就是原地打轉，有人會覺得這浪費了CPU周期，但是你要明白，系統設計就是一場博弈，雖然不是零和，但是也要盡力尋找折中點，然而卻沒有兩全其美的方案。
如果不原地打轉，又該如何呢？很顯然就是切換到别的線程，等待持鎖者釋放鎖的時候，再将它喚醒，然而這裡又有兩次鬥毆，首先，如果有多方都競争一個鎖，那 麼全部将它們喚醒，提供一個鬥毆場地，等待一個勝出嗎？退而求其次，即便僅僅喚醒首先排隊的那個線程，task切換的開銷算進去了嗎？是以說，如果原地打 轉浪費的CPU周期小于兩次切換開銷浪費的CPU周期，那麼原地打轉就是合理的，這麼說來，原地打轉的時間越短越好。
就是如此。自旋鎖的應用場合就是短時間持有臨界區的場合，它是一種短期鎖，如果占據臨界區過久，随着原地打轉浪費的CPU周期的增加，其開銷将逐漸大于兩 次切換(切換開銷是固定的-不考慮cache等)，是以，理論上，能算出自旋鎖在持鎖期間可以執行多少代碼。爆炸！
Linux 自旋鎖發展了兩代，第一代自旋鎖是一種完全鬥毆模式的無序自旋鎖，也就是說，如果多個CPU同時争搶一個自旋鎖，那麼待持鎖者解鎖的時候，理論上它們獲得 鎖的機會是不固定的，和cache等一系列因素相關，這就造成了不公平，第一個開始争搶的CPU不一定第一個獲得...這就需要引入一個秩序，于是第二代 Ticket自旋鎖就設計出來了。
Ticket自旋鎖的設計非常巧妙，它将一個CPU變量，比如32位的值分為高16位和低16位，每次lock的時候，CPU将高16位原子加上 0x01(通過鎖總線)，然後将該值和低16位比較，如果相等則成功，如果不等則自旋的同時持續比較這兩個值，而unlock操作則是簡單遞增鎖的低16 位加0x01(理論上不需要鎖總線，因為不會有兩個及以上的CPU同時擁有鎖進行unlock操作，但是還是要考慮CPU的特性...)。這就是所謂的 Ticket自旋鎖的全部。
最近遇到了鎖優化的問題，衆所周知，鎖優化是一個很精細的活兒，它既不能太複雜也不能太簡單，特别是自旋鎖的設計，更是如此。然而自旋鎖設計的優勢也很明顯，那就是它讓你少考慮很多問題：
1.一個CPU同時隻能在一個自旋鎖上自旋；
2.一旦開始自旋，直到獲得鎖，中間不能放棄退出自旋。
自 旋鎖的應用場合必須要明了，它不适合保護很大的臨界區，因為這将導緻自旋過久，它也不适合大量CPU的情況，因為它會導緻自旋延時的N倍，雖然一段臨界區 很小，但是一個CPU自旋的時間可能是N倍，N為CPU的數量。這就引出了一個争論，Ticket排隊自旋鎖真的比鬥毆型哄搶自旋鎖好嗎？如果不考慮 cache親和，鬥毆型的自旋鎖可以将每個CPU自旋的時間收斂到平均時間，而Ticket自旋鎖将出現兩極分化，也就是說，最長自旋時間和最短自旋時間 是一個固定的倍數關系，随着CPU數量的增加，排隊公平導緻的不合理性将加大，你要知道，任何情況下隊列都不可能超過一個臨界值，超過了不滿情緒将會增 加，雖然這種長延時隻是因為你來得晚導緻的，看似很公平，實際上并不公平，因為并不清楚你來得晚的原因。
目前沒有一種好的方案解決這個問題，一般情況，如果隊列過長，從業人員會建議你一會兒再來看看，或者貼上大緻的預估時間，你自己來絕對是排隊還是放棄。
我 建議在自旋鎖加鎖前，先try lock一次，正如現如今的實作一樣，然而這個try并沒有給出除了成功或者失敗之外的資訊，事實上更好的方式是，try，并且try傳回一些有用的信 息，比如等待預估時間，隊長等統計資訊，以供調用者決定是就地自旋還是幹點别的。誰說核心中不能做大資料分析，很多統計資訊和建議都可以通過資料分析得 到。
此外，對于該統計資訊，可以對spin操作本身進行優化，就是說，内部的pause指令可以進行優化，這對流水線是有益的。
為 什麼我要設計一個新的自旋鎖，一方面是我覺得Ticket自旋鎖多個CPU雖然靠遞增高位實作了排隊，但是它們同時不斷地檢測自旋鎖本身的值，cache 有點浪費，所有的CPU cache上均會出現完全一樣的自旋鎖，并且一旦鎖被unlock，還會觸發cache一緻性協定行為，另一方面，我覺得用一個32位(或者随便其它什麼 CPU内部類型)分為高低兩部分來實作自旋鎖雖然巧妙但是又過于簡單，第三方面，我前些日子特别推崇小巧結構體實作的IP轉發表，如今又重溫更加小巧的 Ticket自旋鎖，心裡總是有些嫉妒，是以怎麼也得按照我的思路來一個”符合我的觀念的“設計吧，事情就是這麼開始的。
如何解決線程間同步問題，這個問題确實不好解決，但是自己管自己，也就是操作本地資料，總是一個合理的思路。
為什麼要在自旋鎖本身上集體自旋呢？如果有500多個CPU，大家一起探測同一個記憶體位址，然後持鎖者釋放鎖，修改了該記憶體位址的CPU cache值，這将導緻大量的cache一緻性動作...為何不在自己的本地變量上自旋呢？如果持鎖者釋放鎖，那麼就将下一個等待者的本地變量置0，這意 味着CPU隻需要拿本地變量和0比較即可。
是以就需要有一個本地的地方儲存這個變量，我為每一個CPU申請了一個per CPU變量，内部儲存一個棧，用于實作嚴格的”後加鎖先解鎖“順序的自旋鎖，當然這樣對調用者有要求，或者說把棧改成一個空閑隊列，用于實作任意順序加鎖 /解鎖得自旋鎖，這個對調用者沒有要求，但是可能會引起死鎖。
為了實作多個CPU同時争搶自旋鎖的優雅排隊，勢必要維護一個隊列，單向推進的即可，沒有必要用list_head結構體。排入隊中的元素就是棧幀，而棧幀是per CPU的。操作棧幀隻有三個機會：
自己加鎖時：加鎖時需要用自己的棧幀排隊，不可避免要操作連結清單，而可能同時有多個CPU的棧幀要排隊，是以需要保證整個排隊動作的單向連結清單操作是原子的，鎖總線是一個辦法。
自己自旋時：這個時段不涉及别的CPU，甚至自己的棧幀都不會到達别的CPU的cache中，棧幀是CPU本地變量。
排在前面的棧幀解鎖時：這 個時候理論上也和其它CPU無關，因為隊列是嚴格順序的，取下一個即可，無需争搶，但是有一種競争情況，即開始取下一個棧幀時，隊列已經沒有下一個，然而 按照空隊列處理時，卻有了下一個棧幀，這将使得剛剛排入的新棧幀永遠無法獲得鎖，是以這個動作必須是原子的。至于說取到下一個排隊棧幀，設定它時，就不用 保證原子了，因為它就是它後面的它，一個棧幀不會排到兩個隊列，且排入了就不能放棄，别人也不會動它的。
下面用一個圖示展示一下我的這個排隊自旋鎖的設計吧
<a href="http://s3.51cto.com/wyfs02/M00/6F/C6/wKiom1WoNiOQuhbzAAUslMkjCNA607.jpg" target="_blank"></a>
看起來有點複雜了，那麼性能一定不高，其實确實比Ticket自旋鎖複雜，但是你能找到比Ticket自旋鎖更簡單優雅的設計嗎？
我不圖更簡單，但圖夠優雅。雖然我的一個原子操作序列比Ticket自旋鎖的單純加1操作複雜了很多，涉及到很多連結清單操作，但是我的局部性利用會更好，特 别是采用了per CPU機制，在集體自旋的時間段，CPU cache資料同步效率會更高，你要知道，自旋的時間和鎖總線的時間相比，那可久多了。采用數組實作的堆棧(即便是空閑連結清單也一樣)，資料的局部性利用效 果會更好，也就說，一個CPU的所有自旋鎖的自旋體均在這個數組中，這個數組有多大，取決于系統同時持有的自旋鎖有多少。
以下是根據上述的圖示寫出的測試代碼，代碼未經優化，隻是能跑。在使用者空間做過測試。
請看上面的那個圖，多個CPU的per CPU自旋堆棧是位址獨立的，這就意味着我們要麼在棧幀中儲存一個指針，要麼就是采用base位址加偏移的方式，這樣可以省掉幾個位元組，采用對齊方案的 話，一個棧幀的後幾個bit對于位址和偏移而言是不用的，是以就可以做status位，這些都是基本的空間優化。
我要做的就是把所有的CPU的自旋堆棧全部整合在一張表中，分為二維，一維代表CPU，一維代表棧幀，這樣就可以在棧幀中寫索引而不是位址了，這樣就能節 省大量的記憶體了，除卻空間節省之外，連續記憶體的時間局部性也更好利用。因為系統中所有的自旋鎖的自旋體，全部都在這一張表中了，整個系統的自旋鎖操作完全 不離此表，它就像MMU一樣，全然成了一個服務性基礎設施。上述例子位址索引化後如下圖所示：
<a href="http://s3.51cto.com/wyfs02/M02/6F/C4/wKioL1WoN--ibywMAAHIZkrjK9g949.jpg" target="_blank"></a>
采用堆棧的方式儲存自旋體，就要嚴格按照push的反順序pop，這就要求加鎖和解鎖操作要和push/pop操作完全一緻。而這種限制雖然不錯，但并不必須，如果不要求解鎖順序，那就需要将堆棧做成空閑連結清單，它的操作如下圖所示：
<a href="http://s3.51cto.com/wyfs02/M00/6F/C4/wKioL1WoN-DhL_iPAAH-QkEknbs373.jpg" target="_blank"></a>
這 種空閑連結清單組織方式和UNIX檔案的空閑塊組織方式類似，另一個例子就是Linux核心的Slab配置設定器中的hot cache的組織方式。采用這種組織方式。這種方式的好處在于，最先釋放的最先被配置設定，這樣會cache會好一點。其實這是一種不受空間限制的堆棧，是以 我不把它作為一種特殊的方式，也稱它為堆棧。
采用單連結清單而不是雙連結清單的一個原始是确實用不到雙向連結清單，另一個更加隐蔽的原因在于，單連結清單修改時隻需要修改一個指針，而一個修改操作可以是原子的，鎖總線鎖cache的開銷更小
好像沒寫完的樣子.....
本文轉自 dog250 51CTO部落格，原文連結:http://blog.51cto.com/dog250/1675506
![linux-svn解除安裝與安裝[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)