首页 > 编程语言 >京东一面挂在了CAS算法的三大问题上,痛定思痛不做同一个知识点的小丑

京东一面挂在了CAS算法的三大问题上,痛定思痛不做同一个知识点的小丑

时间:2024-03-30 09:22:19浏览次数:25  
标签:count 知识点 CAS int 线程 操作 CPU 三大

写在开头

在介绍synchronized关键字时,我们提到了锁升级时所用到的CAS算法,那么今天我们就来好好学一学这个CAS算法

CAS算法对build哥来说,可谓是刻骨铭心,记得是研二去找实习的时候,当时对很多八股文的内容浅尝辄止,很多深奥的知识点只是知道个概念,源码看的也不深,代码量也不够,京东一面,面试官问了CAS算法,大概的介绍了之后,他紧接着追问CAS的三大问题,在很多面试类书籍中背过ABA问题,然后就囫囵吞枣的答了这个,即便后面在面试官的引导下,也没有说清楚其他两个,最终遗憾败北。

面试官当时给的面试表现是:只注重死记硬背,程序员是一个需要创造性的工作,而不是做一个笔者。回来难过了很久,从那时候起,就痛定思痛,大量的看源码,写demo,争取不做同一个知识点上的小丑!现在回想起来,仍然是一份激励,不知道大家在面试时有没有过窘迫,希望诸君能铭记于心,勉而励之!

原子性问题

好了,废话说太多了,现在进入正题!在之前的文章中调到了并发多线程的三大问题,其中之一就是原子性,讲volatile关键字时,说到它可以保证有序性和可见性但无法保证原子性,啥是原子性呢?

原子性: 一个或者多个操作在 CPU 执行的过程中不被中断的特性;

原子操作: 即最小不可拆分的操作,也就是说操作一旦开始,就不能被打断,直到操作完成。

什么时候原子性问题呢?引用我们之前写过的案例。

【代码示例1】

public class Test {
    //计数变量
    static volatile int count = 0;
    public static void main(String[] args) throws InterruptedException {
        //线程 1 给 count 加 10000
        Thread t1 = new Thread(() -> {
            for (int j = 0; j <10000; j++) {
                count++;
            }
            System.out.println("thread t1 count 加 10000 结束");
        });
        //线程 2 给 count 加 10000
        Thread t2 = new Thread(() -> {
            for (int j = 0; j <10000; j++) {
                count++;
            }
            System.out.println("thread t2 count 加 10000 结束");
        });
        //启动线程 1
        t1.start();
        //启动线程 2
        t2.start();
        //等待线程 1 执行完成
        t1.join();
        //等待线程 2 执行完成
        t2.join();
        //打印 count 变量
        System.out.println(count);
    }
}

我们创建了2个线程,分别对count进行加10000操作,理论上最终输出的结果应该是20000万对吧,但实际并不是,我们看一下真实输出。

输出:

thread t1 count 加 10000 结束
thread t2 count 加 10000 结束
14281

原因:
Java 代码中 的 count++ ,至少需要三条CPU指令:

  • 指令 1:把变量 count 从内存加载到CPU的寄存器
  • 指令 2:在寄存器中执行 count + 1 操作
  • 指令 3:+1 后的结果写入CPU缓存或内存

即使是单核的 CPU,当线程 1 执行到指令 1 时发生线程切换,线程 2 从内存中读取 count 变量,此时线程 1 和线程 2 中的 count 变量值是相等,都执行完指令 2 和指令 3,写入的 count 的值是相同的。从结果上看,两个线程都进行了 count++,但是 count 的值只增加了 1。这种情况多发生在cpu占用时间较长的线程中,若单线程对count仅增加100,那我们就很难遇到线程的切换,得出的结果也就是200啦。
image

解决办法:
可以通过JDK Atomic开头的原子类、synchronized、LOCK解决多线程原子性问题,这其中Atomic开头的原子类就是使用乐观锁的一种实现方式CAS算法实现的,那么在了解CAS算法之前,我们还是要先来聊一聊乐观锁。

乐观锁与悲观锁

乐观锁与悲观锁是一组互反锁。

悲观锁(Pessimistic Lock): 线程每次在处理共享数据时都会上锁,其他线程想处理数据就会阻塞直到获得锁。如 synchronized、java.util.concurrent.locks.ReentrantLock;

【代码示例2】

public void testSynchronised() {
    synchronized (this) {
        // 需要同步的操作
    }
}

private Lock lock = new ReentrantLock();
lock.lock();
try {
   // 需要同步的操作
} finally {
    lock.unlock();
}

乐观锁(Optimistic Lock): 相对乐观,线程每次在处理共享数据时都不会上锁,在更新时会通过数据的版本号机制判断其他线程有没有更新数据,或通过CAS算法实现,乐观锁适合读多写少的应用场景。

版本号机制:
所谓版本号机制,一般是在数据表中加上一个数据版本号 version 字段,来记录数据被修改的次数,线程读取数据时,会把对应的version值也读取下来,当发生更新时,会先将自己读取的version值与数据表中的version值进行比较,如果相同才会更新,不同则表示有其他线程已经抢先一步更新成功,自己继续尝试。

CAS算法:
CAS全称为Compare And Swap(比较与交换),是一种算法,更是一种思想,常用来实现乐观锁,通俗理解就是在更新数据前,先比较一下原数据与期待值是否一致,若一致说明过程中没有其他线程更新过,则进行新值替换,否则更新失败,但失败的线程并不会被挂起,仅是被告知失败,并且允许再次尝试,当然也允许失败的线程放弃操作。

两种锁的优缺点:

  • 乐观锁适用于读多写少的场景,可以省去频繁加锁、释放锁的开销,提高吞吐量;
  • 在写比较多的场景下,乐观锁会因为版本号不一致,不断重试更新,产生大量自旋,消耗 CPU,影响性能。这种情况下,适合悲观锁。

CAS算法

那么CAS算法是如何实现的呢?其实在Java中并没有直接给与实现,而是通过JVM底层实现,底层依赖于一条 CPU 的原子指令。那我们在Java中怎么使用,或者说哪里准寻CAS的痕迹呢? 别急,跟着build哥继续向下看!

我们在上面提到了JDK Atomic开头的原子类可以解决原子性问题,那我们就跟进去一探究竟,首先,进入到 java.util.concurrent.atomic 中,里面支持原子更新数组、基本数据类型、引用、字段等,如下图:

image

现在,我们以比较常用的AtomicInteger为例,选取其getAndAdd(int delta)方法,看一下它的底层实现。

【源码解析1】

public final int getAndAdd(int delta) {
    return unsafe.getAndAddInt(this, valueOffset, delta);
}

这里返回的时Unsafe类的getAndAddInt()方法,Unsafe类在sun.misc包中。我们继续根据方法中看源码:

【源码解析2】

 public final int getAndAddInt(Object var1, long var2, int var4) {
     int var5;
     do {
         var5 = this.getIntVolatile(var1, var2);
     } while(!this.compareAndSwapInt(var1, var2, var5, var5 + var4));

     return var5;
 }

我们看一下方法中的参数含义

  • Object var1 :这个参数代表你想要进行操作的对象的起始地址,如:0x00000111。
  • long var2:这个参数是你想要操作的 var1对象中的偏移量。这个偏移量可以通过 Unsafe 类的 objectFieldOffset 方法获得。通俗理解就是需要修改的具体内存地址:如100 ,0x0000011+100 = 0x0000111就是要修改的值的最终内存地址。
  • int var4 :这个参数是你想要增加的值。

首先,在这个方法中采用了do-while循环,通过getIntVolatile(var1, var2)获取当前对象指定的字段值,并将其存入var5中作为预期值,这里的getIntVolatile方法可以保证读取的可见性(禁止指令重拍和CPU缓存,这个之前的文章里解释过,不然冗述);

然后,在while中调用了Unsafe类的compareAndSwapInt()方法,进行数据的CAS操作。其实在这个类中有好几个CAS操作的实现方法

【源码解析3】

/**
  *  CAS
  * @param o         包含要修改field的对象
  * @param offset    对象中某field的偏移量
  * @param expected  期望值
  * @param update    更新值
  * @return          true | false
  */
public final native boolean compareAndSwapObject(Object o, long offset,  Object expected, Object update);

public final native boolean compareAndSwapInt(Object o, long offset, int expected,int update);

public final native boolean compareAndSwapLong(Object o, long offset, long expected, long update);

这几个方法都是native方法,相关的实现是通过 C++ 内联汇编的形式实现的(JNI 调用),因此,和cpu与操作系统都有关系,这也是我们在上文中提到CAS失败后,大量自旋带来CPU消耗严重的原因。

继续,我们回到compareAndSwapInt(var1, var2, var5, var5 + var4)方法中来,我们通过var1对象在var2内存地址上的值与先查到的预期值比较一致性,若相等,则将var5 + var4更新到对应地址上,返回true,否则不做任何操作返回false。

如果 CAS 操作成功,说明我们成功地将 var1 对象的 var2 偏移量处的字段的值更新为 var5 + var4,并且这个更新操作是原子性的,因此我们跳出循环并返回原来的值 var5。

如果 CAS 操作失败,说明在我们尝试更新值的时候,有其他线程修改了该字段的值,所以我们继续循环,重新获取该字段的值,然后再次尝试进行 CAS 操作。

注意: 以上是JDK1.8的源码,在JDK1.9后底层实现逻辑略有改动,增加了@HotSpotIntrinsicCandidate 注解,这个注解允许 HotSpot VM 自己来写汇编或 IR 编译器来实现该方法以提供更加的性能。

CAS带来的三大问题

文章写到这里,终于进入了关键,CAS虽然作为一种不加锁就可以实现高效同步的手段,但它并非完美,仍然存在着很多问题,主要分为三个,分别是:ABA问题长时间自旋多个共享变量的原子操作,这三个问题也是面试官提及CAS时常问的,希望大家能够理解记住,避免像build哥初入职场时的尴尬!

ABA问题

这是CAS非常经典的问题,由于CAS是否执行成功,是需要将当前内存中的值与期望值做判断,根据是否相等,来决定是否修改原值的,若一个变量V在初始时的值为A,在赋值前去内存中检查它的值依旧是A,这时候我们就想当然认为它没有变过,然后就继续进行赋值操作了,很明显这里是有漏洞的,虽然赋值的操作用时可能很短,但在高并发时,这个A值仍然有可能被其他线程改为了B之后,又被改回了A,那对于我们最初的线程来说,是无法感知的。

很多人可能会问,既然这个变量从A->B->A,这个过程中,它不还是原来的值吗,过程不同但结果依旧没变呀,会导致什么问题呢?我们看下面这个例子:

小明在提款机,提取了50元,因为提款机卡住了,小明点击后,又点击了一次,产生了两个修改账户余额的线程(可以看做是线程1和线程2),假设小明账户原本有100元,因此两个线程同时执行把余额从100变为50的操作。
线程1(提款机):获取当前值100,期望更新为50。
线程2(提款机):获取当前值100,期望更新为50。
线程1成功执行,CPU并没有调度线程2执行,
这时,小华给小明转账50,这一操作产生了线程3,CPU调度线程3执行,这时候线程3成功执行,余额变为100。之后,线程2被CPU调度执行,此时,获取到的账户余额是100,CAS操作成功执行,更新余额为50!此时可以看到,实际余额应该为100(100-50+50),但是实际上变为了50(100-50+50-50)。

这就是ABA问题带来的错误,而对于一个银行的提款机来说,发生这种问题可以说是灾难性的,会大大降低客户对于这家银行的信任程度!

那有没有什么解决方案呢,答案是肯定的!在JDK 1.5 以后的 AtomicStampedReference 类就是用来解决 ABA 问题的,其中的 compareAndSet() 方法就是首先检查当前引用是否等于预期引用,并且当前标志是否等于预期标志,如果全部相等,则以原子方式将该引用和该标志的值设置为给定的更新值。

【源码解析4】

public boolean compareAndSet(V   expectedReference,
                             V   newReference,
                             int expectedStamp,
                             int newStamp) {
    Pair<V> current = pair;
    return
        expectedReference == current.reference &&
        expectedStamp == current.stamp &&
        ((newReference == current.reference &&
          newStamp == current.stamp) ||
         casPair(current, Pair.of(newReference, newStamp)));
}

长时间自旋

我们在前面说过CAS适用于读多写少的场景,若被使用在写多的场景,必然会产品大量的版本号不一致情况,从而导致很多线程自旋等待,这对CPU来说很糟糕,可以通过让JVM 能支持处理器提供的 pause 指令,这样对效率会有一定的提升。

PAUSE指令提升了自旋等待循环(spin-wait loop)的性能。当执行一个循环等待时,Intel P4或Intel Xeon处理器会因为检测到一个可能的内存顺序违规(memory order violation)而在退出循环时使性能大幅下降。PAUSE指令给处理器提了个醒:这段代码序列是个循环等待。处理器利用这个提示可以避免在大多数情况下的内存顺序违规,这将大幅提升性能。因为这个原因,所以推荐在循环等待中使用PAUSE指令。

多个共享变量的原子操作

当对一个共享变量执行操作时,CAS 能够保证该变量的原子性。但是对于多个共享变量,CAS 就无法保证操作的原子性,这时通常有两种做法:

  1. 使用AtomicReference类保证对象之间的原子性,把多个变量放到一个对象里面进行 CAS 操作;
  2. 使用锁。锁内的临界区代码可以保证只有当前线程能操作。

总结

关于CAS算法以及其存在的三大问题到这里就说完了,现在再回头来看,京东这道面试题很简单,然而由于当年的不努力变成了一种遗憾说出,希望小伙伴们能够引以为戒!

结尾彩蛋

如果本篇博客对您有一定的帮助,大家记得留言+点赞+收藏呀。原创不易,转载请联系Build哥!

image

如果您想与Build哥的关系更近一步,还可以关注“JavaBuild888”,在这里除了看到《Java成长计划》系列博文,还有提升工作效率的小笔记、读书心得、大厂面经、人生感悟等等,欢迎您的加入!

image

标签:count,知识点,CAS,int,线程,操作,CPU,三大
From: https://www.cnblogs.com/JavaBuild/p/18105028

相关文章

  • 总结TCP各类知识点
    前言本篇博客博主将详细地介绍TCP有关知识点,坐好板凳发车啦~一.TCP特点1.有连接TCP传输的过程中类似于打电话的各个过程2.可靠传输通过TCP自身的多种机制来保证可靠传输3.面向字节流内容是以字节的方式来进行发送与接收4.缓冲区TCP有接收缓冲区,也有发送缓冲区全双工......
  • 深入解析实时数仓Doris:三大数据模型详解
    码到三十五:个人主页心中有诗画,指尖舞代码,目光览世界,步履越千山,人间尽值得!目录一、基本概念二、Aggregate模型导入数据聚合三、Unique模型四、Duplicate模型五、数据模型的选择建议一、基本概念在Doris中,数据以表(Table)的形式进行逻辑上的......
  • 【知识点】hashcode和equals
    哈希计算(Hashing)是一种将数据通过哈希函数(HashFunction)转换成固定长度的值(hashvalue)的过程,是一个通用的计算方式。在Java中的表现就是hashcode()方法,在Object类上,常用于HashMap、HashSet等集合中,用于快速查找、唯一约束等作用。equals()方法是从逻辑上判断两个对象是否相等,如......
  • 【SQL】1661. 每台机器的进程平均运行时间 (四种写法;自连接;case when;窗口函数lead();)
    前述Sql窗口分析函数【lead、lag详解】Hive分析函数lead、lag实例应用lag:用于统计窗口内往上第n行值lead:用于统计窗口内往下第n行值lead(列名,1,0)over(partitionby分组列orderby排序列rowsbetween开始位置precedingand结束位置following)lag和lead......
  • 网络工程师之路由交换组合配置知识点相关技术方法解析
    网络工程师之路由交换组合配置相关技术方法解析交换机部分配置参数vlanif的配置环回的配置vlanbatch配置允许通过trunk口ospf的配置disospfpeerbdisipconospf带宽:默认100bandwidth-reference10000{所有运行ospf的都改}100/10010000/100备份配置:创......
  • 面试题知识点笔记-MySQL开发
    目录可以使用MySQL直接存储文件(ppt,exel,图像等)吗?什么时候存,什么时候不存?Emoji乱码怎么办?存储的时候有遇到过什么问题吗?如何存储ip地址?长文本如何存储?大段文本如何设计表结构?大段文本查找时如何建立索引?有没有在开发中使用过TEXT,BLOB数据类型日期,时间如何存......
  • 面试题知识点笔记-MySQL日志
    目录MysqI会产生几种日志?binlog作用是什么?redolog作用是什么?undolog作用是什么?Mysql日志是否实时写入磁盘?binlog刷盘机制是如何实现的?redolog刷盘机制是如何实现的?undolog刷盘机制是如何实现的?MySQL的binlog有有几种录入格式?分别有什么区别?Mysq!集群同......
  • [SpringMVC]知识点
    【版权声明】未经博主同意,谢绝转载!(请尊重原创,博主保留追究权)https://www.cnblogs.com/cnb-yuchen/p/18032069出自【进步*于辰的博客】目录1、什么是SpringMVC?1.1概述1.2示例6、restful风格6.1概述6.2使用细节7、自定义异常处理器8、自定义类型转换器最后1、什么是Spring......
  • C. Sasha and the Casino
    原题链接题解1.要确保任意回合赢回来的钱都要比之前下注的钱的总和要多令\(b_i\)为第\(i\)回合下注的钱,则有\(b_i·k>\sum_{j=1}^{i}b_j\)则有\(b_i\ge\left\lfloor\frac{\sum_{j=1}^{i-1}b_j}{k-1}\right\rfloor+1\)为了尽可能地不把钱花光,选最小的\(b_i\)2.如......
  • 必备知识点 模版
    模版1.寻找html模版TEMPLATES=[{'BACKEND':'django.template.backends.django.DjangoTemplates','DIRS':[os.path.join(BASE_DIR,'templates')],'APP_DIRS':True,'OPTION......