企业网站ui设计欣赏,建设网站上申请劳务资质,网页设计在线培训网站有哪些,微信网页版官网二维码写在开头 在介绍synchronized关键字时#xff0c;我们提到了锁升级时所用到的CAS算法#xff0c;那么今天我们就来好好学一学这个CAS算法。
CAS算法对build哥来说#xff0c;可谓是刻骨铭心#xff0c;记得是研二去找实习的时候#xff0c;当时对很多八股文的内容浅尝辄止…写在开头 在介绍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 加 10000Thread t1 new Thread(() - {for (int j 0; j 10000; j) {count;}System.out.println(thread t1 count 加 10000 结束);});//线程 2 给 count 加 10000Thread t2 new Thread(() - {for (int j 0; j 10000; j) {count;}System.out.println(thread t2 count 加 10000 结束);});//启动线程 1t1.start();//启动线程 2t2.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 操作 指令 31 后的结果写入CPU缓存或内存 即使是单核的 CPU当线程 1 执行到指令 1 时发生线程切换线程 2 从内存中读取 count 变量此时线程 1 和线程 2 中的 count 变量值是相等都执行完指令 2 和指令 3写入的 count 的值是相同的。从结果上看两个线程都进行了 count但是 count 的值只增加了 1。这种情况多发生在cpu占用时间较长的线程中若单线程对count仅增加100那我们就很难遇到线程的切换得出的结果也就是200啦。 解决办法可以通过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 中里面支持原子更新数组、基本数据类型、引用、字段等如下图 现在我们以比较常用的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 0x0000011100 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这一操作产生了线程3CPU调度线程3执行这时候线程3成功执行余额变为100。之后线程2被CPU调度执行此时获取到的账户余额是100CAS操作成功执行更新余额为50此时可以看到实际余额应该为100100-5050但是实际上变为了50100-5050-50。 这就是ABA问题带来的错误而对于一个银行的提款机来说发生这种问题可以说是灾难性的会大大降低客户对于这家银行的信任程度
那有没有什么解决方案呢答案是肯定的在JDK 1.5 以后的 AtomicStampedReference 类就是用来解决 ABA 问题的其中的 compareAndSet() 方法就是首先检查当前引用是否等于预期引用并且当前标志是否等于预期标志如果全部相等则以原子方式将该引用和该标志的值设置为给定的更新值。
【源码解析4】
public boolean compareAndSet(V expectedReference,V newReference,int expectedStamp,int newStamp) {PairV current pair;returnexpectedReference 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 就无法保证操作的原子性这时通常有两种做法 使用AtomicReference类保证对象之间的原子性把多个变量放到一个对象里面进行 CAS 操作 使用锁。锁内的临界区代码可以保证只有当前线程能操作。 总结 关于CAS算法以及其存在的三大问题到这里就说完了现在再回头来看京东这道面试题很简单然而由于当年的不努力变成了一种遗憾说出希望小伙伴们能够引以为戒 文章转载自JavaBuild 原文链接https://www.cnblogs.com/JavaBuild/p/18105028 体验地址引迈 - JNPF快速开发平台_低代码开发平台_零代码开发平台_流程设计器_表单引擎_工作流引擎_软件架构
