看完你就明白的鎖系列之自旋鎖

在上一篇文章 看完你就應(yīng)該能明白的悲觀鎖和樂觀鎖中我們已經(jīng)學(xué)習(xí)到了什么是悲觀鎖和樂觀鎖、悲觀鎖和樂觀鎖的實(shí)現(xiàn)、優(yōu)缺點(diǎn)分別是什么。其中樂觀鎖的實(shí)現(xiàn)之一 CAS 算法中提到了一個(gè)自旋鎖的概念，為了全面理解 CAS 算法就首先需要了解一下自旋鎖 是什么，自旋鎖的適用場景和優(yōu)缺點(diǎn)分別是什么，別著急，下面為你一一列舉。

自旋鎖的提出背景

由于在多處理器環(huán)境中某些資源的有限性，有時(shí)需要互斥訪問(mutual exclusion)，這時(shí)候就需要引入鎖的概念，只有獲取了鎖的線程才能夠?qū)Y源進(jìn)行訪問，由于多線程的核心是CPU的時(shí)間分片，所以同一時(shí)刻只能有一個(gè)線程獲取到鎖。那么就面臨一個(gè)問題，那么沒有獲取到鎖的線程應(yīng)該怎么辦？

通常有兩種處理方式：一種是沒有獲取到鎖的線程就一直循環(huán)等待判斷該資源是否已經(jīng)釋放鎖，這種鎖叫做自旋鎖，它不用將線程阻塞起來(NON-BLOCKING)；還有一種處理方式就是把自己阻塞起來，等待重新調(diào)度請求，這種叫做互斥鎖。

什么是自旋鎖

自旋鎖的定義：當(dāng)一個(gè)線程嘗試去獲取某一把鎖的時(shí)候，如果這個(gè)鎖此時(shí)已經(jīng)被別人獲取(占用)，那么此線程就無法獲取到這把鎖，該線程將會等待，間隔一段時(shí)間后會再次嘗試獲取。這種采用循環(huán)加鎖 -> 等待的機(jī)制被稱為自旋鎖(spinlock)。

自旋鎖的原理

自旋鎖的原理比較簡單，如果持有鎖的線程能在短時(shí)間內(nèi)釋放鎖資源，那么那些等待競爭鎖的線程就不需要做內(nèi)核態(tài)和用戶態(tài)之間的切換進(jìn)入阻塞狀態(tài)，它們只需要等一等(自旋)，等到持有鎖的線程釋放鎖之后即可獲取，這樣就避免了用戶進(jìn)程和內(nèi)核切換的消耗。

因?yàn)樽孕i避免了操作系統(tǒng)進(jìn)程調(diào)度和線程切換，所以自旋鎖通常適用在時(shí)間比較短的情況下。由于這個(gè)原因，操作系統(tǒng)的內(nèi)核經(jīng)常使用自旋鎖。但是，如果長時(shí)間上鎖的話，自旋鎖會非常耗費(fèi)性能，它阻止了其他線程的運(yùn)行和調(diào)度。線程持有鎖的時(shí)間越長，則持有該鎖的線程將被 OS(Operating System) 調(diào)度程序中斷的風(fēng)險(xiǎn)越大。如果發(fā)生中斷情況，那么其他線程將保持旋轉(zhuǎn)狀態(tài)(反復(fù)嘗試獲取鎖)，而持有該鎖的線程并不打算釋放鎖，這樣導(dǎo)致的是結(jié)果是無限期推遲，直到持有鎖的線程可以完成并釋放它為止。

解決上面這種情況一個(gè)很好的方式是給自旋鎖設(shè)定一個(gè)自旋時(shí)間，等時(shí)間一到立即釋放自旋鎖。自旋鎖的目的是占著CPU資源不進(jìn)行釋放，等到獲取鎖立即進(jìn)行處理。但是如何去選擇自旋時(shí)間呢？如果自旋執(zhí)行時(shí)間太長，會有大量的線程處于自旋狀態(tài)占用 CPU 資源，進(jìn)而會影響整體系統(tǒng)的性能。因此自旋的周期選的額外重要！JDK在1.6 引入了適應(yīng)性自旋鎖，適應(yīng)性自旋鎖意味著自旋時(shí)間不是固定的了，而是由前一次在同一個(gè)鎖上的自旋時(shí)間以及鎖擁有的狀態(tài)來決定，基本認(rèn)為一個(gè)線程上下文切換的時(shí)間是最佳的一個(gè)時(shí)間。

自旋鎖的優(yōu)缺點(diǎn)

自旋鎖盡可能的減少線程的阻塞，這對于鎖的競爭不激烈，且占用鎖時(shí)間非常短的代碼塊來說性能能大幅度的提升，因?yàn)樽孕南臅∮诰€程阻塞掛起再喚醒的操作的消耗，這些操作會導(dǎo)致線程發(fā)生兩次上下文切換！

但是如果鎖的競爭激烈，或者持有鎖的線程需要長時(shí)間占用鎖執(zhí)行同步塊，這時(shí)候就不適合使用自旋鎖了，因?yàn)樽孕i在獲取鎖前一直都是占用 cpu 做無用功，占著 XX 不 XX，同時(shí)有大量線程在競爭一個(gè)鎖，會導(dǎo)致獲取鎖的時(shí)間很長，線程自旋的消耗大于線程阻塞掛起操作的消耗，其它需要 cpu 的線程又不能獲取到 cpu，造成 cpu 的浪費(fèi)。所以這種情況下我們要關(guān)閉自旋鎖。

自旋鎖的實(shí)現(xiàn)

下面我們用Java 代碼來實(shí)現(xiàn)一個(gè)簡單的自旋鎖

public class SpinLockTest {

    private AtomicBoolean available = new AtomicBoolean(false);

    public void lock(){

        // 循環(huán)檢測嘗試獲取鎖
        while (!tryLock()){
            // doSomething...
        }

    }

    public boolean tryLock(){
        // 嘗試獲取鎖，成功返回true，失敗返回false
        return available.compareAndSet(false,true);
    }

    public void unLock(){
        if(!available.compareAndSet(true,false)){
            throw new RuntimeException("釋放鎖失敗");
        }
    }

}

這種簡單的自旋鎖有一個(gè)問題：無法保證多線程競爭的公平性。對于上面的SpinlockTest，當(dāng)多個(gè)線程想要獲取鎖時(shí)，誰最先將available設(shè)為false誰就能最先獲得鎖，這可能會造成某些線程一直都未獲取到鎖造成線程饑餓。

就像我們下課后蜂擁的跑向食堂，下班后蜂擁地?cái)D向地鐵，通常我們會采取排隊(duì)的方式解決這樣的問題，類似地，我們把這種鎖叫排隊(duì)自旋鎖(QueuedSpinlock)。計(jì)算機(jī)科學(xué)家們使用了各種方式來實(shí)現(xiàn)排隊(duì)自旋鎖，如TicketLock，MCSLock，CLHLock。接下來我們分別對這幾種鎖做個(gè)大致的介紹。

TicketLock

在計(jì)算機(jī)科學(xué)領(lǐng)域中，TicketLock 是一種同步機(jī)制或鎖定算法，它是一種自旋鎖，它使用ticket來控制線程執(zhí)行順序。

就像票據(jù)隊(duì)列管理系統(tǒng)一樣。面包店或者服務(wù)機(jī)構(gòu)(例如銀行)都會使用這種方式來為每個(gè)先到達(dá)的顧客記錄其到達(dá)的順序，而不用每次都進(jìn)行排隊(duì)。通常，這種地點(diǎn)都會有一個(gè)分配器(叫號器，掛號器等等都行)，先到的人需要在這個(gè)機(jī)器上取出自己現(xiàn)在排隊(duì)的號碼，這個(gè)號碼是按照自增的順序進(jìn)行的，旁邊還會有一個(gè)標(biāo)牌顯示的是正在服務(wù)的標(biāo)志，這通常是代表目前正在服務(wù)的隊(duì)列號，當(dāng)前的號碼完成服務(wù)后，標(biāo)志牌會顯示下一個(gè)號碼可以去服務(wù)了。

像上面系統(tǒng)一樣，TicketLock 是基于先進(jìn)先出(FIFO) 隊(duì)列的機(jī)制。它增加了鎖的公平性，其設(shè)計(jì)原則如下：TicketLock 中有兩個(gè) int 類型的數(shù)值，開始都是0，第一個(gè)值是隊(duì)列ticket(隊(duì)列票據(jù))， 第二個(gè)值是 出隊(duì)(票據(jù))。隊(duì)列票據(jù)是線程在隊(duì)列中的位置，而出隊(duì)票據(jù)是現(xiàn)在持有鎖的票證的隊(duì)列位置?？赡苡悬c(diǎn)模糊不清，簡單來說，就是隊(duì)列票據(jù)是你取票號的位置，出隊(duì)票據(jù)是你距離叫號的位置?，F(xiàn)在應(yīng)該明白一些了吧。

當(dāng)叫號叫到你的時(shí)候，不能有相同的號碼同時(shí)辦業(yè)務(wù)，必須只有一個(gè)人可以去辦，辦完后，叫號機(jī)叫到下一個(gè)人，這就叫做原子性。你在辦業(yè)務(wù)的時(shí)候不能被其他人所干擾，而且不可能會有兩個(gè)持有相同號碼的人去同時(shí)辦業(yè)務(wù)。然后，下一個(gè)人看自己的號是否和叫到的號碼保持一致，如果一致的話，那么就輪到你去辦業(yè)務(wù)，否則只能繼續(xù)等待。上面這個(gè)流程的關(guān)鍵點(diǎn)在于，每個(gè)辦業(yè)務(wù)的人在辦完業(yè)務(wù)之后，他必須丟棄自己的號碼，叫號機(jī)才能繼續(xù)叫到下面的人，如果這個(gè)人沒有丟棄這個(gè)號碼，那么其他人只能繼續(xù)等待。下面來實(shí)現(xiàn)一下這個(gè)票據(jù)排隊(duì)方案

public class TicketLock {

    // 隊(duì)列票據(jù)(當(dāng)前排隊(duì)號碼)
    private AtomicInteger queueNum = new AtomicInteger();

    // 出隊(duì)票據(jù)(當(dāng)前需等待號碼)
    private AtomicInteger dueueNum = new AtomicInteger();

    // 獲取鎖：如果獲取成功，返回當(dāng)前線程的排隊(duì)號
    public int lock(){
        int currentTicketNum = dueueNum.incrementAndGet();
        while (currentTicketNum != queueNum.get()){
            // doSomething...
        }
        return currentTicketNum;
    }

    // 釋放鎖：傳入當(dāng)前排隊(duì)的號碼
    public void unLock(int ticketNum){
        queueNum.compareAndSet(ticketNum,ticketNum + 1);
    }

}

每次叫號機(jī)在叫號的時(shí)候，都會判斷自己是不是被叫的號，并且每個(gè)人在辦完業(yè)務(wù)的時(shí)候，叫號機(jī)根據(jù)在當(dāng)前號碼的基礎(chǔ)上 + 1，讓隊(duì)列繼續(xù)往前走。

但是上面這個(gè)設(shè)計(jì)是有問題的，因?yàn)楂@得自己的號碼之后，是可以對號碼進(jìn)行更改的，這就造成系統(tǒng)紊亂，鎖不能及時(shí)釋放。這時(shí)候就需要有一個(gè)能確保每個(gè)人按會著自己號碼排隊(duì)辦業(yè)務(wù)的角色，在得知這一點(diǎn)之后，我們重新設(shè)計(jì)一下這個(gè)邏輯

public class TicketLock2 {

    // 隊(duì)列票據(jù)(當(dāng)前排隊(duì)號碼)
    private AtomicInteger queueNum = new AtomicInteger();

    // 出隊(duì)票據(jù)(當(dāng)前需等待號碼)
    private AtomicInteger dueueNum = new AtomicInteger();

    private ThreadLocal<Integer> ticketLocal = new ThreadLocal<>();

    public void lock(){
        int currentTicketNum = dueueNum.incrementAndGet();

        // 獲取鎖的時(shí)候，將當(dāng)前線程的排隊(duì)號保存起來
        ticketLocal.set(currentTicketNum);
        while (currentTicketNum != queueNum.get()){
            // doSomething...
        }
    }

    // 釋放鎖：從排隊(duì)緩沖池中取
    public void unLock(){
        Integer currentTicket = ticketLocal.get();
        queueNum.compareAndSet(currentTicket,currentTicket + 1);
    }

}

這次就不再需要返回值，辦業(yè)務(wù)的時(shí)候，要將當(dāng)前的這一個(gè)號碼緩存起來，在辦完業(yè)務(wù)后，需要釋放緩存的這條票據(jù)。

缺點(diǎn)

TicketLock 雖然解決了公平性的問題，但是多處理器系統(tǒng)上，每個(gè)進(jìn)程/線程占用的處理器都在讀寫同一個(gè)變量queueNum ，每次讀寫操作都必須在多個(gè)處理器緩存之間進(jìn)行緩存同步，這會導(dǎo)致繁重的系統(tǒng)總線和內(nèi)存的流量，大大降低系統(tǒng)整體的性能。

為了解決這個(gè)問題，MCSLock 和 CLHLock 應(yīng)運(yùn)而生。

CLHLock

上面說到TicketLock 是基于隊(duì)列的，那么 CLHLock 就是基于鏈表設(shè)計(jì)的，CLH的發(fā)明人是：Craig，Landin and Hagersten，用它們各自的字母開頭命名。CLH 是一種基于鏈表的可擴(kuò)展，高性能，公平的自旋鎖，申請線程只能在本地變量上自旋，它會不斷輪詢前驅(qū)的狀態(tài)，如果發(fā)現(xiàn)前驅(qū)釋放了鎖就結(jié)束自旋。

public class CLHLock {

    public static class CLHNode{
        private volatile boolean isLocked = true;
    }

    // 尾部節(jié)點(diǎn)
    private volatile CLHNode tail;
    private static final ThreadLocal<CLHNode> LOCAL = new ThreadLocal<>();
    private static final AtomicReferenceFieldUpdater<CLHLock,CLHNode> UPDATER =
            AtomicReferenceFieldUpdater.newUpdater(CLHLock.class,CLHNode.class,"tail");


    public void lock(){
        // 新建節(jié)點(diǎn)并將節(jié)點(diǎn)與當(dāng)前線程保存起來
        CLHNode node = new CLHNode();
        LOCAL.set(node);

        // 將新建的節(jié)點(diǎn)設(shè)置為尾部節(jié)點(diǎn)，并返回舊的節(jié)點(diǎn)（原子操作），這里舊的節(jié)點(diǎn)實(shí)際上就是當(dāng)前節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)
        CLHNode preNode = UPDATER.getAndSet(this,node);
        if(preNode != null){
            // 前驅(qū)節(jié)點(diǎn)不為null表示當(dāng)鎖被其他線程占用，通過不斷輪詢判斷前驅(qū)節(jié)點(diǎn)的鎖標(biāo)志位等待前驅(qū)節(jié)點(diǎn)釋放鎖
            while (preNode.isLocked){

            }
            preNode = null;
            LOCAL.set(node);
        }
        // 如果不存在前驅(qū)節(jié)點(diǎn)，表示該鎖沒有被其他線程占用，則當(dāng)前線程獲得鎖
    }

    public void unlock() {
        // 獲取當(dāng)前線程對應(yīng)的節(jié)點(diǎn)
        CLHNode node = LOCAL.get();
        // 如果tail節(jié)點(diǎn)等于node，則將tail節(jié)點(diǎn)更新為null，同時(shí)將node的lock狀態(tài)職位false，表示當(dāng)前線程釋放了鎖
        if (!UPDATER.compareAndSet(this, node, null)) {
            node.isLocked = false;
        }
        node = null;
    }
}

MCSLock

MCS Spinlock 是一種基于鏈表的可擴(kuò)展、高性能、公平的自旋鎖，申請線程只在本地變量上自旋，直接前驅(qū)負(fù)責(zé)通知其結(jié)束自旋，從而極大地減少了不必要的處理器緩存同步的次數(shù)，降低了總線和內(nèi)存的開銷。MCS 來自于其發(fā)明人名字的首字母： John Mellor-Crummey和Michael Scott。

public class MCSLock {

    public static class MCSNode {
        volatile MCSNode next;
        volatile boolean isLocked = true;
    }

    private static final ThreadLocal<MCSNode> NODE = new ThreadLocal<>();

    // 隊(duì)列
    @SuppressWarnings("unused")
    private volatile MCSNode queue;

    private static final AtomicReferenceFieldUpdater<MCSLock,MCSNode> UPDATE =
            AtomicReferenceFieldUpdater.newUpdater(MCSLock.class,MCSNode.class,"queue");


    public void lock(){
        // 創(chuàng)建節(jié)點(diǎn)并保存到ThreadLocal中
        MCSNode currentNode = new MCSNode();
        NODE.set(currentNode);

        // 將queue設(shè)置為當(dāng)前節(jié)點(diǎn)，并且返回之前的節(jié)點(diǎn)
        MCSNode preNode = UPDATE.getAndSet(this, currentNode);
        if (preNode != null) {
            // 如果之前節(jié)點(diǎn)不為null，表示鎖已經(jīng)被其他線程持有
            preNode.next = currentNode;
            // 循環(huán)判斷，直到當(dāng)前節(jié)點(diǎn)的鎖標(biāo)志位為false
            while (currentNode.isLocked) {
            }
        }
    }

    public void unlock() {
        MCSNode currentNode = NODE.get();
        // next為null表示沒有正在等待獲取鎖的線程
        if (currentNode.next == null) {
            // 更新狀態(tài)并設(shè)置queue為null
            if (UPDATE.compareAndSet(this, currentNode, null)) {
                // 如果成功了，表示queue==currentNode,即當(dāng)前節(jié)點(diǎn)后面沒有節(jié)點(diǎn)了
                return;
            } else {
                // 如果不成功，表示queue!=currentNode,即當(dāng)前節(jié)點(diǎn)后面多了一個(gè)節(jié)點(diǎn)，表示有線程在等待
                // 如果當(dāng)前節(jié)點(diǎn)的后續(xù)節(jié)點(diǎn)為null，則需要等待其不為null（參考加鎖方法）
                while (currentNode.next == null) {
                }
            }
        } else {
            // 如果不為null，表示有線程在等待獲取鎖，此時(shí)將等待線程對應(yīng)的節(jié)點(diǎn)鎖狀態(tài)更新為false，同時(shí)將當(dāng)前線程的后繼節(jié)點(diǎn)設(shè)為null
            currentNode.next.isLocked = false;
            currentNode.next = null;
        }
    }
}

CLHLock 和 MCSLock

• 都是基于鏈表，不同的是CLHLock是基于隱式鏈表，沒有真正的后續(xù)節(jié)點(diǎn)屬性，MCSLock是顯示鏈表，有一個(gè)指向后續(xù)節(jié)點(diǎn)的屬性。
• 將獲取鎖的線程狀態(tài)借助節(jié)點(diǎn)(node)保存,每個(gè)線程都有一份獨(dú)立的節(jié)點(diǎn)，這樣就解決了TicketLock多處理器緩存同步的問題。

總結(jié)

此篇文章我們主要講述了自旋鎖的提出背景，自旋鎖是為了提高資源的使用頻率而出現(xiàn)的一種鎖，自旋鎖說的是線程獲取鎖的時(shí)候，如果鎖被其他線程持有，則當(dāng)前線程將循環(huán)等待，直到獲取到鎖。

自旋鎖在等待期間不會睡眠或者釋放自己的線程。自旋鎖不適用于長時(shí)間持有CPU的情況，這會加劇系統(tǒng)的負(fù)擔(dān)，為了解決這種情況，需要設(shè)定自旋周期，那么自旋周期的設(shè)定也是一門學(xué)問。

還提到了自旋鎖本身無法保證公平性，那么為了保證公平性又引出了TicketLock ，TicketLock 是采用排隊(duì)叫號的機(jī)制來實(shí)現(xiàn)的一種公平鎖，但是它每次讀寫操作都必須在多個(gè)處理器緩存之間進(jìn)行緩存同步，這會導(dǎo)致繁重的系統(tǒng)總線和內(nèi)存的流量，大大降低系統(tǒng)整體的性能。

所以我們又引出了CLHLock和MCSLock，CLHLock和MCSLock通過鏈表的方式避免了減少了處理器緩存同步，極大的提高了性能，區(qū)別在于CLHLock是通過輪詢其前驅(qū)節(jié)點(diǎn)的狀態(tài)，而MCS則是查看當(dāng)前節(jié)點(diǎn)的鎖狀態(tài)。