高级数据结构-10：多线程

从串行到并行

现代体系结构

理解多线程程序的同步成本，需要先了解现代计算机的存储层级与总线结构。现代多核系统常采用 NUMA（Non-Uniform Memory Access）架构：主存不再是所有处理器等价访问的统一空间，而是被划分为多个内存节点。每个 CPU 通常连接本地内存节点，访问本地内存的延迟低于跨总线访问远程节点内存。

单个处理器通常包含多个计算核心。每个核心有独立的 L1/L2 缓存，并与同一芯片上的其他核心共享 L3 缓存。执行写操作时，数据通常先进入核心本地的存储缓冲区，再按缓存一致性协议更新缓存层级。当某个核心修改共享变量时，硬件会向其他持有该缓存行副本的核心发送失效信号，使对应缓存行失效。高频共享写入会引发大量缓存一致性通信，这是多线程共享数据竞争和锁性能下降的重要原因。

串行渲染

串行程序中，代码按顺序进入 CPU 指令流水线，在同一时刻只推进单一逻辑执行流。动画渲染任务可以直观展示串行计算的性能限制。

计算机动画渲染通常以帧为独立处理单元，过程包含几何计算、光栅化、材质着色和全局光照追踪等浮点计算。以某商业动画电影参数为例，平均每帧渲染耗时 11.5 小时，复杂帧最高可达 90 小时，全片约 152640 帧。若逐帧串行渲染，总耗时约为 1755360 小时，即约 200 年，因此必须引入并行计算。

为构建该渲染任务的抽象逻辑表示，首先需定义基础的数据结构载体与辅助验证函数。以下代码展示了表示单帧画面的底层类封装及其状态验证逻辑。

class Frame {
public:
    // 新建帧默认处于未渲染状态。
    Frame() { flag = false; }
    // 示例中用一次状态置位代表完成该帧渲染。
    void render() { flag = true; }
    // 查询当前帧是否已经渲染完成。
    bool isRendered() { return flag; }
private:
    // 帧状态标记；true 表示该帧已完成渲染。
    bool flag;
};

// 需要渲染的帧总数。
const int N = 512;
// 全部帧对象，作为串行或并行渲染任务的共享数据集。
Frame frames[N];

bool check() {
    // 顺序检查每一帧，任意一帧未完成则整部动画未完成。
    for (int i = 0; i < N; i++) {
        if (!frames[i].isRendered()) return false;
    }
    return true;
}

基于上述类定义，串行动画渲染逻辑如下。程序在单一执行流中依次对每个帧对象调用渲染方法。

// 引入标准输出，用于报告渲染结果。
#include <iostream>
using namespace std;

// 串行渲染：单线程按帧编号顺序处理全部帧。
void renderFilm() {
    // 每次循环只渲染一帧，后一帧必须等待前一帧完成。
    for (int i = 0 ; i < N; i++)
        frames[i].render();
}

int main() {
    // 在主线程中执行完整渲染任务。
    renderFilm();
    // 渲染结束后检查所有帧状态。
    if (check())
        cout << "动画渲染成功\n";
    else
        cout << "动画渲染失败\n";
    // 返回 0 表示程序正常结束。
    return 0;
}

线程并发与并行

并发执行通常对应两种实现模式。

第一种是多个物理核心上的并行。操作系统调度器将不同线程映射到不同 CPU 核心，每个核心独立取指、译码和执行，从而在物理时间上同时处理数据。

第二种是单物理核心上的分时并发。当活跃线程数超过可用核心数时，调度器将 CPU 时间划分为短时间片。线程时间片用尽或发生阻塞 I/O 时，系统保存其寄存器和程序计数器，并切换到下一个就绪线程。宏观上多个任务看似同时推进，但在单核心上，指令仍是交替串行执行的。

C++ 11 多线程库

C++11 引入多线程标准库，提供面向对象的线程资源管理接口，并隐藏底层操作系统细节。std::thread 的主要构造形式包括：

1. 默认构造器thread() noexcept：实例化一个空的线程壳对象，不关联任何系统层面的实际执行流。
2. 初始化构造器thread(Fn&& fn, Args&&... args)：利用可变参数模板机制，允许开发者直接传入目标函数指针及任意数量的执行参数。调用该构造器会立即向系统内核申请建立新的内核级线程并调度执行。
3. 复制构造器thread(const thread&) = delete：被语言标准明确标记为删除状态，因为系统级线程资源具有唯一归属性，不能发生浅拷贝或深拷贝。
4. 移动构造器thread(thread&& x) noexcept：允许将线程底层资源的所有权在不同的对象间进行转移。

线程生命周期通过若干方法管理。join 会阻塞当前线程，直到目标线程执行完毕并回收资源；detach 会切断目标线程与当前线程对象的从属关系，使目标线程在后台独立运行；joinable 用于判断线程对象是否仍关联活跃的系统线程。

以下代码提供了一个基础多线程创建、调度与汇合机制的标准范例程序。

// 标准输出库，用于展示线程执行顺序。
#include <iostream>
// std::thread 所需头文件。
#include <thread>

// 第一个线程执行的无参任务。
void foo() { std::cout << "thread 1...\n"; }
// 第二个线程执行的带参任务。
void bar (int x) { std::cout << "thread 2. " << x << '\n'; }

int main() {
    // 创建线程 first，并立即开始执行 foo。
    std::thread first(foo);
    // 创建线程 second，并把参数 0 传给 bar。
    std::thread second(bar, 0);

    // 主线程继续执行；输出顺序由调度器决定。
    std::cout << "thread main...\n";

    // 等待 first 结束，回收其线程资源。
    first.join();
    // 等待 second 结束，回收其线程资源。
    second.join();

    // 两个子线程均已完成后，主线程继续输出。
    std::cout << "foo and bar completed.\n";
    return 0;
}

由于线程交错由内核调度器决定，该程序多次运行时，主线程与派生线程的输出顺序可能不同。

并行渲染

突破串行计算瓶颈的常见方式是并行计算：将任务拆分为多个子任务，并由多个计算单元同时处理。在多线程模型中，常用主从架构组织任务。

在主从架构中，主线程负责划分任务空间，将边界参数分发给从线程，并在派发完成后等待所有子任务结束。以下代码使用 8 个线程处理渲染任务。

// vector 保存 thread 对象，便于批量 join。
#include <vector>
// thread 用于创建并行渲染工作线程。
#include <thread>
// iostream 用于输出线程完成信息。
#include <iostream>
using namespace std;

// 工作线程数量。
const int M = 8;

// 每个工作线程根据 id 计算自己负责的帧区间。
void slaveRenderFilm (int id) {
    // start 是该线程负责区间的起始下标。
    int start = id * (N/M);
    // end 是右开边界，不包含在该线程任务中。
    int end = (id + 1) * (N/M);
    // 只渲染 [start, end) 范围，避免不同线程写同一帧。
    for (int i = start; i < end; i++)
        frames[i].render();
    // 输出该线程完成标记；多个线程输出顺序不确定。
    cout << "线程" << id << "完成\n";
}

// 主线程负责创建工作线程并等待全部完成。
void renderFilm() {
    // 保存线程对象，防止线程对象生命周期提前结束。
    vector<thread> threads;
    // 创建 M 个线程，每个线程处理一个互不重叠的帧区间。
    for (int i = 0; i < M; i++)
        threads.emplace_back(slaveRenderFilm, i);

    // 主线程等待所有工作线程结束。
    for (int i = 0; i < M; i++)
        threads[i].join();
}

该实现用标准库容器保存线程对象，并通过原位构造直接创建线程。线程标识符用于计算各自负责的帧区间。由于不同线程处理不重叠的数组范围，不会发生交叉写入。

数据竞争与共享变量

当多个执行流在没有同步协议的情况下并发读写同一共享内存区域时，程序结果可能不确定。这类由非原子操作引发的一致性问题称为数据竞争（Race）。

全局共享变量冲突

以下代码提供了一个典型的导致内存冲突的计数器程序范本。

// 标准输出库，用于打印最终计数。
#include <iostream>
// std::thread 所需头文件。
#include <thread>
using namespace std;

// 全局共享计数器，两个线程会同时读写它。
int countNum = 0;

// 计数线程函数。
void counter() {
    // 每个线程执行 100000 次自增。
    for(int i = 0; i < 100000; i++)
        // countNum++ 是读-改-写复合操作，不具备原子性。
        countNum++;
}

int main() {
    // 两个线程同时执行 counter，并共享同一个 countNum。
    thread t1(counter), t2(counter);
    // 等待两个线程完成，确保输出发生在计数之后。
    t1.join();
    t2.join();
    // 由于数据竞争，该值可能小于理论结果 200000。
    cout << "count: " << countNum << endl;
    return 0;
}

预期中，两个线程各执行十万次自增，全局变量最终应为二十万。但实际测试输出可能为 135509 或更低。原因是高级语言中的自增语句在底层不是原子操作，通常分为三步：读取内存值到寄存器、在算术逻辑单元中加一、将结果写回内存。

当物理线程 A 执行完数据读取指令后，若此时操作系统调度器判定其时间片用尽并引发线程挂起，线程 B 则会介入并读取内存中尚未被更新的旧有数值，随后完成运算并写回。当线程 A 再次被调度器唤醒时，它将继续依据挂起前的寄存器旧值进行加法运算，并随后覆盖写入内存。在此指令时序交错模型中，线程 B 的计算结果被线程 A 的滞后写回操作覆盖，导致总计数丢失。

数据竞争最容易发生在“读-改-写”三步合成的操作上。countNum++ 看起来是一句代码，但只要中间任意一步被另一个线程插入，就可能出现两个线程基于同一个旧值各自计算，最后只有一次写回被保留下来的情况。并发程序不能只看源代码语句数量，而要看底层状态是否会被多个执行流交错观察和修改。

静态变量冲突

除全局变量外，局部静态变量和通过地址共享的指针也会产生数据竞争。下面的 counter 函数声明了局部静态变量。该变量虽然作用域在函数内，但存储在全局数据段，所有线程共享同一内存位置，因此竞争行为与全局变量相同。

// counts 保存两个线程结束时各自观察到的共享计数值。
int counts[2];
// id 用于区分当前线程应写入 counts 的哪个槽位。
void counter (int id) {
    // 局部静态变量存放在静态存储区，所有线程共享同一个实例。
    static int countNum = 0;
    // 两个线程同时执行自增，仍会产生读-改-写竞争。
    for(int i = 0; i < 100000; i++)
        countNum++;
    // 记录该线程结束时读到的 countNum 值。
    counts[id] = countNum;
}

int main() {
    // 分别传入线程编号 0 和 1。
    thread t1(counter, 0), t2(counter, 1);
    // 等待两个线程完成后再读取 counts。
    t1.join(); t2.join();
    // 取两个观察值中较大的一个作为示例输出。
    int realCount = (counts[0] > counts[1]) ? counts[0] : counts[1];
    cout << "count: " << realCount << endl;
    return 0;
}

共享指针冲突

如果主线程在栈上创建整型变量，并将其地址传给两个线程，两个线程会解引用同一内存地址。即使函数参数语法上看起来是独立传入，底层仍是共享写入，因此同样会触发数据覆盖错误。

void counter(int *cp) {
    for(int i = 0; i < 100000; i++)
        // 两个线程解引用同一个 cp，会对同一整数执行非原子自增。
        (*cp)++;
}

int main() {
    // countNum 位于主线程栈上，但地址被传给两个子线程共享访问。
    int countNum = 0;
    // t1 与 t2 同时修改 countNum，结果可能小于理论值 200000。
    thread t1(counter, &countNum), t2(counter, &countNum);
    // join 保证主线程等两个计数线程结束后再输出结果。
    t1.join(); t2.join();
    cout << "count: " << countNum << endl;
    return 0;
}

对比可知，分配在线程函数内部的普通非静态局部变量存放于各个线程独占的栈内存空间内。因为现代操作系统的线程资源隔离机制，不同线程之间无法直接寻址访问彼此的私有栈段，所以这些局部变量天然具备线程隔离性。

线程同步与互斥锁

互斥锁

为了保证并发状态一致，需要引入具备原子性的同步机制。互斥锁是解决共享资源争用的基础工具。C++ 提供互斥类封装，其底层依赖硬件原子指令，主要接口是加锁与解锁。

互斥锁的语义是：任意时刻只有一个线程能进入该锁保护的临界区。若锁已被占用，其他申请加锁的线程会被阻塞，直到持锁线程解锁并由调度器唤醒等待线程。

以下代码演示用互斥锁保护全局计数。函数开始时加锁，结束时解锁。引入该临界区后，自增操作不会发生并发覆盖。

// 被多个线程共享的全局计数器。
int countNum = 0;
// 用于保护 countNum 的互斥锁。
mutex mtx;

void counter() {
    // 整段循环进入同一个临界区，期间其他线程无法修改 countNum。
    mtx.lock();
    for(int i = 0; i < 100000; i++)
        // 在锁保护下执行自增，避免读-改-写被其他线程打断。
        countNum++;
    // 释放锁后其他线程才能进入临界区。
    mtx.unlock();
}

锁保护的是临界区中的“不变量”。在计数器例子里，不变量是 countNum 的每次自增都必须基于上一次真实写回后的值。把整段循环锁住可以保证正确性，但会让另一个线程长时间无法进入；把单次自增锁住也能保证正确性，但会产生大量加锁/解锁开销。因此锁的粒度是在正确性和吞吐量之间寻找平衡。

细粒度互斥锁与粒度控制

锁机制会将临界区局部串行化，从而降低并行吞吐率。被锁保护的代码范围称为锁的控制粒度。

在之前的代码中，锁覆盖了包含十万次迭代的完整循环，粒度过粗。多个线程在该临界区排队时，执行过程接近串行。

为了降低多线程互相阻塞的等待周期，代码对锁的生效边界进行了精细化收缩，将其仅局限于单一的自增算术指令之前之后。

void counter() {
    for(int i = 0; i < 100000; i++) {
        // 每次自增前单独加锁，缩小临界区范围。
        mtx.lock();
        countNum++;
        // 自增完成后立即解锁，让其他线程有机会进入。
        mtx.unlock();
    }
}

这种细粒度的锁位排布虽然在空间维度释放了循环控制语句等非冲突逻辑指令的并行权，但随着循环体的高频运转，程序向底层内核频繁发起锁定状态切换调用的次数也相应爆发。系统陷入了上下文环境频繁更迭的额外时间开销中。

加锁对性能的影响

为了定量评估由于同步互斥机制而衍生出的性能衰减幅度，设计了一组基于多线程数组求和的实验程序。该测试架构旨在精确测绘处理千万级数据的运行耗时与系统线程编制数量的对应演变规律。主控程序依照命令行所传参数，对计算规模与工作流线程执行池进行动态构建。

// 代码8.10 核心片段
// 为每个逻辑分区创建一个线程，并把分区编号 i 传给线程函数。
for(int i = 0; i < nthreads; i++)
    threads.emplace_back(sum_mutex, i);

代码内部采用锁机制对累加全局基数的操作行为实施保护。

void sum_mutex(int id) {
    // 每个线程负责 [start, end) 区间内的整数求和。
    long start = id * nelems_per_thread;
    long end = start + nelems_per_thread;
    for (long i = start; i < end; i++) {
        // gsum 是所有线程共享的全局变量，必须加锁保护。
        mtx.lock();
        gsum += i;
        // 每次加法都解锁，导致锁竞争和同步开销非常高。
        mtx.unlock();
    }
}

在配置有 8 核计算资源的基础硬件环境中，设定元素总项数为 $2^{31}$ 量级。依据实测反馈结果编制的性能追踪记录表如下所示：

线程数	1	2	4	8	16	32	64
时间 (s)	48.576	176.021	215.823	253.385	255.358	259.631	262.065

测试数据表明，在工作载荷恒定的基准框架下，引入多线程互斥操作未能带来运行速度增益，反而导致计算性能下降。单线程模式耗时 48.5 秒，当开启 64 个并行线程流时，处理耗时增加至 262 秒。诱发这种负优化的核心原因是频繁的锁竞争消耗。处理器核心的大量时间周期被用于锁状态标志位探查与内核休眠唤醒调度。同时，由于所有核心的高频操作均指向同一全局变量所在的内存行地址，系统总线会承受大量缓存一致性失效通知，影响正常数据加载。

Lock-Free 优化策略

减少共享写入是降低同步开销的重要原则。以下代码将求和算法改为局部累加：每个线程先在自己的局部变量中求和，计算完成后再把局部结果写入为该线程预留的全局数组槽位。所有线程结束后，主线程统一汇总。

// 每个线程拥有一个独立结果槽，避免所有线程写同一个 gsum。
long psum[MAXTHREADS] = { 0 };

void sum_local (int id) {
    // sum 是线程栈上的局部变量，不被其他线程共享。
    long sum = 0;
    // 根据线程编号划分该线程负责的连续区间。
    long start = id * nelems_per_thread;
    long end = start + nelems_per_thread;

    for(long i = start; i < end; i++)
        // 局部累加阶段不需要任何锁。
        sum += i;

    // 线程结束前只写一次自己的槽位，主线程稍后统一汇总。
    psum[id] = sum;
}

在同等 8 核物理环境下执行的测试结果追踪如下表所示：

线程数	1	2	4	8	16	32	64
时间 (s)	5.160	2.636	1.445	0.846	0.849	0.851	0.853

在去除锁操作的单流条件下，程序耗时由原有的 48.5 秒降至 5.16 秒，说明锁请求指令自身存在明显调用开销。随着线程数量逐步增加并接近物理核总数 8，计算耗时持续下降并于 0.846 秒附近触及低点。超过该阈值后继续增加线程，受限于物理资源饱和和额外调度开销，整体时间曲线不再出现增益。

这段优化的核心不是“所有场景都要无锁”，而是先把共享写入改造成局部私有计算。每个线程先在自己的局部变量里累加，最后只写一次独立槽位；主线程再做归并。这样既减少了临界区，也避免多个核心持续争抢同一个缓存行。

lock_guard 锁

传统的锁资源管理方式依赖显式的加锁与解锁指令。当临界区内的业务代码抛出运行期异常阻断执行流程，或者函数内存在多个提前返回路径时，容易遗漏解锁调用，进而引发锁资源长期占用，导致后续到达该屏障的程序模块陷入死锁。

为了强化工程代码的安全强度与结构严谨性，C++ 标准引入了资源获取即初始化的编程范式衍生组件。该组件依托面向对象特性的栈内存析构法则提供全自动的互斥器生命周期管理。在该类的作用域初始化阶段自动请求挂载锁，在其实例受作用域失效机制销毁（退出作用域）被唤起析构程序的瞬间自动履行解锁释放。

代码通过语法块限定锁对象生命周期，使临界区范围明确，并在异常或提前退出时自动释放锁。

void counter() {
    for(int i = 0; i < 100000; i++) {
        // 构造 lock_guard 时自动调用 mtx.lock()。
        lock_guard<mutex> lck(mtx);
        // lck 的生命周期覆盖本次循环体中的临界区。
        countNum++;
        // 离开当前作用域时 lck 析构，自动调用 mtx.unlock()。
    }
}

原子操作与无锁编程

对于低延迟计算需求，标准库提供基于硬件原子指令的基础数据类型。通过原子模板包装整数或布尔类型，可以让相关操作映射为处理器原子机器指令，减少操作系统级同步介入。

// 原子整数的自增由硬件原子指令保证不可被其他线程打断。
std::atomic<int> counter{0};
// relaxed 只保证 counter 自身操作原子，不提供跨变量的顺序约束。
counter.fetch_add(1, std::memory_order_relaxed);

在操作层面的约束中引入了内存访问序次概念。该规范用于管控和抑制由编译器优化重排机制以及超标量处理器乱序执行硬件机制所引发的非预期性指令执行顺序颠倒问题。松散次序配置不附带内存屏障保护功能以换取执行周期的压缩，而在错综复杂的数据依赖交织体系下，为确保宏观业务的确定性，通常必须启用严格强加的顺序一致性内存同步机制。

在异步流程控制方面，系统规划了远端操作支持框架模块。利用原生异步启动函数部署分离任务，并通过结果调取凭证对象达成同步阻断阻塞直到运算完毕提取返回值。同时搭配运用状态承诺协议件，能够在各个互相隔离的执行脉络中实现有效值或异常抛出信息安全投递。

自 C++17 标准起，标准库内的常规数据整理算法开始原生接纳并行化计算配置参数执行并行计算调度。随后的标准化推进中增加了内置协同切断功能的新一代线程封装构件，以及更加底层的信号量门禁计数器原语以适应灵活复杂的权限管理场景要求。

并发数据结构

将传统数据结构改造为并发数据结构，是多线程编程的重要应用。设计目标是在保证数据一致性的同时，尽量降低同步开销。

并发链表

在并发单向链表的设计规范中，结构插入与特征核查是最基础的核心应用。实现高频吞吐率的技术关键点在于将占用大量处理周期的操作如动态内存空间分配申请操作置于互斥管控区之外。代码演示了符合此规范的链表应用。

class List {
public:
    // 空链表以 NULL 作为头指针。
    List() { head = NULL; }

    bool insert(int key) {
        try {
            // 内存分配放在加锁前，避免长时间持锁等待 allocator。
            Node *newHead = new Node;
            newHead->key = key;
            {
                // 只在修改 head 和 next 指针时持有互斥锁。
                lock_guard<mutex> lck(mtx);
                // 新节点先接到旧链表头部。
                newHead->next = head;
                // 再发布新头指针，完成头插。
                head = newHead;
            }
            return true;
        }
        catch (bad_alloc &e) {
            // 分配失败时不修改链表结构，直接报告失败。
            cerr << "bad_alloc caught: " << e.what() << endl;
            return false;
        }
    }

    bool lookup(int key) {
        // 遍历期间持锁，防止其他线程同时插入导致结构变化。
        lock_guard<mutex> lck(mtx);
        for (Node *curr = head; curr; curr = curr->next) {
            if (curr->key == key) return true;
        }
        return false;
    }
private:
    struct Node {
        // 当前节点保存的键。
        int key;
        // 指向下一个节点。
        Node *next;
    };
    // 链表头指针，由 insert 和 lookup 共享访问。
    Node *head;
    // 保护整条链表的互斥锁。
    mutex mtx;
};

内存池系统的对象供给操作可能伴随长时间的后台整理任务。该实现在建立节点结构时独立分配内存，有效遏制了互斥阻隔的持锁时间跨度上限。而在执行链表深度特征核对验证逻辑时，为抵御结构体正在被遍历检测的进程中因被另一线程横加切断而爆发的内存逃逸错误，对检索操作启用了针对整条链表的通栏粗粒度锁定机制。

并发散列表

当单把全局互斥锁在应对庞大的写入访问请求时遭遇无可规避的吞吐量退化，将锁管控范围进行分散剥离成为提升并发接纳能力的优选解决途径。并发散列表的基底层依托多个分离且相互无连带关系的内部链表桶协同运作构建而成。

// 散列表桶数；示例使用质数以减少简单取模下的聚集。
const int BUCKET = 101;
// Hash 由多个互相独立的并发链表桶组成。
class Hash {
public:
    // 插入 key。
    bool insert(int key) {
        // 通过取模定位 key 所属桶。
        int bucket = key % BUCKET;
        // 只访问对应桶的链表，因此只竞争该桶内部的锁。
        return lists[bucket].insert(key);
    }
    // 查询 key 是否存在。
    bool lookup (int key) {
        // 查询同样只需要锁定 key 所属桶。
        int bucket = key % BUCKET;
        return lists[bucket].lookup(key);
    }
private:
    // 每个桶拥有独立链表和互斥锁，不同桶可并发访问。
    List lists[BUCKET];
};

此结构的核心性能优势在于，每一个散列计算后映射出的不同寻址桶槽单元都内建独立互斥锁，使得散列偏移不重合的读写修改动作能够并发执行。同等八核环境下对上亿级别的数据进行填充压力测试，随着线程数从 1 增加至上限，采用单互斥防护机制的链表处理耗时一直在十五秒以上波动，而改用该散列表结构后，处理时间从二秒左右下降并稳定至零点五秒以内。这说明细分互斥范围、隔离数据空间可以有效缓解串行瓶颈。

并发队列

基础队列遵循先进先出。普通队列在空队列或仅剩一个元素时，入队和出队可能同时修改头尾指针相关状态，容易产生冲突。因此早期实现通常使用一把全局锁保护两端操作。

为了降低头尾读写在不同业务线程中的耦合，改进型队列模型在头部引入哑节点作为缓冲隔离层。队列初始化时，结构内部保留一个只起占位作用的无效数据节点。head 指针始终指向该哑节点或当前队首之前的占位节点，真正的业务首元素位于 head->next；tail 指针则跟踪队尾实体节点。下面的代码展示该设计的运行逻辑。

// atomic 用于让哑节点 next 指针在不同端锁保护下仍能安全读写。
#include <atomic>

// 使用头锁和尾锁分离的并发队列。
class Queue {
public:
    // 初始化时创建一个哑节点，使 head 与 tail 都指向该占位节点。
    Queue() {
        // 哑节点不存放有效业务数据。
        Node *dummy = new Node(0);
        // 空队列中 head 与 tail 指向同一个哑节点。
        head = tail = dummy;
    }

    // 入队操作只修改 tail 端。
    void enqueue (int key) {
        // 在持锁前完成内存分配，减少 tailMtx 的持有时间。
        Node *tmp = new Node(key);
        // 只锁定尾端，允许出队端在多数情况下并发执行。
        lock_guard<mutex> lock(tailMtx);
        // 发布新节点；空队列时出队线程可能同时读取 head->next。
        tail->next.store(tmp);
        // 尾指针移动到新插入节点。
        tail = tmp;
    }

    // 出队成功时把队首值写入 value，并返回 true。
    bool dequeue (int *value) {
        // 只锁定头端，保护 head 的移动和旧哑节点释放。
        lock_guard<mutex> lock(headMtx);
        // 真实队首位于哑节点 head 之后。
        Node *tmp = head->next.load();
        // head->next 为空表示队列当前为空。
        if (tmp == NULL) return false;

        // 读出业务值。
        *value = tmp->key;
        // 旧 head 是已经消费过的哑节点。
        Node *oldHead = head;
        // 被取出的业务节点转为新的哑节点。
        head = tmp;
        // 释放旧哑节点。
        delete oldHead;
        return true;
    }
private:
    // 队列节点。
    struct Node {
        // 业务值；哑节点中的 key 无意义。
        int key;
        // next 可能被入队线程写、出队线程读，因此使用原子指针。
        std::atomic<Node *> next;
        // 构造节点并初始化 next 为空。
        Node(int val) : key(val), next(nullptr) {}
    };
    // head 指向哑节点，tail 指向最后一个节点。
    Node *head, *tail;
    // 分别保护头端和尾端，降低无关操作之间的竞争。
    mutex headMtx, tailMtx;
};

占位哑元机制将出队与入队的修改位置分离，使入端和出端可以使用不同互斥锁。需要注意，在 C++ 内存模型中，队列为空时 head 与 tail 会指向同一个哑节点；入队线程写入 tail->next 的同时，出队线程可能读取 head->next。因此示例将 next 设为原子指针，避免不同互斥锁保护下的读写形成数据竞争。测试中，一百万次吞吐操作从全局锁的 3.737 秒降至分离锁的 2.028 秒。

哑节点的作用是让 head 永远指向一个“已消费或占位”的节点，而真正队首在 head->next。这样出队主要移动 head，入队主要移动 tail，两个操作在多数情况下不会争抢同一个指针。空队列是特殊边界，所以 next 的原子性仍然重要。

Lock-Free 并发队列

对于无法接受微秒级线程阻塞挂起的核心系统，可以减少或避免内核互斥器调用，借由底层比较替换指令构建无锁队列模型。该方案在特定高并发场景下能够降低阻塞开销，但实现复杂度和内存回收要求也更高。

// atomic 提供原子指针和 CAS 操作。
#include <atomic>
// thread 用于测试多线程访问。
#include <thread>
// iostream 用于示例输出。
#include <iostream>
// vector 用于保存测试线程对象。
#include <vector>

// Michael-Scott 风格的哑节点无锁队列示例。
class LockFreeQueue {
private:
    // 队列节点；next 需要支持并发 CAS。
    struct Node {
        // 节点保存的业务值。
        int key;
        // 指向后继节点的原子指针。
        std::atomic<Node *> next;
        // 默认构造 val=0 时通常用于创建哑节点。
        Node(int val = 0) : key(val), next(nullptr) {}
    };

    // head 指向当前哑节点。
    std::atomic<Node *> head;
    // tail 尽量指向队尾节点，但允许短暂落后。
    std::atomic<Node *> tail;

public:
    // 创建初始哑节点，并让 head 与 tail 同时指向它。
    LockFreeQueue() {
        Node *dummy = new Node();
        head.store(dummy);
        tail.store(dummy);
    }

    // 析构函数只适用于外部已经停止所有并发访问的场景。
    ~LockFreeQueue() {
        // 从当前 head 开始顺序释放链表节点。
        Node *curr = head.load();
        while (curr) {
            // 先保存后继，再释放当前节点。
            Node *next = curr->next.load();
            delete curr;
            curr = next;
        }
    }

    // 入队：把新节点追加到 tail 后方。
    void enqueue(int key) {
        // 新节点在进入 CAS 循环前完成分配。
        Node *newNode = new Node(key);
        // CAS 失败时重新读取快照并重试。
        while (true) {
            // 读取当前观察到的尾节点。
            Node *currTail = tail.load();
            // 检查尾节点之后是否已经存在其他线程追加的新节点。
            Node *tailNext = currTail->next.load();

            // 若 tail 在读取期间发生变化，当前快照过期，重新开始。
            if (currTail != tail.load()) continue;

            if (tailNext == nullptr) {
                // currTail 确实是链表尾，尝试把 newNode 接到 currTail->next。
                if (currTail->next.compare_exchange_weak(tailNext, newNode)) {
                    // 入链成功后尝试推进 tail；失败也可由其他线程帮助完成。
                    tail.compare_exchange_strong(currTail, newNode);
                    return;
                }
            } else {
                // tail 已落后于真实尾节点，帮助推进 tail。
                tail.compare_exchange_strong(currTail, tailNext);
            }
        }
    }

    // 出队：成功时把队首值写入 value。
    bool dequeue(int *value) {
        // CAS 失败或观察到过期快照时重试。
        while (true) {
            // 当前哑节点。
            Node *currHead = head.load();
            // 当前观察到的尾节点。
            Node *currTail = tail.load();
            // 真实队首元素位于哑节点之后。
            Node *headNext = currHead->next.load();

            // 若 head 在读取期间变化，说明快照过期。
            if (currHead != head.load()) continue;

            if (currHead == currTail) {
                // head 与 tail 相同，队列可能为空或 tail 落后。
                if (headNext == nullptr) return false;
                // 队列非空但 tail 落后，先帮助推进 tail。
                tail.compare_exchange_strong(currTail, headNext);
            } else {
                // 先读出业务值，再尝试移动 head。
                *value = headNext->key;
                // CAS 成功后，headNext 成为新的哑节点。
                if (head.compare_exchange_strong(currHead, headNext)) {
                    // 生产级实现不能在这里直接delete currHead，需要危险指针或epoch回收。
                    return true;
                }
            }
        }
    }
    // 队列持有原子指针和动态节点，禁止复制。
    LockFreeQueue(const LockFreeQueue &) = delete;
    // 同样禁止拷贝赋值，避免两个队列共享同一链表。
    LockFreeQueue &operator=(const LockFreeQueue &) = delete;
};

实现中会同时使用强版本和弱版本的 compare-and-swap。弱版本可能出现无语义错误的伪失败，通常放在重试循环中使用；强版本用于要求最终确认的状态切换。无阻塞队列还引入协作推进机制：如果某个线程发现队列尾指针落后于实际尾节点，它会帮助推进尾指针，而不是阻塞等待其他线程。这样可以避免单个线程停滞导致整体无法前进。示例中出队成功后没有立即释放旧哑节点，是为了避免并发读线程仍持有旧地址时出现悬空指针；析构函数应只在确认没有线程继续访问队列后调用。

CAS 循环的阅读方式是“先拍一张快照，再尝试把快照推进到下一状态”。如果快照过期，说明别的线程已经推进了结构，当前线程重读即可；如果发现尾指针落后，当前线程顺手帮它推进。无锁算法追求的不是每个线程都不等待，而是系统整体总有线程能取得进展。

进一步分析底层释放操作的风险可见，当队列出队端分离旧节点时，如果直接释放堆内存，容易触发经典的 ABA 问题。当一条线程读取到某个地址值后，在即将执行比较交换前被挂起；另一条线程可能已经将该节点删除、释放，并在之后的新建对象中复用了同一段内存地址。挂起线程恢复后再次比较地址，发现地址表面上没有变化，可能错误放行并破坏逻辑链表结构。解决该隐患通常需要配合 hazard pointer、epoch-based reclamation 等安全内存回收机制，或采用其他延迟回收方案。

死锁

引入锁可以避免数据竞争，但不当的加锁策略可能导致死锁。死锁发生时，多个执行流围绕有限资源形成循环等待，程序整体无法继续推进。

代码设立了一个暴露死锁弊端的原始范本。

// 标准输出库。
#include <iostream>
// mutex 提供互斥锁。
#include <mutex>
// thread 提供线程创建接口。
#include <thread>
using namespace std;

// 两把共享互斥锁。
mutex mtx1;
mutex mtx2;

// foo 按 mtx1 -> mtx2 的顺序加锁。
void foo() {
    // 先获得第一把锁。
    mtx1.lock();
    // 再等待第二把锁；若 bar 已持有 mtx2，则可能阻塞。
    mtx2.lock();
    // 两把锁都持有后进入临界区。
    cout << "foo" << endl;
    // 释放锁；示例中释放顺序不是死锁根因，根因是加锁顺序不一致。
    mtx1.unlock();
    mtx2.unlock();
}

// bar 按 mtx2 -> mtx1 的顺序加锁，与 foo 相反。
void bar() {
    // 先获得第二把锁。
    mtx2.lock();
    // 再等待第一把锁；若 foo 已持有 mtx1，则形成循环等待。
    mtx1.lock();
    // 两把锁都持有后进入临界区。
    cout << "bar" << endl;
    // 释放已持有的两把锁。
    mtx2.unlock();
    mtx1.unlock();
}

int main() {
    // 两个线程并发执行，调度交错可能触发死锁。
    thread t1(foo), t2(bar);
    // 若两个线程死锁，主线程会永久阻塞在 join。
    t1.join();
    t2.join();
    // 只有两个线程都正常退出时才会执行到这里。
    cout << "Finish!" << endl;
    return 0;
}

对这段代码进行多次运行时，程序可能出现无后续输出且无法正常结束的情况。其原因是两个线程以相反顺序获取互斥锁：线程 foo 先持有 mtx1，随后等待 mtx2；线程 bar 先持有 mtx2，随后等待 mtx1。当调度器在这两个阶段之间切换线程时，两个线程会分别持有一个锁并等待对方释放另一个锁，从而形成循环等待，程序进入死锁状态。避免该问题的常用做法是在设计阶段规定全局一致的加锁顺序，或使用能够一次性获取多个锁的接口来避免反向持锁。

此故事在 ICS ECF 章节亦有记载：

// SIGCHLD 处理函数；真实代码中应避免调用非异步信号安全函数。
void handler_chld(int sig) {
    // 省略信号处理前置逻辑。
    ...
    // printf 可能使用 stdout 内部锁，不适合在信号处理函数中调用。
    printf("..."); // printf_2
    // 省略信号处理后续逻辑。
    ...
}

int main() {
    // 省略主程序前置逻辑。
    ...
    // 创建子进程，子进程结束后可能触发 SIGCHLD。
    Fork()
    // 省略 fork 后逻辑。
    ...
    // 主线程执行 printf 时可能已经持有 stdout 内部锁。
    printf("..."); // printf_1
    // 省略主程序后续逻辑。
    ...
}

如果 main 中的 printf_1 执行的时候过来了一个 SIGCHLD 信号，当前的 printf_1 执行中断，控制转到对应的 handler_chld 函数。此时 main 中的 printf_1 还拿着 stdout 的内部互斥锁，当 handler 运行到 printf_2 的时候，由于抢不到 stdout 的互斥锁，信号处理函数被一直阻塞在 printf 这一行，信号处理完毕之前程序又无法返回去执行 main 中的 printf_1。最终的结果是：信号处理函数一直在等 main 放出输出流的互斥锁，但是 main 中的 printf 由于被信号处理函数打断未执行完成，无法放出互斥锁，导致程序陷入自我死锁。