ReentrantLock:可重入锁，实现与Lock

　　显示锁：可通过lock和unlock方法进行显示的加锁释放锁

　　独占锁：同时只能有一个线程持有锁

　　可重入锁：同一个锁对象，同一个线程可以重入

在ReentrantLock的构造函数中提供了两种公平性选择，非公平的锁（默认）和一个公平的锁，通过FairSync和NonfairSync两个内部类来实现

在公平的锁上，线程将按照它们发出请求的顺序来获得锁，但在非公平的锁上，则允许‘插队’；当一个线程请求非公平的锁时，如果在发出请求的同时该锁的状态变为可用，那么这个线程将跳过队列中所有的等待线程并获得这个锁---java并发编程实战

一，创建锁对象

//true为公平锁，false为非公平锁，无参默认为false
Lock lock = new ReentranLock(true);

二，加锁方法lock()

公平锁lock方法

final void lock() {
        acquire(1);
}

非公平锁lock方法，先尝试更改锁状态，如果可用，直接获得这个锁

final void lock() {
    //先尝试更改锁状态，成功，则作为持有者
    if (compareAndSetState(0, 1))
        setExclusiveOwnerThread(Thread.currentThread());
    else
        acquire(1);
}

acquire方法，获取锁，通过轮询、挂起直到获取锁，可响应线程中断

public final void acquire(int arg) {
    if (!tryAcquire(arg) &&
        acquireQueued(addWaiter(Node.EXCLUSIVE), arg))
        selfInterrupt();
}

公平锁的tryAcquire

protected final boolean tryAcquire(int acquires) {
            final Thread current = Thread.currentThread();
            int c = getState();
            //锁没有被持有
            if (c == 0) {
                //如果队列中没有线程在排队，则可以尝试获取锁, 这是公平模式下
                if (!hasQueuedPredecessors() &&
                    //尝试设置锁状态，这里可能会被其他线程抢先设置，导致竞争锁失败
                    compareAndSetState(0, acquires)) {
                    //设置当前持有锁的线程
                    setExclusiveOwnerThread(current);
                    return true;
                }
            }
            //如果当前持有线程就是当前线程，可重入，
            else if (current == getExclusiveOwnerThread()) {
                //state+1，在释放锁的时候，会state-1，直到减到0，释放锁
                int nextc = c + acquires;
                //数过大时，超过Integer的最大值，计算结果是负值
                if (nextc < 0)
                    throw new Error("Maximum lock count exceeded");
                setState(nextc);
                return true;
            }
            return false;
 }    

//是否需要插队，返回false则不需要插队
public final boolean hasQueuedPredecessors() {
        Node t = tail; //头节点
        Node h = head;//尾节点
        Node s;
         /**
         * //这里返回false，则说明需要排队
         * 无需排队的情况:
         * h==t的情况
         *  1:还未初始化的队列，h,t都为null，此时无等待节点;
         *  2:队列初始化后，无等待节点的队列。最后一个节点获取到了锁资源，会把此节点设置为头h节点,同时此节点也是尾节点，
         *    都指向同一个节点，是相等的（所以，队列一经初始化，头尾节点就不会为空），此时队列无等待节点。
         * h!=t 的情况，
         *  1:另一个线程未完全初始化时，head被设置有值，h!=null,但是tail还没来得及赋值，tail=null
         *     h!=t,但是当执行到h.next时，head的next被另一个线程赋值了，此时(s = h.next) == null为false
         *     但是，被另一个线程初始化，tail节点持有的线程不会是当前线程，
              s.thread != Thread.currentThread())返回true,最终返回true,需要排队
         *  2:队列中有等待节点，此时h.next不为null，但是不是当前线程，最终返回true
         *   目前只想到这些情况了，不知道还有没有其他情况
         */
    return h != t &&
            ((s = h.next) == null || s.thread != Thread.currentThread());
    }

hasQueuedPredecessors

非公平锁的tryAcquire

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

final boolean nonfairTryAcquire(int acquires) {
    final Thread current = Thread.currentThread();
    int c = getState();
    if (c == 0) {
        //区别是这里没了队列状态的判断，!hasQueuedPredecessors()
        if (compareAndSetState(0, acquires)) {
            setExclusiveOwnerThread(current);
            return true;
        }
    }
    else if (current == getExclusiveOwnerThread()) {
        int nextc = c + acquires;
        if (nextc < 0) // overflow
            throw new Error("Maximum lock count exceeded");
        setState(nextc);
        return true;
    }
    return false;
}

 如果返回true,则表示获取锁，如果返回false，执行acquireQueued(addWaiter(Node.EXCLUSIVE), arg)，

private Node addWaiter(Node mode) {
    //新建节点
    Node node = new Node(Thread.currentThread(), mode);
   
    Node pred = tail;
    //如果存在尾节点，尝试快速添加到队列中
    if (pred != null) {
        node.prev = pred;
        //尝试设置插入节点为尾节点，
        if (compareAndSetTail(pred, node)) {
            //设置尾节点关联属性
            pred.next = node;
            return node;
        }
    }
       //快速添加失败，用enq(node)添加
    enq(node);
    return node;
}

快速添加失败，则使用enq(final Node node)方法，通过自旋的方式直到插入队列为止

private Node enq(final Node node) {
    //自旋直到添加进去为止
    for (;;) {
        Node t = tail;
        //不存在尾节点，则说明队列还未初始化，因为队列一旦初始化，首尾队列就不会为空
        if (t == null) { //进行初始化 
            //尝试设置头节点
         if (compareAndSetHead(new Node()))
                //使头尾节点指向同一个节点
                tail = head;
        } else { //如果队列已经初始化
           // 设置插入节点上一个节点为原尾节点
            node.prev = t;
            //尝试把插入节点设置尾节点
            if (compareAndSetTail(t, node)) {
                //调整原尾节点关联属性
                t.next = node;
                return t;
            }
        }
    }
}

enq

添加节点之后 ，执行acquireQueued方法，自旋、挂起，直到获取到锁

final boolean acquireQueued(final Node node, int arg) {
    boolean failed = true;
    try {
        //是否是中断状态
        boolean interrupted = false;
        for (;;) {
               //获取当前节点的上一个节点
            final Node p = node.predecessor();
            //如果上一节点是头节点，尝试获取锁，因为头节点不参与锁的竞争
            if (p == head && tryAcquire(arg)) {
                //成功，设置当前节点为头节点，
                //所以头节点不参与竞争锁资源，因为已经获取到了锁资源了
                setHead(node);
                p.next = null; // help GC
                failed = false;//未执行失败
                return interrupted;//
            }
               //是否应该挂起当前线程，如果需要挂起，挂起，
            //结束后返回中断状态，如果已中断，返回true
            if (shouldParkAfterFailedAcquire(p, node) &&
                parkAndCheckInterrupt())
                interrupted = true;
        }
    } finally {
        //如果失败，取消获取锁
        if (failed)
            cancelAcquire(node);
    }
}

shouldParkAfterFailedAcquire(p, node)，判断是否要挂起当前线程或是接着自旋，以避免刚挂起就获取到锁

private static boolean shouldParkAfterFailedAcquire(Node pred, Node node) {
    //上一节点的等待状态
    int ws = pred.waitStatus;
    //如果是SINNAL(-1)状态，说明需要等待上一个节点释放锁的时候唤醒自己，返回true，挂起
    if (ws == Node.SIGNAL)
        return true;
    if (ws > 0) {//如果上一个节点取消了
        do {
            node.prev = pred = pred.prev;//就关联上上一个节点，
            //直到找到没有被取消的节点，被取消的节点被清除出队列
        } while (pred.waitStatus > 0);
        pred.next = node;
    } else {
        //waitStatus must be 0 or PROPAGATE(-3)
        //上一个节点等待状态为0，先不考虑PROPAGATE（共享下的状态）
            //1:插入节点时，上一个节点（原尾节点）为0;
            //2:释放锁时，头节点状态会重置为0
            //3:初始化时，头尾节点状态为0
        //如果上一个节点是头结点，且状态为0，则可能刚释放完锁，则去自旋尝试获取锁
        compareAndSetWaitStatus(pred, ws, Node.SIGNAL);
    }
    return false;
}

挂起当前线程，在唤醒的时候，返回并重置中断状态

private final boolean parkAndCheckInterrupt() {
    LockSupport.park(this);//挂起休眠，直到获取到许可
    return Thread.interrupted(); //返回并重置中断状态
}

取消节点cancelAcquire

private void cancelAcquire(Node node) {
    // Ignore if node doesn't exist
    if (node == null)
        return;

    node.thread = null;

    // Skip cancelled predecessors
    Node pred = node.prev;
    //清除取消节点出队列
    while (pred.waitStatus > 0)
        node.prev = pred = pred.prev;

    Node predNext = pred.next;
    node.waitStatus = Node.CANCELLED;

    // If we are the tail, remove ourselves.
    //如果被取消的是尾节点
    if (node == tail && compareAndSetTail(node, pred)) {
        //设置取消节点的上一个节点的next为null
        compareAndSetNext(pred, predNext, null);
    } else {
        // 如果上一个节点不是头节点，不是正在或者已经取消的节点，且（waitStatus等于或可以设置成                // Node.SIGNAL状态
        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
    }
}

三，释放锁unlock()

public void unlock() {
    sync.release(1);
}

public final boolean release(int arg) {
    //释放锁，state-1
    if (tryRelease(arg)) {
        //state=0, 释放锁完毕
        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;
    //没有获取到锁，就去unlock,抛出异常
    if (Thread.currentThread() != getExclusiveOwnerThread())
        throw new IllegalMonitorStateException();
    boolean free = false;
    //因为可重入，所以只有state=0的时候，才表示当前线程完全释放锁了
    if (c == 0) {
        free = true;
        setExclusiveOwnerThread(null);
    }
    setState(c);
    return free;
}

唤醒下一个等待节点

private void unparkSuccessor(Node node) {
    int ws = node.waitStatus;
    //释放锁后，重置头节点waitStatus状态为0
    if (ws < 0)
        compareAndSetWaitStatus(node, ws, 0);

   //唤醒当前节点下一个没有被取消的节点
    Node s = node.next;
    //头节点下一个节点为null,或者节点已取消
    if (s == null || s.waitStatus > 0) {
        s = null;
        //从尾节点开始，往前找最接近头节点没有被取消的节点，找到赋值给s
        for (Node t = tail; t != null && t != node; t = t.prev)
            if (t.waitStatus <= 0)
                s = t;
    }
    if (s != null)
        //唤醒线程
        LockSupport.unpark(s.thread);
}

 四，其它

公平锁不是绝对的公平，a线程先调用了lock方法，b再调用，在CPU调度上，如果b获得了更多的执行时间，那么是有可能先获取锁的。