标签：Node AQS 队列 ReentrantLock 获取 state 线程公平

参考：

《对线面试官》

公平锁和非公平锁

公平锁：在竞争环境下，先到的线程一定比后到的线程更快获取到锁

非公平锁：先到的线程未必能够先获取锁

怎么实现

可以使用先进先出队列

公平锁：竞争线程先入队，持有锁的线程释放锁后，唤醒队列的下一个线程去获取锁（先排队）

非公平锁：竞争线程先尝试获取锁，获取到就直接执行同步代码块，获取不到就放入队列进行等待（先尝试获取锁）

区别：是否先尝试获取锁

为什么不自旋而用队列

自旋需要耗费资源，多个线程自旋而且大多数是竞争失败，做无用功

AQS

AbstractQueuedSynchronizer，一个双向队列，存Node节点，双向链表实现

内部实现是一个先进先出队列+state状态变量（加锁成功state为1，重入+1，解锁为0）

会把需要等待的线程一Node的形式放到队列上

head：指向对头

tail：指向队尾

state：锁状态，0锁自由，1锁被占用

Node：

thread
链表

Thread存储要排队的线程信息

队列对头Node的thread永远是null

　　=》第二个才是排队的，第一个叫正在处理中

　　=》持有锁的线程不在队列中，需要虚拟一个头部（Node对象，thread=null）

持有锁的线程不在队列当中，不参与排队

ws =-1表示线程在睡眠

解锁后的头部，是手动把thread设置为null的，旧的头部没有引用指向，方便GC

支持两种模式；独占（锁只会被⼀个线程独占）和共享（多个线程可同时执⾏）

RreetrentLock

一部分是在java级别解决（交替执行时，通过改变锁的状态来实现，AQS中的state，此时不会初始化队列）

还有一部分会使用到os的api(竞争执行时)，放到队列中调用park()方法会用到os函数

支持公平锁与非公平锁，默认是非公平锁非公平锁效率更高

    /**
     * Creates an instance of {@code ReentrantLock}.
     * This is equivalent to using {@code ReentrantLock(false)}.
     */
    public ReentrantLock() {
        sync = new NonfairSync();
    }

通过控制boolean参数可以调整

    public ReentrantLock(boolean fair) {
        sync = fair ? new FairSync() : new NonfairSync();
    }

就两个私有属性，主要属性Sync，可以看到是一个AQS队列

加锁：

非公平锁

代码解析

        /**
         * Performs lock.  Try immediate barge, backing up to normal
         * acquire on failure.
         */
        final void lock() {
            // 先通过cas方式尝试获取锁资源  调用unsave工具包  预期AQS的state值0，尝试更新为1 （默认是0）
            if (compareAndSetState(0, 1))
            // 获取锁资源成功 设置排他独占  将当前线程设置到AQS的exclusiveOwnerThread（AOS中），代表当前线程拿着资源
                setExclusiveOwnerThread(Thread.currentThread());
            else
            // 获取不到，调用尝试获取锁
                acquire(1);
        }


        // 公平锁和非公平锁都会调用acquire
        public final void acquire(int arg) {
            // tryAcquire分为两种实现，一种是公平锁，一种是非公平锁
            // 公平锁操作：如果state为0，再看是否需要排队。如果是重入锁，直接获取锁
            // 非公平锁：如果state为0，直接尝试CAS修改。如果是锁重入，直接获取锁

            // 没有拿到锁，就要排队了  addWaiter将当前线程封装为Node对象放到AQS排队
            if (!tryAcquire(arg) &&
            // 查看当前线程是否是排在队伍前面的，如果是就尝试获取锁资源，如果两次自旋后还是没有拿到，需要将当前线程挂起
                acquireQueued(addWaiter(Node.EXCLUSIVE), arg))
                selfInterrupt();
        }


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

        // 非公平实现
        final boolean nonfairTryAcquire(int acquires) {
            // 拿到当前线程
            final Thread current = Thread.currentThread();
            // 拿到AQS的state
            int c = getState();
            // state 锁自由 
            if (c == 0) {
                // 基于CAS尝试修改state从0~1，如果成功 表示拿到锁
                if (compareAndSetState(0, acquires)) {
                    // 将exclusiveOwnerThread属性设置为当前线程
                    setExclusiveOwnerThread(current);
                    // 返回true 表示已经成功拿到锁资源
                    return true;
                }
            }
            // state不为0 锁被占用
            // 判断占用锁的线程是否是当前线程
            else if (current == getExclusiveOwnerThread()) {
                // 锁重入 对state+1
                int nextc = c + acquires;
                // 判断锁重入是否已经达到最大值（加成负数了 超过了锁重入的最大限制）
                if (nextc < 0) // overflow
                    throw new Error("Maximum lock count exceeded");
                    // AQS state+1
                setState(nextc);
                // 返回true 表示已经成功拿到锁资源
                return true;
            }
            // 尝试拿到锁失败 就要去排队了 state非0，也不是被当前线程占用，无法重入
            return false;
        }

以默认的非公平锁为例

判断锁的状态
如果有人持有，入队（enq()），根据线程实例化一个Node（待入队的Node，就叫做t2吧），再实例化一个thread为null的空Node并将其设置为AQS的头和尾完成初始化队列（队列有人了），t2入队（更改前后指针维护链表）
- 判断上一个节点是不是空Node，即自己是不是第一个排队的，是的话自旋tryAcquire尝试获取锁（万一确实轮到自己了呢，且除了判断锁是否是自由状态，还会判断是否是第一个排队的人，不是则返回false，是才会让拿到锁）
  - 没有拿到（前面的还没搞完），shouldParkAfterFailed()设置头Node的ws=-1(初始为0，一次改为-1，再来就失败退出。多自旋一次是为了尽量不park)，再次自旋尝试获取锁，
    - 还没拿到（头Node的ws已经=-1），shouldParkAfterFailed()方法中确认需要park，park当前线程（阻塞）
如果没有人持有锁，判断自己是否需要排队
- 队列是否初始化
  - 没有被初始化
  - 被初始化了
    - 队列当中的元素>1
    - 队列当中的元素等于1
假设t3来了，维护队列，排在t2后面，shouldParkAfterFailed()发现t2的ws=0，将其改为-1，循环发现t2的ws=-1，t3睡眠，t3的ws=0

为什么修改的是前一个节点的ws？

因为代码中，线程自己睡眠了，需要别人来判断它是否是睡眠了，没法自己再判断自己是否是睡眠了

重入：使用lock加锁时，会判断当前线程和持有锁的线程是否相同，如果相同，会把持有锁的计数器+1，表示重入

公平锁

代码解读

        // 公平锁----------------------------------------
        final void lock() {
            // 直接调用acquire 不会 先尝试直接CAS获取锁
            acquire(1);
        }

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

        /**
         * 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();
            // 获取state
            int c = getState();
            // 如果锁自由
            if (c == 0) {
                // 先查看有无线程排队  抱着不插队的思想
                if (!hasQueuedPredecessors() && 
                // 没有人排队，尝试CAS获取锁
                    compareAndSetState(0, acquires)) {
                        // 设置exclusiveOnwer为当前线程
                    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;
        }
    }

区别

公平锁和非公平锁的tryAcquire方法的唯一区别就是，当判断state为0（锁自由）后

公平锁会先查看是否有线程正在排队，如果有则进行排队，如果没有，执行CAS尝试获取锁资源
非公平锁不管有没有线程排队，直接以CAS的方式尝试获取锁资源，拿不到就去排队

待续、、、

标签：Node,AQS,队列,ReentrantLock,获取,state,线程,公平
From： https://www.cnblogs.com/deity-night/p/17270586.html

ReentrantLock与AQS