自旋鎖-JUC系列

2022 年 1 月 15 日
筆記
JAVA, 我們到底能走多遠系列

前言

2022！這個年份現在看起來都覺得有那麼些恍惚的未來感，然而現在已在腳下。

無邊落木蕭蕭下，不盡長江滾滾來！

人生如白駒過隙！

本來計劃最近把AQS源碼分析做了，然後自下而上把JUC整個探一遍，集合成文記錄下來。但是因為前期沒有很好的筆記準備，加上內容涉及的廣度比較大，只好把目標降低：控制好涉及面情況下，能有輸出就行。主要還是想把以前養成的寫博客習慣撿起來。

所以，就先收集和總結一些內容作為分析源碼學習需要的基礎知識儲備，在這個過程中，發現了兩個經驗：

連成網的知識結構更容易發揮出能量，有時候理解了一個事物後，做一些延展性的思考，總結抽象規律，以及相似性的類比都是很有必要的，以前自己總在需要做這些事的時候中斷了。
凡事都是從功利的角度去衡量投入回報總是會讓人容易懈怠，因為世界上大部分的事情並不是為了什麼而做什麼可以去驅動的，如果真是如此，這也太無趣了。

主文

CAS

Compare-and-Swap，即比較並交換。

是原子操作的一種，可用於在多線程編程中實現不被打斷的數據交換操作，從而避免多線程同時改寫某一數據時由於執行順序不確定性以及中斷的不可預知性產生的數據不一致問題。該操作通過將內存中的值與指定數據進行比較，當數值一樣時將內存中的數據替換為新的值。wiki

CAS是一條CPU的原子指令（cmpxchg指令），不會造成數據不一致問題，而在JAVA世界裏，這個原子操作的能力是通過Unsafe類來提供的，這個類提供的API是低級別也就是底層操作的，比如內存操作，線程調度，對象操作等等。Unsafe提供的CAS方法底層實現就是CPU指令cmpxchg：

public final native boolean compareAndSwapObject(Object var1, long var2, Object var4, Object var5);
public final native boolean compareAndSwapInt(Object var1, long var2, int var4, int var5);
public final native boolean compareAndSwapLong(Object var1, long var2, long var4, long var6);

再詳細一點，CAS操作分成以下步驟：

1，讀取內存上的當前值X
2，進行比較傳入的期望值A和當前值X，相同則只需第三步
3，寫入新值B

並發累加例子

舉一個場景，現在兩個線程對x同時進行累加5000次，結束後打印出結果，我們期望是10000。

public class IntIncr implements Runnable{

    private static int x;

    public static void main(String[] args) throws InterruptedException {
        for (int i = 0; i < 6; i++) {
            IntIncr intIncr = new IntIncr();
            Thread t1 = new Thread(intIncr);
            t1.start();
            
            Thread t2 = new Thread(intIncr);
            t2.start();

            t1.join();
            t2.join();

            System.out.println("x:" + x);
            x = 0;
        }

    }

    @Override
    public void run() {
        for (int i = 0; i < 5000; i++) {
            x++;
        }
    }
}

結果：

x:10000
x:9130
x:10000
x:9038
x:10000
x:7391

結果並不如我們期望那樣，原因是累加的操作並不是一個原子操作，所以是不保證線程安全的。

Atomic包

在JDK中的java.util.concurrent.atomic包中的類以CAS操作為基石構建出原子操作的封裝類的功能，下面AtomicInteger的累加方法代碼：

實現原子變量的能力不僅需要CAS，還有volatile，這部分下一篇單獨展開。

// setup to use Unsafe.compareAndSwapInt for updates
private static final Unsafe unsafe = Unsafe.getUnsafe();
// 內存地址偏移量
private static final long valueOffset;

static {
  try {
    // class加載時計算在對象佔用的內存中value的位置
    valueOffset = unsafe.objectFieldOffset
      (AtomicInteger.class.getDeclaredField("value"));
  } catch (Exception ex) { throw new Error(ex); }
}

// volatile修飾的int值
private volatile int value;

/**
 * Atomically adds the given value to the current value.
 *
 * @param delta the value to add
 * @return the updated value
 */
public final int addAndGet(int delta) {
    return unsafe.getAndAddInt(this, valueOffset, delta) + delta;
}

Unsafe類中的getAndAddInt方法實際是一個while循環使用compareAndSwapInt把累加值賦值到指定內存，能夠賦值的判斷條件是剛剛getIntVolatile讀取的值沒有變化。

public final int getAndAddInt(Object var1, long var2, int var4) {
    int var5;
    do {
        var5 = this.getIntVolatile(var1, var2);
    } while(!this.compareAndSwapInt(var1, var2, var5, var5 + var4));

    return var5;
}

自旋鎖

內存數據同步

關於JMM（java內存模型）這裡不做展開，會在下一篇中詳細解釋，但是需要理解內存數據的同步機制

JMM對內存進行了抽象劃分：

本地內存：線程執行時使用的工作內存，線程私有
主內存：存儲共享變量存儲，線程共享

我們想一個問題，如果有一個共享變量在A線程改成了X值，在B線程看到的還是老的值，會發生什麼呢？

前面的並發累加例子就是要發生的事情！

一個需要頻繁修改的值，需要及時的同步給各個需要使用的線程本地內存中才行，我們先知道是有一個機制來保證的，並且重點需要明白把一個最新的值從一個本地內存同步到主內存，再同步到另一個本地內存是需要有消耗的。

自旋鎖實現

從前面的Atomic包的代碼實現中就看到通過一個CAS操作可以達到原子操作，那麼加入操作的是一個標記，這個標記表示是否獲得資源，也就是獲得鎖的概念。

所以實現一個自旋鎖就非常簡單了：

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();
        // 只需要設置回null，就釋放鎖了
        cas.compareAndSet(current, null);
    }

}

這就是傳說中的自旋鎖，通過一個while循環，就輕鬆實現了。

用一句話總結自旋鎖的好處，那就是自旋鎖用循環去不停地嘗試獲取鎖，讓線程始終處於 Runnable 狀態，節省了線程狀態切換帶來的開銷。

考慮一下，自旋鎖用在什麼場景比較合適？

優化

Spin on READ

我們知道多線程的本地內存能夠及時同步，執行compareAndSet會把其他線程本地內存上的鎖值置成過期，當這些線程需要用到的時候會向主內存上同步。上面自旋的代碼可以發現，所有沒拿到鎖的並發線程都在不停執行compareAndSet，如此你可以想像得到CPU需要花費精力不停的做內存數據同步，也就是CPU緩存一致性總線風暴。

那麼就有了spin on READ的優化，也就是在進入compareAndSet搶鎖前，先讀取數據檢查鎖是不是已經釋放，這樣就大大減少了在compareAndSet上的自旋，把自旋遷移到讀取數據上。實現如下：

public class TTASLock {

    private AtomicReference<Thread> cas = new AtomicReference<Thread>();

    public void lock() {
        Thread current = Thread.currentThread();
        while (true){
            // 判斷未解鎖 就在這裡通過get自旋
            while(cas.get() != null){}
            // 使用CAS搶鎖，搶到鎖的推出執行加鎖後邏輯
            if (cas.compareAndSet(null, current)) {
                // 搶到鎖則退出外部循環
                break;
            }
        }

    }

    public void unlock() {
        Thread current = Thread.currentThread();
        // 只需要設置回null，就釋放鎖了
        cas.compareAndSet(current, null);
    }
}

Spin and Sleep

再想一下，如果為了減少沒有獲取鎖的線程自旋的消耗，能不能在沒獲取鎖的while循環里sleep一會兒，這樣也可以減少compareAndSet的消耗吧，但是因為沒有機制讓我們知道sleep多久是合適的，sleep久了也是極大的浪費，不過這也是可以想到的思路。

TicketLock（Fair Lock）

鎖有公平和不公平之分，公平鎖就是保證多線程並發搶鎖時能按順序獲得，先到的線程先獲得鎖，不公平鎖就是不保證這個順序了。那麼前面寫的自旋鎖實現是不公平的，就有人想怎麼改造一下，獲得公平鎖的能力。

public class TicketLock {

    // 記錄票的號數，初始化是0，記號從1號開始
    private AtomicInteger ticketer = new AtomicInteger(0);
    // 叫號從1號開始
    private AtomicInteger callNumber = new AtomicInteger(1);

    public void lock() {
        // 每次觸發搶鎖就原子操作記號器加1，隱含順序意義
        int num = ticketer.incrementAndGet();
        // 叫號和記錄票的號數相同則獲取到鎖，否則自旋
        while (num != callNumber.get()){}
    }

    public void unlock() {
        // 釋放鎖就是把比對號加1
        callNumber.incrementAndGet();
    }
}

這個實現可以簡單比對成一個生活的場景，我們去銀行辦理業務都是需要取號（ticketer），每次取出號碼規律是累加，假設只有一個客戶經理在上班，她一次只能和一個人對接，對接期間其他人就要排隊，她處理完一個就叫號（callNumber），號碼按順序累加。下一位能被接待的人就是手上的號和叫號相同的人。

MCS

MCS論文

這篇論文詳細解釋了MCS的來源，其中這段就像在向世界介紹一個新發明：

它第一次把隊列引入了進來解決問題，算是一個創新。

MCS自旋鎖是一種基於單向鏈表的高性能、公平的自旋鎖，申請加鎖的線程只需要在本地變量上自旋，直接前驅負責通知其結束自旋，從而極大地減少了不必要的處理器緩存同步的次數，降低了總線和內存的開銷。

關鍵描述：

單向鏈表
本地變量上自旋

單向鏈表是數據結構，java實現一個就行，本地變量就是線程本地變量，java中就可以用ThreadLocal來實現。

public class MCSLock {

    // 鏈表尾部指向
    private final AtomicReference<Node> tail;
    // 每個線程維護的內部變量
    private final ThreadLocal<Node> myNode;
  
    /**
     * 節點定義
     */
    class Node {
        volatile boolean locked = false;
        Node next = null;
    }

    public MCSLock() {
        // 隊尾指向 使用AtomicReference保證原子操作
        tail = new AtomicReference<>();
        // 線程本地變量維護各自線程的Node
        myNode = ThreadLocal.withInitial(() -> new Node());
    }

    public void lock() {
        Node node = myNode.get();
        // 把隊尾指向到自己 注意這裡是有cas 原子操作，確保了多線程並發下依次執行，保證了並發場景下鏈表的形成
        Node pred = tail.getAndSet(node); // step1
        // 如果原先有隊尾node存在，說明已經有線程佔用了鎖
        if (pred != null) {
            // 把自己的節點設置成鎖狀態
            node.locked = true;
            // 並且把前後兩個node用next連接起來
            pred.next = node; // step2
            // 自旋自己node的locked字段
            while (node.locked) {
            }
        }

    }

    // 釋放鎖
    public void unLock() {
        // 操作本線程的本地變量維護的node
        Node node = myNode.get();
        // 判斷自己後面還有沒有等待的節點
        if (node.next == null) {
            // 如果自己是最後一個節點，那麼就把尾部指向改成null，這裡仍然是需要使用cas操作來進行
            if (tail.compareAndSet(node, null)) {
                // 操作成功就結束了
                return;
            }
            // 前面的compareAndSet執行失敗，就是說去設置尾部指向的時候被別人搶先了
            // 只有一種可能那就是有其他線程執行lock了，這裡需要在自旋等待一下node.next被lock操作設置
            while (node.next == null) {
            }
        }
        // 相當於通知自己後面的節點釋放鎖
        node.next.locked = false;
        // 把自己設置成null，釋放內存
        node.next = null;
    }
}

代碼中的注釋已經解釋得比較清楚了，它使用一個單向鏈表實現線程等待的順序效果，每個線程自旋本地變量維護的節點中的boolean字段，從而達到監聽鎖狀態的效果。

其中，在釋放鎖的代碼中有一個自旋判斷node.next == null，要理解這點需要現理解到這裡能執行到這個判斷是在tail.compareAndSet(node, null)執行返回false，也就意味着必然是有線程搶佔了tail的指向，再看上面lock代碼中搶佔tail指向是step1代碼，所以這裡可以確定有線程已經執行到step1了。

然後在繼續看到lock操作中的step1先設置tail指向，然後到step2才把老節點的next指向到自己，這兩步分開意味着第一步完成後第二步還沒執行的時候，pred.next是null，所以去執行釋放鎖中的 node.next.locked = false;就直接空指針了。

CLH

public class CLHLock {
    // 尾部指向
    private final AtomicReference<Node> tail;
    // 當前線程持有節點
    private final ThreadLocal<Node> myNode;
    // 當前線程的前面節點
    private final ThreadLocal<Node> myPred;

    /**
     * 節點定義
     */
    static class Node {
        volatile boolean locked = false;
    }

    public CLHLock() {
        // 初始化尾部指向一個Node對象
        tail = new AtomicReference<>(new Node());
        myNode = ThreadLocal.withInitial(() -> new Node());
        // 初始化前面節點為空
        myPred = ThreadLocal.withInitial(() -> null);
    }

    public void lock(){
        Node node = myNode.get();
        // 設置成獲得鎖狀態
        node.locked = true;
        // 尾部指向自己 剛開始的第一個執行的返回pred就是前面CLHLock初始化時產生的Node對象
        Node pred = tail.getAndSet(node);
        // 自己維護前面節點
        myPred.set(pred);
        // 自旋前面節點的鎖狀態
        while (pred.locked){}
    }

    public void unLock(){
        Node node = myNode.get();
        // 釋放鎖
        node.locked=false;
        // 把自己設置成那個CLHLock初始化時產生的Node對象
        myNode.set(myPred.get());
    }
}

和前面的MCS鎖對比，有幾個關鍵點的區別：

1，MCS自旋的是自己節點上的狀態屬性，變更是有前面節點用過next引用來更改的，而CLH是自旋自己前面節點的狀態屬性，鎖狀態更新就是由前面節點釋放自己節點的鎖狀態來達成的。
2，MCS使用的是顯示鏈表，因為它在Node定義里有next指向，而CLH是隱式鏈表

第一點不同和兩個鎖設計的起因有關，CLH的缺點是在NUMA系統結構下性能很差，但是在SMP系統結構下非常有效的。解決NUMA系統結構的思路是MCS隊列鎖。關於這兩種結構的區別可以查看參考資料。

參考資料

1，//www.cc.gatech.edu/classes/AY2010/cs4210_fall/papers/anderson-spinlock.pdf

2，//www.eecg.utoronto.ca/~amza/ece1747h/papers/readings/tocs91.pdf

3，//en.wikipedia.org/wiki/Spinlock

4，//funzzz.fun/2021/05/19/CLH鎖/

5，//www.quora.com/What-is-the-difference-between-SMP-and-NUMA-architectures

Tags: JAVA 我們到底能走多遠系列