互斥（基础）

发表于 Waline： 阅读次数： 本文字数： 2.7k 阅读时长 ≈ 10 分钟

概念

  • 临界区（critical section）：访问共享资源的一段代码，资源通常是一个变量或数据结构。
  • 竞态条件（race condition）：出现在多个执行线程大致同时进入临界区时，它们都试图更新共享的数据结构，导致非预期的结果。

当程序含有一个或多个竞态条件，程序的输出会因运行而异，具体取决于哪些线程在何时运行，因此结果是不确定的（non-deterministic）。

如何设计机制使得临界区避免出现竞态条件是「并发」的重要主题。

对于运行程序（尤其是并发程序）的两个重要属性：

  • 安全性：没有坏事发生
    • 安全性要求执行中的任何有限步骤内都保持这个性质。
    • 如：执行过程中不可出现除 0 错误
  • 活性：好事终将发生
    • 活性要求只要在最终能满足要求即可，一个隐含的要求是执行中不能发生「不可挽回」的步骤。
    • 如：执行最终停止（执行中间出现一个无限循环就「不可挽回」）

临界区解决方案需满足条件：

  • 互斥（Mutual Exclusion）：临界区内最多只能有一个线程（安全性）
  • 行进（Progress）：如果当前临界区内没有线程，并且有线程想要进入临界区，那么最终某个想要进入临界区的线程会进入该临界区（活性）
  • 有界等待（bounded waiting）：如果某个线程想要进入临界区，那么其等待的期限有限（期间其他线程进入该临界区次数有上限），不可一直排队等待（Fairness/No starvation）
    • 如果这个上限没有被指定，那么这就是一个活性属性，其最终会进入。
    • 如果这个上限被指定具体数字，那么这就是一个安全性属性，因为任何一次执行的有限步骤内，其等待进入的次数只要超过这个上限就发生了「坏事」。

除此以外还有一个临界区解决方案所关心的性能（performance），即进入和退出该临界区的两个操作应该相对于在该临界区内做的计算而言尽可能的小。

经验法则

设计并发算法时，优先考虑安全性。

锁

锁（Lock）是一个变量，其保存了锁在某一时刻的状态。状态有：

  • 可用的（available/unlocked/free），表示没有线程持有锁
  • 被占用的（acquired/locked/held），表示有一个线程持有锁，正处于临界区。

其提供两个配对操作：

  • lock()/acquire()：尝试获取锁，如果没有其他线程持有锁，该线程会获得锁，进入临界区，否则不会返回（该线程会卡在那里）
  • unlock()/release()：锁变成可用，之前如果有因获得锁操作没成功卡在那的线程，那么其中一个会进入临界区。

锁为程序员提供了最小程度的调度控制，通过给临界区加锁，保证临界区内只有一个活跃变量（互斥）。

1
2
3
4
5
6
7
8
9
10
long sum = 0;

void *T_sum(void *arg) {
    for (int i = 0; i < 1000000; i++) {
        lock();
        sum++;
        unlock();
    }
    return NULL;
}

如何实现这样的锁？

关中断

采用「关中断」可以实现锁，关中断后当前程序状态机就能独占计算机系统，然后 unlock 就是再次打开中断。

  • x86：cli 清除 eflags 寄存器的 IF 位；sti 设置 IF 位
  • ARM64：msr daifset, #2 设置 DAIF 寄存器的 IRQ 位；msr daifclr, #2 清除 IRQ 位
  • RISC-V：清除 mstatus 寄存器的 MIE 位；设置 mstatus 寄存器的 MIE 位

但是不是所有中断都可以被屏蔽，处理器有不可屏蔽中断（non-maskable interrupts），主要是为了一些不可处理或通知一些不可恢复的错误，如内部芯片系统错误、系统数据损坏等。

同时这种方式有问题，若临界区代码死循环了，那么整个系统也就卡死了。此外中断关闭时间过长会导致很多其他重要的外界相应丢失，如磁盘 I/O 完成事件。

另外关中断是特权指令，用户态应用无法执行，只有操作系统有权限。在操作系统内核的实现中，关闭中断倒是一个常见的操作。

以及对于多处理器系统，关中断是不够的，因为每个处理器有独立的寄存器组，中断也只是每个处理器内部状态。

lock 标志位

还可以尝试通过软件层面，例如通过 lock 标志位。

1
2
3
4
5
6
7
8
9
10
11
12
int flag = 0;

void lock() {
    while (flag == 1) { // 自旋的观测 flag
        // busy wait
    }
    flag = 1;
}

void unlock() {
    flag = 0;
}

这里假设了 load 一个变量并测试它是原子的（flag == 1），同时假设设置一个变量是原子的（flag = 1）。

但是这样的实现仍然会有问题，这个在上一篇介绍过了，检验 flag 和设置 flag 之间的操作不是原子的，可能会出现竞态条件。

此外上面的假设在单处理器时代是合理的设定，但现代计算系统已经不正确了，因为现代处理器有多级缓存，多核，乱序执行等特性，这些特性会导致上面的假设不成立。

判定条件

如果每个线程都采用同一个判定 test flag == 1，那么完全存在所有的线程可能得到同样的 true。但如果给每个线程的判定条件都不一样，且判定条件不可能同时为 true，那么就不会出现这个问题。一个线程为 true 意味着其他线程为 false，逻辑上达成了互斥。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// T1
void lock() {
    while (flag == 0) {
        // busy wait
    }
}

void unlock() {
    flag = 0;
}

// T2
void lock() {
    while (flag == 1) {
        // busy wait
    }
}

void unlock() {
    flag = 1;
}

这个要求了内存顺序一致性模型才能成立。代码中的 while 循环依赖对 flag 的即时可见性。若没有内存一致性保证，线程可能读取到陈旧的 flag 值，导致逻辑错误。

unlock 会给其他线程机会，自己下一次 lock 判定会为 false，只有别的进程unlock 后自己的下一次lock 判定才会为 true。所以这个方法是让每个线程「严格轮转」的。

这样的实现是正确的，但是这样的实现会导致「饥饿」（starvation），即某个线程可能永远得不到锁。

因为这个方法一个线程能否得到一个锁完全依赖于另一个线程是否先进入了临界区，如果另一个线程一直不释放锁，那么这个线程就永远得不到锁。这违背了活性。

若线程 T1 释放锁后立即尝试重新获取，但 T2 尚未运行，此时 T1 将因 flag = 0（需等待 flag = 1）被阻塞，直到 T2 运行并释放锁。

Peterson 算法

Dekker 算法是第一个被证明是正确的互斥算法，但是它的实现比较复杂，Peterson 算法是一个更简单的算法。

主要思想就是之前尝试中的 test 的改进：除了测试 flag 之外，还看看是否有别的线程要进入临界区（这个部分可以避免之前尝试出现的可能没有「行进」问题）。因此，除了有一个全局变量来进行 flag == i 判定，还得有一个全局变量 intents 来记录是否有其他线程要进入临界区。

Peterson 原始算法只能在两个线程上工作，不过该算法很容易拓展到 NN 个线程上（当然，NN 必须提前知道）。

Peterson 算法通过两个同步机制实现互斥：

  • 主动声明意图：每个线程明确表达进入临界区的意愿
  • 轮转谦让机制：当多个线程同时竞争时，通过轮转变量决定谁先进入
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
bool flag[2] = {false, false}; // 表示线程是否想进入临界区
int turn = 0;                  // 决定轮转顺序的关键变量

void lock(int self) {          // self 是当前线程编号（0 或 1）
    int other = 1 - self;      // 计算对方线程编号
    
    flag[self] = true;         // 步骤 1：声明自己的意图
    turn = other;              // 步骤 2：主动让出优先权
    
    // 步骤 3：谦让检查
    while (flag[other] && turn == other) {
        // 当对方也想进入临界区且轮转权在对方时，等待
    }
}

void unlock(int self) {
    flag[self] = false;        // 退出时撤销自己的意图
}
%%{init: {'themeVariables': { 'edgeLabelBackground':'#FFF5E6'}}}%%
flowchart TD
    subgraph Thread_1["线程 1 操作路线"]
        direction TB
        T1_Entry(["进入 lock(1)"])
        T1_SetFlag["设置 flag[1] = true"]:::green
        T1_SetTurn[设置 turn = 0]:::blue
        T1_Check{等待条件？}
        T1_True[[循环等待]]:::red
        T1_False[[进入临界区]]:::orange
    end

    subgraph Thread_0["线程 0 操作路线"]
        direction TB
        T0_Entry(["进入 lock(0)"])
        T0_SetFlag["设置 flag[0] = true"]:::green
        T0_SetTurn[设置 turn = 1]:::blue
        T0_Check{等待条件？}
        T0_True[[循环等待]]:::red
        T0_False[[进入临界区]]:::orange
    end
    
    T0_Entry --> T0_SetFlag --> T0_SetTurn --> T0_Check
    T0_Check -->|"flag[1] == true<br>且 turn == 0"| T0_True -.-> T0_Check
    T0_Check -->|等待条件不满足| T0_False
    
    T1_Entry --> T1_SetFlag --> T1_SetTurn --> T1_Check
    T1_Check -->|"flag[0] == true<br>且 turn == 1"| T1_True -.-> T1_Check
    T1_Check -->|等待条件不满足| T1_False

    classDef green fill:#D5F5E3,stroke:#2ECC71;
    classDef blue fill:#D6EAF8,stroke:#3498DB;
    classDef red fill:#FADBD8,stroke:#E74C3C;
    classDef orange fill:#FDEBD0,stroke:#EB984E;

双重保险机制：

  • flag[] 数组确保线程能感知彼此的意图
  • turn 变量确保不会出现互相谦让导致的死锁

只有同时满足「对方想进入临界区」和「轮转权在对方」两个条件才会等待，因此确保了至少有一个进程能通过检查。

通过 turn 变量的原子性修改，确保当多个线程同时竞争时，最终只会有一个线程满足条件

示例场景：

  1. 线程 A 和 B 同时设置 turn 为对方
  2. 由于赋值是原子的，最终 turn 值由最后写入的线程决定
  3. 保证至少有一个线程能跳出等待循环

正确性【待补充】

现实的 load 和 store 都不是原子的，甚至两个线程同一刻读的 flag 都不一致。因此现实架构上的 Peterson 算法其实是错误的。

在现代计算机体系架构下，由于多处理器以及乱序指令流的存在，需要硬件的支持，比如：内存屏障（Memory Barrier），例如 gcc 编译器可以将 __sync_synchronize() 编译为相应指令架构的内存屏障：

  • x86：mfence
  • ARM64：dmb ish（数据同步屏障）
  • RISC-V：fence（内存屏障）

硬件锁

上面提到的方案中，只要检验与设置两条指令可以原子化就可以了。软件方案需要用 Peterson 算法等来保证互斥，在现代计算机体系结构下还是有问题的，若硬件能支持两个操作的原子化，那么就不需要软件层面的保证了。

很多硬件架构提供了原子指令实现 Test-And-Set Lock (TSL)。x86 下利用 lock 前缀加上 cmpxchg 指令实现 TSL。

  • TSL (Test-And-Set Lock)：检查标志位是否为 0，同时将其置为 1，返回旧值
    • 特性：单指令完成「检查 + 修改」的原子操作
  • CAS (Compare-And-Swap)：比较内存值与预期值，若相等则替换为新值
    • 典型指令：cmpxchg（x86架构）
    • CAS 是更通用的原子操作，TSL 是 CAS 的特例（预期值固定为 0）

lock 前缀作用：

  • 总线锁定：通过 lock 前缀触发总线锁，阻止其他 CPU 访问该内存地址
  • 缓存一致性：触发缓存一致性协议（如 MESI），确保所有 CPU 缓存同步
  • 自旋等待：执行期间其他 CPU 访问该地址会被阻塞直到操作完成
1
2
3
4
5
6
7
8
9
10
11
12
13
// 原子比较交换操作
asm volatile(
    "lock cmpxchg %2, %1"  // 原子比较交换指令
    : "+a" (expected)      // 用 eax 寄存器保存预期值
    : "m" (flag),          // 内存中的锁标志
    "r" (1)                // 要设置的新值
    : "memory", "cc"       // 告知编译器内存和条件码会被修改
);

// 等价于
if (flag == 0) {
    flag = 1;
}

有了 TSA 硬件支持，之前的锁可以实现如下：

1
2
3
4
5
6
7
8
9
10
11
int flag = 0; // 锁标志位

void lock() {
    // 持续尝试直到成功获取锁
    while(__sync_val_compare_and_swap(&flag, 0, 1) != 0); 
    // 等效于：while(TSL(flag) == 1);
}

void unlock() {
    flag = 0; // 释放锁
}

事实上，所有 x86 CPU 都具有锁定一个特定内存地址的能力，当这个特定内存地址被锁定后，它就可以阻止其他的系统总线读取或修改这个内存地址。通过 Lock 指令前缀 + 具体指令，就可以在执行这个具体指令时「锁住」。