Skip to content

并行与指令

一、引言

在并行计算中，任务通常需要协作，涉及共享数据的读写操作。为避免数据竞争（data race）导致的错误，任务间必须进行同步（synchronize），确保写操作完成后读操作才能安全执行。本节重点探讨MIPS架构中用于同步的硬件支持，特别是加锁（lock）和解锁（unlock）机制，以及链接取数（load linked, LL）和条件存数（store conditional, SC）指令对的实现。

关键概念：

  • 数据竞争：当两个来自不同线程的访存请求访问同一地址，连续发生，且至少一个是写操作时，称为数据竞争，可能导致读写错误。
  • 同步：任务间协调机制，确保读操作在写操作完成后进行。
  • 互斥（mutual exclusion）：通过加锁和解锁创建仅允许单一处理器操作的区域，防止并发访问冲突。

示例：8个记者协作撰写故事，其中总结者需等待其他记者完成章节撰写，需通过同步确保内容一致性。

二、同步的硬件支持

多处理器系统中，同步依赖硬件提供的原子操作原语，确保读写操作不可中断。原子操作要求在执行期间无其他操作插入，否则同步机制成本高昂，且随处理器数量增加而恶化。

1. 原子操作原语

体系结构设计者提供硬件原语（如原子交换），供系统程序员构建同步库，而非直接供用户使用。常见的原语包括：

  • 原子交换（atomic exchange/swap）：交换寄存器和存储器中的值，保证操作不可分割。
  • 原子比较和交换（atomic compare and swap）。
  • 原子取后加（atomic fetch-and-increment）。

原子性保证：

  • 硬件对并发操作排序，确保只有一个处理器成功执行原子操作。
  • 原子操作失败时，需重试，直到成功。

2. 锁机制

锁变量用于控制共享资源访问：

  • 锁状态：
    • 0：解锁（自由）。
    • 1：加锁（被占用）。
  • 加锁过程：
    • 处理器用寄存器中的1与锁单元值交换。
    • 返回锁单元原始值：
      • 0：加锁成功，锁单元置为1。
      • 1：锁已被占用，加锁失败，需重试。
  • 原子性：交换操作不可分割，防止多个处理器同时认为加锁成功。

示例：两个处理器竞争加锁：

  • 第一个处理器交换成功，返回0，锁置为1。
  • 第二个处理器交换返回1，失败，需重试。

三、MIPS中的同步实现

MIPS使用链接取数（LL）和条件存数（SC）指令对实现原子操作。

1. 指令说明

  • 链接取数（LL）：
    • 格式：ll $rt, offset($rs)
    • 功能：从地址$rs+offset读取值到$rt，标记该地址供后续SC指令检查。
  • 条件存数（SC）：
    • 格式：sc $rt, offset($rs)
    • 功能：尝试将$rt的值写入地址$rs+offset，若成功，$rt置为1；若失败（地址值被修改），$rt置为0。

原子性保证：

  • 若在LL和SC之间，锁单元值被其他处理器修改，SC失败，$rt置为0。
  • 失败时，需重试整个指令序列。

2. 原子交换实现

示例：实现锁单元（地址在$s1）与寄存器值的原子交换：

again:
    addi $t0, $zero, 1       # $t0 = 1（准备写入锁）
    ll $t1, 0($s1)           # 读取锁值到$t1
    sc $t0, 0($s1)           # 尝试将$t0写入锁，若成功$t0=1，失败$t0=0
    beq $t0, $zero, again    # 若失败，跳转重试
    add $s4, $zero, $t1      # 保存原始锁值到$s4

工作原理：

  • LL读取锁值，SC尝试写入1。
  • 若LL到SC间锁值未被修改，SC成功，锁置为1，$t0=1。
  • 若锁值被修改，SC失败，$t0=0，跳转again重试。
  • 最终，$s4保存锁原始值，锁单元值为1。

3. 注意事项

  • 指令选择：
    • LL和SC间只能使用寄存器-寄存器指令，避免触发异常或修改锁值。
    • 指令数需尽量少，减少竞争或无关事件导致SC失败的概率。
  • 死锁风险：
    • 重复的页面错误可能导致SC始终失败，需谨慎设计。
  • 单处理器适用性：
    • 在单处理器中，LL/SC对上下文切换敏感，切换会导致SC失败，确保原子性。

四、同步的应用场景

  • 链接取数（LL）和条件存数（SC）原语适用于：
    1. 并行程序中的线程同步：协作线程需同步以正确读写共享数据。
    2. 单处理器上的进程同步：协作进程需同步以确保共享数据访问正确。

场景示例：

  • 多线程程序：数据库事务中，多个线程更新同一记录，需加锁防止数据竞争。
  • 操作系统：多进程共享内核数据结构，需同步避免竞争。
  • 并行算法：如并行矩阵计算，线程间共享部分结果，需同步确保数据一致性。

五、扩展与总结

1. 其他同步原语

LL/SC机制可扩展为其他原语：

  • 原子比较和交换：

    • 比较锁值与预期值，相等则交换。

    • 示例代码：

      assembly ll $t1, 0($s1) # 读取锁值 bne $t1, $t2, fail # 若$t1 != 预期值，跳转失败 addi $t0, $zero, 1 # 准备写入新值 sc $t0, 0($s1) # 尝试写入 beq $t0, $zero, again # 失败重试

  • 原子取后加：

    • 读取值，递增后写回。

    • 示例代码：

      assembly ll $t1, 0($s1) # 读取值 addi $t2, $t1, 1 # 递增 sc $t2, 0($s1) # 尝试写回 beq $t2, $zero, again # 失败重试

2. 性能优化

  • 减少重试：优化LL/SC间指令，降低竞争导致的SC失败率。
  • 锁粒度：细化锁范围，减少互斥区大小，提升并发性能。
  • 无锁同步：使用原子操作替代锁，适用于简单场景，如计数器递增。

3. 硬件设计挑战

  • 原子性实现：需确保LL/SC指令对不可中断，可能通过缓存一致性协议或总线锁定实现。
  • 扩展性：多处理器系统中，同步开销随处理器数量增加，需高效硬件支持（如目录协议）。
  • 单指令原子性：某些架构（如x86）提供单条原子指令（如cmpxchg），简化同步实现。

4. 总结

  • 同步重要性：避免数据竞争，确保并行程序正确性。
  • MIPS LL/SC：通过原子指令对实现锁机制，支持多处理器和单处理器同步。
  • 设计原则：
    • 原子性：操作不可分割。
    • 最小化竞争：减少LL/SC间指令和锁冲突。
    • 扩展性：支持复杂同步原语和多线程场景。
  • 应用前景：随着多核处理器普及，高效同步机制对并行计算性能至关重要。