1 阻止并发 (并行) 的发生

1.1 并发困难的原因

人类是 “sequential creatures[有序生物]”

  • 人类具备 𝐴→…→𝐵 简化为 𝐴→𝐵 的直觉本能
    • 并且据此开发了编译器 (处理器也是编译器)
    • 多处理器和并发执行推翻了顺序执行的基本假设！

c5-4.2-2.webp

1.2 互斥

人类是 (绝不轻言放弃的) sequential creatures

  • 互斥 (互相排斥)：阻止并发，问题不就解决了？
1
ATOMIC { sum++; }
1
2
3
4
5
6
7
8
9
10
11
int T_alipay_withdraw(int amt) {
    ...
    ATOMIC {
        // No concurrency with
        // other critical sections
        if (balance >= amt) {
            balance -= amt;
        }
    }
    ...
}

1.3 互斥：阻止并发、独占访问

既然用互斥 “阻止并发”，那我们为什么还要做并行？

状态机视角的互斥

  • 临界区同时发生时，依然满足执行的原子性
  • 可以把多次状态迁移理解为 “一次大状态迁移”

实现任何共享资源 (内存) 的独占访问

1
2
3
ATOMIC {
    // 状态迁移 (语义）
}
1
2
3
lock();
// 任意代码
unlock();

既然是顺序执行，那我们还要并发做什么？

  • 如果你有1/k1/k的代码是不能并发执行的，那么：

T∞>T1kT_∞>\frac{T_1}{k}

  • 并行计算总是能实现的：

Tp<T∞+T1kT_p < T_∞ + \frac{T_1}{k}

1.4 计算是可以并行的

经典物理：局部性原理

  • 物体对相邻物体的影响需要时间
    • (即便严格来说不成立，依然是一个很好的近似)
  • 推论：任何物理世界模拟皆可以大规模并行

𝑇∞≪𝑇1𝑇_∞≪𝑇_1

Embarrassingly Parallel 的例子

  • 图书馆 v.s. 分布式数据存储
  • 大脑 v.s. 深度神经网络
  • ……

1.5 实现互斥

能否使当前程序状态机独占计算机系统？

  • 类比：关掉电脑手机，专注一件事
  • 单处理器系统中 “其他任何事”：仅有中断

一条指令就可以实现原子性

  • x86: cli 清除 eflags 中的 IF bit
  • RISC-V: 清除 mstatus 的 MIE bit
  • AArch64: msr daifset, #3
    • 程序死循环 = 计算机系统卡死

道高一尺、魔高一丈

  • 处理器有 NMI (Non-Maskable Interrupts)
  • 可以利用 NMI 实现错误监控
    • 设置硬件定时触发
    • 操作系统定时复位定时器
    • 触发 timeout，执行 NMI 处理程序
      • 例如，重启计算机

1.6 关中断不是万能的

操作系统可以，但普通程序不行

  • 中断保证了死循环不能把计算机 “卡死”
  • 操作系统不允许普通程序关中断
    • 但如果是操作系统代码，完全可以短暂关闭中断

单处理器系统可以，多处理器系统不行

  • 每个处理器有独立的寄存器组
  • 中断是每个处理器内部状态

2 使用 load/store 实现互斥

绕口令：A process 𝑃 can enter the critical section if the other does not want to enter, otherwise it may enter only if it is its turn.

实现假设

  • 任何时候可以执行一条 load/store 指令
  • 读写本身是原子的

并发的危险

  • 你很难从字面上判断它到底对不对

2.1 问题重述

举例：上厕所

若希望进入厕所，按顺序执行以下操作：

  1. 举起自己的旗子 (store)
  2. 把写有对方名字的字条贴在厕所门上 (store; 覆盖)

然后进入持续的观察模式：

  1. 观察对方是否举旗 (load)
  2. 观察厕所门上的名字 (load)
    • 对方不举旗或名字是自己，进入厕所，否则继续观察

出厕所后，放下自己的旗子

  • 不用管门上的字条

总结：A手上拿着B的旗子，B手上拿着A的旗子，也就是说最开始A和B都举旗子了，然后A和B就会抢着把对方的旗子贴在门上，然后A和B乱序贴完后就开始观察门上的名字，如果是自己，就进厕所，如果不是自己，就继续观察。（贴的时候闭眼，观察的时候睁眼）

结论：手快反而会后进入。

进入临界区的情况

  • 如果只有一个人举旗，他就可以直接进入
  • 如果两个人同时举旗，由厕所门上的标签决定谁进
    • 手快 🈶️ (被另一个人的标签覆盖)、手慢 🈚

一些具体的细节情况

  • A 看到 B 没有举旗
    • B 一定不在临界区
    • B 可能想进但还没来得及把 “B 正在使用” 贴在门上
  • A 看到 B 举旗子
    • A 一定已经把旗子举起来了 (!@^#&!%^(&^!@%#

自动遍历状态空间的乐趣：快速回答更多问题

  • 如果结束后把门上的字条撕掉，算法还正确吗？
    • 在放下旗子之前撕 v.s. 放下旗子之后撕
  • 先贴标签再举旗，算法还正确吗？
  • 观察模式两个查看操作的顺序影响正确性吗？
    • 看对方的旗有没有举起来
    • 看门上的贴纸是不是自己
  • 是否存在 “两个人谁都无法进入临界区” (liveness)、“对某一方不公平” (fairness) 等行为？
    • 都转换成图 (状态空间) 上的遍历问题了！

2.2 Model Checker和自动化

电脑为什么叫 “电脑”

- 因为它能替代部分人类的思维活动

回忆：每个班上都有一个笔记和草稿纸都工工整整的 Ta

  • Ta：认认真真完成老师作业
    • 工整的笔记可以启发思维，但花费了宝贵的人工
  • 我：烦死了！劳资不干了！玩去了
    • 战略：提出好的问题、适当地分解问题
    • 战术：尽可能使用先进工具替代机械思维活动
      • 对于 Peterson 算法：都是一个晚自习时间，model checker 可以回答更多更深刻的问题

关于学习 (思考)：Tree of Thoughts

  • 有一些别名：“批判性思维”、“第一性原理”……
  • 有一些实现：AlphaGo……

那个好好学习的、总被老师表扬的 Ta？

  • 听话的学生 → Chain of Thoughts (顺从)
  • 不听话的学生 → Tree of Thoughts (质疑)

2.3 实现 Peterson 算法

1
2
3
4
5
6
7
8
a = 1;    // 举起自己的旗子
turn = B; // 贴上对方的名字
do {      // 进入持续观察模式
} while (b && turn == B); // 对方举旗且门上是对方的的名字

// 临界区

a = 0;    // 放下自己的旗子
1
2
3
4
5
6
7
8
b = 1;
turn = A;
do {
} while (a && turn == A);

// 临界区

b = 0;

模型的假设：Atomic load & store

  • 但这个假设在现代多处理器上并不成立
  • 所以实际上按照模型直接写 Peterson 算法应该是错的？
    • 不妨实现了试一试？

c5-4.2-2.webp

2.4 现实中的 Peterson 算法

“实现正确的 Peterson 算法” 是合理需求

  • 编译器应该提供了机制实现

内存屏障 (Memory Barrier)

  • __sync_synchronize() = Compiler Barrier +
    • x86: mfence
    • ARM: dmb ish
    • RISC-V: fence rw, rw

编译器到底做了什么？

  • godbolt.org，不用装那些 cross compiler 了
    • 你甚至可以看到 compiler barrier 是如何在优化中传递的

3 在多处理器上实现互斥

继续回到厕所问题

为什么不能就 “等在门口” 呢？

  • 上一个人出来了，我再进去呗！
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int status = ✅;

void lock() {
retry:
    if (status != ✅) {
        goto retry;
    }
    status = ❌;
}

void unlock() {
    status = ✅;
}
// 锁门的时候有人，不进去，不锁门的时候进去，但是这样是不可以的，因为两个线程同时进去的时候，都会观测到 ✅

没有跨语句 (指令) 的原子性？

  • Peterson 算法真是大费周章
1
2
3
4
5
retry:
    if (status != ✅) {
        goto retry;
    }
    status = ❌;

软件不够，硬件来凑

  • 原子指令：一小段时间的 “Stop the World” 执行
  • 不可打断的 load + 计算 + store
    • x86: Bus Lock; RISC-V: LR/SC (来自 MIPS) + atomic

asm volatile("lock incq %0" : "+m"(sum));

c6-3-1.webp

3.1 第一个自旋锁

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 原子交换操作atomic_xchg
// atomic_xchg就可以stop the world，所以实现了多线程的原子操作
int status = ✅;

void lock() {
retry:
    int got = atomic_xchg(&status, ❌);
    if (got != ✅) {
        goto retry;
    }
}

void unlock() {
    atomic_xchg(&status, ✅);
}

有 “带条件写入” 的版本：节约写入内存带宽

并发编程 “很难”：想要完全理解并发程序的行为，是非常困难的——我们甚至可以利用一个 “万能” 的调度器去帮助我们求解 NP-完全问题。因此，人类应对这种复杂性的方法就是退回到不并发。通过互斥实现 stop/resume the world，我们就可以使并发程序的执行变得更容易理解——而只要程序中 “能并行” 的部分足够多，串行化一小部分也并不会对性能带来致命的影响。