Multithreading相关术语总结

在谈到内存模型,Multithreading,尤其 lock-free programmming 等时,总会遇到一些相关术语来描述,如 Memory Barrier,Acquire semantics,Release semantics,happens-before relation 等.在这里稍微整理一下.

Memory Barriers

在之前浅谈 Memory Reordering 中谈到编译器 reordering 和在多核下的处理器的 reordering,在 lock-free programming 中,如果不控制好这两者的 reordering 就会引起上文中所不想的结果.

你可以通过指令强制 CPU 和编译器在内存处理上的顺序,这些指令就被成为 Memory Barrier.

有很多指令作为 memory barriers,所以需要知道很多不同类型的 memory barriers. Doug Lea 指出如下的四大类可以很好的归纳在 CPU 上的特殊指令.尽管不是完全,大多数时候,一个正真的 CPU 指令执行包含上面 barrier 类型的各种组合,或附带其他效果.无论如何, 一旦你理解了这四种类型的 memory barriers,你就很好的理解了大部分真正 CPU 的关于内存约束的指令. Memory Barriers Are Like Source Control Operations 这篇把 Memory Barriers 与 Source Control 作类比,熟悉 Source Control 机制的可以很形象的理解各类 Memory Barriers 机制.

'memory_barriers_types'

LoadLoad

顺序: Load1; LoadLoad; Load2

保证 Load1 的数据加载在被 load2 和之后的 load 指令读取加载之前.是一个比较好的方法防止看到旧的数据.以这个经典的例子,CPU1 检查一个共享的标识变量 flag 来确认一些数据是否被 CPU1 更新.如果标识变量 flag 是 true 的话,把LoadLoadbarrier 放在读取更新数据之前:

if (is_updated) {
    LOADLOAD_FENCE();  // Prevent reordering of loads
    return value;  // Load updated value
}

只要is_updated被 CPU1 看到为 true, LoadLoadfence 防止 CPU1 读到比标识变量 flag 本身旧的value.

StoreStore

顺序: Store1; StoreStore; Store2

保证 Store1 的数据被其他 CPU 看到在与这数据相关的 Store2 和之后的 store 指令之前.同样,它足够的防止其他 CPU 看到自己的旧数据.同上一样的例子,CPU1 需要更新一些数据到共享的内存中,把StoreStore barrier 放在标识变量 flag 是 true 之前:

value = x;
STORESTORE_FENCE();
is_updated = 1;  // Set shared flag to show the update of data

一旦其他 CPU 看到is_updated为 true,它能自信它看到正确的value值.而且 value不需要原子类型,它可以是一个包含很多元素的大数据结构.

LoadStore

顺序: Load1; LoadStore; Store2

保证 Load1 的数据被加载在与这数据相关的 Store2 和之后的 store 指令之前.

StoreLoad

顺序: Store1; StoreLoad; Load2

保证 Store1 的数据被其他 CPU 看到在数据被 Load2 和之后的 load 指令加载之前.也就是说,它有效的防止所有 barrier 之前的 stores 与所有 barrier 之后的 load 乱序.

StoreLoad是唯一的.它是唯一的 memory barrier 类型来防止r1=r2=0在之前 Memory ordering at processor time 中给出的例子.

StoreLoad有什么区别与StoreStore之后跟LoadLoad?虽然,StoreStore按序把存储改变推送到主内存中,LoadLoad按序把改变加载过来,但是这两种类型的 barrier 是不够的.Store 可以延迟任意的指令,以致在 Load 之后,Load 也可以不是加载最新 Store 之后的内容.这就是为啥 PowerPC 的指令 lwsync,包含这三种 memory barriers,LoadLoad,LoadStore和 StoreStore,但不包含StoreLoad,是不足以防止r1=r2=0在那个实例中.

Data dependency barriers

除了上面 4 大类,还有Loadload的弱化模式的Data dependency barrier.如 LoadLoad类似,在两个 load 顺序执行,load2 依赖于 load1 的结果,Data dependency barrier需要插入保证两者的顺序.

但与LoadLoad不同,Data dependency barrier只是部分顺序约束在内在以来的 load,就是 load1 必须与 load2 是 data dependency 而不是仅仅是 control dependency.

data dependency

r1 与 r2 之间是 data dependency.

r1 = 1;
r2 = r1;

control dependency

r1 与 r2 之间是 control dependency.

r1 = value;
if (r1) {
    r2 = r1;
} else {
    r2 = 1;
}

Acquire and Release semantics

在 lock-free programming 中,共享内存被多个线程通过合作传递信息来处理,在这种处理下,acquire 和 release semantics 是关键技术保证可靠的传递信息在线程之间.

acqure 和 release semantics 并没有好的被定义,这里借用 Jeff Preshing 在这里给予的定义:

'read_acquire'

Acquire semantics 是一种只能应用于如下操作的性质: 从共享内存读取,无论是 read-modify-write 操作还是普通的加载.这一操作被认为是一个 read acquire. Acquire semantics 防止 read acquire 程序上之后的任何读或写操作与它的内存乱序.

'write_release'

Release semantics 是一种只能应用于如下操作的性质: 写入到共享内存, 无论是 read-modify-write 操作还是普通的存储.这一操作被认为是一个 write release. Release semantics 防止 write release 程序上之前的任何读或写操作与它的乱序.

Acqure 和 release semantics 能通过之前四种 memory barrier 的简单组合来达到.

'acquire_release_semantics'

Acqure 和 release semantics 可以基本划分为如下结构:

'acquire_release_semantics_category'

使用明确的平台相关 Fence 指令

在 X86/64 使用mefence指令,mfence 是一个满足全部 memory barrier,防止任何类型的内存乱序.

'platform-specific_fence'

可移植的 C++11 的 Fences

C++11 的 atomic 库定义了一个可移植的函数atomic_thread_fence(),输入一个变量来指定什么类型的 fence.

'fence_in_c++11'

可移植的 C++11 的 atomic,非明确的 fence

在 C++11 中,可以直接对 atomic 变量直接约束 fence,而不是显示的明确 fence.与上面明确 fence 相比,这实际是更优的方法来表达 acquire and release semantics 在 C++11 中.

'without_fence_c++11'

Happens-before relation

Happens-before 是一个术语来描述 C++11,Java,LLVM 之类背后的软件内存模型.

在之上每个语言里都能找到* happends-before *的定义,尽管每个都有不同的说法,但内在意思基本一致.粗略地讲,基本定义如下:

A 和 B 表示一个多线程进行的操作.若 A happens-before B,那么,在 B 进行前,A 对 B 的内存影响有效的被 B 看到.

无论使用任何编程语言,它们都有一个共同处:如果操作 A 和 B 被同一个进程进行,A 的语句在 B 的语句之前在程序顺序上,那么 A 优先发生(happens-before)B.这也是在之前 Memory ordering 中谈到中心原则.

这里再次提一下指令重排序问题,有人有如下疑问: 指令重排序会破坏 happens-before 原则吗？happens-before 的程序次序原则说：在一个线程内，按照程序代码顺序，书写在前面的操作会先行发生于书写在后面的操作。如果线程内出现指令重排序，那不是破坏了程序次序原则了吗？

是会破坏程序次序的执行,但是并不破坏 happens-before 原则,并不造成内存对单线程有效性的破坏.这里主要的困惑是时间上顺序的发生之前(happening before)与先行发生(happens-before)两者关系.

时间上顺序的发生在前于(happening before)与先行发生(happens-before)两者是不一样的,基本没太大关系.特别:

A 先行发生(happens-before)B 并不意味着 A 发生在前于(happening before)B.
A 发生在前于(happening before)B 并不意味 A 先行发生(happens-before)B.

谨记 happens-before 是由一系列编程语言特定定义的操作间的关系,它的存在独立于时间的概念.

happens-before 并不意味 happening before

如下例子有 happens-before 关系但并不是顺序执行,没有 happening before.如下代码:(1) 存储到 A,之后(2)存储到 B.根据程序顺序原则,(1) happens-before (2).

int A, B;
void test() {
  A = B + 1;  // (1)
  B = 0;  // (2)
}

用 O2 打开优化编译的如下:

$ gcc -S -O2  -masm=intel test.c

	mov	eax, DWORD PTR B
	mov	DWORD PTR B, 0
	add	eax, 1
	mov	DWORD PTR A, eax

从汇编指令看出,第二句mov DWORD PTR B, 0就已经完成对B的存储,但是对A的存储还没进行.(1)顺序上并没有在(2)之前执行!

但是 happens-before 原则有被违背吗?根据定义,(1)的内存效用必须有效被看到在进行(2)之前.也就是存储 A 必须影响存储 B.

在这里,存储 A 实际并没有影响存储 B.(2)被提前执行与之后执行仍然一样,相当与 (1)的内存有效性是一样的.因此,这并不算违背 happens-before 原则.

happening before 并不意味 happens-before

这是个时间上发生于前但并含有 happens-before 关系的例子.如下的代码,想象一个线程调用UpdateValue,而另一个线程调用ConsumeValue.因为处理共享的数据并行的,为了简单,认为普通的读取和存储int是 atomic 的.因为程序顺序原则,在(1)和(2)之间 happens-before 关系,(3)和(4)之间 happens-before 关系.

int value = 0;
int updated = 0;

void UpdateValue() {
    value = 123;  // (1)
    update = 1;  // (2)
}

void ConsumeValue() {
if (update) {  // (3)
    printf("%d\n", value);  // (4)
}

进一步假设在运行开始的时候,(3)读取update到为 1,这个值是有(2)在另外个线程中存储的.这里,我们可以得出时间顺序上(2)必须发生前于(3).但是这里并没有规则意味着在(2)和(3)之间有 happens-before 关系.(2)和(3)之间没有 happens-before 关系,(1)和(4)之间也没有 happens-before 关系.因此,(1)和(4) 的内存可以重排序,因为编译器重排序或在 CPU 上内存重排序,以致(4)可以打印 “0”,即使(3)读到 1.

(learn&think)

不浮躁，不自傲，学习，思考，总结