Memory model basics

two aspects:

• the basic structural aspects;
• the concurrency aspects.

Objects and memory location

C++程序中所有的数据都是由object组成，object是"a region of storage"。一个对象存储在一个或多个memory location。

每个memory location，

• 要么是，一个标量的一个对象（或子对象）；
• 要么是，相邻bit fields的序列。（虽然相邻的bit fields是不同对象，它们仍然算作相同的memory location，除非用长度为0的bit fields隔开。）

Modification orders

C++程序中的每个对象都定义了一个modification order，它由程序中的所有线程对这个对象的write组成， starting with the object’s initialization。

在绝大多数情况下，这个order在每次运行的时候都是不同的，但对于一个给定的执行，所有的线程都必须agree on the order。如果不使用原子类型，你就必须提供有效的同步来使得这些线程都agree on the modification order of each variable。但是线程并没有必要agree on the relative order of separate objects。

Atomic Operations and types in C++

一个atomic operation是indivisible operation，要么完成，要么不完成。

The standard atomic types

is_lock_free()：给定类型的操作是直接由atomic instructions完成，还是由编译器和库提供的内部锁完成。

std::atomic_flag没有提供is_lock_free()成员函数。因为在这个类型上的操作required to be lock-free，一旦有了这个lock-free的类型，就能够以它为基础，进而实现所有其他的atomic类型。

在大多数平台上，所有内置类型的atomic变种都应该是lock-free的，但这并不是必须的。

要注意的是，由于历史的原因，在有的平台，atomic类型指的不一定是std::atomic<>的specialization（如：atomic_bool和std::atomic<bool>）。如果混用，就可能导致不兼容的情况出现。

The alternative names for the standard atomic types and their corresponding std::atomic<> specializations.

The standard atomic typedefs and their corresponding built-in typedefs

要注意的是：

1. 标准的atomic类型不是copyable和assignable的；

   因为这些操作总是涉及到两个对象，必须从一个中read，然后write到另一个，这是两个单独的操作，合起来不可能是atomic。因此就不被允许。

2. 支持assignment from和implicit conversion to对应的内置类型；

3. 赋值操作返回的并不是reference to the object it’s assigned to，而是the value assigned。

   因为如果返回了reference to atomic variable，那些使用这个变量的代码需要显示的load()，实际使用到值的可能是其他线程已经修改过的。

Memory-ordering

每个在atomic类型上的操作都有memory-ordering参数，来指定memory-ordering语义。不同的操作可传入不同的参数，操作分为三类：

1. Store
2. Load
3. Read-modify-write

默认是memory_order_seq_cst。

Operations on std::atomic_flag

代表一个boolean flag，只能是两种状态：set或clear，并且总是starts clear。

必须用ATOMIC_FLAG_INIT来初始化，std::atomic_flag guard = ATOMIC_FLAG_INIT。这是唯一需要使用这样的特殊方式来初始化的类型，也是唯一一个保证lock-free的。

如果是static，那么在首次操作flag的时候初始化。

用于实现spinlock，

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class spinlock_mutex {
    std::atomic_flag flag;
public:
    spinlock_mutex():
        flag(ATOMIC_FLAG_INIT) {}
    void lock() {
        while(flag.test_and_set(std::memory_order_acquire));
    }
    void unlock() {
        flag.clear(std::memory_order_release);
    }
};

Operations on std::atomic<bool>

可用nonatomic bool来初始化，还可以向实例赋nonatomic bool值，std::atomic<bool>可能不是lock-free的！

1
2

std::atomic<bool> b(true);
b = false;

• write：store()；
• read-modify-write：exchange()；
• nonmodifying query：load()。

1
2
3
4

std::atomic<bool> b;
bool x=b.load(std::memory_order_acquire);
b.store(true);
x=b.exchange(false,std::memory_order_acq_rel);

compare/exchange

• compare_exchange_weak()
• compare_exchange_strong()

如果失败，expected value或被更新为original value，都接受两个memory-ordering参数。

有这么几个要注意的地方：

1. 一个failed compare/exchange是不会进行保存的，因此某些memory-ordering语义是不可用的（memory_order_release和memory_order_acq_rel）。
2. can’t supply stricter memory ordering for failure than for success。
3. 如果不为failure提供memory-ordering参数，则在满足1的情况下，与success一致。
4. 如果都不提供，则使用默认的memory_order_seq_cst。
5. 它们是read-modify-write operation。

蛋疼的作者啊，很多地方扯到memory-ordering语义，但是总是说“leave to section 5.3…”

Operations on std::atomic<T*>

std::atomic<bool>有的成员函数，这个也有。

std::atomic<T*>还提供了pointer arithmetic operations，由fetch_add()和fetch_sub()实现。

fetch_add()和fetch_sub()

1. 也叫做exchange-and-add，它们是atomic read-modify-write operation。

2. 返回的是原始的值，而不是add或sub后的值。

   1 2 3 4 5 6 7 8 9

   class Foo{}; Foo some_array[5]; std::atomic<Foo*> p(some_array); Foo* x=p.fetch_add(2); assert(x==some_array); assert(p.load()==&some_array[2]); x=(p-=1); assert(x==&some_array[1]); assert(p.load()==&some_array[1]);

Operations on standard atomic integral types

Only division, multiplication, and shift operators are missing。因为atomic integral types通常作为计数器或位域来使用，如果需要额外的操作，可以在loop中用compare_exchange_weak()来实现。

The std::atomic<> primary class template

要将user-defined type用于std::atomic<>，UDT必须满足：

1. 必须有trivial copy-assignment operator；

   • 不能有任何的virtual函数或者virtual基类；
   • 必须使用编译器生成的copy-assignment operator。

2. 每个基类和非static数据成员必须有trivial copy-assignment operator；

   • 这可以使得编译器将memcpy()或等价的操作用于assignment operation。

3. 这个类型必须是bitwise equality comparable。

   • 这里接着2，不仅要能够使用memcpy()来copy，还要能使用memcmp()来比较（以便compare/exchange能工作）。

为什么要满足？

1. If user-supplied copy-assignment or comparison operators were permitted, this would require passing a reference to the protected data as an argument to a user-supplied function, thus violating the guideline.
2. 增大了编译器对std::atomic<UDT>直接使用atomic instruction的可能，因为编译器可以把UDT看作a set of raw bytes。

std::atomic<float> and std::atomic<double>？

因为表示的不同，即使相等compare_exchange_strong()也会fail。

Free functions for atomic operations

与原子类型的成员函数相对应，也有相应的非成员函数，大多数前面都会加上atomic_。

要注意的地方有：

1. 用含有_explict的版本来指定memory ordering；

2. 所有free functions的第一个参数类型都是pointer to atomic objcet(为了C-compatible)；

   对于CAS，要么不指定failure memory ordering，要么两个都要指定。

3. 对于std::atomic_flag只能，

   • std::atomic_flag_test_and_set()
   • std::atomic_flag_clear()
   • std::atomic_flag_test_and_set_explicit()
   • std::atomic_flag_clear_explicit()

4. std::shared_ptr<>算是特殊，它非atomic type，但支持load, store, exchange and compare/exchange。这些free functions第一个参数接受std::shared_ptr<>*。

Reference

1. std::atomic_flag as member variable