java并发之原子操作类和非阻塞算法

背景

近年来,在并发算法领域的大多数研究都侧重于非阻塞算法,这种算法用底层的原子机器指令(例如比较并发交换指令)代替锁来确保数据在并发访问中的一致性。非阻塞算法被广泛的用于在操作系统和JVM中实现线程/进程调度机制、垃圾回收机制以及锁和其他并发数据结构。

与基于锁的方案相比,非阻塞算法在设计和实现上都要复杂的多,但他们在可伸缩性和活跃性上却拥有巨大的优势,由于非阻塞算法可以使多个线程在竞争相同数据时不会发生阻塞,因此它能在粒度更细的层次上面进行协调,并且极大的减少调度开销。锁虽然Java语言锁定语法比较简洁,但JVM操作和管理锁时,需要完成的工作缺并不简单,在实现锁定时需要遍历JVM中一条复杂的代码路径,并可能导致操作系统级的锁定、线程挂起以及上下文切换等操作。

非阻塞算法

在基于锁的算法中可能会发生各种活跃性故障,如果线程在持有锁时由于阻塞I/O,内存页缺失或其他延迟执行,那么很可能所有线程都不能继续执行下去。如果在某种算法中,一个线程的失败或挂起不会导致其他线程也失败或挂起,那么这种算法就称为非阻塞算法。如果在算法的每个步骤中都存在某个线程能够执行下去,那么这种算法也被称为无锁算法。如果在算法中仅将CAS用于协调线程之间的操作,并且能够正确的实现,那么他既是一种无阻塞算法,又是一种无锁算法。

Java对非阻塞算法的支持:从Java5.0开始,底层可以使用原子变量类(例如AtomicInteger和AtoMicReference)来构建高效的非阻塞算法,底层实现采用的是一个比较并交换指令(CAS)。

比较并交换(CAS)

CAS包括了三个操作数,需要读写的内存位置V,进行比较的值A和拟写入的新值B。当且仅当V的值等于A时,CAS才会通过原子方式用新值B来更新A的值,否则不会执行任何操作。无论V的值是否等于A,都将返回V原有的值。CAS的含义是:我认为V的值应该是A,如果是那么将V的值更新为B,否则不修改并告诉V的值实际为多少。

原子变量类

原子变量(对应内存模型中的原子性)比锁的粒度更细。量级更轻,并且对于在多处理器系统上实现高性能的并发代码来说是非常关键的。原子变量将发生竞争的范围缩小到单个变量上面,这是你获得的粒度最细的情况。更新原子变量的快速(非竞争)路径不会被获得锁的快速路径慢,并且通常会更快,而它的慢速路径肯定比锁的慢速路径块,因为他不需要挂起或者重新调度线程。在使用基于原子变量而非锁的算法中,线程在执行时更不易出现延迟,并且如果遇到竞争,也更容易恢复过来。

Java中的13个原子操作类

Java从JDK1.5开始提供了java.util.concurrent.atomic包(以下简称Atomic包),这个包中的原子操作类提供了一种用法简单、性能高效、线程安全地更新一个变量的方式。因为变量的类型有很多种,所以在Atomic包里一共提供了13个类,属于4种类型的原子更新方式,分别是原子更新基本类型、原子更新数组、原子更新引用和原子更新属性(字段)。Atomic包里的类基本都是使用Unsafe实现的包装类。

  • 原子更新基本类型类

使用原子的方式更新基本类型,Atomic包提供了以下3个类。

1.AtomicBoolean:原子更新布尔类型。
2.AtomicInteger:原子更新整型。
3.AtomicLong:原子更新长整型。

  • 原子更新数组

通过原子的方式更新数组里的某个元素,Atomic包提供了以下4个类。

1.AtomicIntegerArray:原子更新整型数组里的元素。
2.AtomicLongArray:原子更新长整型数组里的元素。
3.AtomicReferenceArray:原子更新引用类型数组里的元素。

  • 原子更新引用类型

原子更新基本类型的AtomicInteger,只能更新一个变量,如果要原子更新多个变量,就需要使用这个原子更新引用类型提供的类。Atomic包提供了以下3个类。

1.AtomicReference:原子更新引用类型。
2.AtomicReferenceFieldUpdater:原子更新引用类型里的字段。
3.AtomicMarkableReference:原子更新带有标记位的引用类型。可以原子更新一个布尔类型的标记位和引用类型。构造方法是AtomicMarkableReference(V initialRef,booleaninitialMark)。

  • 原子更新字段类

如果需原子地更新某个类里的某个字段时,就需要使用原子更新字段类,Atomic包提供了以下3个类进行原子字段更新。

1.AtomicIntegerFieldUpdater:原子更新整型的字段的更新器。
2.AtomicLongFieldUpdater:原子更新长整型字段的更新器。
3.AtomicStampedReference:原子更新带有版本号的引用类型。该类将整数值与引用关联起来,可用于原子的更新数据和数据的版本号,可以解决使用CAS进行原子更新时可能出现的
4.ABA问题。

AtomicLong源码分析

上面的4种原子类型都是基于CAS实现,低层借助于unsafe实现原子操作。接下来结合源码,看一下比较有代表性的AtomicLong源码

初始化

//保存AtomicLong的实际值,用volatile 修饰保证可见性
private volatile long value;

// 获取value的内存地址的逻辑操作
  static {
    try {
      valueOffset = unsafe.objectFieldOffset
        (AtomicLong.class.getDeclaredField("value"));
    } catch (Exception ex) { throw new Error(ex); }
  }

//根据传入的参数初始化实际值,默认值为0
public AtomicLong(long initialValue) {
    value = initialValue;
  }

接下来我们主要看一下几个更新方法

//以原子方式更新值为传入的newValue,并返回更新之前的值
public final long getAndSet(long newValue) {
    return unsafe.getAndSetLong(this, valueOffset, newValue);
  }

//输入期望值和更新值,如果输入的值等于预期值,则以原子方式更新该值为输入的值
public final boolean compareAndSet(long expect, long update) {
    return unsafe.compareAndSwapLong(this, valueOffset, expect, update);
  }

//返回当前值原子加1后的值
public final long getAndIncrement() {
    return unsafe.getAndAddLong(this, valueOffset, 1L);
  }

//返回当前值原子减1后的值
public final long getAndDecrement() {
    return unsafe.getAndAddLong(this, valueOffset, -1L);
  }

//返回当前值原子增加delta后的值
public final long getAndAdd(long delta) {
    return unsafe.getAndAddLong(this, valueOffset, delta);
  }

上面列出来主要用的一些方法,可以看出基本都是调用unsafe.getAndAddLong方法,接下来我们具体看下

public native long getLongVolatile(Object var1, long var2); 

public final native boolean compareAndSwapLong(Object var1, long var2, long var4, long var6);

/*
unsafe.getAndAddLong(this, valueOffset, 1L)
var1 当前值
var2 value值在AtomicLong对象中的内存偏移地址
*/

public final long getAndAddLong(Object var1, long var2, long var4) {
    long var6;
    do {
      //根据var1和var2得出当前变量的值,以便接下来执行更新操作
      var6 = this.getLongVolatile(var1, var2);

      //如果当前值为var6,则将值加var4,这样做是确保每次更新时,变量的值是没有被其他线
//程修改过的值,如果被修改,则重新获取最新值更新,直到更新成功
    } while(!this.compareAndSwapLong(var1, var2, var6, var6 + var4));

    return var6;
  }

从源码可以看出,获取当前值getLongVolatile方法,比较并交换compareAndSwapLong方法都是native方法。说明不是采用java实现原子操作的,具体各位同学可以继续去查看底层源码(应该是c++)实现,这里不在深入了(能力有限)。

比较并交换的缺陷

1、通过源码可以看出,原子更新时,会先获取当前值,确保当前值没被修改过后在进行更新操作,这也意味着如果竞争十分激烈,CAS的效率是有可能比锁更低的(一般在实际中不会出现这种情况),JDK后面推出了LongAdd,粒度更小,竞争也会被分散到更低,具体实现各位同学可以自行了解。

2、ABA是谈到CAS不可避免的话题,比较并交换,会存在这样一个场景,当变量为值A时,将值执行更新。然而在实际中,有可能其他线程将值先改为B,然后又将值改回A,此时还是能够成功执行更新操作的(对于某些不在乎过程的没啥影响,对于链表之类的就不满足了)。解决方式是给变量打上版本号,如果版本号和值一致才执行更新操作(可使用AtomicReference)。

总结

非阻塞算法通过底层的并发原语(例如比较交换而不是锁)来维持线程的安全性。这些底层的原语通过原子变量类向外公开,这些类也用做一种“更好的volatile变量”,从而为整数和对象引用提供原子的更新操作。

参考书籍:

《JAVA并发编程实战》

《JAVA并发编程的艺术》

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持我们。

(0)

相关推荐

  • Java垃圾回收之复制算法详解

    之前的Java垃圾回收之标记清除算法详解 会导致内存碎片.下文的介绍的coping算法可以解决内存碎片问题. 概述 如果jvm使用了coping算法,一开始就会将可用内存分为两块,from域和to域, 每次只是使用from域,to域则空闲着.当from域内存不够了,开始执行GC操作,这个时候,会把from域存活的对象拷贝到to域,然后直接把from域进行内存清理. 应用场景 coping算法一般是使用在新生代中,因为新生代中的对象一般都是朝生夕死的,存活对象的数量并不多,这样使用coping算法

  • Java求质数的几种常用算法分析

    本文实例讲述了Java求质数的几种常用算法.分享给大家供大家参考,具体如下: 1.根据质数的定义求 质数定义:只能被1或者自身整除的自然数(不包括1),称为质数. 利用它的定义可以循环判断该数除以比它小的每个自然数(大于1),如果有能被它整除的,则它就不是质数. 对应代码是: void printPrime(int n){//判断n是否是质数 boolean isPrime=true;//是否是质数的标志 for(int i=n-1;i>1;i-){//n除以每个比n小比1大的自然数 if(n%

  • Java一个简单的红包生成算法

    一个简单的红包生成算法,代码如下: /** * 红包 * @param n * @param money 单位:分 * @return **/ public static double[] redPacket(int n, double money) { // 红包结果 double[] result = new double[n]; // 随机数 double[] randNum = new double[n]; // 随机总数 double randSum = 0; // 保证每个人都分到一

  • Java垃圾回收之分代收集算法详解

    概述 这种算法,根据对象的存活周期的不同将内存划分成几块,新生代和老年代,这样就可以根据各个年代的特点采用最适当的收集算法.可以用抓重点的思路来理解这个算法. 新生代对象朝生夕死,对象数量多,只要重点扫描这个区域,那么就可以大大提高垃圾收集的效率.另外老年代对象存储久,无需经常扫描老年代,避免扫描导致的开销. 新生代 在新生代,每次垃圾收集器都发现有大批对象死去,只有少量存活,采用复制算法,只需要付出少量存活对象的复制成本就可以完成收集:可以参看我之前写的Java垃圾回收之复制算法详解 老年代

  • AI算法实现五子棋(java)

    本文实例为大家分享了AI算法实现五子棋的具体代码,供大家参考,具体内容如下 首先,实现一个五子棋要有一个棋盘,然后在这个棋盘上我们再来画出图画,五子棋棋盘有固定的行数和列数,再加上界面的大小和菜单栏,这些数据可能很多个类都需要用到,我们可以先考虑自己写一个接口用来存储这些数据: public interface Config { public static final int SIZE=703; //面板大小 public static final int X0=SIZE/19*2-8; pub

  • Java垃圾回收之标记清除算法详解

    java垃圾回收算法之-引用计数器,这个算法其中一个优点便是,实时性,只要对象的引用计数器的值为0,则立刻回收.接下来介绍的标记清除算法,当对象的引用计数器的值为0时,不会立刻被回收的. 概念介绍 root对象 在标记清除算法中,会把如下对象称之为root对象 被栈中的变量(栈中存的是对象的引用)所引用的对象 被static变量引用的对象 可访问的对象 如果栈中有一个变量a引用了一个对象,那么该对象是可访问的,如果该对象中的某一个字段引用了另一个对象b,那么b也是可访问的.可访问的对象也称之为l

  • Java排序算法之堆排思想及代码实现

    在介绍堆排序前,我们需要了解一下一种数据结构 -- 顶堆. 什么是顶堆? 它是一颗完全二叉树,顶堆有大顶堆和小顶堆两种.所谓大顶堆就是在这颗完全二叉树中,任何一颗子树都满足:父结点的值 > 孩子结点的值:小顶堆则相反. 如图: 什么是堆排序(Heapsort)? 利用堆积树(堆)这种数据结构所设计的一种排序算法,它是选择排序的一种.可以利用数组的特点快速定位指定索引的元素. 现在给我们一个无序数组,我们将其从小到大排序,使用堆排序的实现步骤和思想如下: 1.让这个数组变成一个大根堆 2.将最后一

  • Java利用递归算法实现查询斐波那契数

    package 斐波那契数; import java.util.Scanner; class 斐波那契数 { public static void main(String[] args) { System.out.println("请输入想查询的第几个斐波拉楔数"); long n = new Scanner(System.in).nextLong(); System.out.println(f(n)); } private static int f(long n) { if(n==1

  • Java垃圾回收之标记压缩算法详解

    之前写过的一篇Java垃圾回收之标记清除算法详解 ,这个算法有个缺点就是造成内存碎片,存在不连续的空间,这样会导致申请较大空间的时候,又需要进行垃圾回收.下面介绍一下标记压缩算法,可以避免内存碎片. 空白部分是不连续的. 概述 这个算法的标记清除阶段,跟Java垃圾回收之标记清除算法详解  中的是一样的,而对于压缩阶段,它的工作就是移动所有的可达对象到堆内存的同一个区域中,使他们紧凑的排列在一起,从而将所有非可达对象释放出来的空闲内存都集中在一起,通过这样的方式来达到减少内存碎片的目的.如下图:

  • Java计算器核心算法代码实现

    在进行一个表达式的计算时,先将表达式分割成数字和字符串然后利用出入栈将分割后的表达式进行中缀转后缀,再将后缀表达式进行计算得到结果(思想在上一篇写过)现在贴下Java语言的代码实现.(学习Java时间不长所以可能会有很多不足的地方,我会改进也欢迎大神可以给我一些意见和建议~谢谢啦) 我将这部分分成三个方法完成功能,并在getResult方法调用(getResult方法被主方法调用) private String getResult(String str) { //分割 String[] Str

随机推荐