package test;
    import java.util.concurrent.locks.ReentrantLock;
    public class TestReenTrantLock {
        public static void main(String[] args) throws InterruptedException {
            ReentrantLock lock = new ReentrantLock();
            new Thread(() -> {
                System.out.println("1 start");
                lock.lock();
                System.out.println("1 entry");
                try {
                    Thread.sleep(1000 * 60 * 10);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                } finally {
                    lock.unlock();
                }
            },"t1").start();
            Thread.sleep(2000 );
            new Thread(() -> {
                System.out.println("2 start");
                lock.lock();
                System.out.println("2 entry");
                try {
                } finally {
                    lock.unlock();
                }
            },"t2").start();
        }
    }

public void lock() {
    sync.lock();
}

final void lock() {
    //首先用線程1使用 cas 嘗試將 state 從 0 改為 1,如果成功表示獲得了鎖
    //因為線程1獲取到了鎖state現(xiàn)在等于1,所以此時線程2獲取鎖失敗。 
    //線程2執(zhí)行acquire(1);
    //非公平的體現(xiàn):上來就加鎖
    if (compareAndSetState(0, 1))
        setExclusiveOwnerThread(Thread.currentThread());
    else
        acquire(1);
}

//arg = 1
public final void acquire(int arg) {
    //線程2執(zhí)行tryAcquire(arg),返回false代表鎖獲取失敗,!tryAcquire(arg) ==true
    //由于是&&判斷
    //所以線程2調(diào)用addWaiter做尾部入隊操作
    //線程2接著調(diào)用acquireQueued進入park阻塞
    if (!tryAcquire(arg) &&
        //addWaiter(Node.EXCLUSIVE) 返回的是 線程2的所在的Node節(jié)點
        acquireQueued(addWaiter(Node.EXCLUSIVE), arg)){
        //acquireQueued方法返回的是打斷標志 如果阻塞狀態(tài)或者運行狀態(tài)被打斷
        //返回true 那么會執(zhí)行selfInterrupt自我打斷 
        //selfInterrupt方法只有1句代碼:Thread.currentThread().interrupt();
        selfInterrupt();
    }
}

//acquires=1
protected final boolean tryAcquire(int acquires) {
    return nonfairTryAcquire(acquires);
}

//此時 線程2累計嘗試2次加鎖
final boolean nonfairTryAcquire(int acquires) {
    //acquires=1
    final Thread current = Thread.currentThread();
    int c = getState();
    //如果線程1已經(jīng)釋放鎖 此時c==0滿足 會再次使用cas嘗試加鎖
    //這里線程1仍然持有鎖 條件不滿足
    if (c == 0) {
        // 嘗試用 cas 獲得, 這里體現(xiàn)了非公平性: 不去檢查 AQS 隊列
        // 非公平鎖可以提高并發(fā)度，但是會導(dǎo)致饑餓,可以使用超時時間解決饑餓
        // 線程切換的開銷,其實就是非公平鎖效率高于公平鎖的原因
        // 因為非公平鎖減少了線程掛起的幾率,后來的線程有一定幾率節(jié)省被掛起的開銷
        if (compareAndSetState(0, acquires)) {
            setExclusiveOwnerThread(current);
            //代表加鎖成功
            return true;
        }
    }
    // 判斷是否鎖重入
    else if (current == getExclusiveOwnerThread()) {
        //使用原來的state + acquires,這里acquires = 1
        int nextc = c + acquires;
        if (nextc < 0) // overflow
            throw new Error("Maximum lock count exceeded");
        setState(nextc);
        return true;
    }
    //返回false代表線程2獲取鎖失敗
    return false;
}

static final Node EXCLUSIVE = null;

acquireQueued(addWaiter(Node.EXCLUSIVE), arg))

//node是Node.EXCLUSIVE 默認是null
//enq方法創(chuàng)建的隊列如下:頭結(jié)點->尾結(jié)點(線程2所在節(jié)點)
//后續(xù)的節(jié)點都在addWaiter方法中入隊,不再進入enq:頭結(jié)點->尾結(jié)點(線程2所在節(jié)點)->尾結(jié)點(線程3所在節(jié)點)
private Node addWaiter(Node mode) {
    //static final Node EXCLUSIVE = null;
    //node為持有當前線程的node
    //mode為null 可以看到賦值給了 nextWaiter
    //也就是線程2所在節(jié)點的next指針指向了null
    //注意:nextWaiter是等待隊列中的指針
    /***
        Node(Thread thread, Node mode) {      
            this.nextWaiter = mode;
            this.thread = thread;
        }
        ***/
    Node node = new Node(Thread.currentThread(), mode);
    //獲取同步隊列的尾部節(jié)點
    Node pred = tail;
    //此時同步隊列的tail是null,因為到目前為止并沒有執(zhí)行過enq方法
    //如果tail不為null:使用cas嘗試將Node對象插入隊列尾部,作為新的尾結(jié)點
    if (pred != null) {
        //將當前node節(jié)點的前一個節(jié)點指向原tail節(jié)點 
        node.prev = pred;
        //將當前node節(jié)點作為新的尾節(jié)點
        if (compareAndSetTail(pred, node)) {
            //原來的尾節(jié)點作為當前節(jié)點的下一個節(jié)點
            pred.next = node;
            return node;
        }
    }
    //因為tail節(jié)點是null 嘗試將Node加入隊列
    enq(node);
    //返回線程2節(jié)點
    return node;
}

//下面解釋中的當前節(jié)點指的是Thread-2所在的節(jié)點
//enq相當于是初始化頭尾結(jié)點和第一個入隊的節(jié)點
//只有第1個入隊的節(jié)點才會進入該方法
//后續(xù)的線程都會直接執(zhí)行enq(node)之前的代碼加入尾節(jié)點
//enq方法構(gòu)造了1個雙向隊列:頭結(jié)點->尾結(jié)點(線程2所在節(jié)點)
private Node enq(final Node node) {
    for (;;) {
        Node t = tail;
        //第一次進入循環(huán) tail是尾節(jié)點為null
        if (t == null) { 
            //第一次進入循環(huán):設(shè)置頭結(jié)點為哨兵節(jié)點也叫啞結(jié)點:因為沒有對應(yīng)的線程與之關(guān)聯(lián)
            // head節(jié)點的屬性:thread=null
            if (compareAndSetHead(new Node()))
                //第一次進入循環(huán):將頭結(jié)點賦值給尾節(jié)點 此時頭和尾是同一個節(jié)點 這點很重要
                tail = head;
        } else {
            //第二次進入循環(huán):此處的t就是head,將當前節(jié)點的前置指針指向頭節(jié)點
            node.prev = t;
            //第二次進入循環(huán):使用cas將尾節(jié)點設(shè)置為當前節(jié)點
            //第二次進入循環(huán):此時頭結(jié)點是哨兵節(jié)點(啞結(jié)點),尾節(jié)點即Thread-2所在的線程的節(jié)點
            if (compareAndSetTail(t, node)) {
                //第二次進入循環(huán):將head.next指向當前節(jié)點那么這個鏈表是雙向鏈表
                t.next = node;
                //循環(huán)結(jié)束
                return t;
            }
        }
    }
}

//node是 線程2的節(jié)點
//arg = 1
//node.predecessor():獲取當前節(jié)點的上一個節(jié)點 
//node.predecessor()和node.prev不同的是:
//node.prev如果是null不會拋出異常
//node.predecessor()中如果 node.prev是 null 會拋出異常
//acquireQueued方法返回的是打斷狀態(tài)
final boolean acquireQueued(final Node node, int arg) {
    //node即Thread-2所在的線程的節(jié)點
    boolean failed = true;
    try {
        boolean interrupted = false;
        //死循環(huán)開始
        for (;;) {
            //p是Thread-2所在的線程的節(jié)點的前置節(jié)點即頭結(jié)點
            final Node p = node.predecessor();
            //p == head 即Thread-2所在的線程的節(jié)點的前置節(jié)點是頭結(jié)點
            //tryAcquire(arg) 使用cas再次嘗試獲取鎖 獲取鎖失敗 代碼不進入if向下執(zhí)行
            //此時累計嘗試3次
            if (p == head && tryAcquire(arg)) {
                //如果獲取鎖成功將當前節(jié)點設(shè)置為頭結(jié)點并將當前節(jié)點的thread屬性和prev屬性設(shè)置為null 
                //也就是當前節(jié)點的prev和原來的頭節(jié)點斷開
                //因為當前節(jié)點獲取鎖成功,意味著線程1已經(jīng)釋放鎖,此時需要和代表線程1的原來的頭結(jié)點斷開。
                setHead(node);
                //將原來的頭節(jié)點斷開和當前節(jié)點的連接 相當于原來的節(jié)點出隊
                p.next = null; // help GC
                failed = false;
                //注意這是在死循環(huán)里
                //如果interrupted返回的是true 將會執(zhí)行 selfInterrupt(); 自我中斷
                // if (!tryAcquire(arg) &&acquireQueued(addWaiter(Node.EXCLUSIVE), arg)){selfInterrupt();}
                //即:獲取鎖阻塞的過程中被打斷,也要重新進入死循環(huán)一直等到獲取鎖才能執(zhí)行打斷,這就是不可打斷。
                //可打斷是指在等待鎖的過程中，其它線程可以用interrupt方法終止等待,synchronized鎖是不可打斷的。
                //我們要想在等鎖的過程中被打斷,就要使用lockInterruptibly()方法對lock對象加鎖，而不是lock()方法。
                return interrupted;
            }
            //第一次進入shouldParkAfterFailedAcquire 
            //將當前節(jié)點的前置節(jié)點即頭結(jié)點改為-1 返回false （累計嘗試4次）
            //如果當前節(jié)點的前置節(jié)點以及更前面的節(jié)點有取消的節(jié)點 
            //要斷開這些節(jié)點 包括當前節(jié)點的前置節(jié)點
            //第二次進入shouldParkAfterFailedAcquire 
            //如果當前節(jié)點的前置節(jié)點是-1 返回true
            //shouldParkAfterFailedAcquire 返回true時
            //會進入parkAndCheckInterrupt()方法中,然后會park當前線程
            //Thread-2所在node被阻塞,然后等待喚醒,此時node的waitStatus=0
            if (shouldParkAfterFailedAcquire(p, node) &&
                parkAndCheckInterrupt()){
                //在不可打斷模式中
                //線程park在parkAndCheckInterrupt方法里
                //如果線程被打斷,parkAndCheckInterrupt方法返回true
                //執(zhí)行以下代碼
                //Interrupted = true 
                //Interrupted = true 代表被阻塞期間打斷過
                //然后繼續(xù)進入死循環(huán)直到獲取鎖 
                //獲取鎖后返回Interrupted = true 
                //最后返回到acquire方法
                //進入selfInterrupt();執(zhí)行Thread.currentThread().interrupt();
                //在可打斷模式中
                //線程park在parkAndCheckInterrupt方法里
                //如果線程被打斷,parkAndCheckInterrupt方法返回true
                //執(zhí)行以下代碼
                //throw new InterruptedException();
                interrupted = true;
            }
        }//死循環(huán)結(jié)束
    } finally {
       /**
        這里的failed 什么時候變成true的?
        默認的failed=true
        在死循環(huán)一直都是true！?。∫驗橐恢睕]有獲取鎖成功?。?
        除非是獲取到了鎖才被賦值為false
         1.try代碼塊拋出異常
        ***/
        if (failed)
            cancelAcquire(node);
    }
}

//node是當前節(jié)點
private void setHead(Node node) {
    head = node;
    node.thread = null;
    node.prev = null;
}

//p是Thread-2所在節(jié)點的前置節(jié)點即頭結(jié)點 
//node是 Thread-2所在節(jié)點
private static boolean shouldParkAfterFailedAcquire(Node pred, Node node) {
    //p是Thread-2所在節(jié)點的前置節(jié)點即頭結(jié)點 
    //頭結(jié)點的waitStatus=0 
    int ws = pred.waitStatus;
    //第一次進入 ws=0 修改waitStatus為-1
    //第二次進入ws=-1 Node.SIGNAL=-1 代表等待喚醒  返回true
    if (ws == Node.SIGNAL){
        // 上一個節(jié)點=-1 都在阻塞, 那么自己也阻塞好了
        //返回true代表要park
        return true;
    }
    //如果當前節(jié)點的前置節(jié)點的waitStatus>0 
    //說明當前節(jié)點D的前置節(jié)點C被取消,那么要把當前節(jié)點D的前置節(jié)點重新設(shè)置為[當前節(jié)點的前置節(jié)點C的前置節(jié)點B]
    //B<---C<---D
    //假如B節(jié)點被取消,此時需要斷開C那么直接將D指向B即可
    //A<---B<---C<---D
    //假如BC節(jié)點被取消,此時需要斷開BC那么直接將D指向A即可
    if (ws > 0) {
        do {
            //首先做 do
            //獲取當前節(jié)點的前置節(jié)點的前置節(jié)點pred.prev
            //因為當前節(jié)點的前置節(jié)點pred的status大于0 說明當前節(jié)點是被取消的 需要斷開
            //繼續(xù)往前找當前節(jié)點的前置節(jié)點的前置節(jié)點pred.prev
            //如果當前節(jié)點的前置節(jié)點的前置節(jié)點pred.prev的status還是大于0 說明也是被取消的
            //那么繼續(xù)往前找
            //一直到將當前節(jié)點的前置節(jié)點以及當前節(jié)點的前置節(jié)點之前被取消的節(jié)點都斷開
            //看看代碼是怎么做的
            //獲取當前節(jié)點的前置節(jié)點的前置節(jié)點作為當前節(jié)點的前置節(jié)點 
            pred = pred.prev;
            //然后將當前節(jié)點的前置指針指向當前節(jié)點的前置節(jié)點的前置節(jié)點
            node.prev = pred;
        } while (pred.waitStatus > 0);
        //斷開的是當前節(jié)點的前置節(jié)點 以及 當前節(jié)點的前置節(jié)點之前被取消的節(jié)點
        //從后往前斷開的
        pred.next = node;
    } else {
        //將當前節(jié)點的前置節(jié)點即頭結(jié)點改為-1
        compareAndSetWaitStatus(pred, ws, Node.SIGNAL);
    }
    //第一次進入返回false 因為是死循環(huán) 等第二次進入的時候
    // 符合 ws == Node.SIGNAL 會返回true
    return false;
}

//代碼塊10
private final boolean parkAndCheckInterrupt() {
    //此處park
    LockSupport.park(this);
    //當前線程被unpark喚醒時,當前方法返回true或者false都要重新進入死循環(huán)然后陷入阻塞,一直等獲取到鎖才能被打斷
    //不同的是
    //parkAndCheckInterrupt:返回true
    //會執(zhí)行interrupted = true; 
    //再次進入死循環(huán),再次執(zhí)行shouldParkAfterFailedAcquire(p, node) && parkAndCheckInterrupt()然后阻塞        
    //parkAndCheckInterrupt:返回false
    //會直接進入死循環(huán)再次執(zhí)行shouldParkAfterFailedAcquire(p, node)&&parkAndCheckInterrupt()然后阻塞   
    //這里為什么要調(diào)用interrupted() 而不是isInterrupted() ?
    //interrupted會重置打斷標記為false 而isInterrupted只是返回打斷標記
    //當park的線程在被調(diào)用interrupt方法時，會把中斷狀態(tài)設(shè)置為true。
    //然后park方法會去判斷中斷狀態(tài)，如果為true，就直接返回，然后往下繼續(xù)執(zhí)行,如果為false繼續(xù)阻塞
    return Thread.interrupted();
}

final boolean acquireQueued(final Node node, int arg) {
    boolean failed = true;
    try {
        //省略代碼
    }finally {
       /**
        這里的failed 什么時候變成true的?
        默認的failed=true
        在死循環(huán)一直都是true！??！因為一直沒有獲取鎖成功！！
        除非是獲取到了鎖才被賦值為false
         1.try代碼塊拋出異常
        ***/
        if (failed)
            cancelAcquire(node);
    }

private void cancelAcquire(Node node) {
        // Ignore if node doesn't exist
        if (node == null)
            return;
        node.thread = null;
        Node pred = node.prev;
        while (pred.waitStatus > 0)
            node.prev = pred = pred.prev;
        Node predNext = pred.next;
        node.waitStatus = Node.CANCELLED;
        if (node == tail && compareAndSetTail(node, pred)) {
            compareAndSetNext(pred, predNext, null);
        } else {
            int ws;
            if (pred != head &&
                ((ws = pred.waitStatus) == Node.SIGNAL ||
                 (ws <= 0 && compareAndSetWaitStatus(pred, ws, Node.SIGNAL))) &&
                pred.thread != null) {
                Node next = node.next;
                if (next != null && next.waitStatus <= 0)
                    compareAndSetNext(pred, predNext, next);
            } else {
                unparkSuccessor(node);
            }
            node.next = node; // help GC
        }
    }

//示例代碼1
public static void main(String[] args) {
        Thread thread = new Thread(() -> {
            try {
               while(true){
                System.out.println("start");
                LockSupport.park();
                System.out.println("park");
               }
            } finally {
                System.out.println("end");
            }
        }, "t2");
        thread.start();
        try {
            Thread.sleep(5000);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    	//此處可以用 thread.stop(); 不推薦
        thread.interrupt();
    }

//示例代碼2 
static volatile Boolean flag = false;
    public static void main(String[] args) {
        Thread thread = new Thread(() -> {
            try {
                while(true){
                    System.out.println("start");
                    LockSupport.park();
                    System.out.println("park");
                    if (flag){
                        Thread.interrupted();
                    }
                }
            } finally {
                System.out.println("end");
            }
        }, "t2");
        thread.start();
        try {
            Thread.sleep(100);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
        //此處可以用 thread.stop(); 不推薦
        thread.interrupt();
        try {
            Thread.sleep(100);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
        flag=true;
    }

//示例代碼3 
static volatile Boolean flag = false;
    public static void main(String[] args) {
        Thread thread = new Thread(() -> {
            try {
                while(true){
                    System.out.println("start");
                    LockSupport.park();
                    System.out.println("park");
                    if (flag){
                        throw new RuntimeException();
                    }
                }
            } finally {
                System.out.println("end");
            }
        }, "t2");
        thread.start();
        try {
            Thread.sleep(100);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
        //此處可以用 thread.stop(); 不推薦
        thread.interrupt();
        try {
            Thread.sleep(100);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
        flag=true;
    }

// 解鎖實現(xiàn)
public void unlock() {
	sync.release(1);
}

// AQS 繼承過來的方法, 方便閱讀, 放在此處
public final boolean release(int arg) {
    // 如果所有的鎖釋放成功即state=0
    if (tryRelease(arg)) {
        // 隊列頭節(jié)點 
        Node h = head;
        // 頭結(jié)點不為null 且 waitStatus不等于0 才需要喚醒頭結(jié)點的后置節(jié)點
        // h != null 說明有等待隊列
        // h.waitStatus != 0 說明頭結(jié)點后面有節(jié)點在等待鎖
        // 假設(shè)頭結(jié)點的下一個節(jié)點還沒來得及修改h.waitStatus= -1 會有問題嗎？
        // 不會 因為如果h.waitStatus=0,此時頭結(jié)點的下一個節(jié)點還會再嘗試一次獲取鎖 
        // 因為鎖在這里已經(jīng)被釋放 所以頭結(jié)點的下一個節(jié)點必定能獲取到鎖
        if (h != null && h.waitStatus != 0) {
            // h是隊列頭節(jié)點 
            // unpark AQS 中等待的線程, 進入 ㈡
            unparkSuccessor(h);
        }
        return true;
    }
    return false;
}

// ㈠ Sync 繼承過來的方法, 方便閱讀, 放在此處
protected final boolean tryRelease(int releases) {
    // state--
    int c = getState() - releases;
    if (Thread.currentThread() != getExclusiveOwnerThread())
        throw new IllegalMonitorStateException();
    boolean free = false;
    // 支持鎖重入,  state 減為 0, 表明所有的鎖都釋放成功
    if (c == 0) {
        free = true;
        setExclusiveOwnerThread(null);
    }
    //設(shè)置state為c,c不一定等于0 
    setState(c);
    //返回鎖標志位
    return free;
}

// ㈡ AQS 繼承過來的方法, 方便閱讀, 放在此處
//node是頭結(jié)點
private void unparkSuccessor(Node node) {
    // 此處的node節(jié)點為頭結(jié)點
    // 如果頭節(jié)點的狀態(tài)小于0 嘗試重置頭節(jié)點的狀態(tài)為0
 	//改為0的意義在于:在下面的代碼中：頭結(jié)點的下一個節(jié)點被喚醒時會再次嘗試加鎖
    //在shouldParkAfterFailedAcquire 方法中有1個判斷
    //if (ws == Node.SIGNAL) { return true; }
    //返回true代表獲取鎖失敗進入parkAndCheckInterrupt方法阻塞
    //這里改為0以后 那么頭結(jié)點的下一個節(jié)點會在被unpark的時候再一次嘗試加鎖
    //如果不改為0 那么頭結(jié)點的下一個節(jié)點會直接進入死循環(huán)被park 陷入了死循環(huán)無解了。
    int ws = node.waitStatus;
    if (ws < 0) {
        //配合喚醒線程 再一次嘗試加鎖
        //配合喚醒線程 再一次嘗試加鎖
        //配合喚醒線程 再一次嘗試加鎖
        compareAndSetWaitStatus(node, ws, 0);
    }
    //獲取頭結(jié)點的下一個節(jié)點
    Node s = node.next;
    //node是頭節(jié)點
    //如果頭結(jié)點的后置節(jié)點為空或被取消
    //那么從隊列的末尾從后往前找,找到最前面一個需要unpark的節(jié)點
    //如果頭結(jié)點的后置節(jié)點不為空且沒被取消
    //那么就喚醒頭節(jié)點的下一個節(jié)點
    //這里也是非公平的體現(xiàn)
    if (s == null || s.waitStatus > 0) {
        s = null;
        //循環(huán)遍歷從 AQS 隊列從隊列的末尾從后往前找,找到最前面一個需要unpark的節(jié)點
        //注意這里做了判斷t不等于null且t不等于頭結(jié)點且t.waitStatus <= 0
        //也就是找到的節(jié)點必定是有效的
        for (Node t = tail; t != null && t != node; t = t.prev)
            if (t.waitStatus <= 0){
                s = t;
            }
    }
    //喚醒頭結(jié)點的下一個節(jié)點 或者 從后往前找到的第1個t.waitStatus<= 0的節(jié)點
    if (s != null)
        //喚醒線程 配合 compareAndSetWaitStatus(node, ws, 0); 再一次嘗試加鎖
        //喚醒線程 配合 compareAndSetWaitStatus(node, ws, 0); 再一次嘗試加鎖
        //喚醒線程 配合 compareAndSetWaitStatus(node, ws, 0); 再一次嘗試加鎖
        LockSupport.unpark(s.thread);
}
}

    static final class NonfairSync extends Sync {
		// Sync 繼承過來的方法, 方便閱讀, 放在此處
        final boolean nonfairTryAcquire(int acquires) {
            final Thread current = Thread.currentThread();
            int c = getState();
            if (c == 0) {
                if (compareAndSetState(0, acquires)) {
                    setExclusiveOwnerThread(current);
                    return true;
                }
            }
			// 如果已經(jīng)獲得了鎖, 線程還是當前線程, 表示發(fā)生了鎖重入
            else if (current == getExclusiveOwnerThread()) {
			// state++
                int nextc = c + acquires;
                if (nextc < 0) // overflow
                    throw new Error("Maximum lock count exceeded");
                setState(nextc);
                return true;
            }
            return false;
        }
        // Sync 繼承過來的方法, 方便閱讀, 放在此處
        protected final boolean tryRelease(int releases) {
		// state--
            int c = getState() - releases;
            if (Thread.currentThread() != getExclusiveOwnerThread())
                throw new IllegalMonitorStateException();
            boolean free = false;
		// 支持鎖重入, 只有 state 減為 0, 才釋放成功
            if (c == 0) {
                free = true;
                setExclusiveOwnerThread(null);
            }
            setState(c);
            return free;
        }
    }