面試必備之深入理解自旋鎖

來自專欄 Java面試通關手冊6 人贊了文章

分享一個我自己總結的Java學習的系統知識點以及面試問題，目前已經開源，會一直完善下去，歡迎建議和指導歡迎Star： github.com/Snailclimb/J

本文出自：http://blog.onlycatch.com/post/自旋鎖我對原文做了一點補充與修改，我覺得這篇文章寫的非常非常好。深入學習，不光可以深入掌握自旋鎖，可能提高自己的編程思想。原文作者對於自旋鎖的思考很棒，為他點個贊。

在我的上一篇文章：《面試必備之樂觀鎖與悲觀鎖》 已經為大家對比了樂觀鎖與悲觀鎖。我們知道CAS演算法是樂觀鎖的一種實現方式，CAS演算法中又涉及到自旋鎖，所以這裡給大家講一下什麼是自旋鎖。

簡單回顧一下CAS演算法

CAS演算法 即compare and swap（比較與交換），是一種有名的無鎖演算法。無鎖編程，即不使用鎖的情況下實現多線程之間的變數同步，也就是在沒有線程被阻塞的情況下實現變數的同步，所以也叫非阻塞同步（Non-blocking Synchronization）。CAS演算法涉及到三個操作數

  • 需要讀寫的內存值 V
  • 進行比較的值 A
  • 擬寫入的新值 B

當且僅當 V 的值等於 A時，CAS通過原子方式用新值B來更新V的值，否則不會執行任何操作（比較和替換是一個原子操作）。一般情況下是一個自旋操作，即不斷的重試。

什麼是自旋鎖？

自旋鎖（spinlock）：是指當一個線程在獲取鎖的時候，如果鎖已經被其它線程獲取，那麼該線程將循環等待，然後不斷的判斷鎖是否能夠被成功獲取，直到獲取到鎖才會退出循環。

獲取鎖的線程一直處於活躍狀態，但是並沒有執行任何有效的任務，使用這種鎖會造成busy-waiting。

它是為實現保護共享資源而提出一種鎖機制。其實，自旋鎖與互斥鎖比較類似，它們都是為了解決對某項資源的互斥使用。無論是互斥鎖，還是自旋鎖，在任何時刻，最多只能有一個保持者，也就說，在任何時刻最多只能有一個執行單元獲得鎖。但是兩者在調度機制上略有不同。對於互斥鎖，如果資源已經被佔用，資源申請者只能進入睡眠狀態。但是自旋鎖不會引起調用者睡眠，如果自旋鎖已經被別的執行單元保持，調用者就一直循環在那裡看是否該自旋鎖的保持者已經釋放了鎖，"自旋"一詞就是因此而得名。

Java如何實現自旋鎖？

下面是個簡單的例子：

public class SpinLock { private AtomicReference<Thread> cas = new AtomicReference<Thread>(); public void lock() { Thread current = Thread.currentThread(); // 利用CAS while (!cas.compareAndSet(null, current)) { // DO nothing } } public void unlock() { Thread current = Thread.currentThread(); cas.compareAndSet(current, null); }}

lock（)方法利用的CAS，當第一個線程A獲取鎖的時候，能夠成功獲取到，不會進入while循環，如果此時線程A沒有釋放鎖，另一個線程B又來獲取鎖，此時由於不滿足CAS，所以就會進入while循環，不斷判斷是否滿足CAS，直到A線程調用unlock方法釋放了該鎖。

自旋鎖存在的問題

  1. 如果某個線程持有鎖的時間過長，就會導致其它等待獲取鎖的線程進入循環等待，消耗CPU。使用不當會造成CPU使用率極高。
  2. 上面Java實現的自旋鎖不是公平的，即無法滿足等待時間最長的線程優先獲取鎖。不公平的鎖就會存在「線程飢餓」問題。

自旋鎖的優點

  1. 自旋鎖不會使線程狀態發生切換，一直處於用戶態，即線程一直都是active的；不會使線程進入阻塞狀態，減少了不必要的上下文切換，執行速度快
  2. 非自旋鎖在獲取不到鎖的時候會進入阻塞狀態，從而進入內核態，當獲取到鎖的時候需要從內核態恢復，需要線程上下文切換。 （線程被阻塞後便進入內核（Linux）調度狀態，這個會導致系統在用戶態與內核態之間來回切換，嚴重影響鎖的性能）

可重入的自旋鎖和不可重入的自旋鎖

文章開始的時候的那段代碼，仔細分析一下就可以看出，它是不支持重入的，即當一個線程第一次已經獲取到了該鎖，在鎖釋放之前又一次重新獲取該鎖，第二次就不能成功獲取到。由於不滿足CAS，所以第二次獲取會進入while循環等待，而如果是可重入鎖，第二次也是應該能夠成功獲取到的。

而且，即使第二次能夠成功獲取，那麼當第一次釋放鎖的時候，第二次獲取到的鎖也會被釋放，而這是不合理的。

為了實現可重入鎖，我們需要引入一個計數器，用來記錄獲取鎖的線程數。

public class ReentrantSpinLock { private AtomicReference<Thread> cas = new AtomicReference<Thread>(); private int count; public void lock() { Thread current = Thread.currentThread(); if (current == cas.get()) { // 如果當前線程已經獲取到了鎖，線程數增加一，然後返回 count++; return; } // 如果沒獲取到鎖，則通過CAS自旋 while (!cas.compareAndSet(null, current)) { // DO nothing } } public void unlock() { Thread cur = Thread.currentThread(); if (cur == cas.get()) { if (count > 0) {// 如果大於0，表示當前線程多次獲取了該鎖，釋放鎖通過count減一來模擬 count--; } else {// 如果count==0，可以將鎖釋放，這樣就能保證獲取鎖的次數與釋放鎖的次數是一致的了。 cas.compareAndSet(cur, null); } } }}

自旋鎖的其他變種

1. TicketLock

TicketLock主要解決的是公平性的問題。

思路：每當有線程獲取鎖的時候，就給該線程分配一個遞增的id，我們稱之為排隊號，同時，鎖對應一個服務號，每當有線程釋放鎖，服務號就會遞增，此時如果服務號與某個線程排隊號一致，那麼該線程就獲得鎖，由於排隊號是遞增的，所以就保證了最先請求獲取鎖的線程可以最先獲取到鎖，就實現了公平性。

可以想像成銀行辦理業務排隊，排隊的每一個顧客都代表一個需要請求鎖的線程，而銀行服務窗口表示鎖，每當有窗口服務完成就把自己的服務號加一，此時在排隊的所有顧客中，只有自己的排隊號與服務號一致的才可以得到服務。

實現代碼：

public class TicketLock { /** * 服務號 */ private AtomicInteger serviceNum = new AtomicInteger(); /** * 排隊號 */ private AtomicInteger ticketNum = new AtomicInteger(); /** * lock:獲取鎖，如果獲取成功，返回當前線程的排隊號，獲取排隊號用於釋放鎖. <br/> * * @return */ public int lock() { int currentTicketNum = ticketNum.incrementAndGet(); while (currentTicketNum != serviceNum.get()) { // Do nothing } return currentTicketNum; } /** * unlock:釋放鎖，傳入當前持有鎖的線程的排隊號 <br/> * * @param ticketnum */ public void unlock(int ticketnum) { serviceNum.compareAndSet(ticketnum, ticketnum + 1); }}

上面的實現方式是，線程獲取鎖之後，將它的排隊號返回，等該線程釋放鎖的時候，需要將該排隊號傳入。但這樣是有風險的，因為這個排隊號是可以被修改的，一旦排隊號被不小心修改了，那麼鎖將不能被正確釋放。一種更好的實現方式如下：

public class TicketLockV2 { /** * 服務號 */ private AtomicInteger serviceNum = new AtomicInteger(); /** * 排隊號 */ private AtomicInteger ticketNum = new AtomicInteger(); /** * 新增一個ThreadLocal，用於存儲每個線程的排隊號 */ private ThreadLocal<Integer> ticketNumHolder = new ThreadLocal<Integer>(); public void lock() { int currentTicketNum = ticketNum.incrementAndGet(); // 獲取鎖的時候，將當前線程的排隊號保存起來 ticketNumHolder.set(currentTicketNum); while (currentTicketNum != serviceNum.get()) { // Do nothing } } public void unlock() { // 釋放鎖，從ThreadLocal中獲取當前線程的排隊號 Integer currentTickNum = ticketNumHolder.get(); serviceNum.compareAndSet(currentTickNum, currentTickNum + 1); }}

上面的實現方式是將每個線程的排隊號放到了ThreadLocal中。

TicketLock存在的問題:

多處理器系統上，每個進程/線程佔用的處理器都在讀寫同一個變數serviceNum ，每次讀寫操作都必須在多個處理器緩存之間進行緩存同步，這會導致繁重的系統匯流排和內存的流量，大大降低系統整體的性能。

下面介紹的MCSLock和CLHLock就是解決這個問題的。

2. CLHLock

CLH鎖是一種基於鏈表的可擴展、高性能、公平的自旋鎖，申請線程只在本地變數上自旋，它不斷輪詢前驅的狀態，如果發現前驅釋放了鎖就結束自旋，獲得鎖。

實現代碼如下：

import java.util.concurrent.atomic.AtomicReferenceFieldUpdater;/** * CLH的發明人是：Craig，Landin and Hagersten。 * 代碼來源：http://ifeve.com/java_lock_see2/ */public class CLHLock { /** * 定義一個節點，默認的lock狀態為true */ public static class CLHNode { private volatile boolean isLocked = true; } /** * 尾部節點,只用一個節點即可 */ private volatile CLHNode tail; private static final ThreadLocal<CLHNode> LOCAL = new ThreadLocal<CLHNode>(); private static final AtomicReferenceFieldUpdater<CLHLock, CLHNode> UPDATER = AtomicReferenceFieldUpdater.newUpdater(CLHLock.class, CLHNode.class, "tail"); public void lock() { // 新建節點並將節點與當前線程保存起來 CLHNode node = new CLHNode(); LOCAL.set(node); // 將新建的節點設置為尾部節點，並返回舊的節點（原子操作），這裡舊的節點實際上就是當前節點的前驅節點 CLHNode preNode = UPDATER.getAndSet(this, node); if (preNode != null) { // 前驅節點不為null表示當鎖被其他線程佔用，通過不斷輪詢判斷前驅節點的鎖標誌位等待前驅節點釋放鎖 while (preNode.isLocked) { } preNode = null; LOCAL.set(node); } // 如果不存在前驅節點，表示該鎖沒有被其他線程佔用，則當前線程獲得鎖 } public void unlock() { // 獲取當前線程對應的節點 CLHNode node = LOCAL.get(); // 如果tail節點等於node，則將tail節點更新為null，同時將node的lock狀態職位false，表示當前線程釋放了鎖 if (!UPDATER.compareAndSet(this, node, null)) { node.isLocked = false; } node = null; }}

3. MCSLock

MCSLock則是對本地變數的節點進行循環。

/** * MCS:發明人名字John Mellor-Crummey和Michael Scott * 代碼來源：http://ifeve.com/java_lock_see2/ */public class MCSLock { /** * 節點，記錄當前節點的鎖狀態以及後驅節點 */ public static class MCSNode { volatile MCSNode next; volatile boolean isLocked = true; } private static final ThreadLocal<MCSNode> NODE = new ThreadLocal<MCSNode>(); // 隊列 @SuppressWarnings("unused") private volatile MCSNode queue; // queue更新器 private static final AtomicReferenceFieldUpdater<MCSLock, MCSNode> UPDATER = AtomicReferenceFieldUpdater.newUpdater(MCSLock.class, MCSNode.class, "queue"); public void lock() { // 創建節點並保存到ThreadLocal中 MCSNode currentNode = new MCSNode(); NODE.set(currentNode); // 將queue設置為當前節點，並且返回之前的節點 MCSNode preNode = UPDATER.getAndSet(this, currentNode); if (preNode != null) { // 如果之前節點不為null，表示鎖已經被其他線程持有 preNode.next = currentNode; // 循環判斷，直到當前節點的鎖標誌位為false while (currentNode.isLocked) { } } } public void unlock() { MCSNode currentNode = NODE.get(); // next為null表示沒有正在等待獲取鎖的線程 if (currentNode.next == null) { // 更新狀態並設置queue為null if (UPDATER.compareAndSet(this, currentNode, null)) { // 如果成功了，表示queue==currentNode,即當前節點後面沒有節點了 return; } else { // 如果不成功，表示queue!=currentNode,即當前節點後面多了一個節點，表示有線程在等待 // 如果當前節點的後續節點為null，則需要等待其不為null（參考加鎖方法） while (currentNode.next == null) { } } } else { // 如果不為null，表示有線程在等待獲取鎖，此時將等待線程對應的節點鎖狀態更新為false，同時將當前線程的後繼節點設為null currentNode.next.isLocked = false; currentNode.next = null; } }}

4. CLHLock 和 MCSLock

  • 都是基於鏈表，不同的是CLHLock是基於隱式鏈表，沒有真正的後續節點屬性，MCSLock是顯示鏈表，有一個指向後續節點的屬性。
  • 將獲取鎖的線程狀態藉助節點(node)保存,每個線程都有一份獨立的節點，這樣就解決了TicketLock多處理器緩存同步的問題。

自旋鎖與互斥鎖

  • 自旋鎖與互斥鎖都是為了實現保護資源共享的機制。
  • 無論是自旋鎖還是互斥鎖，在任意時刻，都最多只能有一個保持者。
  • 獲取互斥鎖的線程，如果鎖已經被佔用，則該線程將進入睡眠狀態；獲取自旋鎖的線程則不會睡眠，而是一直循環等待鎖釋放。

總結：

  • 自旋鎖：線程獲取鎖的時候，如果鎖被其他線程持有，則當前線程將循環等待，直到獲取到鎖。
  • 自旋鎖等待期間，線程的狀態不會改變，線程一直是用戶態並且是活動的(active)。
  • 自旋鎖如果持有鎖的時間太長，則會導致其它等待獲取鎖的線程耗盡CPU。
  • 自旋鎖本身無法保證公平性，同時也無法保證可重入性。
  • 基於自旋鎖，可以實現具備公平性和可重入性質的鎖。
  • TicketLock:採用類似銀行排號叫好的方式實現自旋鎖的公平性，但是由於不停的讀取serviceNum，每次讀寫操作都必須在多個處理器緩存之間進行緩存同步，這會導致繁重的系統匯流排和內存的流量，大大降低系統整體的性能。
  • CLHLock和MCSLock通過鏈表的方式避免了減少了處理器緩存同步，極大的提高了性能，區別在於CLHLock是通過輪詢其前驅節點的狀態，而MCS則是查看當前節點的鎖狀態。
  • CLHLock在NUMA架構下使用會存在問題。在沒有cache的NUMA系統架構中，由於CLHLock是在當前節點的前一個節點上自旋,NUMA架構中處理器訪問本地內存的速度高於通過網路訪問其他節點的內存，所以CLHLock在NUMA架構上不是最優的自旋鎖。

參考資料

  1. searchtb.com/2011/06/sp
  2. en.wikipedia.org/wiki/S
  3. en.wikipedia.org/wiki/B
  4. blog.csdn.net/chen77716
  5. ifeve.com/java_lock_see
  6. ifeve.com/java_lock_see
  7. coderbee.net/index.php/

如果想要獲取更多我的原創文章，歡迎關注我的微信公眾號:"Java面試通關手冊" 。無套路，希望能與您共同進步，互相學習。

推薦閱讀：

相关文章