0%

## Leetcode 121 买卖股票的最佳时机(Best Time to Buy and Sell Stock) 题解分析

Posted on 2021-03-14 In Java , leetcode , DP , java , DP Views: Disqus:

### 题目介绍

You are given an array `prices` where `prices[i]` is the price of a given stock on the ith day.

You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.

Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return `0`.

给定一个数组 `prices` ，它的第 `i` 个元素 `prices[i]` 表示一支给定股票第 `i` 天的价格。

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 `0` 。

### 简单分析

其实这个跟二叉树的最长路径和有点类似，需要找到整体的最大收益，但是在迭代过程中需要一个当前的值

    int maxSofar = 0;
    public int maxProfit(int[] prices) {
        if (prices.length <= 1) {
            return 0;
        }
        int maxIn = prices[0];
        int maxOut = prices[0];
        for (int i = 1; i < prices.length; i++) {
            if (maxIn > prices[i]) {
                // 当循环当前值小于之前的买入值时就当成买入值，同时卖出也要更新
                maxIn = prices[i];
                maxOut = prices[i];
            }
            if (prices[i] > maxOut) {
                // 表示一个可卖出点，即比买入值高时
                maxOut = prices[i];
                // 需要设置一个历史值
                maxSofar = Math.max(maxSofar, maxOut - maxIn);
            }
        }
        return maxSofar;
    }

### 总结下

一开始看到 easy 就觉得是很简单，就没有 maxSofar ，但是一提交就出现问题了
对于`[2, 4, 1]`这种就会变成 0，所以还是需要一个历史值来存放历史最大值，这题有点动态规划的意思

## 《垃圾回收算法手册读书》笔记之整理算法

Posted on 2021-03-07 In Java , gc , jvm Views: Disqus:

最近看了下这本垃圾回收算法手册，看到了第三章的标记-整理回收算法，做个简单的读书笔记

### 双指针整理算法

对于一块待整理区域，通过两个指针，free 在区域的起始端，scan 指针在区域的末端，free 指针从前往后知道找到空闲区域，scan 从后往前一直找到存活对象，当 free 指针未与 scan 指针交叉时，会给 scan 位置的对象特定位置标记上 free 的地址，即将要转移的地址，不过这里有个限制，这种整理算法一般会用于对象大小统一的情况，否则 free 指针扫描时还需要匹配scan 指针扫描到的存活对象的大小。

### Lisp 2 整理算法

需要三次完整遍历堆区域
第一遍是遍历后将计算出所有对象的最终地址（转发地址）
第二遍是使用转发地址更新赋值器线程根以及被标记对象中的引用，该操作将确保它们指向对象的新位置
第三次遍历是relocate最终将存活对象移动到其新的目标位置

### 引线整理算法

这个真的长见识了，
可以看到，原来是 A，B，C 对象引用了 N，这里会在第一次遍历的时候把这种引用反过来，让 N 的对象头部保存下 A 的地址，表示这类引用，然后在遍历到 B 的时候在链起来，到最后就会把所有引用了 N 对象的所有对象通过引线链起来，在第二次遍历的时候就把更新A，B，C 对象引用的 N 地址，并且移动 N 对象

### 单次遍历算法

这个一直提到过位图的实现方式，
可以看到在第一步会先通过位图标记，标记的方式是位图的每一位对应的堆内存的一个字（这里可能指的是 byte 吧），然后将一个存活对象的内存区域的第一个字跟最后一个字标记，这里如果在通过普通的方式就还需要一个地方在存转发地址，但是因为具体的位置可以通过位图算出来，也就不需要额外记录了

## 闲聊下乘公交的用户体验

Posted on 2021-02-28 In 生活 , 公交 Views: Disqus:

新年开工开车来杭州，因为没有车位加限行今天来就没开车来了，从东站做公交回住的地方，这班神奇的车我之前也吐槽过了，有神奇的乘客和神奇的司机，因为基本上这班车是从我毕业就开始乘了，所以也算是比较熟悉了，以前总体感觉不太好的是乘坐时间太长了，不过这个也不能怪车，是我自己住得远（离东站），后来住到了现在的地方，也算是直达，并且 LD 比较喜欢直达的，不爱更快却要换乘的地铁，所以坐的频率比较高，也说过前面那些比较气人的乘客，自己不好好戴口罩，反而联合一起上车的乘客诽谤司机，说他要吃人了要打人了，也正是这个司机比较有意思，上车就让戴好口罩，还给大家讲，哪里哪里又有疫情了，我觉得其实这个司机还是不错的，特殊时期，对于这种公共交通，这样的确是比较负责任的做法，只是说话方式，语气这个因人而异，他也不是来伺候人的，而且这么一大车人，说了一遍不行，再说一遍，三遍以上了，嗓门大一点也属于正常的人的行为。
还是说回今天要说的，今天这位司机我看着跟前面说的那位有点像，因为上车的时候比较暗没看清脸，主要原因是这位司机开车比较猛，比较急，然后车上因为这个时间点，比较多大学开学来的学生，拎着个行李箱，一开始是前面已经都站满了人，后面还有很多空位，因为后面没地方放行李箱，就因为这样前面站着的有几个就在说司机开慢点，结果司机貌似也没听进去，还是我行我素，过了会又有人说司机开稳一点，就在这个人说完没一会，停在红绿灯路口的车里，就有人问有没有垃圾桶，接着又让司机开门，说晕车太严重了，要下车，司机开了门，我望出去两个妹子下了车，好像在路边草丛吐了，前面开门下车的时候就有人说她们第一次来杭州，可能有点责怪司机开的不稳，也影响了杭州交通给新来杭州的人的感受，说完了事情经过，其实我有蛮多感触，对于杭州公交司机，我大概是大一来了没多久，陪室友去文三路买电脑就晕车，下车的时候在公交车站吐了，可能是从大学开始缺乏锻炼，又饮食不规律，更加容易晕车，大部分晕车我觉得都是我自己的原因，有时候是上车前吃太多了，或者早上起太早，没睡好，没吃东西，反正自己也是挺多原因的，说到司机的原因的话，我觉得可能这班车还算好的，最让我难受的还是上下班高峰的时候，因为经过的那条路是比较重要的主干道，路比较老比较窄，并且还有很多人行道，所以经常一脚油门连带着一脚刹车，真的很难受，这种算是我觉得真的是公交体验比较差的一点，但是这一点呢也不能完全怪公交司机，杭州的路政规划是很垃圾，没看错，是垃圾，所以总体结论是公交还行，主要是路政规划就是垃圾，包括这条主干道这么多人行道，并且两边都是老小区，老年人在上班高峰可能要买菜送娃或者其他事情，在通畅的情况下可能只需要六分钟的路程，有时候因为各种原因，半小时都开不完，扯开去一点，杭州的路，核心的高速说封就封，本来是高架可以直接通到城西，结果没造，到了路本已经很拥挤的时候开始来造隧道，各种破坏，隧道接高架的地方，无尽的加塞，对于我这样的小白司机来说真的是太恶心了，所以我一直想说的就是杭州这个地方房价领先基础设施十年，地铁，高架，高速通通不行，地面道路就更不行了。
总结下，其实杭州的真正的公交体验差，应该还是路造成的，对于前面的那两位妹子来说，有可能是她们来自于公交司机都是开的特别稳，并且路况也很好的地方，也或者是我被虐习惯了🤦‍♂️

## AQS篇二 之 Condition 浅析笔记

Posted on 2021-02-21 In Java , 并发 Views: Disqus:

Condition也是 AQS 中很重要的一块内容，可以先看段示例代码，这段代码应该来自于Doug Lea大大，可以在 javadoc 中的 condition 部分找到，其实大大原来写过基于 `synchronized` 实现的，后面我也贴下代码

    import java.util.concurrent.locks.Condition;
    import java.util.concurrent.locks.Lock;
    import java.util.concurrent.locks.ReentrantLock;

    class BoundedBuffer {
        final Lock lock = new ReentrantLock();
        // condition 依赖于 lock 来产生
        final Condition notFull = lock.newCondition();
        final Condition notEmpty = lock.newCondition();

        // 对象池子，put 跟 take 的就是这里的
        final Object[] items = new Object[100];
        int putptr, takeptr, count;

        // 生产
        public void put(Object x) throws InterruptedException {
            // 这里也说明了，需要先拥有锁
            lock.lock();
            try {
                while (count == items.length)
                    notFull.await();  // 队列已满，等待，直到 not full 才能继续生产
                items[putptr] = x;
                if (++putptr == items.length) putptr = 0;
                ++count;
                notEmpty.signal(); // 生产成功，队列已经 not empty 了，发个通知出去
            } finally {
                lock.unlock();
            }
        }

        // 消费
        public Object take() throws InterruptedException {
            lock.lock();
            try {
                while (count == 0)
                    notEmpty.await(); // 队列为空，等待，直到队列 not empty，才能继续消费
                Object x = items[takeptr];
                if (++takeptr == items.length) takeptr = 0;
                --count;
                notFull.signal(); // 被我消费掉一个，队列 not full 了，发个通知出去
                return x;
            } finally {
                lock.unlock();
            }
        }
    }

介绍下 Condition 的结构

    public class ConditionObject implements Condition, java.io.Serializable {
            private static final long serialVersionUID = 1173984872572414699L;
            /** First node of condition queue. */
            private transient Node firstWaiter;
            /** Last node of condition queue. */
            private transient Node lastWaiter;

主要的就这么点，而且也复用了 AQS 阻塞队列或者大大叫 `lock queue`中同样的 Node 节点，只不过它没有使用其中的双向队列，也就是prev 和 next，而是在 Node 中的 nextWaiter，所以只是个单向的队列，没使用 next 其实还有个用处，后面会提到，看下结构的示意图
然后主要是看两个方法，`await` 和 `signal`,
先来看下 await

    /**
     * Implements interruptible condition wait.
     * <ol>
     * <li> If current thread is interrupted, throw InterruptedException.
     * <li> Save lock state returned by {@link #getState}.
     * <li> Invoke {@link #release} with saved state as argument,
     *      throwing IllegalMonitorStateException if it fails.
     * <li> Block until signalled or interrupted.
     * <li> Reacquire by invoking specialized version of
     *      {@link #acquire} with saved state as argument.
     * <li> If interrupted while blocked in step 4, throw InterruptedException.
     * </ol>
     */
    public final void await() throws InterruptedException {
        if (Thread.interrupted())
            throw new InterruptedException();

        // 将当前节点包装成一个  condition waiter node 节点
        Node node = addConditionWaiter();

        // 完全释放占有的锁，这里需要是占有锁的线程
        int savedState = fullyRelease(node);
        int interruptMode = 0;

        // 判断下是否在阻塞队列中，因为有可能被其他节点从等待队列移动到阻塞队列
        while (!isOnSyncQueue(node)) {
            // park等待，等待被唤醒
            LockSupport.park(this);
            if ((interruptMode = checkInterruptWhileWaiting(node)) != 0)
                break;
        }

        // 被唤醒后进入阻塞队列，等待获取锁，这里继续用了fullyRelease返回的 state
        if (acquireQueued(node, savedState) && interruptMode != THROW_IE)
            interruptMode = REINTERRUPT;
        if (node.nextWaiter != null) // clean up if cancelled
            unlinkCancelledWaiters();
        if (interruptMode != 0)
            reportInterruptAfterWait(interruptMode);
    }

添加条件队列节点

    /**
     * Adds a new waiter to wait queue.
     * @return its new wait node
     */
    private Node addConditionWaiter() {
        Node t = lastWaiter;
        // If lastWaiter is cancelled, clean out.
        // 如果节点已经不是 CONDITION 状态了，表示已经取消了
        if (t != null && t.waitStatus != Node.CONDITION) {
            // 把等待队列中取消的节点清理出去
            unlinkCancelledWaiters();
            t = lastWaiter;
        }
        // 把当前线程包装成waitStatus=CONDITION 的节点
        Node node = new Node(Thread.currentThread(), Node.CONDITION);
        // 没有 lastWaiter 节点，直接是 firstWaiter
        if (t == null)
            firstWaiter = node;
        else
        // 不然就接在 lastWaiter 后面
            t.nextWaiter = node;
        // 当前节点就会变成新的 lastWaiter
        lastWaiter = node;
        return node;
    }

清理取消的节点

    /**
     * Unlinks cancelled waiter nodes from condition queue.
     * Called only while holding lock. This is called when
     * cancellation occurred during condition wait, and upon
     * insertion of a new waiter when lastWaiter is seen to have
     * been cancelled. This method is needed to avoid garbage
     * retention in the absence of signals. So even though it may
     * require a full traversal, it comes into play only when
     * timeouts or cancellations occur in the absence of
     * signals. It traverses all nodes rather than stopping at a
     * particular target to unlink all pointers to garbage nodes
     * without requiring many re-traversals during cancellation
     * storms.
     */
    private void unlinkCancelledWaiters() {
        Node t = firstWaiter;
        Node trail = null;
        // 循环遍历单向链表的节点，如果状态不是 CONDITION 就清出去
        while (t != null) {
            Node next = t.nextWaiter;
            // 循环链表操作，清掉取消的节点
            if (t.waitStatus != Node.CONDITION) {
                t.nextWaiter = null;
                if (trail == null)
                    firstWaiter = next;
                else
                    trail.nextWaiter = next;
                if (next == null)
                    lastWaiter = trail;
            }
            else
                trail = t;
            t = next;
        }
    }

完全释放锁

    /**
     * Invokes release with current state value; returns saved state.
     * Cancels node and throws exception on failure.
     * @param node the condition node for this wait
     * @return previous sync state
     */
    final int fullyRelease(Node node) {
        boolean failed = true;
        try {
            // 获取下当前的 state 值，因为是可重入的，所以这个值要保存下来
            int savedState = getState();
            // 这里还包含比较多操作，不过跟前面分析 AQS 的释放比较类似，不深入了
            if (release(savedState)) {
                failed = false;
                // 返回这个值
                return savedState;
            } else {
                throw new IllegalMonitorStateException();
            }
        } finally {
            if (failed)
                node.waitStatus = Node.CANCELLED;
        }
    }

判断是否在阻塞队列中

    /**
     * Returns true if a node, always one that was initially placed on
     * a condition queue, is now waiting to reacquire on sync queue.
     * @param node the node
     * @return true if is reacquiring
     */
    final boolean isOnSyncQueue(Node node) {
        // 如果waitStatus 是 CONDITION 或者没有 prev 前置节点肯定就不在
        if (node.waitStatus == Node.CONDITION || node.prev == null)
            return false;
        // 这里就是我前面提到的 next 的作用
        if (node.next != null) // If has successor, it must be on queue
            return true;
        // 从 tail 开始找，是否在阻塞队列中
        /*
         * node.prev can be non-null, but not yet on queue because
         * the CAS to place it on queue can fail. So we have to
         * traverse from tail to make sure it actually made it.  It
         * will always be near the tail in calls to this method, and
         * unless the CAS failed (which is unlikely), it will be
         * there, so we hardly ever traverse much.
         */
        return findNodeFromTail(node);
    }
    /**
     * Returns true if node is on sync queue by searching backwards from tail.
     * Called only when needed by isOnSyncQueue.
     * @return true if present
     */
    private boolean findNodeFromTail(Node node) {
        Node t = tail;
        // 从 tail 开始，从后往前找
        for (;;) {
            if (t == node)
                return true;
            if (t == null)
                return false;
            t = t.prev;
        }
    }

await 的逻辑差不多就是这样子，主要的就是把自己包成一个 Node 节点，waitStatus 的状态是 CONDITION，挂在等待队列的最后，然后完全释放锁，park 等待

## signal

    /**
     * Moves the longest-waiting thread, if one exists, from the
     * wait queue for this condition to the wait queue for the
     * owning lock.
     *
     * @throws IllegalMonitorStateException if {@link #isHeldExclusively}
     *         returns {@code false}
     */
    public final void signal() {
        if (!isHeldExclusively())
            throw new IllegalMonitorStateException();
        // firstWaiter 肯定是最早开始等待的
        Node first = firstWaiter;
        // 如果不为空就唤醒
        if (first != null)
            doSignal(first);
    }
    /**
     * Removes and transfers nodes until hit non-cancelled one or
     * null. Split out from signal in part to encourage compilers
     * to inline the case of no waiters.
     * @param first (non-null) the first node on condition queue
     */
    private void doSignal(Node first) {
        do {
            // 因为要去唤醒 first 节点了，firstWaiter 需要再从后面找一个
            // 并且判断是否为空，如果是空的话就直接可以把 lastWaiter 设置成空了
            if ( (firstWaiter = first.nextWaiter) == null)
                lastWaiter = null;
            //  first 不需要继续保存后面的 waiter 了，因为 firstWaiter 已经是 first 的后置节点了
            first.nextWaiter = null;
        // 如果 first 节点转移不成功，并且 firstWaiter 节点不为空，则继续进入循环
        } while (!transferForSignal(first) &&
                 (first = firstWaiter) != null);
    }
    /**
     * Transfers a node from a condition queue onto sync queue.
     * Returns true if successful.
     * @param node the node
     * @return true if successfully transferred (else the node was
     * cancelled before signal)
     */
    final boolean transferForSignal(Node node) {
        /*
         * If cannot change waitStatus, the node has been cancelled.
         */
        // 如果状态已经不是 CONDITION 就不会设置成功，返回 false
        if (!compareAndSetWaitStatus(node, Node.CONDITION, 0))
            return false;
        /*
         * Splice onto queue and try to set waitStatus of predecessor to
         * indicate that thread is (probably) waiting. If cancelled or
         * attempt to set waitStatus fails, wake up to resync (in which
         * case the waitStatus can be transiently and harmlessly wrong).
         */
        // 调用跟aqs 第一篇中一样的 enq 方法进入阻塞队列，返回入队后的前一节点
        Node p = enq(node);
        int ws = p.waitStatus;
        // 将前置节点状态设置成SIGNAL，表示后面有节点在等了
        if (ws > 0 || !compareAndSetWaitStatus(p, ws, Node.SIGNAL))
            LockSupport.unpark(node.thread);
        // 返回 true，上一个方法的循环就退出了
        return true;
    }

这里其实就是把 condition 等待队列的第一个未取消的节点入队到阻塞队列去争锁

## 附录

`synchronized` 版的 BoundedBuffer

    /*
      File: BoundedBuffer.java

      Originally written by Doug Lea and released into the public domain.
      This may be used for any purposes whatsoever without acknowledgment.
      Thanks for the assistance and support of Sun Microsystems Labs,
      and everyone contributing, testing, and using this code.

      History:
      Date       Who                What
      11Jun1998  dl               Create public version
      17Jul1998  dl               Simplified by eliminating wait counts
      25aug1998  dl               added peek
       5May1999  dl               replace % with conditional (slightly faster)
    */

    package EDU.oswego.cs.dl.util.concurrent;

    /**
     * Efficient array-based bounded buffer class.
     * Adapted from CPJ, chapter 8, which describes design.
     * <p>[<a href="http://gee.cs.oswego.edu/dl/classes/EDU/oswego/cs/dl/util/concurrent/intro.html"> Introduction to this package. </a>] <p>
     **/

    public class BoundedBuffer implements BoundedChannel {

      protected final Object[]  array_;      // the elements

      protected int takePtr_ = 0;            // circular indices
      protected int putPtr_ = 0;

      protected int usedSlots_ = 0;          // length
      protected int emptySlots_;             // capacity - length

      /**
       * Helper monitor to handle puts.
       **/
      protected final Object putMonitor_ = new Object();

      /**
       * Create a BoundedBuffer with the given capacity.
       * @exception IllegalArgumentException if capacity less or equal to zero
       **/
      public BoundedBuffer(int capacity) throws IllegalArgumentException {
        if (capacity <= 0) throw new IllegalArgumentException();
        array_ = new Object[capacity];
        emptySlots_ = capacity;
      }

      /**
       * Create a buffer with the current default capacity
       **/

      public BoundedBuffer() {
        this(DefaultChannelCapacity.get());
      }

      /**
       * Return the number of elements in the buffer.
       * This is only a snapshot value, that may change
       * immediately after returning.
       **/
      public synchronized int size() { return usedSlots_; }

      public int capacity() { return array_.length; }

      protected void incEmptySlots() {
        synchronized(putMonitor_) {
          ++emptySlots_;
          putMonitor_.notify();
        }
      }

      protected synchronized void incUsedSlots() {
        ++usedSlots_;
        notify();
      }

      protected final void insert(Object x) { // mechanics of put
        --emptySlots_;
        array_[putPtr_] = x;
        if (++putPtr_ >= array_.length) putPtr_ = 0;
      }

      protected final Object extract() { // mechanics of take
        --usedSlots_;
        Object old = array_[takePtr_];
        array_[takePtr_] = null;
        if (++takePtr_ >= array_.length) takePtr_ = 0;
        return old;
      }

      public Object peek() {
        synchronized(this) {
          if (usedSlots_ > 0)
            return array_[takePtr_];
          else
            return null;
        }
      }

      public void put(Object x) throws InterruptedException {
        if (x == null) throw new IllegalArgumentException();
        if (Thread.interrupted()) throw new InterruptedException();

        synchronized(putMonitor_) {
          while (emptySlots_ <= 0) {
    	try { putMonitor_.wait(); }
            catch (InterruptedException ex) {
              putMonitor_.notify();
              throw ex;
            }
          }
          insert(x);
        }
        incUsedSlots();
      }

      public boolean offer(Object x, long msecs) throws InterruptedException {
        if (x == null) throw new IllegalArgumentException();
        if (Thread.interrupted()) throw new InterruptedException();

        synchronized(putMonitor_) {
          long start = (msecs <= 0)? 0 : System.currentTimeMillis();
          long waitTime = msecs;
          while (emptySlots_ <= 0) {
            if (waitTime <= 0) return false;
    	try { putMonitor_.wait(waitTime); }
            catch (InterruptedException ex) {
              putMonitor_.notify();
              throw ex;
            }
            waitTime = msecs - (System.currentTimeMillis() - start);
          }
          insert(x);
        }
        incUsedSlots();
        return true;
      }

      public  Object take() throws InterruptedException {
        if (Thread.interrupted()) throw new InterruptedException();
        Object old = null;
        synchronized(this) {
          while (usedSlots_ <= 0) {
            try { wait(); }
            catch (InterruptedException ex) {
              notify();
              throw ex;
            }
          }
          old = extract();
        }
        incEmptySlots();
        return old;
      }

      public  Object poll(long msecs) throws InterruptedException {
        if (Thread.interrupted()) throw new InterruptedException();
        Object old = null;
        synchronized(this) {
          long start = (msecs <= 0)? 0 : System.currentTimeMillis();
          long waitTime = msecs;

          while (usedSlots_ <= 0) {
            if (waitTime <= 0) return null;
            try { wait(waitTime); }
            catch (InterruptedException ex) {
              notify();
              throw ex;
            }
            waitTime = msecs - (System.currentTimeMillis() - start);

          }
          old = extract();
        }
        incEmptySlots();
        return old;
      }

    }

## AQS篇一

Posted on 2021-02-14 In Java , 并发 Views: Disqus:

很多东西都是时看时新，而且时间长了也会忘，所以再来复习下，也会有一些新的角度看法这次来聊下AQS的内容，主要是这几个点，

## 第一个线程

第一个线程抢到锁了，此时state跟阻塞队列是怎么样的，其实这里是之前没理解对的地方

    /**
             * Fair version of tryAcquire.  Don't grant access unless
             * recursive call or no waiters or is first.
             */
            protected final boolean tryAcquire(int acquires) {
                final Thread current = Thread.currentThread();
                int c = getState();
                // 这里如果state还是0说明锁还空着
                if (c == 0) {
                    // 因为是公平锁版本的，先去看下是否阻塞队列里有排着队的
                    if (!hasQueuedPredecessors() &&
                        compareAndSetState(0, acquires)) {
                        // 没有排队的，并且state使用cas设置成功的就标记当前占有锁的线程是我
                        setExclusiveOwnerThread(current);
                        // 然后其实就返回了，包括阻塞队列的head和tail节点和waitStatus都没有设置
                        return true;
                    }
                }
                else if (current == getExclusiveOwnerThread()) {
                    int nextc = c + acquires;
                    if (nextc < 0)
                        throw new Error("Maximum lock count exceeded");
                    setState(nextc);
                    return true;
                }
                // 这里就是第二个线程会返回false
                return false;
            }
        }

## 第二个线程

当第二个线程进来的时候应该是怎么样，结合代码来看

    /**
         * Acquires in exclusive mode, ignoring interrupts.  Implemented
         * by invoking at least once {@link #tryAcquire},
         * returning on success.  Otherwise the thread is queued, possibly
         * repeatedly blocking and unblocking, invoking {@link
         * #tryAcquire} until success.  This method can be used
         * to implement method {@link Lock#lock}.
         *
         * @param arg the acquire argument.  This value is conveyed to
         *        {@link #tryAcquire} but is otherwise uninterpreted and
         *        can represent anything you like.
         */
        public final void acquire(int arg) {
            // 前面第一种情况是tryAcquire直接成功了，这个if判断第一个条件就是false，就不往下执行了
            // 如果是第二个线程，第一个条件获取锁不成功，条件判断!tryAcquire(arg) == true，就会走
            // acquireQueued(addWaiter(Node.EXCLUSIVE), arg)
            if (!tryAcquire(arg) &&
                acquireQueued(addWaiter(Node.EXCLUSIVE), arg))
                selfInterrupt();
        }

然后来看下addWaiter的逻辑

    /**
         * Creates and enqueues node for current thread and given mode.
         *
         * @param mode Node.EXCLUSIVE for exclusive, Node.SHARED for shared
         * @return the new node
         */
        private Node addWaiter(Node mode) {
            // 这里是包装成一个node
            Node node = new Node(Thread.currentThread(), mode);
            // Try the fast path of enq; backup to full enq on failure
            // 最快的方式就是把当前线程的节点放在阻塞队列的最后
            Node pred = tail;
            // 只有当tail，也就是pred不为空的时候可以直接接上
            if (pred != null) {
                node.prev = pred;
                // 如果这里cas成功了，就直接接上返回了
                if (compareAndSetTail(pred, node)) {
                    pred.next = node;
                    return node;
                }
            }
            // 不然就会继续走到这里
            enq(node);
            return node;
        }

然后就是enq的逻辑了

    /**
         * Inserts node into queue, initializing if necessary. See picture above.
         * @param node the node to insert
         * @return node's predecessor
         */
        private Node enq(final Node node) {
            for (;;) {
                // 如果状态没变化的话，tail这时还是null的
                Node t = tail;
                if (t == null) { // Must initialize
                    // 这里就会初始化头结点，就是个空节点
                    if (compareAndSetHead(new Node()))
                        // tail也赋值成head
                        tail = head;
                } else {
                    // 这里就设置tail了
                    node.prev = t;
                    if (compareAndSetTail(t, node)) {
                        t.next = node;
                        return t;
                    }
                }
            }
        }

所以从这里可以看出来，其实head头结点不是个真实的带有线程的节点，并且不是在第一个线程进来的时候设置的

## 解锁

通过代码来看下

    /**
         * Attempts to release this lock.
         *
         * <p>If the current thread is the holder of this lock then the hold
         * count is decremented.  If the hold count is now zero then the lock
         * is released.  If the current thread is not the holder of this
         * lock then {@link IllegalMonitorStateException} is thrown.
         *
         * @throws IllegalMonitorStateException if the current thread does not
         *         hold this lock
         */
        public void unlock() {
            // 释放锁
            sync.release(1);
        }
    /**
         * Releases in exclusive mode.  Implemented by unblocking one or
         * more threads if {@link #tryRelease} returns true.
         * This method can be used to implement method {@link Lock#unlock}.
         *
         * @param arg the release argument.  This value is conveyed to
         *        {@link #tryRelease} but is otherwise uninterpreted and
         *        can represent anything you like.
         * @return the value returned from {@link #tryRelease}
         */
        public final boolean release(int arg) {
            // 尝试去释放
            if (tryRelease(arg)) {
                Node h = head;
                if (h != null && h.waitStatus != 0)
                    unparkSuccessor(h);
                return true;
            }
            return false;
        }
    protected final boolean tryRelease(int releases) {
                int c = getState() - releases;
                if (Thread.currentThread() != getExclusiveOwnerThread())
                    throw new IllegalMonitorStateException();
                boolean free = false;
        		// 判断是否完全释放锁，因为可重入
                if (c == 0) {
                    free = true;
                    setExclusiveOwnerThread(null);
                }
                setState(c);
                return free;
            }
    // 这段代码和上面的一致，只是为了顺序性，又拷下来看下

    public final boolean release(int arg) {
            // 尝试去释放，如果是完全释放，返回的就是true，否则是false
            if (tryRelease(arg)) {
                Node h = head;
                // 这里判断头结点是否为空以及waitStatus的状态，前面说了head节点其实是
                // 在第二个线程进来的时候初始化的，如果是空的话说明没后续节点，并且waitStatus
                // 也表示了后续的等待状态
                if (h != null && h.waitStatus != 0)
                    unparkSuccessor(h);
                return true;
            }
            return false;
        }

    /**
         * Wakes up node's successor, if one exists.
         *
         * @param node the node
         */
    // 唤醒后继节点
        private void unparkSuccessor(Node node) {
            /*
             * If status is negative (i.e., possibly needing signal) try
             * to clear in anticipation of signalling.  It is OK if this
             * fails or if status is changed by waiting thread.
             */
            int ws = node.waitStatus;
            if (ws < 0)
                compareAndSetWaitStatus(node, ws, 0);

            /*
             * Thread to unpark is held in successor, which is normally
             * just the next node.  But if cancelled or apparently null,
             * traverse backwards from tail to find the actual
             * non-cancelled successor.
             */
            Node s = node.next;
            // 如果后继节点是空或者当前节点取消等待了
            if (s == null || s.waitStatus > 0) {
                s = null;
                // 从后往前找，找到非取消的节点，注意这里不是找到就退出，而是一直找到头
                // 所以不必担心中间有取消的
                for (Node t = tail; t != null && t != node; t = t.prev)
                    if (t.waitStatus <= 0)
                        s = t;
            }
            if (s != null)
                // 将其唤醒
                LockSupport.unpark(s.thread);
        }