内存一致性模型基础

发表于 | 分类于

Do one thing, do it well.

1. 内存一致性模型基础

从分析一个经典例子开始：

1
2
3
4
5
6
7
/* Thread 1 */
A = 1; // (1)
print!("{}", B); // (2)

/* Thread 2 */
B = 1; // (3)
print!("{}", A); // (4)

1.1. SC: sequential consistency

顺序一致性对下面两方面给出保证：

  1. 存在读和写的全局顺序
  2. 不同核交叉的读写操作仍保证单个线程的执行顺序

例如上述例子，可能的输出：

  • 01: 1-2-3-4或3-4-1-2
  • 11: 1-3-2-4或3-1-2-4
  • 不会出现00

1.2. TSO: total store ordering

相比SC，放松要求，允许store buffering。可能导致写操作的结果向其它核传播的滞后。x86和x86-64遵循该模型。

因此上述例子，可能出现00，因为对A和B的写都进写入了本地cache，没有最终传播到对方cache。

1.3. weak memory ordering with data dependency

  • 仅当程序中某个内存位置处的值依赖于另一个内存位置处的值时，给出一致性保证。
1
2
3
4
5
6
// program 1
A = 1; // (1)
B = 1; // (2)
// program 2
C = 1; // (3)
D = C; // (4)

对于程序1，A和B是独立的内存位置，因此其它核的线程可能首先观察到(2)其次观察到(1)。对于程序2，由于D依赖于C的值，因此如果其它核线程观察到了D的值为1，则能够保证观察到C的值也为1。

1.4. 语言级别的内存一致性模型

除了硬件，语言也能够定义自己的内存一致性模型。当编译器优化程序代码的时候，能够重排序或者根据语言规范删除特定的语句。

1
2
3
4
5
6
7
8
9
// Program 1
let mut x = &mut 1;
for i in 0..1000 {
    println!("{}", *x);
}
// Program 2
for i in 0..1000 {
    println!("{}", x);
}

对于上述代码，如果不存在其它核的线程修改变量x，则上下两个程序是等价的。由于Rust的可变引用规则，Rust编译器能够将1的代码编译为2.若要表示x可能被其它核线程修改，需要使用原始指针或是UnsafeCell。

2. 内存屏障和原子指令

  • 架构提供了内存屏障(memory barrier)和原子指令(atomic instruction)

2.1. 内存屏障

内存屏障给出了屏障前后指令的强内存序保证。ARM架构中有三类内存屏障：

  • DMB: Data Memory Barrier
    • Data memory barrier acts as a memory barrier. It ensures that all explicit memory access that appear in program order before the DMB instruction are observed before any explicit memory access that appear in program order after the DMB instruction.
  • DSB: Data Synchronization Barrier
    • Data Synchronization Barrier acts as a special kind of memory barrier. No instruction in program order after this instruction executes until this instruction completes.
  • ISB: Instruction Synchronization Barrier
    • Instruction Synchronization Barrier flushes the pipeline in the processor, so that all instructions following the ISB are fetched from cache or memory, after the instruction has been completed.
1
2
3
4
5
// 当更新页表基址寄存器时
dsb ishst
tlbi vmalle1
dsb ish
isb

// TODO:

2.2. 原子指令

原子被认为是不可分割的最小单位。原子指令意味着该指令对应的操作必须全部完成后可见，不能部分执行。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/* thread 1 */
mov x0, #0
mov x1, addr of counter
loop:
    ldr x2, [x1]
    add x2, x2, #1
    str x2, [x1]
    add x0, x0, #1
    cmp x0, #1000
    ble loop

/* program 2 */
mov x0, #0
mov x1, addr of counter
loop:
    ldr x2, [x1]
    add x2, x2, #1
    str x2, [x1]
    add x0, x0, #1
    cmp x0, #1000
    ble loop

上述例子，递增操作并非原子指令，因此不同线程的load、add、store操作可能会相互交错。

原子指令通过下面某一种方式解决该问题。

  1. 非抢占式方式（单指令执行fetch和add）
  2. 检测数据竞争，避免竞争操作

2.3. Rust提供的原子数据类型

Rust标准库提供了AtomicBool和AtomicUsize，它们提供了高级别的fetch_and()和compare_and_swap()抽象。即使架构不直接支持该原子指令，编译器会通过几种更小的原子操作保证该语义。

1
2
3
4
5
6
7
8
9
10
11
12
impl AtomicBool {
    pub fn fetch_and(&self, val: bool, order: Ordering) -> bool { ... }
}

impl AtomicUsize {
    pub fn compare_and_swap(
        &self,
        current: usize,
        new: usize,
        order: Ordering
    ) -> usize { ... }
}

如上面的代码，&self共享引用允许该方法的共享调用，但是原子指令保证了不存在数据竞争。

这些原子指令接收Ordering参数，Rust提供了五种内存序。

  • Relaxed ordering: 无顺序保证的原子操作
  • Acquire and release：成对使用，acquire内存序下load操作阻止load之后的指令，被重排序到load之前；release内存序下store操作阻止store之前的指令，被重排序到store之后。
    • 结果是：对某个地址的acquire-release内存序创建了一个关键区，同时阻止了关键区内的指令跨越关键区。如下图。
    • 结果是：线程A首先使用release ordering对变量写，之后线程A使用acquire ordering对变量的读，所有线程A之后的读都能看到A在acquire之前写的值。如下图。
  • AcqRel：同时保证读、写屏障，即Acquire + Release
  • SeqCst：AcqRel加上所有线程以相同顺序看见顺序一致的操作

mem-order.png

3. reference