public class SpinLockTest {
    /**
     * 持有鎖的線程，null表示鎖未被線程持有
     */
    private AtomicReference<Thread> ref = new AtomicReference<>();
    public void lock(){
        Thread currentThread = Thread.currentThread();
        while(!ref.compareAndSet(null, currentThread)){
            //當(dāng)ref為null的時(shí)候compareAndSet返回true，反之為false
            //通過(guò)循環(huán)不斷的自旋判斷鎖是否被其他線程持有
        }
    }
    public void unLock() {
        Thread cur = Thread.currentThread();
        if(ref.get() != cur){
            //exception ...
        }
        ref.set(null);
    }
}
//自旋鎖測(cè)試
public class SpinLockTestTest {
    static int count = 0;
    @Test
    public void spinLockTest() throws InterruptedException {
        ExecutorService executorService = Executors.newFixedThreadPool(100);
        CountDownLatch countDownLatch = new CountDownLatch(100);
        SpinLockTest2 spinLockTest2 = new SpinLockTest2();
        for (int i = 0; i < 100; i++) {
            executorService.execute(new Runnable() {
                @Override
                public void run() {
                    spinLockTest2.lock();
                    ++count;
                    spinLockTest2.unLock();
                    countDownLatch.countDown();
                }
            });
        }
        countDownLatch.await();
        System.out.println (count);
   }
}

/**
 * @Description TicketLock 是一種同步機(jī)制或鎖定算法，它是一種自旋鎖，它使用ticket 來(lái)控制線程執(zhí)行順序。
 *
 * TicketLock 是基于先進(jìn)先出(FIFO) 隊(duì)列的機(jī)制。
 * 它增加了鎖的公平性，其設(shè)計(jì)原則如下：TicketLock 中有兩個(gè) int 類型的數(shù)值，
 * 開(kāi)始都是0，第一個(gè)值是隊(duì)列ticket(隊(duì)列票據(jù))， 第二個(gè)值是 出隊(duì)(票據(jù))。
 * 隊(duì)列票據(jù)是線程在隊(duì)列中的位置，而出隊(duì)票據(jù)是現(xiàn)在持有鎖的票證的隊(duì)列位置。
 * 可能有點(diǎn)模糊不清，簡(jiǎn)單來(lái)說(shuō)，就是隊(duì)列票據(jù)是你取票號(hào)的位置，出隊(duì)票據(jù)是你距離叫號(hào)的位置。
 *
 *
 * @Author zhoumm
 * @Version V1.0.0
 * @Since 1.0
 * @Date 2020-05-29
 */
//這個(gè)設(shè)計(jì)是有問(wèn)題的，因?yàn)楂@得自己的號(hào)碼之后，是可以對(duì)號(hào)碼進(jìn)行更改的，這就造成系統(tǒng)紊亂，鎖不能及時(shí)釋放。
//需要有一個(gè)能確保每個(gè)人按會(huì)著自己號(hào)碼排隊(duì)辦業(yè)務(wù)的角色
public class TicketLock {
    // 隊(duì)列票據(jù)(當(dāng)前排隊(duì)號(hào)碼)
    private AtomicInteger queueNum = new AtomicInteger();
    // 出隊(duì)票據(jù)(當(dāng)前需等待號(hào)碼)
    private AtomicInteger dueueNum = new AtomicInteger();
    // 獲取鎖：如果獲取成功，返回當(dāng)前線程的排隊(duì)號(hào)
    public int lock(){
        int currentTicketNum = dueueNum.incrementAndGet();
        while (currentTicketNum != queueNum.get()){
            // doSomething...
        }
        return currentTicketNum;
    }
    // 釋放鎖：傳入當(dāng)前排隊(duì)的號(hào)碼
    public void unLock(int ticketNum){
        queueNum.compareAndSet(ticketNum,ticketNum + 1);
    }
    //改進(jìn)后，這就不再需要返回值，辦業(yè)務(wù)的時(shí)候，要將當(dāng)前的這一個(gè)號(hào)碼緩存起來(lái)，在辦完業(yè)務(wù)后，需要釋放緩存的這條票據(jù)。
    //缺點(diǎn):雖然解決了公平性的問(wèn)題，但是多處理器系統(tǒng)上，每個(gè)進(jìn)程/線程占用的處理器都在讀寫(xiě)同一個(gè)變量queueNum ，
    // 每次讀寫(xiě)操作都必須在多個(gè)處理器緩存之間進(jìn)行緩存同步，這會(huì)導(dǎo)致繁重的系統(tǒng)總線和內(nèi)存的流量，大大降低系統(tǒng)整體的性能。
    //為了解決這個(gè)問(wèn)題，MCSLock 和 CLHLock 應(yīng)運(yùn)而生
    public class TicketLock2 {
        // 隊(duì)列票據(jù)(當(dāng)前排隊(duì)號(hào)碼)
        private AtomicInteger queueNum = new AtomicInteger();
        // 出隊(duì)票據(jù)(當(dāng)前需等待號(hào)碼)
        private AtomicInteger dueueNum = new AtomicInteger();
        //線程內(nèi)部的存儲(chǔ)類，可以在指定線程內(nèi)存儲(chǔ)數(shù)據(jù)，數(shù)據(jù)存儲(chǔ)以后，只有指定線程可以得到存儲(chǔ)數(shù)據(jù)
        private ThreadLocal<Integer> ticketLocal = new ThreadLocal<>();
        public void lock(){
            int currentTicketNum = dueueNum.incrementAndGet();
            // 獲取鎖的時(shí)候，將當(dāng)前線程的排隊(duì)號(hào)保存起來(lái)
            ticketLocal.set(currentTicketNum);
            while (currentTicketNum != queueNum.get()){
                // doSomething...
            }
        }
        // 釋放鎖：從排隊(duì)緩沖池中取
        public void unLock(){
            Integer currentTicket = ticketLocal.get();
            queueNum.compareAndSet(currentTicket,currentTicket + 1);
        }
    }
}

/**
 * @Description
 * TicketLock 是基于隊(duì)列的，那么 CLHLock 就是基于鏈表設(shè)計(jì)的
 *
 * CLH 是一種基于鏈表的可擴(kuò)展，高性能，公平的自旋鎖，申請(qǐng)線程只能在本地變量上自旋，
 * 它會(huì)不斷輪詢前驅(qū)的狀態(tài)，如果發(fā)現(xiàn)前驅(qū)釋放了鎖就結(jié)束自旋。
 *
 *
 * @Author zhoumm
 * @Version V1.0.0
 * @Since 1.0
 * @Date 2020-05-29
 */
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)前線程保存起來(lái)
        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)鎖被其他線程占用，通過(guò)不斷輪詢判斷前驅(qū)節(jié)點(diǎn)的鎖標(biāo)志位等待前驅(qū)節(jié)點(diǎn)釋放鎖
            while (preNode.isLocked){
            }
            preNode = null;
            LOCAL.set(node);
        }
        // 如果不存在前驅(qū)節(jié)點(diǎn)，表示該鎖沒(méi)有被其他線程占用，則當(dāng)前線程獲得鎖
    }
    public void unlock() {
        // 獲取當(dāng)前線程對(duì)應(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;
    }
}

/**
 * @Description
 * MCS Spinlock 是一種基于鏈表的可擴(kuò)展、高性能、公平的自旋鎖，申請(qǐng)線程只在本地變量上自旋，
 * 直接前驅(qū)負(fù)責(zé)通知其結(jié)束自旋，從而極大地減少了不必要的處理器緩存同步的次數(shù)，降低了總線和內(nèi)存的開(kāi)銷。
 *
 * 總結(jié)：
 * 1.都是基于鏈表，不同的是CLHLock是基于隱式鏈表，沒(méi)有真正的后續(xù)節(jié)點(diǎn)屬性，MCSLock是顯示鏈表，有一個(gè)指向后續(xù)節(jié)點(diǎn)的屬性。
 * 2.將獲取鎖的線程狀態(tài)借助節(jié)點(diǎn)(node)保存,每個(gè)線程都有一份獨(dú)立的節(jié)點(diǎn)，這樣就解決了TicketLock多處理器緩存同步的問(wèn)題。
 * @Author zhoumm
 * @Version V1.0.0
 * @Since 1.0
 * @Date 2020-05-29
 */
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表示沒(méi)有正在等待獲取鎖的線程
        if (currentNode.next == null) {
            // 更新?tīng)顟B(tài)并設(shè)置queue為null
            if (UPDATE.compareAndSet(this, currentNode, null)) {
                // 如果成功了，表示queue==currentNode,即當(dāng)前節(jié)點(diǎn)后面沒(méi)有節(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í)將等待線程對(duì)應(yīng)的節(jié)點(diǎn)鎖狀態(tài)更新為false，同時(shí)將當(dāng)前線程的后繼節(jié)點(diǎn)設(shè)為null
            currentNode.next.isLocked = false;
            currentNode.next = null;
        }
    }
}