ARM 多核并行编程

发表于 分类于

从线程模型与 Pthreads 入手，覆盖 Linux 内核同步原语、LDREX/STREX 原子操作，以及 false sharing、死锁、cache thrashing 等常见多核性能陷阱。

1. 为什么操作系统不够用？

在 SMP 系统中，操作系统能够把不同的线程调度到不同 CPU 核心上运行，但它不会自动将一个应用拆分成多个线程。

因此，当系统中只有一个主要应用（dominant application）占据大部分 CPU 时间时，即使拥有多个核心，也可能只有一个核心处于繁忙状态，其余核心大多空闲。这不仅浪费计算资源，也不利于发挥多核处理器的性能优势。

要充分利用多核，开发者需要主动将应用拆分为多个可以并行执行的线程，再由操作系统调度到不同核心运行。

2. Amdahl 定律：并行化的理论上限

Amdahl 定律描述了程序并行化后的理论最大加速比：

1
Speedup = 1 / ((1 - P) + (P / N))

其中，P 为程序中可并行执行的比例，N 为 CPU 核心数。

例如，当 90% 的代码可以并行时，即使使用 4 核 CPU，理论最大加速比也只有 3.08 倍；如果只有 50% 的代码可并行，那么无论增加多少核心，加速比都不会超过 2 倍。

需要注意的是，Amdahl 定律是假设没有任何同步和调度开销的理论上限。实际程序还会受到锁竞争、线程同步、缓存一致性、内存带宽等因素影响，因此实际性能通常会低于理论值。

Amdahl 定律告诉我们：多核带来的性能提升，最终取决于程序中有多少工作能够并行执行，而不是 CPU 核心有多少。

3. 并行任务分解策略：数据、任务与功能分解

并行化的第一步是分解——把程序的工作切分成能并发执行的小块。以下是三种策略，各自适用于不同的程序特征。

3.1 数据分解（Data Decomposition）

适用场景：算法对大量数据执行相同的操作，且每个数据元素的处理独立于其他元素。

典型案例：颜色空间转换（RGB → YUV）

1
2
3
输入：一个像素数组，每个像素有 R、G、B 三个分量
输出：一个同样大小的像素数组，每个像素有 Y、U、V 三个分量
计算：每个输出像素的 Y、U、V 值仅依赖于同位置输入像素的 R、G、B

因为像素之间的计算完全独立——不存在数据依赖——你可以把图像切成 N 块（N 为核心数），每个线程处理一块：

1
2
3
4
线程 0 → 处理像素 [0, W*H/N)
线程 1 → 处理像素 [W*H/N, 2*W*H/N)
...
线程 N-1 → 处理像素 [(N-1)*W*H/N, W*H)

实践要点：

  • 切分粒度要合理：每个像素开一个线程是愚蠢的（线程创建开销远大于像素转换）
  • 尽量让每个线程处理连续的内存块——cache 友好
  • 此类任务同时适合 NEON 加速：数据分解 + SIMD 双层并行效果更佳

3.2 任务分解（Task Decomposition）

适用场景：程序中有多个彼此独立的、可并发执行的操作单元。

典型案例：程序启动序列

程序启动时需要做两件事：

  • 检查软件许可证是否有效
  • 显示包含版权信息的启动横幅

这两个操作互不依赖——许可证检查不需要等横幅画完，横幅也不依赖许可证结果。把它们分到两个线程里，启动时间缩短一半。

任务分解的难点在于识别独立性：你必须分析离散操作之间的交互，找到数据依赖的边界。一旦找到，原代码可以不做修改——只要把它们包装成独立的 pthread_create() 调用即可。

3.3 功能分解 / 软件流水线（Functional Decomposition）

适用场景：算法内部有串行依赖，但依赖是数据的、不是时间的——类似于 CPU 内部的指令流水线。

典型案例：MPEG 视频编码器

MPEG 编码是一个典型的多阶段流水线：

1
2
3
4
5
6
原始视频帧
  → 帧内/帧间冗余去除
    → 量化（减少比特数）
      → 运动矢量补偿
        → 游程编码
          → 压缩子码流存储

从一个帧的视角看，各阶段是串行的（前一阶段的输出是后一阶段的输入）。但从多帧的视角看，却是并行的：

1
2
3
4
5
6
时间轴：
  t0: 帧0 → 冗余去除 |                         |
  t1: 帧0 → 量化     | 帧1 → 冗余去除           |
  t2: 帧0 → 运动补偿 | 帧1 → 量化    | 帧2 → 冗余去除 |
  t3: 帧0 → 游程编码 | 帧1 → 运动补偿 | 帧2 → 量化      |
  ...

这本质上是软件流水线：当阶段 1 在处理帧 N+1 时，阶段 2 可以参考帧 N 的数据同时工作。而且在单一阶段内部还可以叠加数据分解——比如运动矢量补偿阶段用多个线程并行处理同一帧的不同区域。

3.4 粒度选择的权衡

无论哪种分解方法，粒度都是关键决策：

粒度太细 粒度太粗
线程数爆炸，创建/销毁开销淹没计算 并行度不足，核心闲置
单线程工作量太小，调度开销 > 有效计算 负载不均衡——一个慢线程拖累所有人
数据块太小，cache 局部性差 数据块太大，cache 不够用

建议是从较大的粒度开始，用 profiler 找到瓶颈后再细化。不要过早优化粒度。

4. 两种线程模型：fork-join 与 workers’ pool

分解完了，下一步是用代码把逻辑块映射为可调度的线程。以下是两种主流模型。

4.1 Fork-Join 模型

注意：这里的 fork 和 UNIX 的 fork() 系统调用完全不同。Fork-Join 中的 “fork” 指”派生一个新线程”。

工作方式：需要时创建线程 → 各自执行任务 → 主线程在 join 点等待子线程完成 → 继续执行。

1
2
3
4
5
6
7
8
9
main thread:
  fork(thread_A)
  fork(thread_B)
  fork(thread_C)
  ... 主线程同时做自己的事 ...
  join(thread_A)   ← 在此阻塞，直到 thread_A 完成
  join(thread_B)   ← 在此阻塞，直到 thread_B 完成
  join(thread_C)   ← 在此阻塞，直到 thread_C 完成
  ... 所有线程都完成了，继续 ...

在 Pthreads 中，线程分为两种：

类型 行为 资源回收
Detached（分离） 后台执行，完成后自动终止，不通知父线程 自动释放（不含手动分配的数据）
Joinable（可汇合） 执行完成后保留状态，等待父线程调用 pthread_join() 由 pthread_join() 触发的回收

Fork-Join 的开销：

  • 线程创建/销毁的系统调用代价
  • Join 点的同步等待：一个慢线程拖慢所有人
  • 因此，线程必须有足够长的寿命来摊平这些开销

4.2 Workers’ Pool（工作者池）模型

工作方式：应用启动时预先创建一组 worker 线程 → 一个 boss（分发者）将任务分派给空闲的 worker → worker 完成任务后报告 boss、等待新任务。

1
2
3
4
5
6
7
8
9
               ┌─────────┐
Work queue →   │  Boss   │
               └────┬────┘
          ┌────────┼────────┐
          ▼        ▼        ▼
       Worker0  Worker1  Worker2
          │        │        │
          └────────┼────────┘
             完成 → 报告 → 等待新任务

几种变体：

变体 分发方式 特点
推模型 Boss 主动把任务分配给空闲 Worker Worker 中断（通知）Boss 表示可用
拉模型 Boss 把任务放入队列，Worker 主动来取 也称为 Work Queue 模型
多 Boss 多个 Boss 共享一个 Worker 池 适合多种类型的任务来源

Workers’ pool 的优势：

  • 消除线程创建/销毁开销——线程只创建一次
  • 可动态调节 worker 数量以应对负载峰值
  • 适合”持续消费输入数据”的流式处理场景

权衡：即使 worker 处理固定量的数据，数据依赖也可能导致执行时间不同——负载不均衡始终存在。

5. Pthreads 入门

以 Pthreads（POSIX Threads）为示例讲解线程库的使用。Pthreads 是 POSIX 标准（IEEE 1003）的子集，提供一套创建、管理、同步线程的 C API。Linux 的 NPTL（Native POSIX Thread Library）实现了 pthread_create() 与内核任务的一一映射。

5.1 编译与链接

1
2
#include <pthread.h>
#include <semaphore.h>

编译时需要链接 pthread 库：

1
arm-linux-gcc -o app app.c -lpthread

5.2 线程的创建与终止

1
2
3
4
5
6
int pthread_create(
    pthread_t *thread,          // [out] 线程标识符
    const pthread_attr_t *attr, // 线程属性（优先级等），NULL = 默认
    void *(*start_routine)(void*), // 线程入口函数
    void *arg                   // 传给入口函数的参数
);

线程终止的两种方式：

  • 入口函数正常 return
  • 调用 pthread_exit(void *retval)

5.3 线程的汇合与分离

1
2
3
4
5
6
7
8
int pthread_join(pthread_t thread, void **retval);
// 阻塞调用线程，等待指定线程终止。无法 join 已 detach 的线程。

int pthread_detach(pthread_t thread);
// 将线程标记为 detached——终止后自动回收资源。
// joinable 线程终止后，若没有线程对它调用 pthread_join()，
// 其资源不会被回收，形成类似僵尸进程的资源泄漏。
// 解决办法是调用 pthread_join() 或在创建时设置为 detached。

5.4 Mutex（互斥锁）

1
2
3
4
5
6
7
pthread_mutex_t mutex;

pthread_mutex_init(&mutex, NULL);    // 初始化
pthread_mutex_lock(&mutex);           // 加锁（阻塞直到成功）
pthread_mutex_trylock(&mutex);        // 尝试加锁（失败立即返回，不阻塞）
pthread_mutex_unlock(&mutex);         // 解锁
pthread_mutex_destroy(&mutex);        // 销毁

Pthreads 还支持三种 mutex 类型：NORMAL（默认，不检测死锁/重复加锁）、ERRORCHECK（重复加锁返回错误）和 RECURSIVE（允许同一线程多次加锁，配合计数解锁）。

5.5 Read-Write Lock（读写锁）

读写锁允许多个读者并发持有锁，但写者独占。适合读多写少的场景：

1
2
3
4
5
6
7
pthread_rwlock_t rwlock;

pthread_rwlock_init(&rwlock, NULL);     // 初始化
pthread_rwlock_rdlock(&rwlock);         // 读锁（允许多个读者并发）
pthread_rwlock_wrlock(&rwlock);         // 写锁（排他）
pthread_rwlock_unlock(&rwlock);         // 解锁
pthread_rwlock_destroy(&rwlock);        // 销毁

5.6 Condition Variable（条件变量）

条件变量是生产者-消费者模型的基础，与 mutex 配合实现”等待某个条件满足”：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
pthread_mutex_t mutex;
pthread_cond_t cond;

// 等待者
pthread_mutex_lock(&mutex);
while (!condition) {                    // 必须用 while 而非 if
    pthread_cond_wait(&cond, &mutex);   // 原子释放 mutex 并睡眠
}
pthread_mutex_unlock(&mutex);

// 通知者
pthread_mutex_lock(&mutex);
condition = true;
pthread_cond_signal(&cond);             // 唤醒一个等待者（或 broadcast 唤醒全部）
pthread_mutex_unlock(&mutex);

要点：pthread_cond_wait() 必须配合 while 循环使用（而非 if），以处理虚假唤醒（spurious wakeup）。

5.7 Barrier（障碍同步）

Barrier 允许多个线程在同步点集体等待，直到所有线程到达后才继续：

1
2
3
4
5
6
7
pthread_barrier_t barrier;

pthread_barrier_init(&barrier, NULL, N);  // 等待 N 个线程
// ... 各线程并行执行 ...
pthread_barrier_wait(&barrier);           // 所有线程在此阻塞，直到第 N 个到达
// ... 所有线程同步后继续 ...
pthread_barrier_destroy(&barrier);

典型的应用场景是迭代型并行算法——每次迭代结束后所有线程在 barrier 处同步，确保上一轮结果已全部产出后再开始下一轮。

5.8 Semaphore（信号量）

与 mutex 的关键不同：semaphore 是计数型的，可以从大于 1 的值开始。

1
2
3
4
5
sem_t sem;

sem_init(&sem, 0, initial_value);   // 初始化（0=线程间共享）
sem_wait(&sem);                      // P 操作：递减，若值为 0 则阻塞
sem_post(&sem);                      // V 操作：递增，唤醒等待者

5.6 完整示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <pthread.h>
#include <stdio.h>

void *thread_func(void *vargp) {
    printf("Hello from POSIX thread!\n");
    return NULL;
}

int main(void) {
    pthread_t tid;
    pthread_create(&tid, NULL, thread_func, NULL);
    /* 主线程和子线程在此并发的区域 */
    pthread_join(tid, NULL);
    return 0;
}

6. 多线程性能：你必须注意的三点

多线程编程中有三个非直觉的性能要点：

6.1 线程也有自己的栈

每个线程有独立栈空间。大量线程意味着大量栈内存。默认栈大小通常较大（Linux 上默认 8MB），如果创建数百个线程，栈空间就会吃掉大量虚拟地址。可通过 pthread_attr_setstacksize() 显式设置，但设太小会导致栈溢出。

6.2 Mutex 竞争浪费核心周期

多个线程争抢同一个 mutex/semaphore 时，失败者会阻塞（或 busy-wait）——核心周期被白白浪费。研究领域有大量关于”如何减少锁竞争”的技术，基本思路是：

  • 缩短临界区（只锁真正需要保护的最小代码段）
  • 用更细粒度的锁（锁数据，而非锁整个数据结构）
  • 考虑无锁数据结构

6.3 线程创建本身有开销

pthread_create() 不是免费的——它涉及内核调度、栈分配、上下文初始化。通过预先创建线程池（参见 workers’ pool 模型）可规避这个开销——线程在池中”休眠”，有任务被唤醒执行，完成后返回池中等待再用，而非销毁重建。

7. 同步机制的全景对比

Linux 内核提供了四类同步原语，它们也是 Pthreads 等用户态线程库的底层实现基础。

7.1 Completions（完成量）

Linux 内核特有的轻量级机制，本质是一个”完成信号旗”。

1
2
3
4
5
6
7
8
struct completion comp;

// 等待者
wait_for_completion(&comp);   // 睡眠直到收到信号

// 发送者
complete(&comp);              // 唤醒一个等待者
complete_all(&comp);          // 唤醒所有等待者

适用场景：两个任务之间”A 等 B 做完某事”的一次性同步。开销极低——等待者可以睡眠。

7.2 Spinlock（自旋锁）

1
2
3
4
5
spinlock_t lock;

spin_lock(&lock);      // 获取锁（失败则 busy-wait）
/* 临界区 */
spin_unlock(&lock);    // 释放锁

核心特征：

  • 不睡眠：获取失败后不调用 schedule()，而是循环检查锁状态
  • 关抢占：持有 spinlock 期间内核抢占被禁用
  • 极短临界区专用（锁持有时间 < 两次上下文切换的时间）

适用场景：中断上下文、极短临界区。绝对不能在持有 spinlock 时睡眠。如果线程和中断共享同一把 Spinlock，线程端应使用 spin_lock_irqsave() / spin_unlock_irqrestore()，避免被中断抢占后再次获取同一把锁而发生死锁。

7.3 Semaphore（信号量）

1
2
3
4
struct semaphore sem;

down(&sem);    // P 操作（获取）
up(&sem);      // V 操作（释放）

核心特征：

  • 会睡眠：获取失败时当前任务让出 CPU，进入等待队列
  • 计数型：可以为大于 1 的值（控制同时访问资源的线程数量）
  • 适用于临界区执行时间较长的情况
维度 Spinlock Semaphore
失败行为 Busy-wait（自旋） 睡眠（让出 CPU）
临界区长度 必须极短 可以较长
中断上下文 可以 不可以（中断上下文不能睡眠）
持有期间抢占 禁用 允许
CPU 开销 浪费核心周期 有上下文切换开销

7.4 同步原语选择决策树

1
2
3
4
5
6
7
8
9
10
需要同步？
  ├── 临界区极短（< 几微秒），不可睡眠？
  │     → Spinlock
  ├── 临界区较长，可以睡眠？
  │     ├── 一次只允许一个线程？
  │     │     → Mutex（binary semaphore）
  │     └── 允许多个并发？
  │           → Counting Semaphore
  └── 简单的"等 B 做完"信号？
        → Completion

8. ARM 原子操作：LDREX/STREX

无锁数据结构的底层硬件基础是 ARM 的独占式加载/存储指令——LDREX（Load Exclusive）和 STREX（Store Exclusive）。它们配合实现 compare-and-swap（CAS）和 fetch-and-add 等原子操作。

1
2
3
4
5
6
loop:
    LDREX R1, [R0]          @ 以独占模式加载共享变量
    ADD   R1, R1, #1        @ 修改（无需锁保护，因为在独占段内）
    STREX R2, R1, [R0]      @ 尝试以独占模式写回
    CMP   R2, #0            @ 检查 STREX 是否成功（0=成功，1=失败）
    BNE   loop              @ 失败则重试（另一核心在 LDREX 和 STREX 之间访问了该地址）

STREX 的成功取决于：在 LDREX 和 STREX 之间，是否有其他核心或 DMA 访问了同一独占内存地址。硬件通过本地独占监视器（Local Exclusive Monitor）和全局独占监视器（Global Exclusive Monitor）来追踪独占状态。

GCC 提供了封装这些指令的内置函数：

1
2
3
4
5
6
7
8
int old_val, new_val;

// __sync 系列（旧版，向后兼容）
old_val = __sync_fetch_and_add(&counter, 1);  // 原子 fetch-and-add
new_val = __sync_add_and_fetch(&counter, 1);  // 原子 add-and-fetch

// __atomic 系列（C11 标准，推荐使用）
__atomic_fetch_add(&counter, 1, __ATOMIC_SEQ_CST);

在 ARM 上，__atomic_fetch_add 最终编译为 LDREX / ADD / STREX / CMP / BNE 的重试循环——硬件级的无锁原子操作。

9. 无锁同步：RCU 与 Seqlock

锁不是解决同步问题的唯一手段。在某些场景下，锁本身成为性能瓶颈——尤其是读者远多于写者时。以下是两种 Linux 内核的无锁机制。

9.1 RCU（Read-Copy-Update）

核心思想：写者不直接修改共享数据——而是复制一份、在副本上修改、再原子地发布新版本。读者始终读旧版本或新版本——永远不会读到”正在修改一半”的脏数据。

1
2
3
4
5
6
7
8
9
10
11
Reader 视角：
  rcu_read_lock();
  data = rcu_dereference(shared_ptr);  // 获取当前版本的指针
  // 使用 data ...
  rcu_read_unlock();

Writer 视角：
  1. 复制 shared_data → new_data
  2. 修改 new_data
  3. rcu_assign_pointer(shared_ptr, new_data);  // 原子发布
  4. synchronize_rcu();  // 等所有 reader 退出临界区后回收旧数据

为什么读者完全无锁？ 因为 rcu_dereference() 仅仅是读一个指针——不涉及任何原子操作或锁。写者的 synchronize_rcu() 则昂贵得多——它要等到所有 CPU 都经历一次上下文切换（保证所有已进入临界区的 reader 都已退出）。

适用场景：

  • 读多写少（路由表、文件缓冲区、垃圾回收）
  • 读者绝不能阻塞
  • 能容忍”读到的可能是旧版本”（最终一致性）

不适用场景：

  • 写操作频繁
  • 临界区很长（延迟旧数据回收）

9.2 Seqlock（顺序锁）

核心思想：读者无锁读取，但读完后验证数据是否被并发修改。如果被改了，重试。

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

// Reader
do {
    unsigned seq_no = read_seqbegin(&seq);
    // 读取共享数据 ...
} while (read_seqretry(&seq, seq_no));  // 检查是否被写过

// Writer
write_seqlock(&seq);
// 修改共享数据 ...
write_sequnlock(&seq);

关键特征：

  • 读者完全无锁、无原子操作
  • 读者可能重试（当与写者冲突时）
  • 写者排他（同一时刻只有一个写者）
  • 适用于”临界区很短、读者极其多”的场景

典型案例：Linux 内核的 jiffies（系统滴答计数器）——被无数读者频繁访问，仅由定时器中断以高优先级写入。用 seqlock 替代 mutex，读者完全不受限。

9.3 无锁 vs 有锁的选择

场景 推荐机制
读极多、写极少、数据可复制 RCU
读极多、临界区短、数据不适合复制 Seqlock
读写均衡、临界区短 Spinlock
读写均衡、临界区长 Mutex/Semaphore

10. 五大性能陷阱：从带宽到活锁

多核环境下常见的五类性能问题：

10.1 带宽瓶颈（Bandwidth）

根因：集群内所有核心共享同一个外部内存接口，核心运行频率远高于内存。I/O 密集型代码的瓶颈不在计算，在带宽。

解决策略：

  • 优化代码本身——减少 cache miss 就是减少带宽消耗（见第 18 章优化技巧）
  • 使用线程亲和性（thread affinity）让调度器把线程钉在特定核心上，减少跨核 cache 迁移带来的额外总线流量

10.2 线程依赖与优先级反转

Starvation（饥饿）：一个线程反复尝试获取资源，但始终被其他线程抢先，永远得不到执行。

Priority Inversion（优先级反转）：经典场景——

1
2
3
4
5
6
时间线:
  高优先级线程 H 需要资源 R
  低优先级线程 L 持有资源 R 的锁
  中优先级线程 M 不依赖 R，持续运行
  → H 等待 L 释放锁，但 L 被 M 抢占，无法执行
  → H 实际上被 "优先级反转" 为最低优先级

Priority Inheritance（优先级继承）解法：

  • 当低优先级线程 L 持有资源 R 而高优先级线程 H 在等 R 时
  • L 的优先级临时提升至 H 的级别
  • L 可以不受 M 抢占地完成临界区，释放锁
  • L 的优先级恢复原值
  • H 现在可以获取锁

Linux 内核的 rt_mutex 实现了优先级继承。RTOS 通常内置此功能。

Race Condition：在单核系统上隐式依赖”任务按优先级顺序执行完毕”的代码，迁移到多核后可能失效——低优先级任务和高优先级任务可以同时运行，执行顺序不再有保证。

解法：

  • 快速修复：用线程亲和性把所有相关线程绑到一个核心上（恢复单核行为）
  • 正确修复：用显式同步机制（completion、semaphore）代替隐式时序依赖

10.3 Cache Thrashing（缓存颠簸）

在 SMP 系统中，一个任务可能被调度器在不同核心之间迁移：

1
2
3
4
5
时刻 T0: 任务在 Core 0 运行 → Core 0 的 L1/L2 缓存填满了任务的数据
时刻 T1: 任务被抢占，休眠
时刻 T2: 任务被调度到 Core 1 运行 → Core 1 的缓存是冷的……
         → 任务的所有访问全部 cache miss
         → 从外部内存重新加载 → 带宽消耗、延迟上升、功耗增加

这种”缓存刚暖就换核心”的模式称为 cache thrashing。内存密集型任务尤甚——它们的数据量足够大，能把每个核心的缓存都”搅乱”一次。

缓解手段：

  • 内核调度器尝试保持任务在同一个核心上（CPU affinity hint）
  • 开发者显式设置线程亲和性
  • CPU 硬件层面的 cache-to-cache migration（在 Cortex-A15/A7 集群中）可以降低迁移开销

10.4 False Sharing（假共享）

这是最隐蔽、也最难排查的性能杀手。它是一种非自愿的内存争用。

场景：

1
2
3
4
struct counters {
    int count_A;   // 由 Core 0 上的线程频繁写入
    int count_B;   // 由 Core 1 上的线程频繁写入
};

count_A 和 count_B 在逻辑上完全独立——Core 0 只写 count_A，Core 1 只写 count_B。但物理上它们落在了同一条 cache line（通常 32 或 64 字节）内。

发生了什么：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Core 0 写 count_A →
  → Core 0 获得该 cache line 的 Exclusive/Modified 状态
  → MESI 协议向 Core 1 发送 Invalidate 消息
  → Core 1 的该 cache line 被标记为 Invalid

Core 1 写 count_B →
  → cache line 在 Core 1 中已 Invalid → 必须重新从 Core 0 获取
  → Core 1 获得 Exclusive 状态
  → MESI 协议向 Core 0 发送 Invalidate 消息
  → Core 0 的该 cache line 被标记为 Invalid

→ 无限循环：一个 cache line 在两个核心之间乒乓迁移
→ 每次写入都触发 cache 一致性协议的全部开销
→ 性能不如单核！功耗还更高！

解决：

  • 用 __attribute__((aligned(64))) 确保独立变量不在同一 cache line
  • 在多线程数据结构的每线程字段之间插入 padding
  • 减少内层循环的并行粒度时格外谨慎

10.5 Deadlock 与 Livelock（死锁与活锁）

Deadlock（死锁） Livelock（活锁）
现象 线程互相等待，永久阻塞 线程持续运行，但系统整体没有进展
原因 循环资源依赖 不断失败并重试，彼此相互影响
比喻 两辆车在桥上顶牛 两人在走廊里不断互相让路，始终过不去

活锁举例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 线程1
lock(A);

if (trylock(B) == FAIL) {
    unlock(A);
    重试;
}

// 线程2
lock(B);

if (trylock(A) == FAIL) {
    unlock(B);
    重试;
}

死锁的四个必要条件（破坏任一即可预防）：

  1. 互斥：资源不能共享
  2. 持有并等待：持有锁的同时等待其他锁
  3. 不可剥夺：锁不能被强制释放
  4. 循环等待：A 等 B，B 等 C，C 等 A

解决思路：

  • 统一锁的获取顺序，避免循环等待。
  • 使用 pthread_mutex_trylock()，获取失败时释放已持有的锁并稍后重试，避免长期占有资源。
  • 对于无锁算法，可采用指数退避（Exponential Backoff）、随机重试等策略，降低 CAS 冲突，减少活锁发生的概率。

11. 线程亲和性：何时该把线程绑定到指定核心

Thread Affinity（线程亲和性） 是指将线程绑定到指定的 CPU 核心（或核心集合）上运行。

默认情况下，操作系统调度器会根据系统负载在各个核心之间迁移线程，以实现较好的负载均衡。但在线程频繁迁移时，CPU Cache 中的数据可能失效，从而影响性能。因此，在某些场景下，适当设置线程亲和性能够获得更好的性能。

适合设置线程亲和性：

  • 线程能够重复利用 Cache 数据，减少 Cache Miss。
  • 线程依赖特定核心的本地资源（如 per-CPU 数据结构）。
  • 为实时线程保留专用 CPU，减少调度干扰。

不适合设置线程亲和性：

  • 大量线程绑定到同一个核心，导致负载不均衡。
  • 线程负载变化较大，需要调度器动态迁移线程以充分利用各个核心。

ARM DS-5 Streamline 的 Core Map 视图可以可视化线程亲和性的实际分布——看到哪个核心过载、哪个空闲。

12. 线程安全与可重入性

线程安全（Thread-safe）和可重入（Reentrant）是两个容易混淆的概念，它们关注的问题并不相同。

可重入函数（Reentrant）

可重入函数可以在任意时刻被再次调用（例如被另一个线程调用，或在中断中再次调用），而不会破坏之前调用的执行状态。

通常需要满足：

  1. 不依赖可修改的全局或静态数据。
  2. 不在多次调用之间保存状态。
  3. 不返回指向静态数据的指针。
  4. 不调用非可重入函数。

线程安全函数（Thread-safe）

线程安全函数允许多个线程同时调用，并始终得到正确的结果。

它可以通过多种方式实现，例如：

  • 不共享可变数据（天然线程安全）。
  • 使用互斥锁保护共享数据。
  • 使用原子操作（Atomic）等无锁同步机制。

两者的关系

1
2
可重入 → 线程安全（必然，因为无需共享数据也就不需要锁）
线程安全 → 不一定可重入（可以用锁保护全局数据，违背条件 2）

典型反例：C 标准库的 ctime() ——每次调用返回一个指向静态缓冲区的指针，新调用会覆盖上次的结果。它不是可重入的，在多线程下会互相覆盖。应使用 ctime_r()（可重入版本）。

在改造单线程程序为多线程时，必须检查所有使用的库函数是否线程安全。如果库没有提供可重入版本，就需要用 mutex 把所有对该库的调用串行化。

13. SMP 系统上的性能剖析

ARM 多核处理器提供了额外的性能计数器，支持以下 SMP 特定事件：

  • Coherent linefill missed in all cores：所有核心的缓存中都未命中，必须从外部内存加载
  • Coherent linefill hit in other core caches：本核未命中，但数据存在于另一核心的缓存中（cache-to-cache 迁移）

这两个计数器是分析 false sharing 和 cache thrashing 的关键数据来源。ARM DS-5 Streamline 会配置一组默认的硬件性能计数器，针对性地追踪这些 SMP 特有的 cache 一致性事件。

14. 并行化决策框架

将本章知识转化为可操作的工作流：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
1. 识别主导应用：哪个程序占了绝大部分 CPU？
      │
2. 分析并行化潜力（Amdahl 定律）
   可并行比例 P 越高 → 加速比上限越高
      │
3. 选择分解策略
   ├── 同构数据处理 → 数据分解
   ├── 独立操作 → 任务分解
   └── 有依赖的流水线 → 功能分解
      │
4. 选择线程模型
   ├── 短期、固定任务 → Fork-Join
   └── 长期、持续消费 → Workers' Pool
      │
5. 实现同步
   ├── 选对锁的类型
   ├── 缩短临界区
   └── 考虑无锁替代
      │
6. 排查性能陷阱
   ├── Cache thrashing?
   ├── False sharing?
   ├── 优先级反转?
   └── 带宽饱和?
      │
7. 用 DS-5 Streamline 验证
   └── 回到步骤 2，迭代优化