背景

SMP(Symmetric Multi-Processor)

對稱多處理器結構，它是相對非對稱多處理技術而言的、應用十分廣泛的并行技術。

image

• 在這種架構中，一臺計算機由多個CPU組成，并共享內存和其他資源，所有的CPU都可以平等地訪問內存、I/O和外部中斷。
• 雖然同時使用多個CPU，但是從管理的角度來看，它們的表現(xiàn)就像一臺單機一樣。
• 操作系統(tǒng)將任務隊列對稱地分布于多個CPU之上，從而極大地提高了整個系統(tǒng)的數(shù)據(jù)處理能力。
• 但是隨著CPU數(shù)量的增加，每個CPU都要訪問相同的內存資源，共享資源可能會成為系統(tǒng)瓶頸，導致CPU資源浪費。

NUMA(Non-Uniform Memory Access)

非一致存儲訪問，將CPU分為CPU模塊，每個CPU模塊由多個CPU組成，并且具有獨立的本地內存、I/O槽口等，模塊之間可以通過互聯(lián)模塊相互訪問。

image

• 訪問本地內存（本CPU模塊的內存）的速度將遠遠高于訪問遠程內存(其他CPU模塊的內存)的速度，這也是非一致存儲訪問的由來。

• NUMA較好地解決SMP的擴展問題，當CPU數(shù)量增加時，因為訪問遠地內存的延時遠遠超過本地內存，系統(tǒng)性能無法線性增加。

CLH鎖

CLH是一種基于單向鏈表的高性能、公平的自旋鎖。申請加鎖的線程通過前驅節(jié)點的變量進行自旋。在前置節(jié)點解鎖后，當前節(jié)點會結束自旋，并進行加鎖。

image

• 在SMP架構下，CLH更具有優(yōu)勢。
• 在NUMA架構下，如果當前節(jié)點與前驅節(jié)點不在同一CPU模塊下，跨CPU模塊會帶來額外的系統(tǒng)開銷，而MCS鎖更適用于NUMA架構。

加鎖邏輯

1. 獲取當前線程的鎖節(jié)點，如果為空，則進行初始化；

2. 同步方法獲取鏈表的尾節(jié)點，并將當前節(jié)點置為尾節(jié)點，此時原來的尾節(jié)點為當前節(jié)點的前置節(jié)點。

3. 如果尾節(jié)點為空，表示當前節(jié)點是第一個節(jié)點，直接加鎖成功。

4. 如果尾節(jié)點不為空，則基于前置節(jié)點的鎖值（locked==true）進行自旋，直到前置節(jié)點的鎖值變?yōu)閒alse。

解鎖邏輯

1. 獲取當前線程對應的鎖節(jié)點，如果節(jié)點為空或者鎖值為false，則無需解鎖，直接返回；

2. 同步方法為尾節(jié)點賦空值，賦值不成功表示當前節(jié)點不是尾節(jié)點，則需要將當前節(jié)點的locked=false解鎖節(jié)點。如果當前節(jié)點是尾節(jié)點，則無需為該節(jié)點設置。

public class CLHLock {
    private final AtomicReference<Node> tail;
    private final ThreadLocal<Node> myNode;
    private final ThreadLocal<Node> myPred;
 
    public CLHLock() {
        tail = new AtomicReference<>(new Node());
        myNode = ThreadLocal.withInitial(() -> new Node());
        myPred = ThreadLocal.withInitial(() -> null);
    }
 
    public void lock(){
        Node node = myNode.get();
        node.locked = true;
        Node pred = tail.getAndSet(node);
        myPred.set(pred);
        while (pred.locked){}
    }
 
    public void unLock(){
        Node node = myNode.get();
        node.locked=false;
        myNode.set(myPred.get());
    }
 
 
    static class Node {
        volatile boolean locked = false;
    }
 
}

MCS鎖

MSC與CLH最大的不同并不是鏈表是顯示還是隱式，而是線程自旋的規(guī)則不同:CLH是在前趨結點的locked域上自旋等待，而MCS是在自己的結點的locked域上自旋等待。正因為如此，它解決了CLH在NUMA系統(tǒng)架構中獲取locked域狀態(tài)內存過遠的問題。

MCS鎖具體實現(xiàn)規(guī)則：

• a. 隊列初始化時沒有結點，tail=null

• b. 線程A想要獲取鎖，將自己置于隊尾，由于它是第一個結點，它的locked域為false

• c. 線程B和C相繼加入隊列，a->next=b,b->next=c，B和C沒有獲取鎖，處于等待狀態(tài)，所以locked域為true，尾指針指向線程C對應的結點

• d. 線程A釋放鎖后，順著它的next指針找到了線程B，并把B的locked域設置為false，這一動作會觸發(fā)線程B獲取鎖。

public class MCSLock {
 
    private final AtomicReference<Node> tail;
 
    private final ThreadLocal<Node> myNode;
 
    public MCSLock() {
        tail = new AtomicReference<>();
        myNode = ThreadLocal.withInitial(() -> new Node());
    }
 
    public void lock() {
 
        Node node = myNode.get();
        Node pred = tail.getAndSet(node);
        if (pred != null) {
            node.locked = true;
            pred.next = node;
            while (node.locked) {
            }
        }
 
    }
 
    public void unLock() {
        Node node = myNode.get();
        if (node.next == null) {
            if (tail.compareAndSet(node, null)) {
                return;
            }
 
            while (node.next == null) {
            }
        }
        node.next.locked = false;
        node.next = null;
    }
 
    class Node {
        volatile boolean locked = false;
        Node next = null;
    }
 
    public static void main(String[] args) {
 
        MCSLock lock = new MCSLock();
 
        Runnable task = new Runnable() {
            private int a;
 
            @Override
            public void run() {
                lock.lock();
                for (int i = 0; i < 10; i++) {
                    a++;
                    try {
                        Thread.sleep(100);
                    } catch (InterruptedException e) {
                        e.printStackTrace();
                    }
                }
                System.out.println(a);
                lock.unLock();
            }
        };
 
        new Thread(task).start();
        new Thread(task).start();
        new Thread(task).start();
        new Thread(task).start();
    }
}