自旋锁退避算法

代码

template <typename Predicate>
void SpinWaitWhile(Predicate pred) {
    int count = 0;
    while (pred()) {
        if (count < 100) {
            tbb::detail::machine_pause(10);
            ++count;
        } else if (count < 200) {
            utils::yield();
            ++count;
        } else {
            std::this_thread::sleep_for(std::chrono::microseconds(count/100));
            if (count < 10000) {
                count += 100;
            }
        }
    }
}

static inline void machine_pause(int32_t delay) {
#if __TBB_x86_64 || __TBB_x86_32
    while (delay-- > 0) { _mm_pause(); }
#elif __ARM_ARCH_7A__ || __aarch64__
    while (delay-- > 0) { __asm__ __volatile__("isb sy" ::: "memory"); }
#else /* Generic */
    (void)delay; // suppress without including _template_helpers.h
    yield();
#endif
}

函数说明与CPU周期分析

该自旋锁退避算法采用三级退避策略，逐步降低CPU占用：

1. 第一阶段：`machine_pause()` (count < 100)

x86架构 (_mm_pause())

功能：执行 PAUSE 指令，提示CPU当前处于自旋等待状态
系统调用：❌ 否 - 纯用户态CPU指令
进入内核态：❌ 否 - 完全在用户态执行
调用调度器：❌ 否 - 不涉及操作系统调度
CPU周期：
- Intel处理器：约 140个周期（Skylake及以后架构）
- AMD处理器：约 10-40个周期
- 代码中调用 machine_pause(10)，实际执行10次 PAUSE 指令
开销来源：
- CPU指令执行延迟（主要开销）
- 流水线停顿（Pipeline Stall）
- 无系统调用开销、无上下文切换开销
作用：
- 降低CPU功耗（避免超线程的忙等待）
- 减少内存顺序违规（Memory Order Violation）
- 在超线程环境下，让出执行资源给同核心的另一个线程
总开销：每次循环约 1400-4000个周期（Intel）或 100-400个周期（AMD）

ARM架构 (isb sy)

功能：指令同步屏障（Instruction Synchronization Barrier），确保所有指令完成
系统调用：❌ 否 - 纯用户态CPU指令
进入内核态：❌ 否 - 完全在用户态执行
调用调度器：❌ 否 - 不涉及操作系统调度
CPU周期：约 10-50个周期（取决于具体ARM核心）
开销来源：
- CPU指令执行延迟（主要开销）
- 指令流水线同步等待
- 无系统调用开销、无上下文切换开销
作用：确保内存访问顺序，避免乱序执行导致的问题
总开销：每次循环约 100-500个周期

2. 第二阶段：`utils::yield()` (100 ≤ count < 200)

功能：主动让出CPU时间片，通常对应 sched_yield() 系统调用
系统调用：✅ 是 - 调用 sched_yield() 系统调用（Linux）或 SwitchToThread()（Windows）
进入内核态：✅ 是 - 必须进入内核态执行系统调用
调用调度器：✅ 是 - 主动调用内核调度器，将当前线程移出运行队列
CPU周期：
- 系统调用开销：约 1000-3000个周期
  - 用户态到内核态切换：~200-500周期
  - 系统调用处理：~300-1000周期
  - 内核态到用户态切换：~200-500周期
- 调度器开销：约 2000-5000个周期
  - 调度器决策：~500-1500周期
  - 运行队列操作：~300-800周期
- 上下文切换开销：约 3000-15000个周期（如果发生线程切换）
  - 寄存器保存/恢复：~1000-3000周期
  - TLB刷新：~500-2000周期
  - 缓存失效：~1500-10000周期
- 总计：6000-23000个周期
开销来源：
- 系统调用开销：用户态/内核态切换（主要开销之一）
- 调度器开销：调度决策和运行队列操作
- 上下文切换开销：如果调度器选择运行其他线程（主要开销）
- 缓存失效：线程切换导致L1/L2缓存失效
作用：
- 让调度器有机会运行其他线程
- 避免长时间占用CPU核心
- 在锁竞争激烈时，给持有锁的线程更多执行机会

3. 第三阶段：`sleep_for()` (count ≥ 200)

功能：线程主动睡眠指定时间
系统调用：✅ 是 - 调用 nanosleep() 或 futex() 系统调用（Linux）
进入内核态：✅ 是 - 必须进入内核态执行系统调用
调用调度器：✅ 是 - 将当前线程移出运行队列，放入等待队列
CPU周期：
- 系统调用开销：约 1000-3000个周期
  - 用户态到内核态切换：~200-500周期
  - 系统调用处理（设置定时器）：~500-1500周期
  - 内核态到用户态切换：~200-500周期
- 调度器开销：约 3000-8000个周期
  - 调度器决策：~500-1500周期
  - 运行队列操作：~500-1000周期
  - 等待队列操作：~500-1000周期
  - 定时器设置：~1500-4500周期
- 上下文切换开销：约 7000-42000个周期（必然发生）
  - 寄存器保存/恢复：~1000-3000周期
  - TLB刷新：~500-2000周期
  - 缓存失效：~5500-37000周期（L1/L2/L3缓存）
- 睡眠时间：count/100 微秒（例如 count=200 时睡眠2微秒）
- 总计：11000-53000个周期 + 睡眠时间
开销来源：
- 系统调用开销：用户态/内核态切换（主要开销之一）
- 调度器开销：调度决策、队列操作、定时器管理（主要开销之一）
- 上下文切换开销：线程必然被切换，寄存器、TLB、缓存全部失效（主要开销）
- 定时器开销：内核定时器设置和管理
- 唤醒开销：定时器到期后唤醒线程的开销（未计入上述周期）
作用：
- 大幅降低CPU占用
- 睡眠时间随 count 增长而增加（最大100微秒）
- 适用于锁竞争非常激烈或持锁时间较长的情况

退避策略总结

阶段	循环次数	主要操作	系统调用	内核态	调度器	CPU周期/次	适用场景
阶段1	0-99	`machine_pause(10)`	❌	❌	❌	100-4000	锁很快释放，短时间等待
阶段2	100-199	`yield()`	✅	✅	✅	6000-23000	中等竞争，需要让出CPU
阶段3	200+	`sleep_for()`	✅	✅	✅	11000-53000+	高竞争或长持锁时间

开销来源对比

开销类型	阶段1 (`machine_pause`)	阶段2 (`yield`)	阶段3 (`sleep_for`)
CPU指令执行	✅ 主要开销	❌	❌
系统调用	❌	✅ 主要开销之一	✅ 主要开销之一
用户态/内核态切换	❌	✅ 主要开销之一	✅ 主要开销之一
调度器调用	❌	✅ 主要开销之一	✅ 主要开销之一
上下文切换	❌	⚠️ 可能发生	✅ 必然发生
缓存失效	❌	⚠️ 可能发生	✅ 必然发生
定时器管理	❌	❌	✅ 额外开销

这种分级退避策略能够在锁快速释放时保持低延迟（阶段1，纯用户态，无系统调用开销），同时在竞争激烈时避免浪费CPU资源（阶段2和3，通过系统调用和调度器协作降低CPU占用）。

PAUSE指令与普通指令的区别

在自旋锁实现中，为什么使用 PAUSE 指令而不是普通的空操作指令（如 NOP）？两者在硬件层面的行为有显著差异：

1. 执行延迟差异

特性	PAUSE指令	普通指令（如NOP）
执行周期	约140个周期（Intel）	1个周期
流水线行为	主动暂停流水线	正常流水线执行
功耗	降低功耗	正常功耗

为什么PAUSE需要更多周期？

PAUSE 指令被设计为延迟执行，而不是快速完成
CPU会主动等待一段时间，让内存子系统有机会完成待处理的操作
这140个周期是有意为之的延迟，而非性能缺陷

2. 内存顺序违规（Memory Order Violation）处理

普通指令的问题：

// 使用普通循环的自旋锁
while (lock.load() == LOCKED) {
    // 空循环或NOP - 可能导致内存顺序违规
}

在超线程（Hyper-Threading）环境下，两个逻辑核心共享执行单元
如果线程A在自旋等待，线程B在修改锁变量，CPU的乱序执行可能导致：
- 线程A持续读取锁的旧值（缓存未更新）
- 即使线程B已经释放锁，线程A仍无法感知
- 造成虚假的自旋等待

PAUSE指令的解决方案：

// 使用PAUSE的自旋锁
while (lock.load() == LOCKED) {
    _mm_pause(); // 提示CPU这是自旋等待
}

PAUSE 指令向CPU发出信号：当前处于自旋等待状态
CPU会：
- 暂停内存推测执行（Memory Speculation）
- 刷新内存访问队列
- 等待内存子系统完成待处理操作
减少内存顺序违规，确保能及时看到锁状态变化

3. 超线程资源分配

普通指令：

两个超线程竞争相同的执行资源
自旋线程占用大量执行单元，影响同核心另一个线程的性能
CPU无法区分”有用工作”和”忙等待”

PAUSE指令：

CPU识别出这是自旋等待，而非实际工作
在超线程环境下，优先将执行资源分配给同核心的另一个线程
提高整体CPU利用率

4. 功耗管理

普通指令：

CPU持续高速执行，功耗较高
在自旋等待期间浪费能源

PAUSE指令：

CPU可以降低执行单元的频率或暂停部分单元
显著降低功耗（特别是在移动设备和服务器上）

5. 实际性能对比

// 方案A：普通空循环（不推荐）
void spin_with_nop() {
    while (lock.load() == LOCKED) {
        // 空循环或NOP
    }
}

// 方案B：使用PAUSE（推荐）
void spin_with_pause() {
    while (lock.load() == LOCKED) {
        _mm_pause();
    }
}

性能差异：

延迟感知：方案B能更快感知到锁释放（减少内存顺序违规）
吞吐量：在超线程环境下，方案B的整体吞吐量更高
功耗：方案B功耗显著更低
单线程延迟：方案A可能略快（1周期 vs 140周期），但实际应用中差异可忽略

6. 为什么不能简单用空循环？

如果只是简单的空循环：

1	for (volatile int i = 0; i < 100; ++i); // 不推荐

问题：

❌ 无法解决内存顺序违规
❌ 无法优化超线程资源分配
❌ 功耗较高
❌ CPU无法识别这是自旋等待

总结

对比项	PAUSE指令	普通指令/NOP
执行周期	~140周期（有意延迟）	1周期
内存顺序	✅ 减少违规	❌ 可能违规
超线程优化	✅ 资源优先分配	❌ 无优化
功耗	✅ 降低	❌ 正常
锁感知速度	✅ 更快	❌ 可能延迟
适用场景	✅ 自旋等待	❌ 不适合

结论：PAUSE 指令虽然执行周期更长，但这是有意设计的延迟，用于优化自旋等待的整体性能。在自旋锁场景中，PAUSE 指令带来的收益（减少内存违规、优化资源分配、降低功耗）远大于其执行延迟的成本。

逻辑核心与执行单元

在理解超线程（Hyper-Threading）和PAUSE指令的作用时，需要明确逻辑核心和执行单元的概念：

1. 物理核心（Physical Core）

物理核心是CPU中实际存在的、独立的处理单元，包含：

执行单元（Execution Units）：ALU（算术逻辑单元）、FPU（浮点单元）、加载/存储单元等
寄存器文件（Register File）：通用寄存器、浮点寄存器
一级缓存（L1 Cache）：指令缓存（L1I）和数据缓存（L1D）
分支预测器（Branch Predictor）
指令解码器（Instruction Decoder）
重排序缓冲区（Reorder Buffer, ROB）

2. 逻辑核心（Logical Core）

逻辑核心是操作系统看到的”CPU核心”，在超线程技术中：

一个物理核心可以对应两个逻辑核心
每个逻辑核心有独立的寄存器文件和程序计数器（PC）
但共享执行单元和其他硬件资源

示例：

物理核心1
├── 逻辑核心0（线程0）
│   ├── 寄存器文件（独立）
│   └── 程序计数器（独立）
├── 逻辑核心1（线程1）
│   ├── 寄存器文件（独立）
│   └── 程序计数器（独立）
└── 共享资源
    ├── 执行单元（ALU、FPU等）
    ├── L1缓存
    ├── 分支预测器
    └── 指令解码器

3. 执行单元（Execution Units）

执行单元是CPU中实际执行指令的硬件单元，包括：

执行单元类型	功能	示例指令
ALU（算术逻辑单元）	整数运算	`ADD`, `SUB`, `AND`, `OR`
FPU（浮点单元）	浮点运算	`FADD`, `FMUL`, `FDIV`
加载单元（Load Unit）	从内存/缓存加载数据	`MOV`, `LOAD`
存储单元（Store Unit）	将数据写入内存/缓存	`STORE`, `MOV [mem]`
分支单元（Branch Unit）	处理分支指令	`JMP`, `CALL`, `RET`
SIMD单元	向量运算	`SSE`, `AVX` 指令

4. 超线程的工作原理

超线程（Hyper-Threading）允许一个物理核心同时运行两个线程：

时间线示例（单物理核心，双逻辑核心）：

时钟周期 | 逻辑核心0（线程A）        | 逻辑核心1（线程B）        | 执行单元使用情况
---------|------------------------|------------------------|------------------
1        | ADD指令（使用ALU）      | 等待                    | ALU: 线程A
2        | FPU指令（使用FPU）      | LOAD指令（使用Load）    | FPU: 线程A, Load: 线程B
3        | 等待（指令解码）        | ADD指令（使用ALU）      | ALU: 线程B
4        | STORE指令（使用Store）  | FPU指令（使用FPU）      | Store: 线程A, FPU: 线程B

关键点：

两个逻辑核心共享执行单元
当一个线程的指令在等待（如等待内存访问）时，另一个线程可以使用空闲的执行单元
这提高了硬件利用率，但两个线程会竞争相同的执行资源

5. 为什么PAUSE指令能优化超线程？

问题场景：

// 线程A在逻辑核心0上自旋等待
while (lock.load() == LOCKED) {
    // 空循环 - 持续占用执行单元
}

// 线程B在逻辑核心1上（同一物理核心）执行实际工作
do_real_work();

没有PAUSE的问题：

线程A的空循环持续占用ALU等执行单元
线程B的指令无法使用这些执行单元
两个逻辑核心竞争执行资源，整体性能下降

使用PAUSE的优化：

// 线程A在逻辑核心0上自旋等待
while (lock.load() == LOCKED) {
    _mm_pause(); // 提示CPU这是自旋等待
}

// 线程B在逻辑核心1上执行实际工作
do_real_work();

PAUSE的作用：

CPU识别出这是自旋等待，而非实际工作
优先将执行单元分配给线程B（执行实际工作）
线程A的PAUSE指令执行时，让出执行资源
提高整体CPU利用率

6. 执行单元的竞争与调度

执行单元调度策略（简化模型）：

场景	线程A状态	线程B状态	执行单元分配
无PAUSE	自旋（空循环）	执行工作	竞争激烈，性能下降
有PAUSE	自旋（PAUSE）	执行工作	优先分配给线程B
双工作线程	执行工作	执行工作	公平分配，交替使用

实际效果：

使用PAUSE时，自旋线程对执行单元的占用减少
同核心的另一个线程获得更多执行资源
整体吞吐量提升（特别是在超线程环境下）

7. 物理核心 vs 逻辑核心 vs 执行单元

层级关系：

CPU芯片
└── 物理核心1
    ├── 逻辑核心0（操作系统看到的CPU 0）
    │   └── 线程A运行在此
    ├── 逻辑核心1（操作系统看到的CPU 1）
    │   └── 线程B运行在此
    └── 共享执行单元
        ├── ALU（算术逻辑单元）
        ├── FPU（浮点单元）
        ├── Load/Store单元
        └── 其他执行单元

物理核心2
├── 逻辑核心2（操作系统看到的CPU 2）
├── 逻辑核心3（操作系统看到的CPU 3）
└── 共享执行单元（独立于物理核心1）

关键区别：

概念	数量关系	独立性	共享资源
物理核心	1个	完全独立	不共享
逻辑核心	1-2个/物理核心	部分独立（寄存器独立）	共享执行单元
执行单元	多个/物理核心	硬件资源	被逻辑核心共享

8. 实际应用示例

查看系统核心信息：

# Linux系统
lscpu
# 输出示例：
# CPU(s):                8          # 逻辑核心数
# Thread(s) per core:    2          # 每个物理核心的逻辑核心数
# Core(s) per socket:    4          # 每个CPU插槽的物理核心数
# Socket(s):             1          # CPU插槽数
# 
# 含义：1个物理插槽 × 4个物理核心 × 2个逻辑核心 = 8个逻辑核心

在代码中的体现：

// 操作系统看到8个逻辑核心（CPU 0-7）
std::thread t1([]() { /* 运行在CPU 0或1 */ });
std::thread t2([]() { /* 运行在CPU 2或3 */ });

// 如果t1和t2运行在同一物理核心的不同逻辑核心上
// 它们会共享执行单元，PAUSE指令能优化资源分配

总结

逻辑核心：操作系统看到的CPU核心，每个逻辑核心可以运行一个线程
执行单元：实际执行指令的硬件单元（ALU、FPU等），被逻辑核心共享
超线程：一个物理核心提供两个逻辑核心，共享执行单元
PAUSE指令：让CPU识别自旋等待，优先将执行单元分配给执行实际工作的线程

理解这些概念有助于理解为什么PAUSE指令在超线程环境下能提高整体性能。

参考资料

TBB spin_barrier.h

代码