原子操作的实现原理

原子操作


第一节 原子

背景

  当程序更新一个变量时,如果多线程同时更新这个变量,可能得到期望之外的值,比如变量i=1,A线程更新i+1,B线程也更新i+1,经过两个线程操作之后可能i不等于3,而是等于2。因为A和B线程在更新变量i的时候拿到的i都是1,这就是线程不安全的更新操作,通常我们会使用synchronized来解决这个问题,synchronized会保证多线程不会同时更新变量i。

  而Java从JDK 1.5开始提供了java.util.concurrent.atomic包(以下简称Atomic包),这个包中的原子操作类提供了一种用法简单、性能高效、线程安全地更新一个变量的方式。

  因为变量的类型有很多种,所以在Atomic包里一共提供了13个类,属于4种类型的原子更新方式,分别是原子更新基本类型、原子更新数组、原子更新引用和原子更新属性(字段)。Atomic包里的类基本都是使用Unsafe实现的包装类。

定义

  原子(atomic):是不能再被切割的最小粒子。

  原子操作:是不能被中断的一个或一系列操作。

CPU常用术语

CPU术语


第二节 原子更新基本类型类

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

  • AtomicBoolean:原子更新布尔类型。
  • AtomicInteger:原子更新整型。
  • AtomicLong:原子更新长整型。

AtomicInteger

  以上3个类提供的方法几乎一模一样,所以本节仅以AtomicInteger为例进行讲解,AtomicInteger的常用方法如下。

  • int addAndGet(int delta):以原子方式将输入的数值与实例中的值(AtomicInteger里的 value)相加,并返回结果。
  • boolean compareAndSet(int expect,int update):如果输入的数值等于预期值,则以原子方
    式将该值设置为输入的值。
  • int getAndIncrement():以原子方式将当前值加1,注意,这里返回的是自增前的值。
  • void lazySet(int newValue):最终会设置成newValue,使用lazySet设置值后,可能导致其他线程在之后的一小段时间内还是可以读到旧的值。关于该方法的更多信息可以参考并发编程网翻译的一篇文章《AtomicLong.lazySet是如何工作的?》,文章地址是“http://ifeve.com/howdoes-atomiclong-lazyset-work/”。
  • int getAndSet(int newValue):以原子方式设置为newValue的值,并返回旧值。

  AtomicInteger示例代码如下所示。

1
2
3
4
5
6
7
8
9
10
import java.util.concurrent.atomic.AtomicInteger; 

public class AtomicIntegerTest {
static AtomicInteger ai = new AtomicInteger(1);

public static void main(String[] args) {
System.out.println(ai.getAndIncrement());
System.out.println(ai.get());
}
}

  输出结果如下。

1
1 2

  那么getAndIncrement是如何实现原子操作的呢?让我们一起分析其实现原理,getAndIncrement的源码如下所示。

1
2
3
4
5
6
7
8
9
10
11
12
public final int getAndIncrement() {        
for (;;) {
int current = get();
int next = current + 1;
if (compareAndSet(current, next))
return current;
}
}

public final boolean compareAndSet(int expect, int update) {
return unsafe.compareAndSwapInt(this, valueOffset, expect, update);
}

  源码中for循环体的第一步先取得AtomicInteger里存储的数值,第二步对AtomicInteger的当前数值进行加1操作,关键的第三步调用compareAndSet方法来进行原子更新操作,该方法先检查当前数值是否等于current,等于意味着AtomicInteger的值没有被其他线程修改过,则将 AtomicInteger的当前数值更新成next的值,如果不等compareAndSet方法会返回false,程序会进入for循环重新进行compareAndSet操作。

  Atomic包提供了3种基本类型的原子更新,但是Java的基本类型里还有char、float和double等。那么问题来了,如何原子的更新其他的基本类型呢?Atomic包里的类基本都是使用Unsafe实现的,让我们一起看一下Unsafe的源码,如下所示。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/** 
* 如果当前数值是expected,则原子的将Java变量更新成x
* @return 如果更新成功则返回true
*/
public final native boolean compareAndSwapObject(Object o,
long offset,
Object expected,
Object x);

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

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

  通过代码,我们发现Unsafe只提供了3种CAS方法:compareAndSwapObject、compareAndSwapInt和compareAndSwapLong,再看AtomicBoolean源码,发现它是先把Boolean转换成整型,再使用compareAndSwapInt进行CAS,所以原子更新char、float和double变量也可以用类似的思路来实现。


第三节 原子更新数组

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

  • AtomicIntegerArray:原子更新整型数组里的元素。
  • AtomicLongArray:原子更新长整型数组里的元素。
  • AtomicReferenceArray:原子更新引用类型数组里的元素。
  • AtomicIntegerArray类主要是提供原子的方式更新数组里的整型,其常用方法如下。
  • int addAndGet(int i,int delta):以原子方式将输入值与数组中索引i的元素相加。
  • boolean compareAndSet(int i,int expect,int update):如果当前值等于预期值,则以原子方式将数组位置i的元素设置成update值。

  以上几个类提供的方法几乎一样,所以本节仅以AtomicIntegerArray为例进行讲解, AtomicIntegerArray的使用实例代码如下所示。

1
2
3
4
5
6
7
8
9
public class AtomicIntegerArrayTest {        
static int[] value = new int[] { 12 };
static AtomicIntegerArray ai = new AtomicIntegerArray(value);
public static void main(String[] args) {
ai.getAndSet(03);
System.out.println(ai.get(0));
System.out.println(value[0]);
}
}

  以下是输出的结果。

1
3 1

  需要注意的是,数组value通过构造方法传递进去,然后AtomicIntegerArray会将当前数组复制一份,所以当AtomicIntegerArray对内部的数组元素进行修改时,不会影响传入的数组。


第四节 原子更新引用类型

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

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

  以上几个类提供的方法几乎一样,所以本节仅以AtomicReference为例进行讲解, AtomicReference的使用示例代码如下所示。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public class AtomicReferenceTest {        
public static AtomicReference<user> atomicUserRef = new AtomicReference<user>();
public static void main(String[] args) {
User user = new User("conan", 15);
atomicUserRef.set(user);
User updateUser = new User("Shinichi", 17);
atomicUserRef.compareAndSet(user, updateUser);
System.out.println(atomicUserRef.get().getName());
System.out.println(atomicUserRef.get().getOld());
}

static class User {
private String name;
private int old;
public User(String nameint old) {
this.name = name;
this.old = old;
}

public String getName() {
return name;
}

public int getOld() {
return old;
}
}
}

  代码中首先构建一个user对象,然后把user对象设置进AtomicReferenc中,最后调用 compareAndSet方法进行原子更新操作,实现原理同AtomicInteger里的compareAndSet方法。代码执行后输出结果如下。

1
Shinichi 17

第五节 原子更新字段类

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

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

  要想原子地更新字段类需要两步。第一步,因为原子更新字段类都是抽象类,每次使用的时候必须使用静态方法newUpdater()创建一个更新器,并且需要设置想要更新的类和属性。第二步,更新类的字段(属性)必须使用public volatile修饰符。

  以上3个类提供的方法几乎一样,所以本节仅以AstomicIntegerFieldUpdater为例进行讲解, AstomicIntegerFieldUpdater的示例代码如下所示。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public class AtomicIntegerFieldUpdaterTest {        
// 创建原子更新器,并设置需要更新的对象类和对象的属性
private static AtomicIntegerFieldUpdater<User> a = AtomicIntegerFieldUpdater.newUpdater(User.class, "old");
public static void main(String[] args) {
// 设置柯南的年龄是10岁
User conan = new User("conan"10);
// 柯南长了一岁,但是仍然会输出旧的年龄
System.out.println(a.getAndIncrement(conan));
// 输出柯南现在的年龄
System.out.println(a.get(conan));
}

public static class User {
private String name;
public volatile int old;
public User(String name, int old) {
this.name = name;
this.old = old;
}
public String getName() {
return name;
}
public int getOld() {
return old;
}
}
}

  代码执行后输出如下。

1
10 11

第六节 底层扩展

一、CPU实现原子操作

  1. 简单读写:处理器保证从系统内存中读取或者写入一个字节是原子的,意思是当一个处理器读取一个字节时,其他处理器不能访问这个字节的内存地址。

  2. 复杂操作:处理器提供总线锁定和缓存锁定两个机制来保证复杂内存操作的原子性。

非原子操作:如比较常用的读改写操作,最经典的i++就是,要分步执行读取、修改、写入操作。

总线锁

  处理器可以通过总线锁来保证原子性,即通过在总线上输出LOCK #信号,使其他处理器的请求阻塞,此处理器就可以独占共享内存了。

  因为总线锁封闭了处理器和内存间的通信,造成这个阶段其他处理器无法工作的局面,这是很大的性能开销,所以一些场合可以用缓存锁定来代替总线锁定。

缓存锁定

  谓“缓存锁定”是指内存区域如果被缓存在处理器的缓存行中,并且在Lock操作期间被锁定,那么当它执行锁操作回写到内存时,处理器不在总线上声言LOCK#信号,而是修改内部的内存地址,并允许它的缓存一致性机制来保证操作的原子性,因为缓存一致性机制会阻止同时修改由两个以上处理器缓存的内存区域数据,当其他处理器回写已被锁定的缓存行的数据时,会使缓存行无效。

无法使用缓存锁定的情况:

  1. CPU不支持缓存锁定
  2. 操作的数据无法被缓存到处理器的缓存区,或操作的数据跨了多个缓存行。

缓存一致性机制

  简单说就是:当某处理器对缓存中的数据进行了操作之后,通知其他处理器放弃储存在它们内部的缓存,或者从主内存中重新读取

PS: 频繁使用的内存会缓存在处理器的L1、L2和L3高速缓存里,以便减少处理器和内存的交互。

缓存一致性机制

MESI协议(Modified、Exclusive、Share or Invalid)

Modified、Exclusive、Share or Invalid即缓存行的四个状态:

  1. Modified-被修改:处于此状态的数据,只在本CPU中有缓存数据,而其他CPU中没有。同时其状态相对于内存中的值来说,是已经被修改的,且没有更新到内存中。
  2. Exclusive-独占:处于此状态的数据,只有在本CPU中有缓存,且其数据没有修改,即与内存中一致。
  3. Share-共享:处于此状态的数据在多个CPU中都有缓存,且与内存一致。
  4. Invalid-无效:本CPU中的这份缓存已经无效。

此协议规定:

  • 一个处于Modified状态的缓存行,必须时刻监听所有试图读取该缓存行对应的主存地址的操作,如果监听到,则必须在此操作执行前把其缓存行中的数据写回CPU。
  • 一个处于Share状态的缓存行,必须时刻监听使该缓存行无效或者独享该缓存行的请求,如果监听到,则必须把其缓存行状态设置为I。
  • 一个处于Exclusive状态的缓存行,必须时刻监听其他试图读取该缓存行对应的主存地址的操作,如果监听到,则必须把其缓存行状态设置为S。

  当某CPU读取数据时,若其缓存行的状态为Invalid,则需要从内存中读取数据,然后把状态改为Share;如果不是Invalid,则可以直接读取缓存中的数据。但还需要同时判断其他CPU的监听结果,如果其他CPU也有此数据的缓存,并处于Modified状态,则要等待其将数据更新回内存后,才能继续读取。

  当某CPU写入数据时,只能在状态为Modified和Exclusive时才允许执行,否则需要发送RFO指令(Read Or Ownership,这是一种总线事务),通知其他CPU使其缓存无效,会有一定的性能开销,写入后将状态转换为Modified。

指令支持

  CPU提供了一些Lock前缀的指令来支持两种锁定:

  • 位测试和修改指令:BTS、BTR、BTC
  • 交换指令:XADD、CMPXCHG
  • 操作和逻辑指令:ADD、OR等

  这些指令都会使被操作的内存区域加锁。

二、Java实现原子操作

  在Java中可以通过锁机制循环CAS的方式来实现原子操作。

锁机制

  可以参考锁机制

  锁机制保证了只有获得锁的线程才有权操作被锁定的内存区域,。JVM内部实现了很多种锁机制,有偏向锁、轻量级锁和互斥锁。有意思的是除了偏向锁,JVM实现锁的方式都用了循环CAS,即当一个线程想进入同步块的时候使用循环CAS的方式来获取锁,当它退出同步块的时候使用循环CAS释放锁。

循环CAS

  可以参考CAS原理

  循环CAS保证了共享变量的原子性操作。


参考博客和文章书籍等:

《Java并发编程的艺术》

http://www.cnblogs.com/mengheng/p/3491092.html

因博客主等未标明不可引用,若部分内容涉及侵权请及时告知,我会尽快修改和删除相关内容