当我们在谈论 memory order 的时候,我们在谈论什么

阅读 2114,2017-09-12 发布,来源:cloud.tencent.com

导语: C++ 11与JDK 1.9都新增了对memory order的支持,对于memory order这个概念,本文试图阐述清楚与它相关的问题的由来,概念定义以及c++ 11与jdk 1.9对其的支持。

Memory Model

在分析memory order之前,我们先讲一下为什么要考虑memory order问题,这里需要简单分析一下多线程编程环境中的内存模型。

上图所示的是一个典型的多核CPU系统架构,它包含有2个CPU核,每个CPU核有一个私有的32KB 的 L1 cache,两个CPU 核共享 1MB的 L2 cache 以及 512MB的主存。

在这个内存模型下,cpu写数据并不是立即写入RAM中,而是写入L1 cache,再从L1 cache存入(store) RAM中,读数据也是先从L1 cache中读,读不到再从RAM中读,这种读写数据的模式是能够提高数据存取效率的,但是在一些特殊情况下会导致程序出错,考虑以下这个例子。

 x=y=0;
 Thread 1 Thread 2
 x = 1; y = 1;
 r1 = y; r2 = x;

表面上看,r1==r2==0这种输出是不可能出现的,然而,有一种可能性是,由于r1不依赖于x,编译器可以把r1=y这步操作调整到x=1这步操作之前,同样,r2=x这步操作可以调整到y=1这步操作之前,这样一来,core 1可以先读取L1 cache中的y的值,core 2 才执行 y = 1的赋值操作,同理,r2 = x这步操作也可以在x=1这步赋值操作之前执行,这时候就会出现r1 == r2 ==0的输出结果。

如何避免这种情况的出现呢?最简单的方案是给x, y变量操作加互斥锁,然而,我们都知道,互斥锁会导致代码执行效率降低,那么,有没有其他同步原语,既能保证程序的正确性,又能尽可能地提高程序执行效率呢?下面介绍4种 Memory Barrier 。

Memory Barrier

理论上讲,Memory Barrier有4类,如下图所示。

下面分别进行分析。

LoadLoad

LoadLoad 这种内存栅栏(memory barrier),顾名思义,就是阻止栅栏后面的load操作被调整到栅栏前面的load操作之前,类似于 git pull 或者 svn update 操作,如下图所示。

LoadLoad 的主要作用是防止程序加载已经过期的数据,考虑以下代码:

if (IsPublished) // Load and check shared flag
{
 LOADLOAD_FENCE(); // Prevent reordering of loads
 return Value; // Load published value
}

LOADLOAD_FENCE 在其中的作用是阻止读取Value这步操作被reorder到读取IsPublished这步操作之前,这样,只有在IsPublished置位后,才会去读取Value的值。

StoreStore

类似于LoadLoad,StoreStore 这种内存栅栏用于阻止栅栏后面的store操作被调整到栅栏前面的store操作之前,类似于git push或者svn commit操作,如下图所示。

同理,StoreStore可以避免将过期的数据写入内存。

Value = x; // Publish some data
STORESTORE_FENCE();
IsPublished = 1; // Set shared flag to indicate availability of data

LoadStore

LoadStore 内存栅栏用于保证所有在这个栅栏之前的load操作一定会在这个栅栏之后的store操作之前执行。例如:

IsPublished = X; // Load X and set IsPublished
LOADSTORE_FENCE();
Value = 1; // Publish some data

在这里,Value = 1 这步操作可以被提前到读取X的值这步操作之前,之所以允许这种优化,是因为有时候在L1 cache中没有缓存X的值,而已经缓存了Value=1这步操作,这时候先执行store再执行load效率会更高。然而,LoadStore这种栅栏可以阻止这种情况的发生。

StoreLoad

StoreLoad 用于保证所有在这个栅栏之前的store操作一定会在这个栅栏之后的load操作之前执行,可以认为这是svn或者git中用户本地代码目录与central repository之间的一次同步操作,如下图所示。

StoreLoad 可以解决前文所说的r1==r2==0的问题,考虑将程序改成如下这种形式。

 x=y=0;
 Thread 1 Thread 2
 x = 1; y = 1;
STORELOAD_FENCE(); STORELOAD_FENCE();
 r1 = y; r2 = x;

在这种情况下,r1==r2==0这个情况是不会出现的。

Acquire与Release语义

Acquire与Release是无锁编程中最容易混淆的两个原语,它们是线程之间合作进行数据操作的关键步骤。在这里,借助前面对memory barrier的解释,对acquire与release的语义进行阐述。

  • acquire本质上是read-acquire,它只能应用在从RAM中read数据这种操作上,它确保了所有在acquire之后的语句不会被调整到它之前执行,如下图所示。

用上面的memory barrier来描述,acquire等价于LoadLoad加上LoadStore栅栏。

  • release本质上是write-release,它只能应用在write数据到RAM中,它确保了所有在release之前的语句不会被调整到它之后执行,如下图所示。

用上面的memory barrier来描述,release等价于LoadStore加上StoreStore栅栏。

互斥锁(mutex)

借助acquire与release语义,我们再重新来看一下互斥锁(mutex)如何用acquire与release来实现,实际上,mutex正是acquire与release这两个原语的由来,acquire的本意是acquire a lock,release的本意是release a lock,因此,互斥锁能保证被锁住的区域内得到的数据不会是过期的数据,而且所有写入操作在release之前一定会写入内存,如下图所示。

以上关于memory barrier的背景和相关概念说明的部分,有很多参考自Preshing on Programming博客,有兴趣的同学可以前往该博客阅读其博文,上面有不少实验也非常地有趣。

C++ 11中与memory order相关的同步操作

C++ 11 在标准中提出了6种同步操作: memory_order_relaxed, memory_order_acquire, memory_order_consume, memory_order_release, memory_order_acq_rel, memory_order_seq_cst,关于C++ 11的memory order,

  • 漫谈C++11多线程内存模型
  • C++并发无锁编程 之 memory order

这两篇文章有比较详细的描述,结合上述对一些专有名词的解释,这两篇文章应该比较容易看懂,这里不再赘述。

JDK 1.9中与memory order相关的同步操作

为了与C++ 11对齐,jdk 1.9标准中也新增了与memory order相关的同步操作,新添加了VarHandle这个类来封装相关的方法。

VarHandle类的设计目的是为了替代java.util.concurrent.atomic以及sun.misc.Unsafe这两个类中的一些方法,标准中指出这两个类的一些方法存在性能和可移植性问题,下面举例说明:

  • AtomicInteger类会带来额外的内存消耗以及因引用替换带来的新的并发问题。
  • 原子化的FieldUpdaters操作通常会比原操作带来更多的开销
  • 特定的JVM内置的sun.misc.Unsafe包里面的API可以高效地执行原子更新操作,但是这个包会损害安全性与可移植性。

为了解决这些问题,JEP希望设计VarHandle这样一种变量类型,它能够支持在多种不同的访问模式下对变量进行读写操作,支持的变量类型包括对象域、静态域、数组元素以及一些不在堆上的用ByteBuffer描述的字节数组。

VarHandle类的访问模式包括以下几类:

  1. 读模式,即以volatile内存访问顺序读变量(顺序读);
  2. 写模式,即以release模式的内存访问顺序写变量(顺序写,防止乱序);
  3. 对变量进行原子化地更新操作,例如在compare and set操作中,以volatile内存访问顺序读写变量;
  4. 对数字进行原子化地更新操作,例如在get and add操作中,对写操作使用普通的内存访问顺序,对读操作使用acquire内存访问顺序;
  5. 对bitset进行逐位的原子化更新操作,例如在get and bitwise add操作中,对写操作使用release内存访问顺序,对读操作使用一般的内存访问顺序。

后面三种内存访问模式通常被称为read-modify-write模式。

VarHandle类可以由MethodHandle类进行生产,代码示例如下:

class Foo {
 int i;

 ...
}

...

class Bar {
 static final VarHandle VH_FOO_FIELD_I;

 static {
 try {
 VH_FOO_FIELD_I = MethodHandles.lookup().
 in(Foo.class).
 findVarHandle(Foo.class, "i", int.class);
 } catch (Exception e) {
 throw new Error(e);
 }
 }
}

在获取并返回一个VarHandle实例之前,MethodHandle的Lookup方法会进行访问控制权限检查。

如果要获取一个用于访问数组的VarHandle实例,可以采用以下方法。

VarHandle intArrayHandle = MethodHandles.arrayElementVarHandle(int[].class);

获取到VarHandle类实例后,如何用这个类去修改类的域呢?

Foo f = ...
boolean r = VH_FOO_FIELD_I.compareAndSet(f, 0, 1);
int o = (int) VH_FOO_FIELD_I.getAndSet(f, 2);

为了保证效率,VarHandle类的实例通常需要被声明为static final变量(其实就是常量),这样可以在编译期对它进行优化。

用VarHandle类反射获取MethodHandle类的方法如下:

Foo f = ...
MethodHandle mhToVhCompareAndSet = MethodHandles.publicLookup().findVirtual(
 VarHandle.class,
 "compareAndSet",
 MethodType.methodType(boolean.class, Foo.class, int.class, int.class));

调用这个MethodHandle的代码如下:

boolean r = (boolean) mhToVhCompareAndSet.invokeExact(VH_FOO_FIELD_I, f, 0, 1);

MethodHandle mhToBoundVhCompareAndSet = mhToVhCompareAndSet
 .bindTo(VH_FOO_FIELD_I);
boolean r = (boolean) mhToBoundVhCompareAndSet.invokeExact(f, 0, 1);

反射生成MethodHandle的另一种方案是:

MethodHandle mhToVhCompareAndSet = MethodHandles.varHandleExactInvoker(
 VarHandle.AccessMode.COMPARE_AND_SET,
 MethodType.methodType(boolean.class, Foo.class, int.class, int.class));

boolean r = (boolean) mhToVhCompareAndSet.invokeExact(VH_FOO_FIELD_I, f, 0, 1);

关于MethodHandle的更多使用方法可以参考文章理解JDK中的MethodHandle。

最后,陈列一下VarHandle类内部支持memory order的方法

/**
 * Ensures that loads and stores before the fence will not be
 * reordered with loads and stores after the fence.
 *
 * @apiNote Ignoring the many semantic differences from C and
 * C++, this method has memory ordering effects compatible with
 * atomic_thread_fence(memory_order_seq_cst)
 */
 public static void fullFence() {}

 /**
 * Ensures that loads before the fence will not be reordered with
 * loads and stores after the fence.
 *
 * @apiNote Ignoring the many semantic differences from C and
 * C++, this method has memory ordering effects compatible with
 * atomic_thread_fence(memory_order_acquire)
 */
 public static void acquireFence() {}

 /**
 * Ensures that loads and stores before the fence will not be
 * reordered with stores after the fence.
 *
 * @apiNote Ignoring the many semantic differences from C and
 * C++, this method has memory ordering effects compatible with
 * atomic_thread_fence(memory_order_release)
 */
 public static void releaseFence() {}

 /**
 * Ensures that loads before the fence will not be reordered with
 * loads after the fence.
 */
 public static void loadLoadFence() {}

 /**
 * Ensures that stores before the fence will not be reordered with
 * stores after the fence.
 */
 public static void storeStoreFence() {}

通过上面的背景描述,我们可以知道,对于读操作,fullFence强于acquireFence强于loadLoadFence,对于写操作,fullFence强于releaseFence强于storeStoreFence。

JDK 1.9还提供了一种可达性屏障,定义在java.lang.ref.Reference类里面

class java.lang.ref.Reference {
 // add:

 /**
 * Ensures that the object referenced by the given reference
 * remains <em>strongly reachable</em> (as defined in the {@link
 * java.lang.ref} package documentation), regardless of any prior
 * actions of the program that might otherwise cause the object to
 * become unreachable; thus, the referenced object is not
 * reclaimable by garbage collection at least until after the
 * invocation of this method. Invocation of this method does not
 * itself initiate garbage collection or finalization.
 *
 * @param ref the reference. If null, this method has no effect.
 */
 public static void reachabilityFence(Object ref) {}

}

总结

program reorder这个问题其实在平时的开发中比较少会遇到,但是考虑到特定的cpu或者编译器在优化指令时会有重排序的情况,了解这些知识有助于调试一些疑难杂症。

参考文献

[1] Preshing on Programming博客
[2] jdk 1.9 标准
[3] C++ 11关于memory order的说明

更多精彩文章

SegmentFault

一起探索更多未知

下载 App