Skip to content

并发编程中的互斥实现

1. 阻止并发：基于“Stop-the-World”的思路

  • 核心思想： 通过某种方式暂停其他所有可能并发执行的操作，独占系统资源来执行临界区代码。
  • 操作系统内核实现：关闭中断
    • 在操作系统内核开发中，短暂地关闭硬件中断是一种实现 Stop-the-World 的常见技术。当中断被关闭时，处理器不再响应外部事件（如时钟中断、设备中断），也就不会发生抢占式的任务切换，当前执行流可以不被打扰地完成原子操作序列。
    • 局限性：
      • 仅限内核态： 出于安全和系统稳定性考虑，用户态应用程序绝对不能直接关闭中断。操作系统通过管理中断来实现对应用程序的控制。
      • 性能影响： 长时间关闭中断会严重影响系统响应性。
      • 多核问题： 在多处理器系统上，关闭一个 CPU 的中断并不能阻止其他 CPU 并发执行。

2. 使用基础 Load/Store 指令实现互斥

  • 核心思想： 尝试仅通过普通的内存读（Load）和写（Store）指令，结合精巧的算法逻辑来实现互斥。
  • 典型例子：Peterson 算法
    • Peterson 算法是一种经典的、仅使用 Load/Store 实现两个线程互斥的算法。
    • 复杂性与脆弱性：
      • 状态繁多： 即便是简单的算法，线程切换（并发交错）的可能性也极其繁多，手工分析和验证非常困难且容易出错。历史上许多互斥算法都被证明存在缺陷。
      • Model Checker 辅助： 可以使用模型检查器（Model Checker）来探索算法变体、语句顺序的影响，并快速反馈潜在问题，有助于理解算法原理。
      • 宽松内存模型挑战： 现代多处理器通常采用宽松内存模型（Relaxed Memory Models），允许指令重排、写缓冲等优化，这使得 Load/Store 指令的执行顺序和可见性变得不确定。在这种模型下，Peterson 算法不仅效率低下，而且要正确实现（例如，需要插入合适的内存屏障/栅栏 (Memory Barrier/Fence)）变得异常困难。

3. 在多处理器上实现互斥：基于原子指令

  • 核心思想： 利用处理器硬件提供的原子指令（Atomic Instructions）。这些指令能够保证其操作（通常是读-改-写序列）在多处理器环境下是不可分割的、原子的，从而提供短暂的、针对特定内存位置的 “Stop-the-World” 效果。
  • 常见原子指令及应用：
    • 带 lock 前缀的指令 (x86架构):
      • 例如 lock add, lock inc 等。lock 前缀确保其后的指令（如加法、自增）在执行期间会锁住总线或使用缓存一致性协议，阻止其他处理器访问同一内存地址，从而实现原子更新。可用于实现原子计数器等。
    • 比较并交换 (Compare-and-Swap, cmpxchg / CAS):
      • 功能： 原子地执行以下操作：读取内存位置 M 的当前值 old，将其与期望值 expected 比较。如果相等，则将 M 的值更新为新值 new；如果不相等，则不做任何操作。无论是否更新，操作都返回 M 原始的 old 值（或一个表示成功/失败的标志）。
      • 实现自旋锁 (Spinlock):
        1. 锁状态通常用一个内存变量表示（例如，0 代表 UNLOCKED，1 代表 LOCKED）。
        2. lock() 操作：循环尝试使用 cmpxchg 将锁状态从 UNLOCKED (0) 原子地设置为 LOCKED (1)。 // 伪代码 while (cmpxchg(&lock_variable, 0, 1) != 0) { // 比较失败，说明锁已被其他线程持有或状态不是0 // 继续旋转等待 (spin) } // cmpxchg 返回 0，表示成功将 0 原子地换成了 1，已获得锁
        3. unlock() 操作：简单地将锁状态设置回 UNLOCKED (0)。
      • 原理： cmpxchg 的原子性保证了即使多个线程同时尝试获取锁（执行 cmpxchg），也只有一个线程能够成功地观察到锁状态为 UNLOCKED (0) 并将其原子地修改为 LOCKED (1)。其他线程的 cmpxchg 会因为比较失败而不会修改锁状态。
  • 优势： 借助硬件提供的原子性，我们终于可以在多处理器系统上构建正确、高效的互斥原语（如锁）。