自旋鎖（Spin lock）

自旋鎖是指當(dāng)一個(gè)線程嘗試獲取某個(gè)鎖時(shí)，如果該鎖已被其他線程占用，就一直循環(huán)檢測(cè)鎖是否被釋放，而不是進(jìn)入線程掛起或睡眠狀態(tài)。

自旋鎖適用于鎖保護(hù)的臨界區(qū)很小的情況，臨界區(qū)很小的話，鎖占用的時(shí)間就很短。

簡(jiǎn)單的實(shí)現(xiàn)

import java.util.concurrent.atomic.AtomicReference;

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

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

              // 如果鎖未被占用，則設(shè)置當(dāng)前線程為鎖的擁有者
       while (owner.compareAndSet(null, currentThread)) {
       }
   }

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

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

SimpleSpinLock里有一個(gè)owner屬性持有鎖當(dāng)前擁有者的線程的引用，如果該引用為null，則表示鎖未被占用，不為null則被占用。

這里用AtomicReference是為了使用它的原子性的compareAndSet方法（CAS操作），解決了多線程并發(fā)操作導(dǎo)致數(shù)據(jù)不一致的問(wèn)題，確保其他線程可以看到鎖的真實(shí)狀態(tài)。

缺點(diǎn)

1. CAS操作需要硬件的配合；
2. 保證各個(gè)CPU的緩存（L1、L2、L3、跨CPU Socket、主存）的數(shù)據(jù)一致性，通訊開(kāi)銷(xiāo)很大，在多處理器系統(tǒng)上更嚴(yán)重；
3. 沒(méi)法保證公平性，不保證等待進(jìn)程/線程按照FIFO順序獲得鎖。

Ticket Lock

Ticket Lock 是為了解決上面的公平性問(wèn)題，類(lèi)似于現(xiàn)實(shí)中銀行柜臺(tái)的排隊(duì)叫號(hào)：鎖擁有一個(gè)服務(wù)號(hào)，表示正在服務(wù)的線程，還有一個(gè)排隊(duì)號(hào)；每個(gè)線程嘗試獲取鎖之前先拿一個(gè)排隊(duì)號(hào)，然后不斷輪詢鎖的當(dāng)前服務(wù)號(hào)是否是自己的排隊(duì)號(hào)，如果是，則表示自己擁有了鎖，不是則繼續(xù)輪詢。

當(dāng)線程釋放鎖時(shí)，將服務(wù)號(hào)加1，這樣下一個(gè)線程看到這個(gè)變化，就退出自旋。

簡(jiǎn)單的實(shí)現(xiàn)

import java.util.concurrent.atomic.AtomicInteger;

public class TicketLock {
   private AtomicInteger serviceNum = new AtomicInteger(); // 服務(wù)號(hào)
   private AtomicInteger ticketNum = new AtomicInteger(); // 排隊(duì)號(hào)

   public int lock() {
         // 首先原子性地獲得一個(gè)排隊(duì)號(hào)
         int myTicketNum = ticketNum.getAndIncrement();

              // 只要當(dāng)前服務(wù)號(hào)不是自己的就不斷輪詢
       while (serviceNum.get() != myTicketNum) {
       }

       return myTicketNum;
    }

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

缺點(diǎn)

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

下面介紹的CLH鎖和MCS鎖都是為了解決這個(gè)問(wèn)題的。

MCS 來(lái)自于其發(fā)明人名字的首字母： John Mellor-Crummey和Michael Scott。

CLH的發(fā)明人是：Craig，Landin and Hagersten。

MCS鎖

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

import java.util.concurrent.atomic.AtomicReferenceFieldUpdater;

public class MCSLock {
    public static class MCSNode {
        MCSNode next;
        boolean isLocked = true; // 默認(rèn)是在等待鎖
    }

    volatile MCSNode queue ;// 指向最后一個(gè)申請(qǐng)鎖的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.isLocked ) {// step 3
            }
        }
    }

    public void unlock(MCSNode currentThread) {
        if ( UPDATER.get( this ) == currentThread) {// 鎖擁有者進(jìn)行釋放鎖才有意義
            if (currentThread.next == null) {// 檢查是否有人排在自己后面
                if (UPDATER.compareAndSet(this, currentThread, null)) {// step 4
                    // compareAndSet返回true表示確實(shí)沒(méi)有人排在自己后面
                    return;
                } else {
                    // 突然有人排在自己后面了，可能還不知道是誰(shuí)，下面是等待后續(xù)者
                    // 這里之所以要忙等是因?yàn)椋簊tep 1執(zhí)行完后，step 2可能還沒(méi)執(zhí)行完
                    while (currentThread.next == null) { // step 5
                    }
                }
            }

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

CLH鎖

CLH鎖也是一種基于鏈表的可擴(kuò)展、高性能、公平的自旋鎖，申請(qǐng)線程只在本地變量上自旋，它不斷輪詢前驅(qū)的狀態(tài)，如果發(fā)現(xiàn)前驅(qū)釋放了鎖就結(jié)束自旋。

import java.util.concurrent.atomic.AtomicReferenceFieldUpdater;

public class CLHLock {
    public static class CLHNode {
        private boolean isLocked = true; // 默認(rèn)是在等待鎖
    }

    @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) {//已有線程占用了鎖，進(jìn)入自旋
            while(preNode.isLocked ) {
            }
        }
    }

    public void unlock(CLHNode currentThread) {
        // 如果隊(duì)列里只有當(dāng)前線程，則釋放對(duì)當(dāng)前線程的引用（for GC）。
        if (!UPDATER .compareAndSet(this, currentThread, null)) {
            // 還有后續(xù)線程
            currentThread. isLocked = false ;// 改變狀態(tài)，讓后續(xù)線程結(jié)束自旋
        }
    }
}

CLH鎖 與 MCS鎖 的比較

下圖是CLH鎖和MCS鎖隊(duì)列圖示：

差異：

1. 從代碼實(shí)現(xiàn)來(lái)看，CLH比MCS要簡(jiǎn)單得多。
2. 從自旋的條件來(lái)看，CLH是在本地變量上自旋，MCS是自旋在其他對(duì)象的屬性。
3. 從鏈表隊(duì)列來(lái)看，CLH的隊(duì)列是隱式的，CLHNode并不實(shí)際持有下一個(gè)節(jié)點(diǎn)；MCS的隊(duì)列是物理存在的。
4. CLH鎖釋放時(shí)只需要改變自己的屬性，MCS鎖釋放則需要改變后繼節(jié)點(diǎn)的屬性。

注意：這里實(shí)現(xiàn)的鎖都是獨(dú)占的，且不能重入的。