Strong / Weak Memory Model

  1. 强内存模型：常常指线性一致性（sequential model）。满足以下两个条件

    • 程序按照源文件中的代码顺序执行；
    • 各个线程的所有操作存在一个固定的顺序（global order）。想象各线程共享一个 gloabl clock；

  2. 弱内存模型：常常指 relaxed semantic.

    • thread-1 可能看到 thread-2 不是按照其源文件中代码顺序来执行的；
    • 甚至 thread-2 本身自己执行指令就不按照源代码顺序；

这两种模型间还有其他内存模型，比如 Acquire-release semantic. 内存模型越强，对于程序员来讲越好理解，但是对于系统（编译器、处理器、caches）来讲，留有的优化空间越小。反之，采用较弱的内存模型写的程序，具有很大的优化潜能，但是比较反人类直觉，一般程序员难以理解。

The Atomic Flag

std::atomic_flag 是一个原子的布尔量，具有 clear, set 两种状态。clear 状态下值为 false, set 状态下值为 true。

  1. 成员方法：

    • clear() 方法，将变量的值设置为 false。
    • test_and_set() 方法，返回变量的旧值并将变量值设置为 false。
    • C++20 新加入 test(), wait(), notify_one(), notify_all() 成员方法，本文暂不讨论，专注 C++11 内容。

  2. 初始化：

    必须以如下方式初始化。

    std::atomic_flag flag = ATOMIC_FLAG_INIT;
std::atomic_flag flag(ATOMIC_FLAG_INIT); // !! unspecified.

  3. 特点：

    • 唯一保证真正 lock-free 的原子量 (atomic)。lock-free 含义：系统范围内保证运行无阻塞。

      其他原子量，比如 std::atomic ，C++ 标准允许其内部使用 mutex 来实现。有 mutex 就有可能存在阻塞，可能不是真正的 lock-free，成员函数 is_lock_free() 可以用来验证是否真正的 lock-free。（已知的大部分实现都是 lock-free 的。）

    • 构建 higher level 的线程等抽象的基石。

Spinlock

  1. 原理：与使用 mutex 进程主动阻塞不同，使用 spinlock 进程CPU空转尝试获取锁进入临界区，减少了上下文切换的开销同时，浪费了 CPU cycles。通常某 lock 的实现会结合 spinlock 和 mutex 的思路实现，自旋一段时间后仍无法进入临界区就主动阻塞。

  2. 注意事项：spinlock 不应在单核系统上使用，最好情况下（比如进行 spin 的进程时间片到了，CPU 被分配给其他进程），浪费了CPU cycles，减慢了锁持有者的执行进度。最坏情况下（非抢占式），会造成 dead_lock。

  3. 利用 std::atomic_flag 实现一个简单的 spinlock.

    • 第一个调用 lock() 的进程会立马返回。
    • 倘若后续同一个进程还没有 unlock()，其他进程尝试 lock() 则会 spin。
    • 只有调用 lock() 的进程调用 unlock(), 其他进程调用 lock() 才不会阻塞。
    #include <atomic>
#include <thread>

class Spinlock {
 private:
  std::atomic_flag flag = ATOMIC_FLAG_INIT;

 public:
  void lock() {
    while (flag.test_and_set())
      ;
  }
  void unlock() { flag.clear(); }
};

Spinlock spin;
void WorkOnResource() {
  spin.lock();
  spin.unlock();
}

int main(int argc, char const *argv[]) {
  std::thread t(WorkOnResource);
  std::thread t1(WorkOnResource);

  t.join();
  t1.join();
  return 0;
}

Ref

  1. wait-free and lock-free