自旋鎖、排隊自旋鎖、MCS鎖、CLH鎖

1、實作自旋鎖

通過一個AtomicReference<Thread>類型成員變量owner，就可以實作一個自旋鎖，owner屬性持有目前擁有鎖的線程引用，如果該引用為null，表示鎖未被用，不為null則被占用。通過AtomicReference對象compareAndSet方法解決了多線程并發操作導緻資料不一緻問題，確定其它線程可以看到鎖的真實狀态。

2、實作公平自旋鎖

通過上面簡單CAS操作無法保證公平性，不能保證等待線程按照FIFO順序獲得鎖。可以通過類似排隊叫号方案實作公平鎖：鎖對象擁有一個服務号，表示正在服務的線程，還有一個排隊号，每個線程擷取鎖前先拿一個排隊号，然後不斷輪詢目前的服務号是否是自己的排隊号，若是就擁有鎖，否則繼續輪詢。釋放鎖時将服務号加1，進而使下一個線程退出自旋。但這個方法多個線程都在讀寫同一個變量服務号，每次操作都會導緻多個處理器緩存之間同步，增加系統總線和記憶體流量，降低系統整體性能。

3、MCS鎖和CLH鎖

是以又産生了MCS鎖和CLH鎖。MCS鎖是基于連結清單的可擴充、高性能、公平自旋鎖，申請線程隻在本地變量上自旋，直接前驅負責通知其自旋結束，進而減少了處理器緩存同步次數，降低了系統總開銷。

CLH鎖是基于隐形連結清單的可擴充、高性能、公平的自旋鎖，申請線程隻在本地變量上自旋，它不斷輪詢前驅的狀态，發現前驅釋放了鎖就結束自旋。CLH鎖代碼實作上比MCS要簡單的多，它在釋放鎖時隻改變自己的屬性，而MCS鎖釋放鎖時需要改變後繼節點的屬性。

自旋鎖（SPIN LOCK）

自旋鎖是指當一個線程嘗試擷取某個鎖時，如果該鎖已被其他線程占用，就一直循環檢測鎖是否被釋放，而不是進入線程挂起或睡眠狀态。

自旋鎖适用于鎖保護的臨界區很小的情況，臨界區很小的話，鎖占用的時間就很短。

簡單的實作

import java.util.concurrent.atomic.AtomicReference;

public class SpinLock {
   private AtomicReference<Thread> owner = new AtomicReference<Thread>();

   public void lock() {
       Thread currentThread = Thread.currentThread();

              // 如果鎖未被占用，則設定目前線程為鎖的擁有者
       while (!owner.compareAndSet(null, currentThread)) {
       }
   }

   public void unlock() {
       Thread currentThread = Thread.currentThread();

              // 隻有鎖的擁有者才能釋放鎖
       owner.compareAndSet(currentThread, null);
   }
}
           

SimpleSpinLock裡有一個owner屬性持有鎖目前擁有者的線程的引用，如果該引用為null，則表示鎖未被占用，不為null則被占用。

這裡用AtomicReference是為了使用它的原子性的compareAndSet方法（CAS操作），解決了多線程并發操作導緻資料不一緻的問題，確定其他線程可以看到鎖的真實狀态。

缺點

1. CAS操作需要硬體的配合；
2. 保證各個CPU的緩存（L1、L2、L3、跨CPU Socket、主存）的資料一緻性，通訊開銷很大，在多處理器系統上更嚴重；
3. 沒法保證公平性，不保證等待程序/線程按照FIFO順序獲得鎖。

TICKET LOCK

Ticket Lock 是為了解決上面的公平性問題，類似于現實中銀行櫃台的排隊叫号：鎖擁有一個服務号，表示正在服務的線程，還有一個排隊号；每個線程嘗試擷取鎖之前先拿一個排隊号，然後不斷輪詢鎖的目前服務号是否是自己的排隊号，如果是，則表示自己擁有了鎖，不是則繼續輪詢。

當線程釋放鎖時，将服務号加1，這樣下一個線程看到這個變化，就退出自旋。

import java.util.concurrent.atomic.AtomicInteger;

public class TicketLock {
   private AtomicInteger serviceNum = new AtomicInteger(); // 服務号
   private AtomicInteger ticketNum = new AtomicInteger(); // 排隊号

   public int lock() {
         // 首先原子性地獲得一個排隊号
         int myTicketNum = ticketNum.getAndIncrement();

              // 隻要目前服務号不是自己的就不斷輪詢
       while (serviceNum.get() != myTicketNum) {
       }

       return myTicketNum;
    }

    public void unlock(int myTicket) {
        // 隻有目前線程擁有者才能釋放鎖
        int next = myTicket + 1;
        serviceNum.compareAndSet(myTicket, next);
    }
}
           

Ticket Lock 雖然解決了公平性的問題，但是多處理器系統上，每個程序/線程占用的處理器都在讀寫同一個變量serviceNum ，每次讀寫操作都必須在多個處理器緩存之間進行緩存同步，這會導緻繁重的系統總線和記憶體的流量，大大降低系統整體的性能。

下面介紹的CLH鎖和MCS鎖都是為了解決這個問題的。

MCS 來自于其發明人名字的首字母： John Mellor-Crummey和Michael Scott。

CLH的發明人是：Craig，Landin and Hagersten。

MCS鎖

MCS Spinlock 是一種基于連結清單的可擴充、高性能、公平的自旋鎖，申請線程隻在本地變量上自旋，直接前驅負責通知其結束自旋，進而極大地減少了不必要的處理器緩存同步的次數，降低了總線和記憶體的開銷。

import java.util.concurrent.atomic.AtomicReferenceFieldUpdater;

public class MCSLock {
    public static class MCSNode {
        volatile MCSNode next;
        volatile boolean isBlock = true; // 預設是在等待鎖
    }

    volatile MCSNode queue;// 指向最後一個申請鎖的MCSNode
    private static final AtomicReferenceFieldUpdater<mcslock, mcsnode=""> UPDATER = AtomicReferenceFieldUpdater
            .newUpdater(MCSLock.class, MCSNode.class, "queue");

    public void lock(MCSNode currentThread) {
        MCSNode predecessor = UPDATER.getAndSet(this, currentThread);// step 1
        if (predecessor != null) {
            predecessor.next = currentThread;// step 2

            while (currentThread.isBlock) {// step 3
            }
        }else { // 隻有一個線程在使用鎖，沒有前驅來通知它，是以得自己标記自己為非阻塞
               currentThread. isBlock = false;
          }
    }

    public void unlock(MCSNode currentThread) {
        if (currentThread.isBlock) {// 鎖擁有者進行釋放鎖才有意義
            return;
        }

        if (currentThread.next == null) {// 檢查是否有人排在自己後面
            if (UPDATER.compareAndSet(this, currentThread, null)) {// step 4
                // compareAndSet傳回true表示确實沒有人排在自己後面
                return;
            } else {
                // 突然有人排在自己後面了，可能還不知道是誰，下面是等待後續者
                // 這裡之是以要忙等是因為：step 1執行完後，step 2可能還沒執行完
                while (currentThread.next == null) { // step 5
                }
            }
        }

        currentThread.next.isBlock = false;
        currentThread.next = null;// for GC
    }
}
           

CLH鎖

CLH鎖也是一種基于連結清單的可擴充、高性能、公平的自旋鎖，申請線程隻在本地變量上自旋，它不斷輪詢前驅的狀态，如果發現前驅釋放了鎖就結束自旋。

import java.util.concurrent.atomic.AtomicReferenceFieldUpdater;

public class CLHLock {
    public static class CLHNode {
        private volatile boolean isLocked = true; // 預設是在等待鎖
    }

    @SuppressWarnings("unused" )
    private volatile CLHNode tail ;
    private static final AtomicReferenceFieldUpdater<CLHLock, CLHNode> UPDATER = AtomicReferenceFieldUpdater
                  . newUpdater(CLHLock.class, CLHNode .class , "tail" );

    public void lock(CLHNode currentThread) {
        CLHNode preNode = UPDATER.getAndSet( this, currentThread);
        if(preNode != null) {//已有線程占用了鎖，進入自旋
            while(preNode.isLocked ) {
            }
        }
    }

    public void unlock(CLHNode currentThread) {
        // 如果隊列裡隻有目前線程，則釋放對目前線程的引用（for GC）。
        if (!UPDATER .compareAndSet(this, currentThread, null)) {
            // 還有後續線程
            currentThread. isLocked = false ;// 改變狀态，讓後續線程結束自旋
        }
    }
}
           

CLH鎖 與 MCS鎖 的比較

下圖是CLH鎖和MCS鎖隊列圖示：

差異：

1. 從代碼實作來看，CLH比MCS要簡單得多。
2. 從自旋的條件來看，CLH是在前驅節點的屬性上自旋，而MCS是在本地屬性變量上自旋。
3. 從連結清單隊列來看，CLH的隊列是隐式的，CLHNode并不實際持有下一個節點；MCS的隊列是實體存在的。
4. CLH鎖釋放時隻需要改變自己的屬性，MCS鎖釋放則需要改變後繼節點的屬性。