公平锁非公平锁

并发包中ReentrantLock创建指定构造函数的boolean类型来得到公平锁还是非公平锁，默认是非公平锁。

公平锁和非公平锁的差异？

非公平锁：当一个线程请求非公平锁的时候，如果这个时候原先持有锁的线程释放了锁，那么这个当前请求的线程可以越过等待队列中所有的线程来获取这个锁。

（如果线程请求锁的时候，锁已经被别的线程所拥有，那么这个线程会被放到队列中。）

公平锁：如果线程请求锁的时候，队列中已经有等待锁的线程，那么这个线程将先被挂起到等待队列中。

为什么非公平锁性能更好

为什么性能更好？
- 在恢复一个被挂起的线程与这个线程真正运行之间有着巨大的延迟。
- 假设线程A持有一个锁，线程B来请求，被加入到阻塞队列，此时线程A放弃锁，唤醒线程B，如果这个时候有一个线程C来获取锁，那么C很有可能在B被完全唤醒之前就已经获得锁并使用完毕释放这个锁，此时线程B完全醒来，B得到锁的时刻并没有受到推迟，但是中间C更早的获得了锁，吞吐量也相应的提升了。
什么时候使用公平锁？
- （由上例）如果线程持有锁的时间较长，或者请求锁的平均时间间隔较长，那么可以使用公平锁。

可重入锁（又名递归锁）指的是同一线程外层函数获得锁之后，内层递归函数仍然能获取该锁的代码。
在同一个线程外层获取锁的时候，在进入内层方法会自动获取锁。也就是说，线程可以进入到任何一个它已经拥有的锁的所同步的代码块。 ReentrantLock/synchronized就是典型的可重入锁。可重入锁最大的作用就是避免死锁。

自旋锁
是指尝试获取锁的线程不会立即阻塞，而是采用循环的方式去尝试获取锁，这样的好处是减少线程上下切换的消耗，缺点是循环或消耗CPU。自旋好处：循环比较获取直到成功为止，没有wait阻塞。

ReentrantLock

** ReentrantLock - 图1
ReentrantLock 默认采用非公平的策略，也可以在构造的时候指定是否公平的策略。

非公平锁

非公平锁是指在竞争获取锁的过程中，有可能后来者居上

获取锁

static final class NonfairSync extends Sync {
    private static final long serialVersionUID = 7316153563782823691L;
    /**
     * Performs lock.  Try immediate barge, backing up to normal
     * acquire on failure.
     */
    final void lock() {
        // CAS 设置 state 值为 1
        if (compareAndSetState(0, 1))
            // CAS 成功则说明获取到锁, 此时将当前线程设置为独占模式下锁对象的持有者
            setExclusiveOwnerThread(Thread.currentThread());
        else
            // CAS 失败
            // 可能是同一线程再次获取锁
            // 也可能是不同线程获取锁
            acquire(1);
    }
    protected final boolean tryAcquire(int acquires) {
        // 调用父类 sync
        return nonfairTryAcquire(acquires);
    }
}
final boolean nonfairTryAcquire(int acquires) {
    final Thread current = Thread.currentThread();
    int c = getState();
    if (c == 0) {
      // 此时说明已有线程释放了锁
      // 有可能是同步队列里阻塞的线程被唤醒时尝试获取锁
        if (compareAndSetState(0, acquires)) {
            // CAS 成功则说明获取到锁, 此时将当前线程设置为独占模式下锁对象的持有者
            setExclusiveOwnerThread(current);
            return true;
        }
    }
    else if (current == getExclusiveOwnerThread()) {
        // 说明同一线程再次获取锁
        // state 加 1
        int nextc = c + acquires;
        if (nextc < 0) // overflow
            throw new Error("Maximum lock count exceeded");
        setState(nextc);
        return true;
    }
    return false;
}

获取锁的过程如下：

通过 CAS 操作，设置 state = 1
若 CAS 操作成功，则将当前线程设置为独占模式锁对象的持有者
若 CAS 操作失败, 最终会调用 sync 的方法 nonfairTryAcquire; 此时说明可能是同一线程再次尝试获取锁，也有可能是其他线程尝试获取锁
若当前 state == 0, 继续执行前两步操作
若当前 state != 0, 则判断当前线程是否为锁的持有者；若判断成立，则对 state + 1

释放锁

非公平锁的释放调用的是父类 sync 的 tryRelease 方法

protected final boolean tryRelease(int releases) {
    // state 减一操作
    int c = getState() - releases;
    if (Thread.currentThread() != getExclusiveOwnerThread())
        // 当前线程不是当前锁的持有者时抛出异常
        throw new IllegalMonitorStateException();
    boolean free = false;
    if (c == 0) {
        // 只有 state == 0 时 才是真正完成锁的释放
        free = true;
        // 将锁的持有者清空
        setExclusiveOwnerThread(null);
    }
    setState(c);
    return free;
}
========
ReentrantLock lock = new ReentrantLock();
public void do () {
  lock.lock();
  try {
    do();
    // 退出递归
  } finally {
    lock.unlock();
  }
}

公平锁

protected final boolean tryAcquire(int acquires) {
    final Thread current = Thread.currentThread();
    int c = getState();
    if (c == 0) {
        // 不同于非公平锁操作，公平锁多了个判断条件 hasQueuedPredecessors
        if (!hasQueuedPredecessors() &&
            compareAndSetState(0, acquires)) {
            setExclusiveOwnerThread(current);
            return true;
        }
    }
    else if (current == getExclusiveOwnerThread()) {
        int nextc = c + acquires;
        if (nextc < 0)
            throw new Error("Maximum lock count exceeded");
        setState(nextc);
        return true;
    }
    return false;
}
public final boolean hasQueuedPredecessors() {
    // The correctness of this depends on head being initialized
    // before tail and on head.next being accurate if the current
    // thread is first in queue.
    Node t = tail; // Read fields in reverse initialization order
    Node h = head;
    Node s;
    // h != t 说明同步队列已有等待的节点
    // s = h.next == null 这个有点没明白; head 的后置为空应该就是 head == tail 吧
    // s.thread != Thread.currentThread 是判断当前线程是不是同步队列的首个阻塞线程 如果是是允许获取到锁的
    return h != t &&
        ((s = h.next) == null || s.thread != Thread.currentThread());
}

hasQueuedPredecessors 方法主要实现的是查找是否有等待时间超过当前线程的其他线程, 公平锁也就是通过该方法保证获取锁的有序性。

unlock() - 释放锁

公平锁的释放与非公平锁的释放操作一致

public final boolean release(int arg) {
    if (tryRelease(arg)) {
        // 当释放锁成功以后，需要唤醒同步队列中的其他线程
        Node h = head;
        // 当waitStatus!=0时，表示同步队列中还有其他线程在等待获取锁
        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();
    // 因为上面一步已经确认了是当前线程持有锁，所以在修改state时，肯定是线程安全的
    boolean free = false;
    // 因为可能锁被重入了，重入了几次就需要释放几次锁，所以这个地方需要判断，只有当state=0时才表示完全释放了锁。
    if (c == 0) {
        free = true;
        setExclusiveOwnerThread(null);
    }
    setState(c);
    return free;
}

ReentrantLock 如何实现可重入 ? (通过判断当前线程是否为当前锁对象的持有者)
如何实现公平锁 ? (若当前同步队列中有等待的节点则获取锁失败)
非公平锁和公平锁对性能有什么影响 ? (公平锁会造成大量的线程切换，非公平锁会出现线程“饥饿”现象，但线程切换少提高吞吐量)

ReentrantLock

公平锁 非公平锁

公平锁和非公平锁的差异？

为什么非公平锁性能更好

ReentrantLock

非公平锁

公平锁

unlock() - 释放锁

公平锁非公平锁