第10章：并发

从“同时推进”不等于“同时执行”开始

concurrency表示多个活动的lifetime重叠、系统能在它们之间推进；parallelism表示多个工作在不同execution resources上同时执行。单核通过time slicing也能并发，多核程序也可能因一把锁而没有有效并行。并发首先服务响应与结构，并行才以更多hardware缩短work。

先预测工作是CPU-bound、memory-bound、I/O-bound还是lock-bound，再决定threads数量和partition。CPU-bound tasks通常围绕available cores，blocking tasks可能需要不同模型；threads超过可运行资源会oversubscribe，增加context switch、cache displacement与scheduler overhead。

time slice结束、线程blocking或更高优先级任务出现时，scheduler可切换线程。context switch保存/恢复execution state，但更大的成本常是working-set cache变冷和迁移到另一core。不能把“thread数量越多越快”当成公式；需画scaling curve并记录run queue、switches和utilization。

shared memory与data races

shared memory让threads直接访问同一object，通信低延迟，却要求同步lifetime与mutation。C++ data race发生在不同threads访问同一memory location、至少一个write、且访问非atomic并没有happens-before ordering；data race导致undefined behavior，不只是偶尔读到旧值。

mutex把一组invariants放进critical section。所有访问共享invariant的路径都必须使用同一协议；只给writer加锁、reader不加仍是race。锁的范围应覆盖状态从old invariant到new invariant的完整transition，但不在锁内执行不可控callback、I/O或长计算。

class Catalog {
public:
    void update(Key key, Value value) {
        std::lock_guard lock(mutex_);
        entries_.insert_or_assign(std::move(key), std::move(value));
        ++version_;
    }
 
    Snapshot snapshot() const {
        std::lock_guard lock(mutex_);
        return Snapshot{entries_, version_};
    }
 
private:
    mutable std::mutex mutex_;
    Map entries_;
    std::uint64_t version_ = 0;
};

snapshot复制可能很贵，可用immutable state + atomic shared owner等设计降低read lock，但首先要保留lifetime和publication语义。把每个field改atomic也不能自动形成跨字段一致snapshot；invariant是设计单位，不是变量数量。

deadlock与锁顺序

deadlock常来自循环等待：thread A持有M1等M2，thread B持有M2等M1。统一global lock ordering、用std::scoped_lock一次获取多个mutex、减少nested locking能破坏循环条件。调用unknown code时持锁可能引入看不见的反向锁顺序。

try_lock/timeout可以避免永久等待，却可能形成livelock或复杂rollback，不等于修复协议。thread sanitizer可发现部分race与lock issue，但不能证明所有interleavings正确。写出lock ownership table、critical invariants与ordering rules，再做stress和fault injection。

thread support library与tasks

C++ thread support library提供std::thread、mutex、locks、condition variables、future/promise与std::async等。raw thread直接表达execution thread和join/detach lifetime；task表达“产生一个result/error的工作”，调度可交给pool/runtime。每任务创建thread对短任务常不划算，但具体成本依赖OS/runtime，不能写死微秒。

condition variable允许线程sleep直到state predicate可能成立。wait必须与mutex和predicate loop配合，因为notification不是queued data，且允许spurious wakeup。producer应在同一mutex下修改predicate state，再notify；consumer醒来后重新检查。

std::optional<Job> Queue::take() {
    std::unique_lock lock(mutex_);
    ready_.wait(lock, [this] { return closed_ || !jobs_.empty(); });
 
    if (jobs_.empty()) return std::nullopt;
    Job job = std::move(jobs_.front());
    jobs_.pop_front();
    return job;
}

future传递value或exception并表示completion，promise设置结果；async的launch policy会影响立即新线程还是deferred execution，不能假定固定调度。task graph需要处理cancellation、backpressure、exception aggregation和shutdown，不能只展示happy path。

线程池复用workers并限制并行度，但unbounded queue会把过载变成memory/latency问题。bounded queue或admission control提供backpressure；长blocking task与短CPU task混在一个固定pool会产生head-of-line blocking。设计时按resource class分池或采用work-stealing/task runtime，并测queue latency与utilization。

atomic support与C++ memory model

atomic object保证其atomic operations没有data race，并按memory order参与线程间ordering。C++ memory model描述sequenced-before、synchronizes-with与happens-before，决定一个thread的writes何时对另一个thread可见。cache coherence直觉不能替代语言模型，compiler也会重排普通operations。

memory_order_seq_cst提供最强的全局单序直觉；release store之前的writes可由读取该value的acquire load同步看到；relaxed只保证该atomic自身原子性和modification order，不发布其他普通data。memory order是correctness proof的一部分，不是“调小会更快”的旋钮。

Payload payload;
std::atomic<bool> ready{false};
 
// Producer
payload = buildPayload();
ready.store(true, std::memory_order_release);
 
// Consumer
if (ready.load(std::memory_order_acquire)) {
    consume(payload); // payload write happens-before this read
}

若producer后来复用payload，单个ready flag不够；protocol需定义state transitions与exclusive ownership。acquire必须读取release sequence中的相应value才能建立synchronizes-with。用relaxed polling再读ordinary payload会形成race，即使某台x86机器看起来工作。

lock-free programming不是“没有等待”

lock-free表示system-wide progress：某个operation会完成，不保证每个thread在有限步骤完成；wait-free才是per-thread bound。CAS loop在contention下可能反复失败，仍消耗CPU和coherence traffic。lock-free data structure还要解决ABA与memory reclamation，后者往往比pointer update更难。

SPSC ring buffer是边界较清楚的lock-free queue：single producer独占write index，single consumer独占read index；producer以release发布新write position，consumer acquire读取；反向index同理用于确认slot已释放。该算法不能直接推广到MPMC。

template <class T, std::size_t N>
class SpscQueue {
public:
    bool push(T value) {
        const auto write = write_.load(std::memory_order_relaxed);
        const auto next = (write + 1) % N;
        if (next == read_.load(std::memory_order_acquire)) return false;
        slots_[write] = std::move(value);
        write_.store(next, std::memory_order_release);
        return true;
    }
 
    bool pop(T& value) {
        const auto read = read_.load(std::memory_order_relaxed);
        if (read == write_.load(std::memory_order_acquire)) return false;
        value = std::move(slots_[read]);
        read_.store((read + 1) % N, std::memory_order_release);
        return true;
    }
 
private:
    std::array<T, N> slots_{};
    std::atomic<std::size_t> write_{0};
    std::atomic<std::size_t> read_{0};
};

这个教学版本要求T的producer/consumer操作适配slot lifetime，capacity实际为N-1，且对象构造策略简化。通用queue需处理non-default-constructible T、exceptions、shutdown和cache layout。MPMC还需per-slot sequence或其他protocol，不能只把producer数量增加。

contention、thread affinity与false sharing

contention表示多个threads竞争同一lock、atomic、queue、allocator或memory bandwidth。降低方法常比lock-free简单：shard state、per-thread buffer后reduce、batch updates、缩短critical section、减少共享write。先看wait time与scaling curve，不能仅凭CPU 100%判断工作有效。

thread affinity把thread限制在特定CPU，可保持cache/NUMA locality并减少migration，也可能妨碍scheduler load balancing、与容器CPU quota冲突或把threads固定到SMT siblings。部署topology与workload改变后结论会漂移，必须记录pinning policy并提供unbound baseline。

false sharing发生在threads修改逻辑上独立但位于同一coherence block的data，cache line在cores间ping-pong。用padding/alignment或per-thread arrays分离writers；不要硬编码所有机器line size为64，也不要给每个read-only object盲目填充。

std::hardware_destructive_interference_size若实现提供，可表达避免干扰的建议尺寸，但仍需核对platform。perf counters、cache-to-cache分析与per-core scaling可帮助区分false sharing、true sharing和memory-bandwidth saturation。

第10章实验协议

1. 对CPU、I/O与mixed tasks分别画threads到throughput/latency的scaling curve。
2. 用TSan验证共享snapshot实现，故意移除reader lock观察race evidence。
3. 构造双锁反序案例，再用global order或scoped_lock消除等待环。
4. 为condition variable测试spurious wakeup、notify-before-wait、close与shutdown。
5. 对release/acquire publication写positive test，并比较错误relaxed版本的语言证据。
6. 对SPSC queue测试wraparound、full/empty、producer/consumer速度差和shutdown。
7. 比较mutex queue、SPSC ring与batching，记录throughput、p99、CPU和retries。
8. 对per-thread counters比较packed、padded、affinity与unbound，采集cache-to-cache事件。

小结

• concurrency是活动交错推进，parallelism是同时执行；time slicing本身不会增加CPU算力
• shared memory访问必须由mutex、atomic或message protocol建立happens-before
• mutex保护invariant，统一lock ordering或scoped_lock避免deadlock
• condition variable等待predicate；task/future表达结果，但调度、异常和backpressure仍需设计
• atomic只保证指定对象和memory-order语义，release/acquire可安全发布普通data
• lock-free保证system-wide progress，不保证无重试；queue正确性依赖producer/consumer模型
• contention可来自lock、atomic、allocator、cache line或bandwidth
• affinity与padding是部署相关优化，必须用topology和scaling evidence验证