深入剖析AQS和CAS,看了都说好

本人花费半年的时间总结的《Java面试指南》已拿腾讯等大厂offer,已开源在github ,欢迎star!

转载声明:转载请注明出处,本技术博客是本人原创文章

本文GitHub https://github.com/OUYANGSIHAI/JavaInterview 已收录,这是我花了6个月总结的一线大厂Java面试总结,本人已拿大厂offer,欢迎star

原文链接:blog.ouyangsihai.cn >> 深入剖析AQS和CAS,看了都说好

点击上方 **好好学java **,选择 **星标 **公众号


重磅资讯、干货,第一时间送达


今日推荐:

个人原创100W+访问量博客:点击前往,查看更多

前言

不知不觉写文章已经快半年了,本来之前写文章只是为了自己总结知识,不知不觉中关注的朋友越来越多了。

现在写文章不单单只是为了考虑自己能看懂,还要考虑各位读者大大是否能看懂,考虑输出文章的质量。

现在的每一次写作就好像在搞一次艺术品,细细雕琢,进行每一次的加工。文章的「逻辑性」「易懂性」,还有「文章的排版的美观度」,都要细细斟酌。

写在前面先来一碗鸡汤:「世界上并没有什么救世主,假如有那便是你自己;世界上也没有什么奇迹,假如有那只是努力的另一个名字罢了。」

想想自己毕业差不多一年来走过来的路,看看现在的自己,一切都值得,往后还会不断的努力,看到越来越强的自己。

上一篇讲到Redis篇的内存满了的问题,并带说明了这篇文章[]比较受欢迎,然后一下子的阅读量升到1.1k,感谢读者大大们的肯定。

话不多说下面就直接上干货了,今天来深入的了解 CAS AQS,文章采用层次式、图文并茂的方式一层一层的进行剖析,让各位读者大大能够深入理解。

AQS简介

AQS(AbstractQueuedSynchronizer)「抽象队列同步器」,简单的说「AQS就是一个抽象类」,抽象类就是 AbstractQueuedSynchronizer,没有实现任何的接口,「仅仅定义了同步状态(state)的获取和释放的方法」

它提供了一个「FIFO队列」,多线程竞争资源的时候,没有竞争到的线程就会进入队列中进行等待,并且「定义了一套多线程访问共享资源的同步框架」

在AQS中的锁类型有两种:分别是「Exclusive(独占锁)「和」Share(共享锁)」

「独占锁」就是「每次都只有一个线程运行」,例如 ReentrantLock。关于ReentrantLock之前写过一篇详细的源码文章,喜欢的可以看一看[]。

「共享锁」就是「同时可以多个线程运行」,如 Semaphore、``CountDownLatch、ReentrantReadWriteLock

AQS源码分析

在AQS的源码可以看到对于「state共享变量」,使用「volatile关键字」进行修饰,从而「保证了可见性」,若是对于volatile关键字不熟悉的可以参考这一篇[]。从上面的源码中可以看出,对于state的修改操作提供了 setState compareAndSetState「那么为什么要提供这两个对state的修改呢?」

因为 compareAndSetState方法「通常使用在获取到锁之前」,当前线程不是锁持有者,对于state的修改可能存在线程安全问题,所以「需要保证对state修改的原子性操作」

setState方法通常用于当前正持有锁的线程对「state共享变量」进行修改,因为不存在竞争,是线程安全的,所以没必要使用CAS操作。

分析了AQS的源码的实现,接下来我们看看AQS的实现的原理。这里AQS的实现源码和理论都会比较简单,因为还没有涉及到具体的实现类。

AQS实现原理

上面说到AQS中维护了一个「FIFO队列」,并且「该队列是一个双向链表」,链表中的每一个节点为「Node节点」「Node类是AbstractQueuedSynchronizer中的一个内部类」

让我们来看看AQS中Node内部类的源码,这样有助于我们能够对AQS的内部的实现更加的清晰:


 static final class Node {

        static final Node SHARED = new Node();
        static final Node EXCLUSIVE = null;
        static final int CANCELLED =  1;
        static final int SIGNAL    = -1;
        static final int CONDITION = -2;
        static final int PROPAGATE = -3;
        volatile int waitStatus;
        volatile Node prev;
        volatile Node next;
        volatile Thread thread;
        Node nextWaiter;

        final boolean isShared() {
            return nextWaiter == SHARED;
        }

        final Node predecessor() throws NullPointerException {
            Node p = prev;
            if (p == null)
                throw new NullPointerException();
            else
                return p;
        }

        Node() {    // Used to establish initial head or SHARED marker
        }

        Node(Thread thread, Node mode) {     // Used by addWaiter
            this.nextWaiter = mode;
            this.thread = thread;
        }

        Node(Thread thread, int waitStatus) { // Used by Condition
            this.waitStatus = waitStatus;
            this.thread = thread;
        }
    }

可以看到上面的Node类比较简单,只是对于每个Node节点拥有的属性进行维护,在Node内部类中最重要的基本构成就是这几个:


    volatile Node prev;
    volatile Node next;
    volatile Thread thread;

「根据源码的分析和线程的竞争共享资源的原理」,关于AQS的实现原理,我这里画了一张图:在FIFO队列中,「头节点占有锁」,也就是头节点才是锁的持有者,尾指针指向队列的最后一个等待线程节点,除了头节点和尾节点,节点之间都有「前驱指针」「后继指针」

在AQS中维护了一个「共享变量state」,标识当前的资源是否被线程持有,多线程竞争的时候,会去判断state是否为0,尝试的去把state修改为1

分析了AQS的源码的实现和原理实现,但是AQS里面具体是没有做同步的具体实现,如果要什么了解AQS的具体的实现原理,要需要看AQS的具体实现类,这边就以 ReentrantLock为例。

ReentrantLock实现原理

如果多线程在竞争共享资源时,「竞争失败的线程就会添加入FIFO队列的尾部」

ReentrantLock的的具体实现中,这边以在ReentrantLock的非公平锁的实现为例,因为公平锁的实现,之前已经写过一篇文章分析过了。

我们来看看新添加节点的源码写的实现逻辑:当竞争锁资源的线程失败后直接进入 acquire(1)方法,来来看看acquire(1)的具体实现:从源码中可以看出,acquire(1)的实现主要有这三步的逻辑:

  1. tryAcquire(arg):尝试再次获取锁。1. addWaiter(Node.EXCLUSIVE):若是获取锁失败,就会将当前线程组装成一个Node节点,进行入队操作。1. acquireQueued(addWaiter(Node.EXCLUSIVE), arg)):acquireQueued方法以addWaiter返回的头节点作为参数,内部实现进行锁自旋,以及判断是否应该执行线程挂起。
    下面我们再来看看 tryAcquire(arg)的源码,从上面的看一看出arg的值为1,具体的实现源码如下:从源码的分析中可以看出, tryAcquire(arg)的实现也就是判断state的值是否已经被释放,「若释放则当前线程就会CAS操作将state设置为1,若是没有释放,就会判断是否可以进行锁的重入」

分析完 tryAcquire(arg)的实现,来看看 addWaiter,入队操作的实现源码如下:从上面的源码分析,可以看出对于新加入的线程添加到双向链表中使用尾插法,具体的实现原理图如下所示。从上图分析,当线程加入队列中,主要进行这几步操作「新加入的节点prev指针指向原来的tail节点,原来的tail节点的next指针指向新加入的节点」,这个也就是常见的「双向链表尾插法」的操作。

「最后把tail指向新加入的节点」,如此一来就完成了新加入节点的入队操作,接下来我们接着分析源码。

当然这里的前提是「队列中不为空」,若是为空的话,不会走上面的逻辑,而是走 enq(node),进行初始化节点,我们来看看 enq(node)操作,源码如下:执行完上面的入对操作后,接着执行 acquireQueued方法,来看看它的具体实现源码:从上上面的源码中可以看出,涉及到「头节点head的出队」操作,并且将「当前线程的node节点晋升为head节点」

因为只有「头节点才是锁的持有者」,所以对于head节点的出队操作,head的指向会随时改变,我这里画了一张原理图如下所示:具体实现如上图所示,会把「原来的头节点进行出队操作,也就是把原来的头节点next指针指向null,原来第二节点的prev指针指向null」

最后把head指针指向第二节点,当然thread2同时还会修改共享状态变量state的值,如此一来就完成了锁的释放。

当释放完锁之后,就会执行 shouldParkAfterFailedAcquire(p, node) &&parkAndCheckInterrupt()判断当前的线程是否应该被挂起,我们来看看它的源码实现: shouldParkAfterFailedAcquire中的实现,当前驱节点的状态量 waitStatus SIGNAL的时候,就会挂起。通过上面的分析对于AQS的实现基本有比较清晰的认识,主要是对实现类 ReentrantLock的实现原理进行深入的分析,并且是基于「非公平锁」「独占锁」的实现。

在AQS的底层维护了一个「FIFO队列」,多线程竞争共享资源的时候,「失败的线程会被添加入队列中」「非公平锁」实现中,新加入的线程节点会「自旋」尝试的获取锁。

分析完AQS我们来分析CAS,「那么什么是CAS呢?」

CAS简介

在分析 ReentrantLock的具体实现的源码中,可以看出所有涉及设置共享变量的操作,都会指向CAS操作,保证原子性操作。

CAS(compare and swap)原语理解就是比较并交换的意思,「CAS是一种乐观锁的实现」

在CAS的算法实现中有三个值:「更新的变量」「旧的值」「新值」。在修改共享资源时候,会与原值进行比较,若是等于原值,就修改为新值。

于是在这里的算法实现下,即使不加锁,也能保证数据的可见性,即使的发现数据是否被更改,若是数据已经被更新则写操作失败。

但是CAS也会引发ABA的问题,「什么是ABA问题呢?」 不慌请听我详细道来

ABA问题

ABA问题就是假如有两个线程,同一时间读取一个共享变量 state=1,此时两个线程都已经将state的副本赋值到自己的工作内存中。

当线程一对state修改 state=state+1,并且写入到主存中,然后线程一又对 state=state-1写入到主存,此时主存的state是变化了两次,只不过又变回了原来的值。

那么此时线程二修改state的时候就会修改成功,这就是ABA问题。对于「ABA问题的解决方案就是加版本号(version)」,每次进行比较的时候,也会比较版本号。

因为版本版是只增不减,比如以时间作为版本号,每一时刻的时间都不一样,这样就能避免ABA的问题。

CAS性能分析

相对于「synchronized的阻塞算法」的实现,「CAS采用的是乐观锁的非阻塞算法」的实现,一般CPU在进行线程的上下文切换的时间比执行CPU的指令集的时间长,所以CAS操作在性能上也有了很大的提升。

但是所有的算法都是没有最完美的,在执行CAS的操作中,没有更新成功的就会自旋,这样也会消耗CPU的资源,对于CPU来说是不友好的。


最后,再附上我历时三个月总结的 Java 面试 + Java 后端技术学习指南,笔者这几年及春招的总结,github 1.4k star,拿去不谢!

下载方式1. 首先扫描下方二维码
2. 后台回复「Java面试」即可获取

原文地址:https://sihai.blog.csdn.net/article/details/109466003

本人花费半年的时间总结的《Java面试指南》已拿腾讯等大厂offer,已开源在github ,欢迎star!

转载声明:转载请注明出处,本技术博客是本人原创文章

本文GitHub https://github.com/OUYANGSIHAI/JavaInterview 已收录,这是我花了6个月总结的一线大厂Java面试总结,本人已拿大厂offer,欢迎star

原文链接:blog.ouyangsihai.cn >> 深入剖析AQS和CAS,看了都说好


 上一篇
新手一看就懂的线程池 新手一看就懂的线程池
点击上方 **好好学java **,选择 **星标 **公众号 重磅资讯、干货,第一时间送达 今日推荐:个人原创100W+访问量博客:点击前往,查看更多 相信大家也能感受到,其实用多线程是很麻烦的,包括线程的创建、销毁和调度等等,而
2021-04-04
下一篇 
当Docker遇到Intellij IDEA,再次解放了生产力~ 当Docker遇到Intellij IDEA,再次解放了生产力~
点击上方 **好好学java **,选择 **星标 **公众号 重磅资讯、干货,第一时间送达 今日推荐:个人原创100W+访问量博客:点击前往,查看更多 本文来源:https://juejin.im/post/5d026212f26
2021-04-04