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

/**
 * @Description
 * TicketLock 是基于隊列的，那么 CLHLock 就是基于鏈表設(shè)計的
 *
 * CLH 是一種基于鏈表的可擴展，高性能，公平的自旋鎖，申請線程只能在本地變量上自旋，
 * 它會不斷輪詢前驅(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é)點
    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é)點并將節(jié)點與當(dāng)前線程保存起來
        CLHNode node = new CLHNode();
        LOCAL.set(node);
        // 將新建的節(jié)點設(shè)置為尾部節(jié)點，并返回舊的節(jié)點（原子操作），這里舊的節(jié)點實際上就是當(dāng)前節(jié)點的前驅(qū)節(jié)點
        CLHNode preNode = UPDATER.getAndSet(this,node);
        if(preNode != null){
            // 前驅(qū)節(jié)點不為null表示當(dāng)鎖被其他線程占用，通過不斷輪詢判斷前驅(qū)節(jié)點的鎖標(biāo)志位等待前驅(qū)節(jié)點釋放鎖
            while (preNode.isLocked){
            }
            preNode = null;
            LOCAL.set(node);
        }
        // 如果不存在前驅(qū)節(jié)點，表示該鎖沒有被其他線程占用，則當(dāng)前線程獲得鎖
    }
    public void unlock() {
        // 獲取當(dāng)前線程對應(yīng)的節(jié)點
        CLHNode node = LOCAL.get();
        // 如果tail節(jié)點等于node，則將tail節(jié)點更新為null，同時將node的lock狀態(tài)職位false，表示當(dāng)前線程釋放了鎖
        if (!UPDATER.compareAndSet(this, node, null)) {
            node.isLocked = false;
        }
        node = null;
    }
}

/**
 * @Description
 * MCS Spinlock 是一種基于鏈表的可擴展、高性能、公平的自旋鎖，申請線程只在本地變量上自旋，
 * 直接前驅(qū)負責(zé)通知其結(jié)束自旋，從而極大地減少了不必要的處理器緩存同步的次數(shù)，降低了總線和內(nèi)存的開銷。
 *
 * 總結(jié)：
 * 1.都是基于鏈表，不同的是CLHLock是基于隱式鏈表，沒有真正的后續(xù)節(jié)點屬性，MCSLock是顯示鏈表，有一個指向后續(xù)節(jié)點的屬性。
 * 2.將獲取鎖的線程狀態(tài)借助節(jié)點(node)保存,每個線程都有一份獨立的節(jié)點，這樣就解決了TicketLock多處理器緩存同步的問題。
 * @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<>();
    // 隊列
    @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é)點并保存到ThreadLocal中
        MCSNode currentNode = new MCSNode();
        NODE.set(currentNode);
        // 將queue設(shè)置為當(dāng)前節(jié)點，并且返回之前的節(jié)點
        MCSNode preNode = UPDATE.getAndSet(this, currentNode);
        if (preNode != null) {
            // 如果之前節(jié)點不為null，表示鎖已經(jīng)被其他線程持有
            preNode.next = currentNode;
            // 循環(huán)判斷，直到當(dāng)前節(jié)點的鎖標(biāo)志位為false
            while (currentNode.isLocked) {
            }
        }
    }
    public void unlock() {
        MCSNode currentNode = NODE.get();
        // next為null表示沒有正在等待獲取鎖的線程
        if (currentNode.next == null) {
            // 更新狀態(tài)并設(shè)置queue為null
            if (UPDATE.compareAndSet(this, currentNode, null)) {
                // 如果成功了，表示queue==currentNode,即當(dāng)前節(jié)點后面沒有節(jié)點了
                return;
            } else {
                // 如果不成功，表示queue!=currentNode,即當(dāng)前節(jié)點后面多了一個節(jié)點，表示有線程在等待
                // 如果當(dāng)前節(jié)點的后續(xù)節(jié)點為null，則需要等待其不為null（參考加鎖方法）
                while (currentNode.next == null) {
                }
            }
        } else {
            // 如果不為null，表示有線程在等待獲取鎖，此時將等待線程對應(yīng)的節(jié)點鎖狀態(tài)更新為false，同時將當(dāng)前線程的后繼節(jié)點設(shè)為null
            currentNode.next.isLocked = false;
            currentNode.next = null;
        }
    }
}