写点什么

一文搞懂 ReentrantLock 的公平锁和非公平锁

作者:Ayue、
  • 2021 年 12 月 26 日
  • 本文字数:13154 字

    阅读完需:约 43 分钟

一文搞懂ReentrantLock的公平锁和非公平锁

什么是 ReentrantLock

reentrant 翻译为可重入的,因此从字面上翻译为可重入锁,我们知道可重入是指:同一个线程对于已经获得到的锁,可以多次继续申请到该锁的使用权。ReentrantLock 在调用 lock()方法时,已经获取到锁的线程,能够再次调用lock()方法获取锁而不被阻塞。


如果要实现该特性,则需要解决以下两个问题:


  1. 线程再次获取锁。锁需要去识别获取锁的线程是否为当前占据锁的线程,如果是,则再次成功获取。

  2. 锁的最终释放。线程重复 n 次获取了锁,随后在第 n 次释放该锁后,其他线程能够获取到该锁。锁的最终释放要求锁对于获取进行计数自增,计数表示当前锁被重复获取的次数,而锁被释放时,计数自减,当计数等于 0 时表示锁已经成功释放。

再谈 AQS

之前写过一篇关于AQS的文章,AQS 全称队列同步器 AbstractQueuedSynchronizer,它是一个队列,用来构建锁或者其他同步组件的基础框架。


我们可以 AQS 和 ReentrantLock 的关系理解为:


  • 锁是面向使用者的。它定义了使用者与锁交互的接口(比如可以允许两个线程并行访问),隐藏了实现细节。

  • 同步器面向的是锁的实现者。它简化了锁的实现方式,屏蔽了同步状态管理、线程的排队、等待与唤醒等底层操作。


它既然是一个队列,那其中必然维护了一个链表内部类,并且是一个双向链表,我们可以看看它的结构:



其中 Node 中各属性如下:



属性很多,但我们大致只需要记住每个 Node 里面最主要的 3 个:



我们知道 AQS 的设计是基于模板方法模式的,其中定义了一系列的方法让实现者自己去实现,就好比定义一个支付的方法,但是其具体的实现包括微信支付,支付宝支付,银行卡支付等等。而 AQS 中主要的模板方法如下:



而对于其中方法涉及到的状态,AQS 内部提供了一个state属性,因为这是一个会被并发访问的属性,为了防止出现可见性问题要用volatile进行修饰,并且提供了如下 3 个方法来访问或修改同步状态:


  • getState():获取当前同步状态。

  • setState(int newState):设置当前同步状态。

  • compareAndSetState(int expect,int update):使用 CAS 设置当前状态,该方法能够保证状态设置的原子性。


另外,AQS 还拥有首节点(head)和尾节点(tail)两个引用,一个指向队列头节点,而另一个指向队列尾节点(头节点没有前驱,尾结点没有后继)。


注意:因为首节点 head 是不保存线程信息的节点,仅仅是因为数据结构设计上的需要,在数据结构上,这种做法往往叫做空头节点链表。对应的就有非空头结点链表


因此,一个 AQS 我们大致可以抽象为:


ReentrantLock 和 AQS

ReentrantLock 是基于 AQS 实现的,在ReentrantLock 内部有一个内部类Sync,其继承关系如下:



其中具体的方法在之前的文章有讲过,可以自行参考,这里主要是讲非公平锁和公平锁的加锁流程。

非公平锁

加锁流程

一、未加锁

在没加锁之前 AQS 的状态:


二、第一个线程 t1 加锁

1、ReentrantLock()。根据ReentrantLock的默认构造方法可知,当new ReentrantLock(),默认为非公平锁。


public ReentrantLock() {    sync = new NonfairSync();}
复制代码


2、lock()。当第一个线程去获取锁,从Lock.lock()方法开始。


public void lock() {    sync.lock();}
复制代码


3、NonfairSync.lock()。进入非公平锁的实现方法中,并且获取锁。


final void lock() {  //比较并设置状态成功,状态0表示锁没有被占用    if (compareAndSetState(0, 1))      //把当前线程设置独占了锁        setExclusiveOwnerThread(Thread.currentThread());    else //锁已经被占用,或者set失败        acquire(1); //以独占模式获取对象,忽略中断}
复制代码


4、compareAndSetState()。在获取锁之前先通过CAS的方式将AQS中的状态state


  • state == 0, 表示该锁不被任何线程持有。

  • state == 1,表示线程恰好持有该锁 1 次(未重入)。

  • state > 1,表示锁被线程重入 state 次。


protected final boolean compareAndSetState(int expect, int update) {    // See below for intrinsics setup to support this    return unsafe.compareAndSwapInt(this, stateOffset, expect, update);}
复制代码


当第一个线程获取锁时,state的默认值为 0 ,通过 CAS 将state的状态改为 1,并且通过setExclusiveOwnerThread()把当前线程设为独占锁,然后返回成功的结果。


此时 AQS 的状态为:


三、第二个线程 t2 加锁

当第二个线程来加锁,此时存在两种情况,一是是t1已经释放锁了 ,第二t1线程已经还持有锁未释放。


5、若t1已经释放锁,此时 AQS 就是处于未加锁的状态,此时t2来加锁和线程t1的步骤相同。



由此可得出结论,ReentrantLock 如果线程之间没有竞争,那么其效率非常高,甚至队列都没有初始化。这也是为什么t1进来就通过 CAS 获取锁的原因。


当然,既然使用到锁了,那必然是为了高并发场景做准备的。


6、acquire()。若t1未释放锁,此时t2想来获取锁,那么 CAS 就会失败,从而进入acquire()方法。


public final void acquire(int arg) {    if (!tryAcquire(arg) && //当前线程尝试获取锁,若获取成功返回true,否则false        acquireQueued(addWaiter(Node.EXCLUSIVE), arg))        selfInterrupt();}
复制代码


该方法主要的逻辑都在 if 判断条件中,这里面有 3 个重要的方法tryAcquire()addWaiter()acquireQueued(),这三个方法中分别封装了加锁流程中的主要处理逻辑,理解了这三个方法到底做了哪些事情,整个加锁流程就清晰了。


7、tryAcquire()。当前线程尝试获取锁,若获取成功返回 true,否则 false。它是 AQS 中定义的模板方法,ReentrantLock 在公平和非公平模式下对此有不同实现,非公平模式的实现如下:


protected final boolean tryAcquire(int acquires) {    return nonfairTryAcquire(acquires);}
复制代码


底层调用了nonfairTryAcquire(),从方法名上我们就可以知道这是非公平模式下尝试获取锁的方法,具体方法实现如下:


//acquires == 1final boolean nonfairTryAcquire(int acquires) {  //获取当前线程    final Thread current = Thread.currentThread();    //获取state变量的值,即当前锁被重入的次数    int c = getState();    if (c == 0) {//state为0,说明当前锁未被任何线程持有,即t1已经释放了      //通过 CAS 获取锁,同第一个线程加锁方式        if (compareAndSetState(0, acquires)) {            setExclusiveOwnerThread(current);            return true;        }    }    //如果state不为0且为当前线程,说明同一线程锁重入    else if (current == getExclusiveOwnerThread()) {        int nextc = c + acquires;        if (nextc < 0) // overflow            throw new Error("Maximum lock count exceeded");        //更新state        setState(nextc);        return true;    }    //否则获取锁失败    return false;}
复制代码


这里为什么不直接返回 false,主要原因是存在一个时间差,假如在t2刚进入nonfairTryAcquire()方法,t1就释放了,那它就可以立马拿取锁,效率高,因为少了那些没必要的判断。


8、acquireQueued()。当tryAcquire()失败,即返回 false 之后才会执行。该方法主要是将获取锁失败的线程安全的加入同步队列


该方法调用了addWaiter(),且传入了一个空的节点Node.EXCLUSIVE = null,其代码实现如下:


//mode = nullprivate Node addWaiter(Node mode) {  //首先创建一个新节点,并将当前线程实例封装在内部,mode这里为null  //并且mode赋值给Node节点的 nextWaiter    Node node = new Node(Thread.currentThread(), mode);    // Try the fast path of enq; backup to full enq on failure    Node pred = tail;//第一次加锁的时候队列还没有初始化,因此第二次加锁的时候tail = null    if (pred != null) {        node.prev = pred;        if (compareAndSetTail(pred, node)) {            pred.next = node;            return node;        }    }    enq(node);    return node;}
复制代码


由于第一次加锁队列还没有初始化,因此第二次加锁的时候tail = null,所以直接走enq()方法,其中 for(;;)while(true)效果一致。


private Node enq(final Node node) {    for (;;) {        Node t = tail;        //若tail为null,说明队列未初始化,先初始化一个空的节点        if (t == null) { // Must initialize            //构造新结点,CAS方式设置为队列首元素,当head==null时更新成功            if (compareAndSetHead(new Node()))              //头结点与尾结点都指向同一个新生结点                tail = head;        } else {//若tail不为null,即已经被初始化过          //将node结点的prev连接到原尾结点            node.prev = t;            //CAS比较结点t是否为尾结点,若是则将尾结点设置为node            if (compareAndSetTail(t, node)) {              //把原尾结点的next指针指向当前结点node                t.next = node;                return t;            }        }    }}
复制代码


按照步骤分析:

if (t == null),说明队列未初始化,先初始化一个空的节点,CAS 方式设置为队列首元素,当head==null时更新成功,并把尾指针指向首结点。



② 当第二次循环t != null,即已经被初始化过,将 node 结点的 prev 连接到尾结点,CAS 比较结点 t 是否为尾结点,若是则将尾结点设置为 node,然后把原尾结点的 next 指针指向当前结点 node。


我们可以写一段代码去查看对象的赋值情况。


public static void main(String[] args) {    ReentrantLock lock = new ReentrantLock();    //t1首先获取锁 然后阻塞5s    Thread t1 = new Thread(() -> {        try {            lock.lock();//获取锁            //睡眠            TimeUnit.SECONDS.sleep(Integer.MAX_VALUE);        } catch (InterruptedException e) {            e.printStackTrace();        } finally {            lock.unlock();        }    }, "t1");    t1.start()            //主要是为了让t1先拿到锁    TimeUnit.SECONDS.sleep(1);        //t2加锁失败因为被t1持有    Thread t2 = new Thread(() -> {        try {            lock.lock();            System.out.println("t2 获取了锁--执行代码");        } catch (Exception e) {            e.printStackTrace();        } finally {            lock.unlock();        }    }, "t2");    t2.start();}
复制代码


初始化之后



此时,AQS 的队列为:



在死循环中只有通过 CAS 将节点设置成为尾节点之后,当前线程才能从该方法返回,否则,当前线程不断地尝试设置。节点进入同步队列之后,在回头看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;            }            //判断是否要阻塞当前线程            if (shouldParkAfterFailedAcquire(p, node) &&              //线程进入阻塞状态,等待被唤醒(锁被释放的时候唤醒)                parkAndCheckInterrupt())                interrupted = true;        }    } finally {        if (failed)            cancelAcquire(node);    }}
复制代码


  1. 在第一个 if 语句中,先会判断前驱结点是否是头结点,如果是则尝试获取锁,获取锁成功则会设置当前结点为头结点(更新头指针)。**为什么必须前驱结点为头结点才尝试去获取锁?**先不管我们先看第二个 if 判断。

  2. 第二个 if 语句中,shouldParkAfterFailedAcquire(),字面意思挺好理解,在获取资源失败之后是否需要阻塞,代码如下:


// 当获取(资源)失败后,检查并且更新结点状态private static boolean shouldParkAfterFailedAcquire(Node pred, Node node) {  // 获取前驱结点的状态    int ws = pred.waitStatus;    //pred状态为SIGNAL,则返回true,表示要阻塞当前线程    if (ws == Node.SIGNAL)        /*         * This node has already set status asking a release         * to signal it, so it can safely park.         */        return true;    if (ws > 0) {// 表示状态为CANCELLED,为1        //找到pred结点前面最近的一个状态不为CANCELLED的结点        do {            node.prev = pred = pred.prev;        } while (pred.waitStatus > 0);        // 赋值pred结点的next域        pred.next = node;    } else {        //为PROPAGATE -3 或者是 0 表示无状态,(为CONDITION -2时,表示此节点在condition queue中)         // 比较并设置前驱结点的状态为SIGNAL        compareAndSetWaitStatus(pred, ws, Node.SIGNAL);    }    return false;}
复制代码


这个方法我们可以理解为只有当该节点的前驱结点的状态为SIGNAL时,才可以对该结点所封装的线程进行 park 操作。否则,将不能进行 park 操作。其中各属性如下:


  • int CANCELLED = 1,即waitStatus值为 1 ,表示该线程节点已释放(超时、中断),已取消的节点不会再阻塞。

  • int SIGNAL = -1,即waitStatus为 -1 ,表示前驱节点已经设置了SIGNAL,闹钟已经设好,现在我可以安心睡觉(阻塞)了。如果前驱变成了 head,并且 head 的代表线程 exclusiveOwnerThread 释放了锁,就会来根据这个 SIGNAL 来唤醒自己。

  • int CONDITION = -2,即waitStatus为 -2 ,表示该线程在Condition队列中阻塞(Condition 有使用)

  • int PROPAGATE = -3,即waitStatus为 -3,表示该线程以及后续线程进行无条件传播(CountDownLatch中有使用)共享模式下, PROPAGATE 状态的线程处于可运行状态 。


再看parkAndCheckInterrupt()方法,源码如下:


private final boolean parkAndCheckInterrupt() {    //park 当前线程    LockSupport.park(this);    //调用 Thread.interrupted()方法返回中断状态,并且重置中断状态    return Thread.interrupted();}
复制代码


使用 LockSupport.park 挂起当前线程变成 WATING 状态,关于 LockSupport 可以查看这篇文章:LockSupport功能简介及原理浅析


Thread.interrupted(),返回当前线程是否被其他线程触发过中断请求,也就是Thread.interrupt(), 如果有触发过中断请求,那么这个方法会返回当前的中断标识 true,并且对中断标识进行复位标识已经响应过了中断请求。如果返回 true,意味着在 acquire() 方法中会执行 selfInterrupt()


static void selfInterrupt() {    Thread.currentThread().interrupt();}
复制代码


因此,selfInterrupt() 执行的前提是 acquireQueued(addWaiter(Node.EXCLUSIVE), arg)方法返回 true。这个方法返回的是线程在获取锁的过程中是否发生过中断,返回 true 则证明发生过中断。所以 acquire() 中的 selfInterrupt() 其实是对获取锁的过程中发生过的中断的补充。


怎么理解?为什么 park之后要调用Thread.interrupted()以及selfInterrupt()

当调用了 LockSupport 的 park 后,该线程从 park 方法返回的情况有两种:

  1. 一种是其他线程释放了资源,调用了该线程的 unpark 方法。

如果是被调用了unpark 方法,那么 Thread.interrupted() 将返回 false,然后进入循环代码继续尝试获取锁,这一步就是正常情况。

  1. 另外一种就是该线程被某些线程给中断了,但是如果是因为线程被中断而返回,那么Thread.interrupted() 将返回 true,如果此时线程从循环中获取到了资源,那么最终会调用selfInterrupt() 这个方法,此时又会中断该线程。


问题来了,为什么获取到锁后要进行一次中断?个人觉得这一步主要是为了该线程的中断信息不被吃掉,当调用 park 方法阻塞后,如果被中断了,那么继续回去获取锁,获取锁后,会再次中断自己,让上层调用者获取到自己被中断的信息,由上层调用者决定是否对中断处理,而不是悄悄把中断信息吃掉。因为我们知道lock()方法是不能被中断的。


可以参考 lockInterruptibly() 这个方法,这里面唯一的区别就是调用 park 后,如果线程发生了中断,则直接抛出中断异常,而不是去获取锁了。

9、cancelAcquire()。然后在acquireQueued()的 final 块中还有一个方法cancelAcquire(),该方法完成的功能就是取消当前线程对资源的获取,即设置该结点的状态为 CANCELLED,一般来说条件比较苛刻,而且对加锁过程影响不是很大,至少我没看出什么影响,并且暂时没想到什么场景去适配,所以这里不在细究。


//取消继续获取(资源)private void cancelAcquire(Node node) {    // node为空,返回    if (node == null)        return;    // 设置node结点的thread为空    node.thread = null;    // 保存node的前驱结点    Node pred = node.prev;    //找到node前驱结点中第一个状态小于0的结点,即不为CANCELLED状态的结点    while (pred.waitStatus > 0)        node.prev = pred = pred.prev;    //获取pred结点的下一个结点    Node predNext = pred.next;    //设置node结点的状态为CANCELLED    node.waitStatus = Node.CANCELLED;    //node结点为尾结点,则设置尾结点为pred结点    if (node == tail && compareAndSetTail(node, pred)) {        // 比较并设置pred结点的next节点为null        compareAndSetNext(pred, predNext, null);    } else { // node结点不为尾结点,或者比较设置不成功        int ws;        if (pred != head &&                ((ws = pred.waitStatus) == Node.SIGNAL ||                        (ws <= 0 && compareAndSetWaitStatus(pred, ws, Node.SIGNAL))) &&                pred.thread != null) { // (pred结点不为头结点,并且pred结点的状态为SIGNAL)或者             // pred结点状态小于等于0,并且比较并设置等待状态为SIGNAL成功,并且pred结点所封装的线程不为空            // 保存结点的后继            Node next = node.next;            if (next != null && next.waitStatus <= 0) // 后继不为空并且后继的状态小于等于0                compareAndSetNext(pred, predNext, next); // 比较并设置pred.next = next;        } else {            unparkSuccessor(node); // 释放node的前一个结点        }        node.next = node; // help GC    }}
复制代码


其中对于unparkSuccessor函数,其主要目的就是为了唤醒 node 节点的后继结点。也就是当前节点拿到锁释放之后,回去唤醒后继结点,所以此时把首节点指向了释放锁后的下一节点。源码如下:


 //释放后继结点 private void unparkSuccessor(Node node) {     // 获取node结点的等待状态     int ws = node.waitStatus;     if (ws < 0) // 状态值小于0,为SIGNAL -1 或 CONDITION -2 或 PROPAGATE -3         // 比较并且设置结点等待状态,设置为0         compareAndSetWaitStatus(node, ws, 0);     // 获取node节点的下一个结点     Node s = node.next;     if (s == null || s.waitStatus > 0) { //下一个结点为空或者下一个节点的等待状态大于0,即为CANCELLED状态,此时会从尾结点往前找不是CANCELLED状态的节点         // s赋值为空         s = null;         // 从尾结点开始从后往前开始遍历         for (Node t = tail; t != null && t != node; t = t.prev)             if (t.waitStatus <= 0) // 找到等待状态小于等于0的结点,找到最前的状态小于等于0的结点                 // 保存结点                 s = t;     }     if (s != null) // 该结点不为为空,释放许可         LockSupport.unpark(s.thread); }
复制代码


然后再回到上面遗留的问题,**为什么必须前驱结点为头结点才尝试去获取锁?**原因有两个:


  1. 因为头结点表示当前正占有锁的线程。我们想想头结点有什么?头节点代表第一个进入队列的线程,注意是进入队列的线程,不是指上面例子的t1,上面的例子t2线程才是第一个进入队列的线程,如果t1这时候释放了锁且同时没有其他线程来竞争锁,那么它将直接拿到锁,并成功获取到同步状态state,即头节点是成功获取到同步状态的节点,如果这个时候第二个线程进入队列,那么它会去看它的前驱节点是否是头结点,因为头结点有同步状态state,如果刚好释放那么他就立刻获取锁,否者排队阻塞。

  2. 维护同步队列的 FIFO 原则。当线程获取到同步状态后,让首节点这个引用指向自己所在节点。当同步状态获取成功后,当前线程就从 acquire 方法返回了。如果同步器实现的是锁,那就代表当前线程获得了锁。


因此,进入队列排队是两回事,也就是说我进入队列了我并不一定就是在排队(park),举个例子:


比如我们去火车站买票,如果说我们看到售票窗口处于空闲状态,即没人排队买票,那这个时候你就直接去买就行,如果有人在排队,一般来说排队的时候我们可能就会玩玩手机,但不是一定排队就会去玩手机,你会看看前面那个人是不是第一个人,如果是第一个人的话,那可能马上就轮到你了,你就不用掏出手机来玩了,如果不是得话,你才掏出手机玩直到你前面只有一个人的时候才收起手机。

小结

总结一下非公平锁获取锁的流程:


  1. 第一次去获取锁的时候,会去尝试去加锁。

  2. 如果加锁失败,则去看为什么失败(是否锁被人持有了)。

  3. 在判断的过程中如果锁没有被持有,非公平锁就会去直接加锁(不会判断是否有人排队),成功则进入同步块,失败则进入队列。

  4. 进入队列后如果前面获取锁的节点是头结点 head 则再次尝试加锁,成功则执行同步代码块,失败则park()(真正的排队)。


解锁流程

解锁流程就比较简单。


1、unlock()


public void unlock() {    sync.release(1);}
复制代码


2、release()


public final boolean release(int arg) {    //若尝试释放锁成功    if (tryRelease(arg)) {        //先获取头结点        Node h = head;         //如果头节点不为null且节点的状态不为0        if (h != null && h.waitStatus != 0)            //唤醒后继节点中的线程            unparkSuccessor(h);        return true;    }    return false;}
复制代码


该方法在 if 语句中调用了tryRelease(),源码如下:


protected final boolean tryRelease(int releases) {    //获取AQS中的同步状态并计算    int c = getState() - releases;    //判断是否是当前线程,不是就抛异常(一般情况下不会发生)    if (Thread.currentThread() != getExclusiveOwnerThread())        throw new IllegalMonitorStateException();    //释放标识    boolean free = false;    //如果当前状态为0,说明可释放锁,把标识改为true    if (c == 0) {        free = true;        setExclusiveOwnerThread(null);    }    //更新state    setState(c);    return free;}
复制代码


tryRelease()的作用是将线程持有锁的次数减 1 ,即将 state 值减 1,若减少后线程将完全释放锁(state==0),则该方法将返回 true,否则返回 false。由于执行该方法的线程必然持有锁,故该方法不需要任何同步操作,等待流程走完即可。若当前线程已经完全释放锁,即锁可被其他线程使用,则还应该唤醒后续等待线程


tryRelease()尝试释放锁返回 true,则需要满足 if 语句中的 2 个条件:


  • head != null。防止队列为空队列,若头节点为 null,则说明队列中没有其他线程处于队列中,当然也就无需执行唤醒操作。

  • h.waitStatus != 0。是为了防止队列中虽有线程,但该线程还未阻塞,由前面的分析知,线程在阻塞自己前必须设置前驱结点的状态为 SIGNAL,否则它不会阻塞自己。如果没阻塞那也就不需要被唤醒。


如果上述 2 个条件都满足,则需要通过unparkSuccessor()去唤醒后继节点,该方法的源码如下:


private void unparkSuccessor(Node node) {     //头结点的状态    int ws = node.waitStatus;    /**    * 尝试将ws改为 0 ,即使失败也无所谓。    * 这里使用cas的方式修改是因为他的前置节点也可能修改他的waitStatus   * 将ws更新为0的理由是让唤醒的线程可以多一轮竞争。提高竞争率   */    if (ws < 0)        compareAndSetWaitStatus(node, ws, 0);    //头结点的后继节点    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);}
复制代码


一般情况下只要唤醒后继结点的线程就行了,但是后继结点可能已经取消等待,所以从队列尾部往前回溯,找到离头结点最近的正常结点,并唤醒其线程。


主要注意的是,因为这里是非公平锁,所以唤醒不等于拥有锁,因为在高并发场景下如果有外部的线程也来获取锁,那么此时的同步状态已经改为了 0,CAS 成功获取锁,而s.thread被唤醒后还是也需要通过tryAcquire() 方法去竞争,如果竞争失败则继续阻塞,等着获取的线程再次唤醒自己。


当然,如果使用的是公平锁(fair),那么它就一定会被唤醒,因为其他来的线程不会首先去获取锁,而是直接被放到队尾。

公平锁

加锁流程

对于公平锁我们依旧通过入口lock()分析:


1、lock()FairSync类的方法。


public void lock() {    sync.lock();}
复制代码


2、acquire()


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


3、tryAcquire()FairSync类的方法。


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;        }    }    // 状态不为0,即资源已经被线程占据    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()发现不同点,多了一个hasQueuedPredecessors()方法:


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;    return h != t &&        ((s = h.next) == null || s.thread != Thread.currentThread());}
复制代码


先理解字面意思,该方法是判断队列中是否有优先级更高的等待线程,队列中哪个线程优先级最高?由于头结点是当前获取锁的线程,那么队列中的第二个结点代表的线程优先级最高。


因此,我们需要判断队列中的第二个节点是否存在以及这个节点是否为当前线程。


先把上面 return 的代码分解开来分析:


  • h != t

  • 当它们为fasle说明头节点和尾结点指向同一节点,即上个节点获取锁的节点是头结点 head,然后 CAS 尝试加锁,否者走下面的判断。

  • (s = h.next) == null || s.thread != Thread.currentThread()

  • 第二个节点不存在

  • 这个不存在并不是真的不存在,只是由于 CPU 上下文切换的原因,通过对非公平锁的入队enq()方法我们可以知道节点入队有三步:

  • ① 将待插入结点的 prev 指针 连接到原尾结点。

  • ② CAS 更新尾指针。

  • ③ 把原尾结点的 next 指针指向待插入结点。

  • 因此s = h.next的作用是用来判断 ② 刚执行完成,但是还未执行 ③ 这种情况,如果是这种情况直接返回 true,即s = h.next ==null = true ,那么hasQueuedPredecessors()返回 truetryAcquire()返回 false,然后进入队列乖乖排队。

  • 第二个节点存在且是否代表当前线程

  • 如果s = h.next == null = false,此时第二个节点已经完全插入到队列中,通过s.thread != Thread.currentThread()进行判断,如果为 true,说明不是当前线程,队列中前面还有未执行的线程,所以进入队列乖乖排队。否则,说明队列没有排队的线程了,直接获取锁。

解锁流程

公平锁的释放同非公平锁的释放。

面试题

1、什么是非公平锁,什么是公平锁?


非公平锁:


  1. 第一次去获取锁的时候,会去尝试去加锁。

  2. 如果加锁失败,则去看为什么失败(是否锁被其他线程持有了)。

  3. 在判断的过程中如果锁没有被持有,非公平锁就会去直接加锁(不会判断是否有线程排队),成功则进入同步块,失败则进入队列(并不等于排队)。

  4. 进入队列后如果前面获取锁的节点是头结点 head 则再次尝试加锁,成功则执行同步代码块,失败则park()(真正的排队)。


公平锁:


  1. 第一次去获取锁的时候,不会去尝试加锁,会去看一下前面有没有线程在排队(hasQueuedPredecessors),如果有,则进入队列(并不等于排队)。

  2. 然后还不死心,再次看一下我有没有拿锁的资格(前面那个人是否为 head,同非公平锁),如果有资格(前面节点刚好为 head)则继续拿锁,成功则执行同步块,失败则 park(排队)。


记住一句话:一朝排队,永远排队


2、在解锁过程中,为什么unparkSuccessor() 方法中 for 循环是从 tail 开始而不是 head?


为什么呢?Doug Lea 为什么这么设计?其必然是为了解决某些问题?而这个问题就出在入队过程的enq()方法:


private Node enq(final Node node) {    for (;;) {        Node t = tail;        //若tail为null,说明队列未初始化,先初始化一个空的节点        if (t == null) { // Must initialize            //构造新结点,CAS方式设置为队列首元素,当head==null时更新成功            if (compareAndSetHead(new Node()))              //头结点与尾结点都指向同一个新生结点                tail = head;        } else {//若tail不为null,即已经被初始化过          //将node结点的prev连接到原尾结点            node.prev = t;            //CAS比较结点t是否为尾结点,若是则将尾结点设置为node            if (compareAndSetTail(t, node)) {              //把原尾结点的next指针指向当前结点node                t.next = node;                return t;            }        }    }}
复制代码


可以看到在初始化队列后,else代码块中是没有利用任何手段来保证线程安全的。若有其他线程入队,在入队之前的队列状态为:



  • 若线程 A 到来则先执行node.prev = t,然后并通过 CAS 把当前节点设置为尾节点,此时正常情况下将执行t.next = node,如下:


  • 在正常情况下上面是没问题的,我们知道 CAS 是基于 CPU 的,在高并发场景下,如果此时线程 B 也到来,即当 A 还没有执行完t.next = node这一步时,CPU 发生上下文切换,把时间片给了 B,那么此时线程 B 则开始执行enq()入队操作,不管线程 B 是否执行完成,但此时对于上图中的node节点来说:node.next = null


  • 然后 CPU 发生上下文切换,把时间片给了线程 C ,线程 C 是解锁线程调用unparkSuccessor() 方法,如果此时是从头到尾的方式,则发现node.next = null,会发现没后后继节点了。

  • 但此时再次发生上下文切换,时间片交由线程 A,A 执行t.next = node,则此时node.next = nodeA。所以问题就来了:对于线程 C 来说,后续没有 nodeA 及后续节点,但是对于其它线程来说,却有这个节点


那么为什么从尾部遍历不会出现这种问题呢?


是因为node.prev = t先于 CAS 执行,也就是说,你在将当前节点置为尾部之前就已经把前驱节点赋值了,自然不会出现prev = null的情况。


所以,Doug Lea 有多牛逼不用说了吧。


参考:https://blog.csdn.net/foxException/article/details/108917338


3、为什么选择非公平锁?

一切为了效率。

发布于: 5 小时前
用户头像

Ayue、

关注

个人站点:javatv.net 2019.10.16 加入

学习知识,目光坚毅

评论

发布
暂无评论
一文搞懂ReentrantLock的公平锁和非公平锁