并发相关的 bug 类型 与并发直接相关的 bug 一般可以分为两大类，一是非预期阻塞，二是 race condition 非预期阻塞包含以下几种情况 死锁（deadlock）：两个线程互相等待，导致均无法完成工作。最明显的情况是，如果负责用户界面的线程死锁，界面将失去响应。也有一些情况是，界面可以保持响应，但一些任务无法完成，比如搜索不返回结果

执行策略（execution policy） C++17 对标准库算法重载了并行版本，区别是多了一个指定执行策略的参数 1 2 std::vector<int> v; std::sort(std::execution::par, v.begin(), v.end()); std::execution::par 表示允许多线程并行执行此算法，注意这是一个权限（permission）而非强制要求（requirement），此算法依然可以被单线程执行 另外，如果指定了执行策略，算法复杂度的要求也

线程池 线程池一般会用一个表示线程数的参数来初始化，内部需要一个队列来存储任务。下面是一个最简单的线程池实现 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 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 #include <condition_variable> #include <functional> #include <mutex> #include <queue> #include <thread> #include <utility> class ThreadPool { public: explicit ThreadPool(std::size_t n) { for (std::size_t i = 0; i < n; ++i) { std::thread{[this] { std::unique_lock<std::mutex> l(m_); while (true) { if (!q_.empty()) { auto task = std::move(q_.front());

非阻塞数据结构 阻塞的算法和数据结构使用 mutex、条件变量、期值来同步数据，但非阻塞不等价于 lock-free，比如自旋锁没有使用任何阻塞函数的调用，是非阻塞的，但并非 lock-free 非阻塞数据结构由松到严可分为三个等级：obstruction-free、lock-free、wait-free obstructio

设计并发数据结构要考虑两点，一是确保访问 thread-safe，二是提高并发度 thread-safe 基本要求如下 数据结构的不变量（invariant）被一个线程破坏时，确保不被线程看到此状态 提供操作完整的函数来避免数据结构接口中固有的 race condition 注意数据结构出现异常时的行为，以确保不变量不被破坏 限制锁的范围，避免可能的嵌套锁，

进程 在进程模型中，计算机上所有可运行的软件，通常也包括操作系统，被组织成若干顺序进程(sequential process)，简称进程(process)，一个进程就是就是一个正在执行程序的实例，包括程序计数器、寄存器和变量的当前值 概念上来说，每个进程有自己的虚拟 CPU，但实际上真正的 CPU(假设只有一

无存储器抽象 早期计算机没有存储器抽象，每个程序都直接访问物理内存 1 MOV REGISTER1, 1000 ;将位置1000的物理内存中的内容移到 REGISTER1 中 因此那时呈现给程序员的存储器模型就是简单的物理内存：从 0 到某个上限的地址集合，每个地址对应一个可容纳一定数目（通常是 8 个）二进制位的存储单元 这种情况下，在内存中同时运行两个程序是不可能的

I/O 硬件原理 I/O 设备就是可以将数据输入到计算机(如鼠标、键盘)，或者可以接收计算机输出数据的外部设备(如显示器) I/O 设备按信息交换单位可分为两类 块设备(block device)：把信息存储在固定大小的块中，每个块都有自己的地址。块设备的基本特征是，传输速率快，可寻址，每个块都能独立于其他块而读写。磁盘就是

进程运行时，可以在自己的地址空间存储信息，但这样保存信息的问题是 对于一些程序，如银行系统，这样的存储空间太小 进程终止时，保存的信息就丢失了 经常需要多个进程访问同一信息，这要求信息独立于任何一个进程 因此，长期存储信息有三个基本要求 能够存储大量信息 使用信息的进程终止时，信息仍存在 允许多个进程并发访问信息

资源死锁(resource deadlock) 资源分为两类 可抢占资源(preemptable resource): 可以从拥有它的进程中抢占，而不会产生任何副作用，如存储器 不可抢占资源(nonpreemptable resource): 在不引起相关的计算失败的情况下，无法把它从占有它的进程处抢占过来，如光盘刻录机 死锁主要关心不可抢占资源 如果一个进程集合中，每