专栏首页Linyb极客之路你必须要知道的热门 ReentrantLock 及 AQS 的实现原理

你必须要知道的热门 ReentrantLock 及 AQS 的实现原理

提到 JAVA 加锁,我们通常会想到 synchronized 关键字或者是 Java Concurrent Util(后面简称JCU)包下面的 Lock,今天就来扒一扒 Lock 是如何实现的,比如我们可以先提出一些问题:当我们通实例化一个 ReentrantLock 并且调用它的 lock 或 unlock 的时候,这其中发生了什么?如果多个线程同时对同一个锁实例进行 lock 或 unlcok 操作,这其中又发生了什么?

什么是可重入锁?

ReentrantLock 是可重入锁,什么是可重入锁呢?可重入锁就是当前持有该锁的线程能够多次获取该锁,无需等待。可重入锁是如何实现的呢?这要从 ReentrantLock 的一个内部类 Sync 的父类说起,Sync 的父类是 AbstractQueuedSynchronizer(后面简称AQS)。

什么是AQS?

AQS 是 JDK1.5 提供的一个基于 FIFO 等待队列实现的一个用于实现同步器的基础框架,这个基础框架的重要性可以这么说,JCU 包里面几乎所有的有关锁、多线程并发以及线程同步器等重要组件的实现都是基于 AQS 这个框架。AQS 的核心思想是基于 volatile int state 这样的一个属性同时配合 Unsafe 工具对其原子性的操作来实现对当前锁的状态进行修改。当 state 的值为 0 的时候,标识改 Lock 不被任何线程所占有。

ReentrantLock 锁的架构

ReentrantLock 的架构相对简单,主要包括一个 Sync 的内部抽象类以及 Sync 抽象类的两个实现类。上面已经说过了 Sync 继承自 AQS,他们的结构示意图如下:

上图除了 AQS 之外,我把 AQS 的父类 AbstractOwnableSynchronizer(后面简称AOS)也画了进来,可以稍微提一下,AOS 主要提供一个 exclusiveOwnerThread 属性,用于关联当前持有该所的线程。另外、Sync 的两个实现类分别是 NonfairSync 和 FairSync,由名字大概可以猜到,一个是用于实现公平锁、一个是用于实现非公平锁。那么 Sync 为什么要被设计成内部类呢?我们可以看看 AQS 主要提供了哪些 protect 的方法用于修改 state 的状态,我们发现 Sync 被设计成为安全的外部不可访问的内部类。ReentrantLock 中所有涉及对 AQS 的访问都要经过 Sync,其实,Sync 被设计成为内部类主要是为了安全性考虑,这也是作者在 AQS 的 comments 上强调的一点。

AQS 的等待队列

作为 AQS 的核心实现的一部分,举个例子来描述一下这个队列长什么样子,我们假设目前有三个线程 Thread1、Thread2、Thread3 同时去竞争锁,如果结果是 Thread1 获取了锁,Thread2 和 Thread3 进入了等待队列,那么他们的样子如下:

AQS 的等待队列基于一个双向链表实现的,HEAD 节点不关联线程,后面两个节点分别关联 Thread2 和 Thread3,他们将会按照先后顺序被串联在这个队列上。这个时候如果后面再有线程进来的话将会被当做队列的 TAIL。

1)入队列

我们来看看,当这三个线程同时去竞争锁的时候发生了什么?代码:

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

解读:三个线程同时进来,他们会首先会通过 CAS 去修改 state 的状态,如果修改成功,那么竞争成功,因此这个时候三个线程只有一个 CAS 成功,其他两个线程失败,也就是 tryAcquire 返回 false。接下来,addWaiter 会把将当前线程关联的 EXCLUSIVE 类型的节点入队列:

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);
    return node;
}

解读:如果队尾节点不为 null,则说明队列中已经有线程在等待了,那么直接入队尾。对于我们举的例子,这边的逻辑应该是走 enq,也就是开始队尾是 null,其实这个时候整个队列都是 null 的。代码:

private Node enq(final Node node) {
    for (;;) {
        Node t = tail;
        if (t == null) { // Must initialize
            if (compareAndSetHead(new Node()))
                tail = head;
        } else {
            node.prev = t;
            if (compareAndSetTail(t, node)) {
                t.next = node;
                return t;
            }
        }
    }
}

解读:如果 Thread2 和 Thread3 同时进入了 enq,同时 t==null,则进行 CAS 操作对队列进行初始化,这个时候只有一个线程能够成功,然后他们继续进入循环,第二次都进入了 else 代码块,这个时候又要进行 CAS 操作,将自己放在队尾,因此这个时候又是只有一个线程成功,我们假设是 Thread2 成功,哈哈,Thread2 开心的返回了,Thread3 失落的再进行下一次的循环,最终入队列成功,返回自己。

2)并发问题

基于上面两段代码,他们是如何实现不进行加锁,当有多个线程,或者说很多很多的线程同时执行的时候,怎么能保证最终他们都能够乖乖的入队列而不会出现并发问题的呢?这也是这部分代码的经典之处,多线程竞争,热点、单点在队列尾部,多个线程都通过【CAS+死循环】这个free-lock黄金搭档来对队列进行修改,每次能够保证只有一个成功,如果失败下次重试,如果是N个线程,那么每个线程最多 loop N 次,最终都能够成功。

3)挂起等待线程

上面只是 addWaiter 的实现部分,那么节点入队列之后会继续发生什么呢?那就要看看 acquireQueued 是怎么实现的了,为保证文章整洁,代码我就不贴了,同志们自行查阅,我们还是以上面的例子来看看,Thread2 和 Thread3 已经被放入队列了,进入 acquireQueued 之后:

  1. 对于 Thread2 来说,它的 prev 指向 HEAD,因此会首先再尝试获取锁一次,如果失败,则会将 HEAD 的 waitStatus 值为 SIGNAL,下次循环的时候再去尝试获取锁,如果还是失败,且这个时候 prev 节点的 waitStatus 已经是 SIGNAL,则这个时候线程会被通过 LockSupport 挂起。
  2. 对于 Thread3 来说,它的 prev 指向 Thread2,因此直接看看 Thread2 对应的节点的 waitStatus 是否为 SIGNAL,如果不是则将它设置为 SIGNAL,再给自己一次去看看自己有没有资格获取锁,如果 Thread2 还是挡在前面,且它的 waitStatus 是 SIGNAL,则将自己挂起。

如果 Thread1 死死的握住锁不放,那么 Thread2 和 Thread3 现在的状态就是挂起状态啦,而且 HEAD,以及 Thread 的 waitStatus 都是 SIGNAL,尽管他们在整个过程中曾经数次去尝试获取锁,但是都失败了,失败了不能死循环呀,所以就被挂起了。当前状态如下:

锁释放-等待线程唤起

我们来看看当 Thread1 这个时候终于做完了事情,调用了 unlock 准备释放锁,这个时候发生了什么。代码:

public final boolean release(int arg) {
    if (tryRelease(arg)) {
        Node h = head;
        if (h != null && h.waitStatus != 0)
            unparkSuccessor(h);
        return true;
    }
    return false;
}

解读:首先,Thread1 会修改AQS的state状态,加入之前是 1,则变为 0,注意这个时候对于非公平锁来说是个很好的插入机会,举个例子,如果锁是公平锁,这个时候来了 Thread4,那么这个锁将会被 Thread4 抢去。。。

我们继续走常规路线来分析,当 Thread1 修改完状态了,判断队列是否为 null,以及队头的 waitStatus 是否为 0,如果 waitStatus 为 0,说明队列无等待线程,按照我们的例子来说,队头的 waitStatus 为 SIGNAL=-1,因此这个时候要通知队列的等待线程,可以来拿锁啦,这也是 unparkSuccessor 做的事情,unparkSuccessor 主要做三件事情:

  1. 将队头的 waitStatus 设置为 0。
  2. 通过从队列尾部向队列头部移动,找到最后一个 waitStatus<=0 的那个节点,也就是离队头最近的没有被cancelled的那个节点,队头这个时候指向这个节点。
  3. 将这个节点唤醒,其实这个时候 Thread1 已经出队列了。

还记得线程在哪里挂起的么,上面说过了,在 acquireQueued 里面,我没有贴代码,自己去看哦。这里我们也大概能理解 AQS 的这个队列为什么叫 FIFO 队列了,因此每次唤醒仅仅唤醒队头等待线程,让队头等待线程先出。

羊群效应

这里说一下羊群效应,当有多个线程去竞争同一个锁的时候,假设锁被某个线程占用,那么如果有成千上万个线程在等待锁,有一种做法是同时唤醒这成千上万个线程去去竞争锁,这个时候就发生了羊群效应,海量的竞争必然造成资源的剧增和浪费,因此终究只能有一个线程竞争成功,其他线程还是要老老实实的回去等待。AQS 的 FIFO 的等待队列给解决在锁竞争方面的羊群效应问题提供了一个思路:保持一个 FIFO 队列,队列每个节点只关心其前一个节点的状态,线程唤醒也只唤醒队头等待线程。其实这个思路已经被应用到了分布式锁的实践中,见:Zookeeper 分布式锁的改进实现方案。

总结

这篇文章粗略的介绍一下 ReentrantLock 以及锁实现基础框架 AQS 的实现原理,大致上通过举了个三个线程竞争锁的例子,从 lock、unlock 过程发生了什么这个问题,深入了解 AQS 基于状态的标识以及 FIFO 等待队列方面的工作原理,最后扩展介绍了一下羊群效应问题。

本文分享自微信公众号 - Linyb极客之路(gh_c420b2cf6b47),作者:Float_Luuu

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-05-13

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • JVM内存模型和性能优化之线程锁优化(下篇)

    当一个线程更新了自己工作内存中的数据后,没有写到主内存,其他线程是不知道的。 (1)顺序一致性模型: 要求对改变的值立即进行传播, 并确保该值被所有...

    lyb-geek
  • JAVA多线程和并发基础面试问答

    一个进程是一个独立(self contained)的运行环境,它可以被看作一个程序或者一个应用。而线程是在进程中执行的一个任务。Java运行环境是一个包含了不同...

    lyb-geek
  • 干货:Java并发编程必懂知识点解析(内附面试题)

    原子,即一个不可再被分割的颗粒。在Java中原子性指的是一个或多个操作要么全部执行成功要么全部执行失败。

    lyb-geek
  • Java Concurrent AQS原理&源码概要(Java 10)

    开始说AQS之前,继续说上一篇没说完的建议,相对于看一些不知道时效性的blog,说实话,理解一个知识点最简便的方式就是看论文及源码实现了,解决一个问题最好的方式...

    邹志全
  • Java并发编程笔记——J.U.C之executors框架:ScheduledThreadPoolExecutor

    在executors框架设计理念 一节中,我们曾经提到过一种可对任务进行延迟/周期性调度的执行器(Executor),这类Executor一般实现了Schedu...

    须臾之余
  • AQS(上) 同步队列AQS介绍篇

    AbstractQueuedSynchronizer抽象同步队列简称AQS,它是实现同步器的基础组件,并发包中锁的底层就是使用AQS实现的。另外,大多数开发者可...

    YanL
  • Java多线程—AQS框架源码阅读

    AQS,全称AbstractQueuedSynchronizer,是Concurrent包锁的核心,没有AQS就没有Java的Concurrent包。

    Zack说码
  • Java基础之Synchronized原理

    思维导图svg: https://note.youdao.com/ynoteshare1/index.html?id=eb05fdceddd07759b8b8...

    Ryan-Miao
  • 不用synchronized块的话如何实现一个原子的i++?

    上周被问到这个问题,没想出来,后来提示说concurrent包里的原子类。回来学习一下。 一、何谓Atomic?  Atomic一词跟原子有点关系,后者曾被人认...

    老白
  • 高并发编程-CyclicBarrier深入解析

    CyclicBarrier是一个同步辅助类,它允许一组线程互相等待,直到所有线程都到达某个公共屏障点(也可以叫同步点),即相互等待的线程都完成调用await方法...

    JavaQ

扫码关注云+社区

领取腾讯云代金券