第 6 章 同步、锁与死锁

1
2
3
4
5
6
7

/* count++ 为什么不是原子的：它在机器层被拆成"读-改-写"三步，中间任何一处都可被抢占 */
void *worker(void *arg) {
    for (long i = 0; i < 1000000; i++) {
        count++;   /* 等价于 tmp = count; tmp = tmp + 1; count = tmp; 三步 */
    }
    return NULL;
}

1
2
3
4
5
6
7
8

     三条件的失效场景对照（两个线程 T1、T2 争一把锁）
  违反互斥        : T1 |----CS----|        两者同时在 CS，数据被破坏
                    T2      |----CS----|
  违反进展        : T1 申请 ─┐
                    T2 申请 ─┴─▶ 选择器不表态，CS 空着谁都不许进
                                  （活锁：大家都在动，没有进展）
  违反有限等待    : T1 申请 ──▶ 一直被后来的 T3、T4、T5… 插队
                                  （系统有进展，T1 被饿死）

1
2
3
4
5

  CAS(addr, expected, new) :
      old = *addr                 // 原子地读
      if (old == expected)        // 原子地比较
          *addr = new             // 原子地写
      return old                  // 无论成功失败都返回"操作前的值"

1
2
3
4
5
6
7
8
9

  ABA 在无锁栈上的真实破坏力
  初始栈:  top ─▶ [A] ─▶ [B] ─▶ [C]
  T1: old = top = A ; 读到 next = B ;   ⏸ 被抢占
  T2: pop A ; pop B ; push A           （B 已被回收）
      现在  top ─▶ [A] ─▶ [C]
  T2: 把 B 的那块内存重新分配出去（例如又压入一个 B'）
  T1 恢复: CAS(top, A, B)  成功！因为 top 当前确实等于 A
      ⟹ 新栈变成 top ─▶ [B]（可能已失效的对象）─▶ ???  ← 结构被撕裂
  关键：CAS 成功，但 T1 所基于的"世界状态"已经不存在了。

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

  lock 前缀的两种实现（按硬件世代）
  ── 早期（486 及之前）：锁总线 ──
     CPU 拉低 LOCK# 信号，独占内存总线整个操作周期
     ▸ 所有核的所有内存访问都被阻塞，代价与"总线宽度 × 操作周期"成正比
  ── Pentium Pro 及之后：锁缓存行 ──
     操作数已在本核缓存且缓存行处于 Exclusive/Modified ⟹ 不碰总线，缓存内部完成
     读-改-写，靠 MESI 保证原子性；缓存行不在本核（Shared/Invalid）⟹ 发 RFO
     （read-for-ownership）把该行独占过来再本地完成，只有此时才近似锁总线
     ▸ 结论：lock 的代价 ≈ 一次缓存行所有权转移，而不是一次总线独占
  ── 附带语义 ──
     lock 前缀同时是一条完整的全屏障（Intel SDM 明确其具有栅栏语义），
     所以 lock cmpxchg / lock xadd 之后不需要再补 mfence

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

/* TAS 自旋锁：用 xchg 抢占 0 → 1 的所有权 */
typedef struct { volatile int locked; } tas_lock_t;
static inline void tas_lock(tas_lock_t *l) {
    /* 为什么写成 while(xchg(...)) 而不是先读再 xchg：
       读操作不改变状态，从读到 0 到执行 xchg 之间仍可能被别人抢走，
       所以"是否拿到锁"必须由原子操作本身来回答，不能由普通读来预判 */
    while (__atomic_exchange_n(&l->locked, 1, __ATOMIC_ACQUIRE) != 0) {
        /* 空转；真实实现会在这里插 PAUSE（见 6.3.3） */
    }
}
static inline void tas_unlock(tas_lock_t *l) {
    /* 释放只需"临界区内的写先于 locked=0 可见"，所以普通写 + release 就够，
       不必再用一次原子 RMW，省掉一次独占缓存行的开销 */
    __atomic_store_n(&l->locked, 0, __ATOMIC_RELEASE);
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

  决策不等式
      自旋胜出        : T_cs < T_switch
      互斥（睡眠）胜出 : T_cs > T_switch
  数字口径（本书全书统一使用）
      T_switch ≈ 1 ~ 5 μs
          = 陷入内核（约 0.1~1 μs）+ 调度决策与队列操作
          + 两次上下文切换的寄存器/栈/地址空间相关开销（见第 5 章 5.5 节）
      ⟹ 工程上取分界 ≈ 1 μs：
         T_cs 在 100 ns ~ 1 μs 量级 ⟹ 自旋
         T_cs 在 10 μs 以上         ⟹ 睡眠
         中间地带 ⟹ "先短自旋再挂起"的自适应策略（Linux futex、Java 轻量级锁都走这条路）

1
2
3
4
5
6
7

  单核上 TAS 自旋锁的完整时间线（T1 持有锁，T2 自旋）
  时间 ─────────────────────────────────────────────────────────▶
  CPU   [T1 进入CS ....] [T1 被抢占] [T2 运行并自旋 ......] [T1 恢复] [释放锁]
                          ▲                                  ▲
                          │                                  │
                    调度器选中 T2                    T2 已烧掉近一个时间片
        T2 在这整段时间里执行的指令：全是 xchg，产出为零

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

  MCS 锁结构：一个原子 tail 指针 + 每个等待者一个栈上节点
     tail ─▶ [node3] ─▶ [node2] ─▶ [node1] ─▶ (holder 的节点)
              locked=1   locked=1   locked=0
  lock(qnode):
      qnode->next = NULL ; qnode->locked = 1     // 先把自己标成"未获锁"
      pred = xchg(&tail, qnode)                  // 原子地把 tail 指向自己，拿到前驱
      if (pred != NULL) {
          pred->next = qnode                     // 告诉前驱"我排在你后面"
          while (qnode->locked) pause;           // ★ 自旋在【自己的】节点上
      }
  unlock():
      if (qnode->next == NULL) {                 // 后继可能还没挂链，需处理这个竞态窗口
          if (CAS(&tail, qnode, NULL)) return;
          while (qnode->next == NULL) pause;
      }
      qnode->next->locked = 0                    // 只写【后继】的节点，唤醒它

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

/* 用信号量把"先 A 后 B"的顺序强制出来，而不是靠 sleep 猜时间 */
sem_t s_ab;
void *thread_a(void *_) {
    do_a();
    sem_post(&s_ab);            /* V：告诉 B "轮到你了"；初值为 0 意味着 B 会先阻塞 */
    return NULL;
}
void *thread_b(void *_) {
    sem_wait(&s_ab);            /* P：A 没发信号就阻塞在这里 */
    do_b();                     /* 这里的先后关系由计数器保证，与调度顺序无关 */
    return NULL;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

/* 错误模式：用 if 只检查一次，醒来后径直认为条件成立 */
pthread_mutex_lock(&m);
if (!queue_empty(&q)) {            /* ✗ 只检查一次 */
    item = queue_pop(&q);
    pthread_mutex_unlock(&m);
    return item;
}
pthread_cond_wait(&cv, &m);        /* ✗ 醒来后没有回到上面重新判断 */
item = queue_pop(&q);              /* 队列可能仍是空的 → 取到垃圾/越界 */
pthread_mutex_unlock(&m);
/* 正确模式：while 每次唤醒都重新判断条件 */
pthread_mutex_lock(&m);
while (queue_empty(&q)) {          /* 不把"被唤醒"等同于"条件成立" */
    pthread_cond_wait(&cv, &m);    /* 原子地释放 m 并入等待队列；返回时已重新持有 m */
}
item = queue_pop(&q);
pthread_mutex_unlock(&m);
return item;

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

  RCU 的三条规则（以链表中删除一个节点为例）
  ① 发布/替换：写者先构造新版本，再用【单个原子指针赋值】把它发布出去，
     读者始终看到"某个完整版本"，绝不会看到半成品（配合 release 屏障完成发布）
  ② 读侧不加锁：读者进入临界区只需禁用抢占，不做任何原子 RMW，
     因此读路径的可扩展性与核数近似无关
  ③ 延迟释放：写者不能立刻 free 旧节点，必须等所有"在发布之前就已开始
     的读者"全部离开临界区（synchronize_rcu 等待宽限期 grace period 结束）
  ┌── 宽限期 ──────────────────────────────────────────┐
  │ 旧读者:  [====临界区====]                          │
  │ 旧读者:        [====临界区====]                    │
  │ 新读者:                        [==] [==] [==]      │  ← 新读者只会看到新版本
  └────────────────────────────────────────────────────┘
                        ▲ 所有旧读者离开后，旧节点才可安全释放
  ⟹ 读侧零原子操作、零写共享行 ⟹ 无缓存行争抢、无锁等待、无死锁

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

  x86-TSO 下的 StoreLoad 重排（为什么 mfence 是 x86 上唯一必需的通用屏障）
  线程1                        线程2
  ─────────────────────        ─────────────────────
  X = 1;                       Y = 1;
  r1 = Y;   ← 可能读到 0       r2 = X;   ← 可能读到 0
  直觉上两个 r 不可能同时为 0（谁先写谁就该被读到），但 TSO 允许：
    - 线程1 的 X=1 还躺在【线程1 的写缓冲】里没进缓存，r1 读 Y 直接越过它
    - 线程2 同理 ⟹ r1 == 0 && r2 == 0 是合法结果
  ⟹ TSO 保持的三种顺序：LoadLoad、LoadStore、StoreStore
  ⟹ TSO 唯一不保持的：StoreLoad

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

  银行家算法算例（单一资源类型，共 12 个实例）
  进程      已分配 Alloc      最大需求 Max      仍需 Need = Max − Alloc
  P1            2                  6                    4
  P2            3                  8                    5
  P3            4                  7                    3
  已分配合计 = 2 + 3 + 4 = 9  ⟹  Available = 12 − 9 = 3
  ── 判安全：找安全序列 ──
  Available = 3：P1 需 4 > 3 跳过；P2 需 5 > 3 跳过；P3 需 3 ≤ 3 ✓
      P3 跑完释放 Alloc + Need = 4 + 3 = 7 ⟹ Available = 0 + 7 = 7
  Available = 7：P1 需 4 ≤ 7 ✓ 跑完释放 2 + 4 = 6 ⟹ Available = 7 − 4 + 6 = 9
  Available = 9：P2 需 5 ≤ 9 ✓
  ⟹ 安全序列存在：P3 → P1 → P2，当前状态【安全】
  ── P3 提出新请求 Request = 3（Available 3 → 0）──
  只有 P3 的 Need 变成 0 能完成，释放 0 + 7 = 7 ⟹ Available = 7
  再检查：P1 需 4 ≤ 7 ✓ ⟹ Available = 9；P2 需 5 ≤ 9 ✓
  ⟹ 新状态仍安全，【批准 Request = 3】
  ── 若 P1 改请求 Request = 1（Available 3 → 2）──
  所有 Need 都 > 2（P1 剩 3、P2 需 5、P3 需 3）⟹ 找不到任何一个能完成的进程
  ⟹ 无安全序列 ⟹ 【拒绝】
     注意：此时资源明明够用，拒绝的理由是"分配后将进入不安全状态"，
     这正是银行家算法与"资源够就给"的朴素做法最关键的区别

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

  两把锁上的经典死锁 ⟹ 等待图恰好是一条 2-环
  资源视角                          等待图视角
  ┌──────────┐                    ┌──────────┐
  │  锁 A    │◀──持有── T1        │   T1     │
  └──────────┘         │          └──────────┘
        ▲              │等待            │ 等待 B
        │              ▼                ▼
     等待 A         ┌──────────┐   ┌──────────┐
        │           │  锁 B    │   │   T2     │
        └──── T2 ───┴──────────┘   └──────────┘
                                    ▲    │
                                    └────┘  T2 等待 A ⟹ 环
  单实例资源：环 ⟺ 死锁（充要）
  多实例资源：环只是必要条件，需用"资源分配图可完全化简"来判定

1
2
3
4
5
6
7
8
9

  优先级反转的经典时序（H > M > L）
  时刻    L (低)          M (中)          H (高)          结果
  ─────────────────────────────────────────────────────────────
   t0   持锁 ──▶
   t1                                   申请锁 ──▶ 阻塞      H 等 L
   t2                  就绪 ──▶ 抢占！                     L 被挤下 CPU
   t3                  长时间运行 ──▶                     L 拿不到 CPU
   t4                                   仍在阻塞           ★ H 被 M 无限期延迟
                                                          （H 优先级最高，却等最久）