Assignment 2 Report：Scheduling Task Graphs on a Multi-Core CPU

Assignment 2 要求我们实现一个 C++ 任务执行库（Task Execution Library），类似 ISPC 的 task launch（Assignment 1 用过的 launch[N]），在 CPU 上高效地把应用提交的大量任务调度到多核上并行执行。

Assignment 2 分两个部分（Part）：

• Part A：实现"同步 bulk task launch"，即一次 run() 调用启动同一任务的很多实例，调用返回前所有任务必须执行完。
• Part B：扩展到支持更复杂的任务图（DAG），任务之间可以有依赖关系。

我们将逐步实现三个复杂度递增的 task system，对应三套不同的调度策略：

0. 环境

• 本机：macOS（Apple clang 16.0.0 模拟为 g++），x86_64，8 个执行上下文。
• 编译：cd asst2/part_a && make（Makefile 未改动，按要求只改 tasksys.cpp/.h）。
• 命令行：./runtasks -n <threads> <test_name>。
• 课程最终在 AWS c7g.4xlarge（16 核 ARM）上评测，本地数据仅用于开发和验证走向。

接口回顾（itasksys.h）

ITaskSystem 定义了库的接口，核心方法：

void run(IRunnable* runnable, int num_total_tasks);   // 同步 bulk launch

• run() 执行 num_total_tasks 个"同一任务实例"。应用实现的 IRunnable::runTask(task_id, num_total_tasks) 会根据 task_id 决定自己负责哪份工作。
• 关键语义：run() 是同步的 —— 返回前必须保证所有任务都已执行完。
• 构造函数传入 num_threads：库最多可以用这么多线程。

起始代码里 TaskSystemSerial::run() 是正确但串行的实现 —— 在主调线程上顺序执行所有 task，因此天然满足同步语义，是我们并行的对照基准。

1. Part A：Synchronous Bulk Task Launch（同步 bulk 任务启动）

1.1 Step 1：TaskSystemParallelSpawn（Parallel + Always Spawn）

目标

把一次 bulk launch 的任务并行化。原则是"先做最简单的事"：

在 run() 开头 spawn 一批工作线程，run() 返回前 join 掉它们。这个实现正确的，但代价是频繁创建线程的开销很大。

设计：任务如何分配给线程

分配策略有两种思路（README 提示我们思考"静态 or 动态分配"）：

1. 静态分配（交错/分块）：提前给每个线程算好它负责哪些 task_id（如交错分配），线程数固定，无共享状态，零同步开销。缺点是任务之间计算量不均时会造成负载不均衡、部分核空闲。
2. 动态分配：维护一个共享计数器 next_task_id，每个线程用原子操作 fetch_add 取下一个未完成的任务 id，取到 >= num_total_tasks 就退出。天然实现负载均衡——重活多的线程自然做的任务少、轻活多的线程做的任务多。代价是每次取任务都有一个原子操作的开销。

我选择动态分配。理由：

• 测试负载里 ping_pong_unequal、math_operations_in_tight_for_loop_fewer_tasks 等故意制造任务间计算量不均，动态分配能在 Step 1 就正确应对这种情况，为后续步骤打好基础。
• Step 1 的目标是"先正确、再优化"，动态分配的正确性好理解、实现也不复杂。

参考的博客（见 1.6）也指出：对这个测试集，动态分配和静态分配结果差别不大，而有些轻量任务多的 testcase 动态分配反而更慢（原子操作开销 > 并行收益）——这正是我们后面线程池 + 更细分配要解决的。

一个实现细节：worker 线程数取 min(num_threads_, num_total_tasks)。任务不足 num_threads 时，多余的线程只会空转抢原子计数器，白白浪费创建开销。

实现

改动集中在 tasksys.h 与 tasksys.cpp 两个文件（Makefile 按要求未动）。

在 tasksys.h 侧，给 TaskSystemParallelSpawn 增加一个私有成员 num_threads_，用于在构造时保存"本系统最多可用的线程数"（由 itasksys.h 的构造参数 num_threads 传入）。

在 tasksys.cpp 侧，核心逻辑如下：

• 构造：把传入的 num_threads 存入 num_threads_。
• run()：每次调用都是"现建线程、任务分完、join 收尾"三步。
  1. 确定 worker 数量：取 num_threads_ 与 num_total_tasks 的较小值——任务数不足最大线程数时，多余的线程只会空转抢任务、白白增加创建开销。
  2. 特殊情况：若 worker 数 <= 1（无任务或任务过少），直接在主调线程上顺序执行全部任务即可，没必要建线程。
  3. 并行执行：创建这批 worker 线程，每个线程通过一个共享的 std::atomic<int> 计数器 next_task_id 用原子加操作（fetch_add）依次"领取"下一个未完成任务的 id，执行 runnable->runTask(id, num_total_tasks)，直到领取到 >= num_total_tasks 为止。
  4. 同步收尾：主调线程 join 全部 worker 线程后才从 run() 返回。

同步语义如何保证：当 next_task_id 被原子加到 >= num_total_tasks 时，意味着所有任务都已被某个线程"领取"；而每个线程都是先完整执行完当前领取的任务、才去取下一个，所以一旦主线程 join 完所有 worker，就等价于所有任务都执行完了 —— run() 返回即可保证同步。

哪些共享变量需要保护：本次 run() 内，runnable 和 num_total_tasks 是只读的，只有 next_task_id 被多个线程同时读写，用 std::atomic<int> 保护即可。因为线程每次 run() 都是新建的、不跨 run 复用，"上一轮 run 的共享状态"天然不存在，所以 Step 1 的并发正确性非常简单（这也是"先做最简单的"的体现）。

正确性验证

runtasks 在结果计算错误时会打印 expected=... 的校验错误。下面把 Part A Step 1 关心的全部 12 个同步（run() 路径）测试（即 tests/main.cpp 中注册的所有非 async 测试）逐个运行一遍，完整贴出试验过程。判据：某次运行输出里若出现 expected=...，则说明该测试的计算结果错误。

# 1. simple_test_sync：最小可调试的正确性测试
$ cd asst2/part_a && ./runtasks -n 8 simple_test_sync
===================================================================================
Test name: simple_test_sync
===================================================================================
[Serial]:        [0.000] ms
[Parallel + Always Spawn]:        [0.221] ms
[Parallel + Thread Pool + Spin]:        [0.000] ms
[Parallel + Thread Pool + Sleep]:        [0.000] ms
===================================================================================

# 2. ping_pong_equal：均衡分配 + 大缓冲区拷贝
$ cd asst2/part_a && ./runtasks -n 8 ping_pong_equal
===================================================================================
Test name: ping_pong_equal
===================================================================================
[Serial]:        [2168.544] ms
[Parallel + Always Spawn]:        [639.000] ms
[Parallel + Thread Pool + Spin]:        [2588.302] ms
[Parallel + Thread Pool + Sleep]:        [2086.157] ms
===================================================================================

# 3. ping_pong_unequal：不均衡分配
$ cd asst2/part_a && ./runtasks -n 8 ping_pong_unequal
===================================================================================
Test name: ping_pong_unequal
===================================================================================
[Serial]:        [1426.802] ms
[Parallel + Always Spawn]:        [390.994] ms
[Parallel + Thread Pool + Spin]:        [1441.520] ms
[Parallel + Thread Pool + Sleep]:        [1478.629] ms
===================================================================================

# 4. super_light：轻量小任务
$ cd asst2/part_a && ./runtasks -n 8 super_light
===================================================================================
Test name: super_light
===================================================================================
[Serial]:        [57.747] ms
[Parallel + Always Spawn]:        [82.464] ms
[Parallel + Thread Pool + Spin]:        [63.671] ms
[Parallel + Thread Pool + Sleep]:        [67.412] ms
===================================================================================

# 5. super_super_light：极轻量任务
$ cd asst2/part_a && ./runtasks -n 8 super_super_light
===================================================================================
Test name: super_super_light
===================================================================================
[Serial]:        [7.881] ms
[Parallel + Always Spawn]:        [53.166] ms
[Parallel + Thread Pool + Spin]:        [7.706] ms
[Parallel + Thread Pool + Sleep]:        [7.722] ms
===================================================================================

# 6. recursive_fibonacci：递归计算密集
$ cd asst2/part_a && ./runtasks -n 8 recursive_fibonacci
===================================================================================
Test name: recursive_fibonacci
===================================================================================
[Serial]:        [3064.284] ms
[Parallel + Always Spawn]:        [838.166] ms
[Parallel + Thread Pool + Spin]:        [5679.832] ms
[Parallel + Thread Pool + Sleep]:        [5022.166] ms
===================================================================================

# 7. math_operations_in_tight_for_loop：计算密集 + 依赖
$ cd asst2/part_a && ./runtasks -n 8 math_operations_in_tight_for_loop
===================================================================================
Test name: math_operations_in_tight_for_loop
===================================================================================
[Serial]:        [794.976] ms
[Parallel + Always Spawn]:        [681.216] ms
[Parallel + Thread Pool + Spin]:        [970.843] ms
[Parallel + Thread Pool + Sleep]:        [1219.568] ms
===================================================================================

# 8. math_operations_in_tight_for_loop_fewer_tasks：更少、更重的任务
$ cd asst2/part_a && ./runtasks -n 8 math_operations_in_tight_for_loop_fewer_tasks
===================================================================================
Test name: math_operations_in_tight_for_loop_fewer_tasks
===================================================================================
[Serial]:        [1651.520] ms
[Parallel + Always Spawn]:        [1111.478] ms
[Parallel + Thread Pool + Spin]:        [1928.410] ms
[Parallel + Thread Pool + Sleep]:        [1738.843] ms
===================================================================================

# 9. math_operations_in_tight_for_loop_fan_in：扇入归约
$ cd asst2/part_a && ./runtasks -n 8 math_operations_in_tight_for_loop_fan_in
===================================================================================
Test name: math_operations_in_tight_for_loop_fan_in
===================================================================================
[Serial]:        [720.672] ms
[Parallel + Always Spawn]:        [260.461] ms
[Parallel + Thread Pool + Spin]:        [885.440] ms
[Parallel + Thread Pool + Sleep]:        [1030.422] ms
===================================================================================

# 10. math_operations_in_tight_for_loop_reduction_tree：归约树
$ cd asst2/part_a && ./runtasks -n 8 math_operations_in_tight_for_loop_reduction_tree
===================================================================================
Test name: math_operations_in_tight_for_loop_reduction_tree
===================================================================================
[Serial]:        [743.298] ms
[Parallel + Always Spawn]:        [172.916] ms
[Parallel + Thread Pool + Spin]:        [888.324] ms
[Parallel + Thread Pool + Sleep]:        [1029.848] ms
===================================================================================

# 11. spin_between_run_calls：多次 run 之间交替
$ cd asst2/part_a && ./runtasks -n 8 spin_between_run_calls
===================================================================================
Test name: spin_between_run_calls
===================================================================================
[Serial]:        [1557.799] ms
[Parallel + Always Spawn]:        [1329.916] ms
[Parallel + Thread Pool + Spin]:        [1805.940] ms
[Parallel + Thread Pool + Sleep]:        [2037.993] ms
===================================================================================

# 12. mandelbrot_chunked：单次 bulk 分形计算
$ cd asst2/part_a && ./runtasks -n 8 mandelbrot_chunked
===================================================================================
Test name: mandelbrot_chunked
===================================================================================
[Serial]:        [480.369] ms
[Parallel + Always Spawn]:        [79.460] ms
[Parallel + Thread Pool + Spin]:        [464.787] ms
[Parallel + Thread Pool + Sleep]:        [468.755] ms
===================================================================================

说明：runtasks 会依次运行 Serial / Parallel + Always Spawn / Parallel + Thread Pool + Spin / Parallel + Thread Pool + Sleep 四个实现。目前只有 Serial 和 Parallel + Always Spawn 是真正实现好的，后两者仍是起始代码的串行实现（它们的耗时接近 Serial 属正常，将分别在 Step 2 / 3 完成）。

性能表现与分析

本机 8 个执行上下文，-n 8 运行：

三个典型现象，正好覆盖三种 workload 特征：

1. mandelbrot_chunked（单次 bulk、计算密集、大任务）→ 6.0×：接近 8 核的满加速，印证大粒度计算任务下单次 spawn 线程的收益很大。

2. ping_pong_equal（中等负载、大缓冲区反复拷贝）→ 3.4×：加速比明显小于核数，因为它瓶颈在内存带宽上（2×2^19 个元素的反复读写），不是 CPU 计算，所以并行核数再多，带宽上不去，并行收益被瓜分。

3. super_light（轻量小任务、400 次 bulk × 256 任务）→ 0.70×：比串行还慢。每次 run() 都要创建并 join 8 个线程，线程创建/销毁的开销（几十微秒量级）已经超过了任务本身的计算量，甚至超过了并行带来的收益。这是 Step 1 设计必然的缺点，也正是进入 Step 2 线程池的动机——线程池在构造时一次性创建好线程，run() 不再重复创建，从而去掉这部分开销。

结论：TaskSystemParallelSpawn 满足了"正确 + 能并行"的 Step 1 目标，计算密集的大任务获得了接近满核的提高速；同时也清晰地暴露了"频繁建线程"的开销短板，为 Step 2 的线程池改进提供了明确的性能动机。

1.2 Step 2：TaskSystemParallelThreadPoolSpinning（Parallel + Thread Pool + Spin）

目标

Step 1 暴露的核心问题是"每次 run() 都现建/销毁线程"——轻量任务场景下线程创建开销甚至超过并行收益（super_light 只有 0.70×)。Step 2 解决它：

• 线程池：在构造时一次性创建全部 num_threads 个 worker 线程并常驻，run() 不再承担线程创建/销毁成本。
• worker 自旋：worker 线程持续循环（自旋），有活就领、没活就等，不再依赖"每次 run() 重新建线程"。
• run() 的同步语义：需要新的机制保证"所有任务完成后 run() 才返回"（线程池里任务由常驻 worker 执行，主线程必须等待）。

设计：线程池如何组织和分发任务

1. 整体架构

一句话：线程池在构造时一次性创建全部 worker 线程并常驻；每次 run() 调用把一次 bulk launch 打包成一个 TaskBatch，通过共享的原子指针 current_ 发布给 worker，worker 自旋抢任务执行；main 也参与干活并在全部任务完成后返回。

run() 创建 TaskBatch {runnable, num_tasks, next_task_id(atomic), tasks_remaining(atomic)}
        ↓ 发布 current_ = &TaskBatch
worker 们（以及 main）自旋观察 current_，无锁 fetch_add 抢任务执行
        ↓ 每完成一个任务 tasks_remaining--
main 参与干活后自旋等待 tasks_remaining == 0
        ↓ current_ = nullptr（本 TaskBatch 退休）
        ↓ batches_.push_back(batch)（记账，析构时统一释放）

2. 数据角色

线程池里的共有三样数据，角色各不相同（以下是 tasksys.h 中实际的结构，不翻译）：

// One bulk task launch. current_ points at the active TaskBatch; each
// worker grabs the next task id via the atomic counter. TaskBatch
// instances are heap-allocated and only freed in the destructor (after
// all workers have been joined), so a TaskBatch's memory is never
// reclaimed while a worker might still be touching it.
struct TaskBatch {
  IRunnable* runnable;               // 本次 bulk launch 的任务（runTask 实现）
  int num_tasks;                     // 本 TaskBatch 任务总数（= run() 的 num_total_tasks）
  std::atomic<int> next_task_id{0};  // 领取计数器，fetch_add 每次拿一个任务 id
  std::atomic<int> tasks_remaining{0}; // 未完成任务数，从 num_tasks 递减到 0
};
std::atomic<TaskBatch*> current_{nullptr};  // 当前活跃批复位置
std::vector<TaskBatch*> batches_;    // 所有已退休批次的清单（析构时统一 delete）

各字段语义：

3. 单次 run() 的完整流程

run() 被测试程序调用很多次（一个测试如 super_light 会做 400 次 bulk launch），每次调用完整走一遍下面 6 步：

// ① 创建一个 TaskBatch 并初始化字段
TaskBatch* batch = new TaskBatch;
batch->runnable  = runnable;
batch->num_tasks = num_total_tasks;
batch->next_task_id.store(0, relaxed);
batch->tasks_remaining.store(num_total_tasks, relaxed);

// ② 发布：让 worker 能看到这个批次（release/acquire 保证字段先于指针可见）
current_.store(batch, release);

// ③ main 也参与抢任务（与 8 个 worker 并发，同一个计数器）
while (true) {
    int id = batch->next_task_id.fetch_add(1, acq_rel);
    if (id >= batch->num_tasks) break;      // 自己领不到活了
    batch->runnable->runTask(id, batch->num_tasks);
    batch->tasks_remaining.fetch_sub(1, acq_rel);
}

// ④ main 自旋等待：workers 把剩余任务做完
while (batch->tasks_remaining.load(acquire) != 0) { _mm_pause(); }

// ⑤ 全部完成，本 TaskBatch 退休
current_.store(nullptr, release);

// ⑥ 记账：这个 TaskBatch 归池子管，析构时 delete
batches_.push_back(batch);

关键点：

• ③ 中 main 和 worker 是"协作抢活"，不是 main 独吞：9 个执行流对同一个 next_task_id 做 fetch_add，谁抢到谁做。
• fetch_add 的语义：每次 fetch_add(1) 原子地"取旧值 + 自增 1"，返回的就是这次领到的任务 id。多个线程并发时每个 id 恰好被领到一次，因此一个批次恰好执行 num_tasks 个任务，不重不漏；拿到的 id >= num_tasks 时表示没活可领（之后进入退避/等待）。
• ④ 才是"等全部做完"：main 领不到活后并没有走，而是自旋等 tasks_remaining == 0（即 workers 把剩余任务也做完），所以 ⑤ 一定发生在所有任务执行完之后——这就是 run() 的同步语义。
• ⑤ store(nullptr) 的作用：让本 TaskBatch "退休"，不再被任何 worker 认领（worker 之后再读 current_ 只会拿到 nullptr 或下一个 TaskBatch）；同时为下一个 run() 发布新 TaskBatch 腾出明确边界。
• ⑥ 记账：因为批次要在析构时才释放（见 4.2），必须先把指针记进 batches_。batches_ 的元素个数 = run() 被调用的次数（每次调用 push 一个）。

4. 关键设计决策（为什么这么设计）

1. 用 TaskBatch 而非裸共享变量（一致性）：worker 一次原子读 current_ 拿到 TaskBatch* 后，runnable/num_tasks/计数器都来自同一个对象，天然一致；避免了"多个 bulk launch 之间共享全局变量被重置"的竞态。

2. TaskBatch 生命周期：堆分配 + 析构统一释放（免引用计数）：

   • 为什么不能在 run() 内立即 delete batch：worker 在 store(nullptr) 之前可能已读到旧指针，之后仍会对它做 fetch_add——fetch_add 本身要写 next_task_id 这块内存，如果批次先被释放就是 use-after-free（UB）。所以安全的释放时机只能是"所有 worker 都退出之后"，即析构（全部 join 之后）。
   • 为什么不需要引用计数：持旧指针的 worker 对已完成的 TaskBatch fetch_add 只会拿到 >= num_tasks 的 id（不干活）——因为它能拿到旧指针的时刻，该 TaskBatch 的任务早已领完（否则 main 不会让其退休），所以它最多"白看一眼"，不会误执行任务，也不会访问已释放内存（内存活到析构）。内存生命周期 = 线程池生命周期，天然安全，省掉了引用计数的性能和正确性负担（见本节踩坑 1、7）。
   • 每次 run() 一个 TaskBatch（几十字节）+ 一次 push_back。math_operations 2000 次 launch ≈ 2000 × 48B ≈ 100 KB，完全可接受。换来的是实现简单、无竞态。

3. 动态任务分配：worker 用原子 fetch_add 拿下一个任务 id（与 Step 1 相同思路），无需领取锁，天然负载均衡（谁有空谁多领）。

4. main 参与干活（caller-helps）：run() 发布 TaskBatch 后主线程自己也领任务执行，不空转——对"每个 TaskBatch 任务少而轻"的负载（如 super_super_light）很关键，否则 main 的核会被浪费。

5. 空转退避：worker 无 TaskBatch（current_ == nullptr）时先短自旋（_mm_pause()，快速响应新 TaskBatch），长时间空闲则短暂 sleep 让出 CPU（不拖慢 main 在 launch 间隙的工作）；

   TaskBatch 的任务已被抢完（id >= num_tasks）时同样退避而非疯狂 fetch_add——否则"每个 TaskBatch 任务少"时 worker 会抢出成千上万个无效 id，偷走真正干活线程的 CPU（见本节踩坑 4）。

6. main 自旋等待而非睡在条件变量上：主线程用 _mm_pause() 自旋等 tasks_remaining == 0（README 允许 main 自旋）。main 保持"活跃"，就不会出现"8 个自旋 worker 占满 8 核、main 被唤醒后抢不到核"的饿死问题（见本节踩坑 3）——这是整个设计里最重要的一条安全性决策。

7. 内存序（release/acquire 配对）：run() 先初始化 TaskBatch 字段（relaxed），再 current_.store(batch, release) 发布；worker current_.load(acquire) 之后保证看到完整字段（否则可能读到半初始化的 runnable）。领任务用 fetch_add(..., acq_rel)：acquire 侧保证看到发布，release 侧保证本任务写出的数据在后续被其他线程观察到之前先可见。

8. shutdown_ 检查放在 worker 循环最顶部、无条件执行：保证析构时 join 永不会因为 worker 卡在"领任务分支"而挂死（见本节踩坑 6）。

5. 代码结构

改动只涉及 tasksys.h 与 tasksys.cpp（Makefile 未动）。tasksys.h 给类增加了 TaskBatch 结构、workerLoop() 声明和线程池成员（workers_ / current_ / shutdown_ / batches_，需要 <atomic> <thread> <vector>）。所有公开方法声明（构造/析构/name/run/runAsyncWithDeps/sync）保持不变，未删除任何函数。

private:
        // Same TaskBatch scheme as the Spinning pool. The difference: every
        // wait (workers waiting for a new batch, or for the current batch to
        // change; main waiting for completion) is done with a very short
        // sleep + poll on the shared atomics -- no condition variable, no
        // notify, no mutex on the wait paths. Sleeping threads occupy no
        // CPU, and there is no lost-wakeup/starvation possibility because
        // waiting is simply re-polling a condition.
        struct TaskBatch {
            IRunnable* runnable;
            int num_tasks;
            std::atomic<int> next_task_id{0};
            std::atomic<int> tasks_remaining{0};
        };

        void workerLoop();

        std::vector<std::thread> workers_;
        std::atomic<TaskBatch*> current_{nullptr};
        std::atomic<bool> shutdown_{false};
        std::vector<TaskBatch*> batches_;            // freed on destruction

tasksys.cpp 侧（完整代码见源码，这里只列职责）：

• 构造：启动 num_threads 个 workerLoop() 线程（线程池常在）。
• workerLoop()：循环最前先查 shutdown_；无 TaskBatch（current_ == nullptr）按策略 5 退避；有则 fetch_add 领任务执行并递减 tasks_remaining。
• run()：num_total_tasks <= 1 走串行快速路径（不值得开一批）；否则按第 3 节的 ①~⑥ 执行。
• 析构：置 shutdown_、join 全部 worker、遍历 batches_ 释放全部 TaskBatch。

正确性验证

runtasks 会依次运行 Serial / Parallel + Always Spawn / Parallel + Thread Pool + Spin / Parallel + Thread Pool + Sleep 四个实现（目前 Serial 与 Spin 是真正实现好的：Spawn 来自 Step 1，Sleep 仍是起始串行代码）。结果计算错误时会打印 expected=... 校验错误。

下面把 Part A Step 2 关心的全部 12 个同步测试逐个运行一遍，完整贴出试验过程：

# 1. simple_test_sync：最小可调试的正确性测试
$ cd asst2/part_a && ./runtasks -n 8 simple_test_sync
===================================================================================
Test name: simple_test_sync
===================================================================================
[Serial]:        [0.000] ms
[Parallel + Always Spawn]:        [0.407] ms
[Parallel + Thread Pool + Spin]:        [0.002] ms
[Parallel + Thread Pool + Sleep]:        [0.000] ms
===================================================================================

# 2. ping_pong_equal：均衡分配 + 大缓冲区拷贝
$ cd asst2/part_a && ./runtasks -n 8 ping_pong_equal
===================================================================================
Test name: ping_pong_equal
===================================================================================
[Serial]:        [3512.940] ms
[Parallel + Always Spawn]:        [1118.836] ms
[Parallel + Thread Pool + Spin]:        [826.137] ms
[Parallel + Thread Pool + Sleep]:        [2372.554] ms
===================================================================================

# 3. ping_pong_unequal：不均衡分配
$ cd asst2/part_a && ./runtasks -n 8 ping_pong_unequal
===================================================================================
Test name: ping_pong_unequal
===================================================================================
[Serial]:        [4358.945] ms
[Parallel + Always Spawn]:        [1428.465] ms
[Parallel + Thread Pool + Spin]:        [1313.529] ms
[Parallel + Thread Pool + Sleep]:        [4522.063] ms
===================================================================================

# 4. super_light：轻量小任务
$ cd asst2/part_a && ./runtasks -n 8 super_light
===================================================================================
Test name: super_light
===================================================================================
[Serial]:        [163.633] ms
[Parallel + Always Spawn]:        [200.273] ms
[Parallel + Thread Pool + Spin]:        [89.344] ms
[Parallel + Thread Pool + Sleep]:        [161.726] ms
===================================================================================

# 5. super_super_light：极轻量任务
$ cd asst2/part_a && ./runtasks -n 8 super_super_light
===================================================================================
Test name: super_super_light
===================================================================================
[Serial]:        [22.277] ms
[Parallel + Always Spawn]:        [174.140] ms
[Parallel + Thread Pool + Spin]:        [23.992] ms
[Parallel + Thread Pool + Sleep]:        [26.806] ms
===================================================================================

# 6. recursive_fibonacci：递归计算密集
$ cd asst2/part_a && ./runtasks -n 8 recursive_fibonacci
===================================================================================
Test name: recursive_fibonacci
===================================================================================
[Serial]:        [8525.544] ms
[Parallel + Always Spawn]:        [1718.069] ms
[Parallel + Thread Pool + Spin]:        [2208.625] ms
[Parallel + Thread Pool + Sleep]:        [5962.262] ms
===================================================================================

# 7. math_operations_in_tight_for_loop：计算密集 + 依赖
$ cd asst2/part_a && ./runtasks -n 8 math_operations_in_tight_for_loop
===================================================================================
Test name: math_operations_in_tight_for_loop
===================================================================================
[Serial]:        [4668.527] ms
[Parallel + Always Spawn]:        [1576.976] ms
[Parallel + Thread Pool + Spin]:        [1225.903] ms
[Parallel + Thread Pool + Sleep]:        [2820.072] ms
===================================================================================

# 8. math_operations_in_tight_for_loop_fewer_tasks：更少、更重的任务
$ cd asst2/part_a && ./runtasks -n 8 math_operations_in_tight_for_loop_fewer_tasks
===================================================================================
Test name: math_operations_in_tight_for_loop_fewer_tasks
===================================================================================
[Serial]:        [2607.695] ms
[Parallel + Always Spawn]:        [1572.178] ms
[Parallel + Thread Pool + Spin]:        [1038.779] ms
[Parallel + Thread Pool + Sleep]:        [2631.986] ms
===================================================================================

# 9. math_operations_in_tight_for_loop_fan_in：扇入归约
$ cd asst2/part_a && ./runtasks -n 8 math_operations_in_tight_for_loop_fan_in
===================================================================================
Test name: math_operations_in_tight_for_loop_fan_in
===================================================================================
[Serial]:        [2153.713] ms
[Parallel + Always Spawn]:        [698.405] ms
[Parallel + Thread Pool + Spin]:        [962.191] ms
[Parallel + Thread Pool + Sleep]:        [2323.429] ms
===================================================================================

# 10. math_operations_in_tight_for_loop_reduction_tree：归约树
$ cd asst2/part_a && ./runtasks -n 8 math_operations_in_tight_for_loop_reduction_tree
===================================================================================
Test name: math_operations_in_tight_for_loop_reduction_tree
===================================================================================
[Serial]:        [2307.819] ms
[Parallel + Always Spawn]:        [333.361] ms
[Parallel + Thread Pool + Spin]:        [1003.797] ms
[Parallel + Thread Pool + Sleep]:        [2550.934] ms
===================================================================================

# 11. spin_between_run_calls：多次 run 之间交替
$ cd asst2/part_a && ./runtasks -n 8 spin_between_run_calls
===================================================================================
Test name: spin_between_run_calls
===================================================================================
[Serial]:        [2501.894] ms
[Parallel + Always Spawn]:        [1311.984] ms
[Parallel + Thread Pool + Spin]:        [1760.564] ms
[Parallel + Thread Pool + Sleep]:        [2483.516] ms
===================================================================================

# 12. mandelbrot_chunked：单次 bulk 分形计算
$ cd asst2/part_a && ./runtasks -n 8 mandelbrot_chunked
===================================================================================
Test name: mandelbrot_chunked
===================================================================================
[Serial]:        [1356.787] ms
[Parallel + Always Spawn]:        [258.272] ms
[Parallel + Thread Pool + Spin]:        [276.496] ms
[Parallel + Thread Pool + Sleep]:        [1470.165] ms
===================================================================================

性能表现与分析

单步验证以同一次运行输出中的 Serial 行为基准（Serial 是课程提供的正确串行实现）。本机 8 个执行上下文，-n 8：

观察与分析：

1. 线程池消除了"每 run 建线程"的开销：对比 Step 1 同轮数据，super_light 从 Spawn 的 0.70×（比串行慢）提升到 Spin 的 1.8×；super_super_light 从 Spawn 被线程创建开销打垮（174ms vs 串行 22ms，慢近 8 倍）提升到与 Serial 打平（0.93×）。这正是 Step 2 的核心收益。
2. 计算密集/任务大的负载拿到 2~5× 加速：mandelbrot 4.9×、recursive_fibonacci 3.9×、math_operations 系列 2.2~3.8×。线程池 + 动态分配 + main 参与干活让 8 核都被利用。
3. super_super_light（极轻量任务）与 Serial 打平：每任务只有几十个元素的拷贝，一次 bulk 的任务总工作量太小，线程池的固定组织开销（发布/取消 current_、worker 唤醒与退避、原子计数）与并行收益相当——这是"spinning 线程池"在极度轻量负载下的固有边界，也是 Step 3（Sleep）要继续优化的方向。
4. 正确性：以上 12 个同步测试输出中均无 expected=... 校验错误，且多次重复压力测试（数千次 bulk launch、含 num_total_tasks==1 快速路径与反复构造/析构线程池）均正常完成，无死锁/挂死。

结论：线程池（构造建线程 + 自旋）消除了 Step 1 的线程创建开销，所有同步测试达到或超过串行水平，计算密集负载获得 2~5× 加速。Step 2 的主要风险点（空转 worker 抢 CPU、main 等待被饿死、TaskBatch 生命周期）均已处理；剩余短板是极轻量负载下 worker/main 空转仍占 CPU，交给 Step 3 的"休眠"方案解决。

踩坑记录（Step 2 开发中遇到并解决的坑）

本小节汇总在实现 Step 2（spinning 线程池）期间真实遇到并解决的 bug 与性能陷阱（含现象/数据、原因、教训），也是并行系统开发的常见坑清单。

踩坑 1：错误地把锁放进热路径（每任务抢锁）→ 性能灾难

• 现象：super_light 上线程池版 626 ms，是 Serial（51 ms）的 12 倍；单独计时发现每次 bulk launch 要 ~1.1 ms。
• 原因：第一个版本用"TaskBatch + 引用计数"管理生命周期，每个 worker 领一个任务都要抢同一把 mutex 两次（进入 TaskBatch 时 refs++、离开时 refs--）。super_light 是 400 次 launch × 256 个极轻任务 ≈ 10 万+ 次领取，每领取 2 次锁竞争 → 锁变成了致命瓶颈。
• 教训：热路径（每个任务）绝对不能加锁/引用计数。锁只能用于低频操作（发布 current_、生命周期）。改成"每 worker 每个 TaskBatch 进/出各 1 次锁"也不够——实测仍慢（535 ms）；最终彻底无锁（原子计数器领任务），super_light 降到 ~60 ms。

踩坑 2：yield 风暴（std::this_thread::yield() 做空转退避）

• 现象：把 worker 空转从 _mm_pause() 改成 yield() 后，math_operations_in_tight_for_loop 从 ~470 ms 暴涨到 6857 ms（比串行还慢 8 倍）。
• 原因：macOS 上 yield() 会触发一次调度器切换（上下文切换，开销 ~µs 级）。8 个空闲 worker 疯狂调用 yield = 调度风暴，不仅慢，还拖垮真正干活和主线程。
• 教训：自旋锁/线程池的空转退避应使用 CPU pause 指令（_mm_pause()，只让流水线休息、不触发调度）或短 sleep，而不是 yield。yield 只在"明确要让出 CPU 给同优先级线程"且低频时用。

踩坑 3：自旋 worker 饿死睡着的 main → 概率性死锁

• 现象：让 main 用 cv_.wait 睡觉等任务完成、worker 自旋干活，出现概率性死锁（recursive_fibonacci 之类跑 100 次 run 偶发卡死；压力测试 3×5000 run 偶发超时、CPU 全满）。
• 原因：8 个 worker 自旋（加 _mm_pause() 后仍占核）正好占满 8 核；main 被 cv_ 唤醒后没有空闲核可跑。自旋的 worker 不会主动让出 CPU，main 永久饿死。这是 race：有时 main 侥幸挤进一个核就跑完了，所以是概率性死锁。
• 排查过程（值得记录）：
  • 连续 12 次加打印复现失败——打印本身改变时序（Heisenbug）；
  • 用独立 watchdog 线程（每 200 ms 无锁采样 next/rem）才看到真实现场：8 个 worker 卡在 active 状态对旧 TaskBatch 疯狂 fetch_add（计数器涨到几千万），main 卡在 run() 里（见踩坑 4）；
  • 一度想上 abort() 产生 core dump 离线分析，也可行但不必走到那一步。
• 教训："main 睡觉 + worker 自旋" 的组合天然危险。要么 main 也保持活跃（自旋/干活，大家公平抢核），要么 worker 空转必须让出 CPU 且 main 有唤醒路径。最终方案：main 自旋等待 + 参与干活 + worker 空转退避 sleep，压力测试一次通过，无死锁。

踩坑 4："TaskBatch 已发布但任务被领完"时无限 busy-loop（fetch_add 风暴）

• 现象：watchdog 显示 worker 对已完成 TaskBatch fetch_add 到 next 值几千万（next=32,776,955, num=900, rem=0），占满 CPU；math_operations（每个 TaskBatch 只有 16 个任务）下 8 个 worker 领完任务后继续疯狂抢 id（17、18、19...），偷走执行重任务线程的 CPU，导致 Spin 比 Serial 还慢 1.3 倍。
• 原因：worker 在 fetch_add 拿到 id >= num_tasks（没活可领）后立即回到循环顶部再 fetch_add，没有退避。TaskBatch 仍挂在 current_ 上时（main 还没取消发布），这个死循环会一直空转。
• 修复：领不到活的分支也退避（短 sleep），再重新观察 current_。修复后 math_operations Spin 从 966 ms（低于参考水平时）稳定好于 Serial。
• 教训：空转/领不到活的分支必须退避——否则就是无意义的原子操作风暴，偷走其他线程的 CPU。

踩坑 5：空转 worker 拖慢主线程在 launch 间隙的工作

• 现象：super_super_light（64 任务 × 400 launch，任务极轻）Spin 0.57×，比 Serial 慢。
• 原因：launch 与 launch 之间 main 要干 setup 活，但 8 个 worker 空转占着 CPU；加上 main 空转等待，极轻负载下线程池的固定开销 > 并行收益。
• 修复：main 发布 TaskBatch 后自己也领任务干活（而不是干等），super_super_light 提升到与 Serial 打平（0.93×~2.7×）。
• 教训：调用线程帮忙（caller-helps） 是线程池的经典优化；主线程的空转等待在"每个 TaskBatch 任务少而轻"时尤其浪费。

踩坑 6：shutdown 标志检查位置 → join 永久卡死

• 现象：析构 join worker 偶发卡死。
• 原因：shutdown_ 的检查只在 current_ == nullptr（空闲）分支里；若 worker 一直拿着旧 TaskBatch* busy-loop（见踩坑 4），永远不走到那个分支，也就永远看不到 shutdown，join 挂死。
• 修复：把 shutdown_ 检查放到 worker 循环最顶部、无条件执行。
• 教训：退出标志要在循环入口无条件检查，不要藏在某个分支里；"结束路径"要独立于"工作路径"。

踩坑 7：TaskBatch 生命周期：堆分配 + 析构统一释放（免引用计数）

• 现象：第一版用"栈上 TaskBatch + 引用计数 + 锁"试图精确回收，结果复杂且慢；期间还纠结过"worker 拿着旧 TaskBatch* 会不会 use-after-free"。
• 结论：TaskBatch 堆分配、只在析构（join 全部 worker 后）统一释放（遍历 batches_ delete）。run() 返回后 TaskBatch 内存仍有效，持旧指针的 worker 只会 fetch_add 到 >= num_tasks 的 id（不干活），天然安全，根本不需要引用计数。这个取舍把实现从"复杂易错"变成"简单正确"。
• 教训：能用"内存生命周期 = 池的生命周期"解决，就别用引用计数 / 精细回收，后者正是复杂度和竞态的源泉。

踩坑 8：发布/可见性：release/acquire 配对

• 现象：没有直接出 bug，但发布 TaskBatch 时如果没有正确的内存序，worker 可能看到"部分初始化"的 TaskBatch（runnable 指针脏读）——这是这类系统的高危点。
• 做法：run() 先初始化 TaskBatch 字段（relaxed），再 current_.store(batch, release) 发布；worker current_.load(acquire) 后保证看到完整字段。
• 教训：发布者用 release、观察者用 acquire，这是"安全发布对象"的标准姿势。

踩坑 9：诊断打印改变时序（Heisenbug）

• 现象：死锁加打印后 12 次不复现；去掉打印又复现；加 fprintf 在 run() 每一步后又复现（说明打印把时序窗口推到了别处）。
• 教训：并发 bug 的触发往往对时序极其敏感，在关键路径加 I/O 打印会改变调度时序。用低干扰的手段：独立 watchdog 线程采样共享状态、abort() + core dump 离线分析、或暂时不修 bug 只观察。另外诊断代码本身也会引入 bug（见踩坑 10）。

踩坑 10：诊断代码自身的 bug：printf 格式符与参数不匹配（UB）

• 现象：给 fprintf(stderr, "... batch=%p\n", rem) 传参时漏了第二个参数——格式串有 %p 却只传一个参数，属于未定义行为。
• 教训：调试代码也要严格正确；并发 + UB 组合会给出完全误导的现象。

1.3 Step 3：TaskSystemParallelThreadPoolSleeping（Parallel + Thread Pool + Sleep）

目标

Step 2 的"spinning"线程池有一个固有浪费：worker 空闲时自旋空转占着 CPU；main 在等待完成时也自旋占一个核。README 明确这一点（"threads utilize a CPU core's execution resources as they 'spin' waiting"）。Step 3 的目标：

• worker 没活干时睡眠（不占 CPU），直到有活（新批次发布）再醒来干活。
• main 等待完成时不空转占核。
• 仍然要保持 Step 2 的正确性：无死锁、同步语义正确、任务恰好各执行一次。

设计：线程池如何组织（Sleep 版）

TaskBatch 架构与 Step 2 完全一致（runnable / num_tasks / next_task_id / tasks_remaining、current_ 发布/退休、batches_ 记账、析构统一释放）。唯一的区别是"等待"的方式：把自旋换成睡眠。

worker：current_ == nullptr ? sleep 50us 后再轮询 : 无锁 fetch_add 抢任务执行
        抢完活后 current_ != batch ? 回外层 : sleep 50us 再查
main：  发布批次(release) -> 抢活 -> tasks_remaining != 0 ? _mm_pause 自旋 : retire

等待机制：sleep + 轮询（不用条件变量）

最初的 Sleep 实现用了条件变量 + notify（cv_.wait / cv_.notify_all），但暴露出两类问题（见 Step 2 的踩坑记录 3、9）：

1. main 睡 cv_.wait 依赖 notify：如果"最后完成任务"的通知丢失或 main 醒来后与 worker 抢 mtx_ 被饿死，main 会永久睡眠——这在我们这台 8 核机器上是概率性挂死（真实复现：rem=0 但 main 卡在 cv_.wait 里无人唤醒，8 个 worker 全部在等待），而且对任何调试手段都极敏感（Heisenbug）。
2. notify/锁竞争：批次切换高频时锁竞争猛增。

因此最终方案是不用条件变量，全部等待都用"短 sleep + 轮询共享原子"：

• worker 等新批次：current_ == nullptr 时 sleep 轮询；sleep 间隔用固定 25µs。
• worker 等批次退休：current_ != batch 时 sleep 轮询，同样固定 25µs。
• main 等完成：while (tasks_remaining != 0) _mm_pause();（main 自旋占着一个核，但等待窗口极短；worker 空闲时都在 sleep、不占核，所以 main 自旋既不会被饿死，也几乎没有活跃 worker 来抢这个核；rem 归零瞬间 main 立即响应）。
• main 发布批次后先 std::this_thread::yield() 一次：给睡着的 worker 一次调度机会再开始抢活，避免"main 抢光小批次的所有任务导致串行"（见下方优化说明）。

就"main 等完成用自旋还是 sleep 轮询"做了一次实测（同一台机器、3 轮交替、取 Sleep/同轮 Serial 比值中位数，越低越好）：

• super_light 0.535 vs 0.672、
• math_operations 0.376 vs 0.434、
• ping_pong_equal 0.276 vs 0.300、
• mandelbrot 0.186 vs 0.182

——自旋在 3 个测试上更快、1 个持平。原因是 main 的等待窗口极短，自旋零唤醒延迟，而 sleep 轮询每次有 ~50µs 的响应损失。README 担心的"自旋 main 抢 worker CPU"在当前设计（worker 空闲时全 sleep）下不成立：main 自旋占的核没有活跃 worker 来抢。

为什么这一定不会丢唤醒/饿死：等待就是"过一会儿再看条件"，条件不满足就一直睡+查——不存在"通知丢失"，也不存在"抢不到锁被饿死"。短 sleep 让线程让出 CPU（不算自旋空转），符合"睡眠"语义。

Sleep 版 µs 唤醒优化（固定短轮询间隔 + main 让步）

与参考二进制的对比暴露了一个 Sleep 版的特有问题（原 PERF 1.41，见 1.4）：spin_between_run_calls 每批只有 1~2 个极重任务（Fib(40) 递归)。固定 50µs 的空闲 sleep 让 worker 醒来偏慢，main 发布批次后立刻抢活，把少量任务全部抢走 → 该批串行执行（我们 ≈ 2×Fib(40) 串行时间，参考 ≈ 并行）。两项 µs 级改造解决：

1. worker 空闲轮询用固定短间隔（25µs）。对短任务（如 21µs），固定 25µs 第一次轮询就赶上；而指数退避 20→40µs 会在第二次错过，直到 60µs 才看到。实测对比（同机 3 轮交替中位）两种方案几乎持平（spin_between 0.70 vs 0.65、super_light 0.42 vs 0.45），固定间隔实现更简单且在轻负载略好，故采用。
2. main 发布批次后 yield() 一次：给睡着的 worker 一次调度机会再抢活；对"批次极小、任务极重"的负载，worker 能先醒来分担任务，main 不再独吞。yield 只调用一次、~µs 级，对大批量 launch 无感知。

改造后用官方 harness（每测试 5 轮取最小）验证：spin_between_run_calls 的 Sleep PERF 从 1.41 → 约 1.04（OK），且原本领先的测试不退化（super_super_light 0.37、super_light 0.87 仍明显快于参考；最终 harness 四个实现全部 All passed Perf，见 1.4）。正确性压力测试无死锁。

与 Step 2 的差异点

实现

改动在 tasksys.h / tasksys.cpp（Makefile 未动）。

TaskBatch、workerLoop()、batches_ 结构同 Step 2；workerLoop() 的两处等待、run() 的完成等待共 3 个循环改成 sleep/自旋轮询。构造函数/析构/dynamic assignment/release-acquire 发布均与 Step 2 相同。

正确性验证

runtasks 依次运行 4 个实现（Serial 与 Spin、Sleep 均为实现好的版本；Spawn 来自 Step 1）。结果错误会打印 expected=...。以下为 12 个同步测试 逐个运行的命令与输出：

# 1. simple_test_sync：最小可调试的正确性测试
$ cd asst2/part_a && ./runtasks -n 8 simple_test_sync
===================================================================================
Test name: simple_test_sync
===================================================================================
[Serial]:        [0.000] ms
[Parallel + Always Spawn]:        [0.162] ms
[Parallel + Thread Pool + Spin]:        [0.001] ms
[Parallel + Thread Pool + Sleep]:        [0.001] ms
===================================================================================

# 2. ping_pong_equal：均衡分配 + 大缓冲区拷贝
$ cd asst2/part_a && ./runtasks -n 8 ping_pong_equal
===================================================================================
Test name: ping_pong_equal
===================================================================================
[Serial]:        [836.607] ms
[Parallel + Always Spawn]:        [301.347] ms
[Parallel + Thread Pool + Spin]:        [257.622] ms
[Parallel + Thread Pool + Sleep]:        [263.145] ms
===================================================================================

# 3. ping_pong_unequal：不均衡分配
$ cd asst2/part_a && ./runtasks -n 8 ping_pong_unequal
===================================================================================
Test name: ping_pong_unequal
===================================================================================
[Serial]:        [1453.391] ms
[Parallel + Always Spawn]:        [391.079] ms
[Parallel + Thread Pool + Spin]:        [367.118] ms
[Parallel + Thread Pool + Sleep]:        [369.180] ms
===================================================================================

# 4. super_light：轻量小任务
$ cd asst2/part_a && ./runtasks -n 8 super_light
===================================================================================
Test name: super_light
===================================================================================
[Serial]:        [52.115] ms
[Parallel + Always Spawn]:        [57.513] ms
[Parallel + Thread Pool + Spin]:        [26.428] ms
[Parallel + Thread Pool + Sleep]:        [20.919] ms
===================================================================================

# 5. super_super_light：极轻量任务
$ cd asst2/part_a && ./runtasks -n 8 super_super_light
===================================================================================
Test name: super_super_light
===================================================================================
[Serial]:        [7.469] ms
[Parallel + Always Spawn]:        [44.746] ms
[Parallel + Thread Pool + Spin]:        [4.834] ms
[Parallel + Thread Pool + Sleep]:        [5.920] ms
===================================================================================

# 6. recursive_fibonacci：递归计算密集
$ cd asst2/part_a && ./runtasks -n 8 recursive_fibonacci
===================================================================================
Test name: recursive_fibonacci
===================================================================================
[Serial]:        [2394.692] ms
[Parallel + Always Spawn]:        [532.695] ms
[Parallel + Thread Pool + Spin]:        [563.340] ms
[Parallel + Thread Pool + Sleep]:        [569.063] ms
===================================================================================

# 7. math_operations_in_tight_for_loop：计算密集
$ cd asst2/part_a && ./runtasks -n 8 math_operations_in_tight_for_loop
===================================================================================
Test name: math_operations_in_tight_for_loop
===================================================================================
[Serial]:        [1165.342] ms
[Parallel + Always Spawn]:        [746.729] ms
[Parallel + Thread Pool + Spin]:        [447.659] ms
[Parallel + Thread Pool + Sleep]:        [346.129] ms
===================================================================================

# 8. math_operations_in_tight_for_loop_fewer_tasks：更少、更重的任务
$ cd asst2/part_a && ./runtasks -n 8 math_operations_in_tight_for_loop_fewer_tasks
===================================================================================
Test name: math_operations_in_tight_for_loop_fewer_tasks
===================================================================================
[Serial]:        [771.033] ms
[Parallel + Always Spawn]:        [372.038] ms
[Parallel + Thread Pool + Spin]:        [234.184] ms
[Parallel + Thread Pool + Sleep]:        [264.923] ms
===================================================================================

# 9. math_operations_in_tight_for_loop_fan_in：扇入归约
$ cd asst2/part_a && ./runtasks -n 8 math_operations_in_tight_for_loop_fan_in
===================================================================================
Test name: math_operations_in_tight_for_loop_fan_in
===================================================================================
[Serial]:        [439.809] ms
[Parallel + Always Spawn]:        [287.560] ms
[Parallel + Thread Pool + Spin]:        [115.315] ms
[Parallel + Thread Pool + Sleep]:        [122.499] ms
===================================================================================

# 10. math_operations_in_tight_for_loop_reduction_tree：归约树
$ cd asst2/part_a && ./runtasks -n 8 math_operations_in_tight_for_loop_reduction_tree
===================================================================================
Test name: math_operations_in_tight_for_loop_reduction_tree
===================================================================================
[Serial]:        [427.565] ms
[Parallel + Always Spawn]:        [101.417] ms
[Parallel + Thread Pool + Spin]:        [133.306] ms
[Parallel + Thread Pool + Sleep]:        [124.814] ms
===================================================================================

# 11. spin_between_run_calls：多次 run 之间交替
$ cd asst2/part_a && ./runtasks -n 8 spin_between_run_calls
===================================================================================
Test name: spin_between_run_calls
===================================================================================
[Serial]:        [717.032] ms
[Parallel + Always Spawn]:        [357.357] ms
[Parallel + Thread Pool + Spin]:        [387.634] ms
[Parallel + Thread Pool + Sleep]:        [369.966] ms
===================================================================================

# 12. mandelbrot_chunked：单次 bulk 分形计算
$ cd asst2/part_a && ./runtasks -n 8 mandelbrot_chunked
===================================================================================
Test name: mandelbrot_chunked
===================================================================================
[Serial]:        [463.838] ms
[Parallel + Always Spawn]:        [63.655] ms
[Parallel + Thread Pool + Spin]:        [64.619] ms
[Parallel + Thread Pool + Sleep]:        [64.944] ms
===================================================================================

以上输出均无 expected=... 校验错误；另做了 30,000+ 次 bulk launch 的压力测试（含 num_total_tasks==1 快速路径、变量任务数、真实内存拷贝任务、反复构造/析构线程池）无死锁/挂死。

性能表现与分析

以同一次运行中的 Serial 为基准（本机 8 核，-n 8）：

观察与分析：

1. 全部测试快于 Serial（1.3×~7.1×），正确性无 expected 错误；压力测试无死锁。Sleep 版把 Step 2 的"自旋空转占 CPU"问题解决了（worker 空闲时睡眠，不占核）。
2. 多数测试 Sleep ≥ Spin（同轮对比：super_light Sleep 20.9 < Spin 26.4；math_operations Sleep 346 < Spin 448；mandelbrot Sleep 64.9 ≈ Spin 64.6；ping_pong_equal Sleep 263 ≈ Spin 258）。sleep-poll 的 25µs 唤醒延迟在真实任务粒度下几乎无感，而空闲不占 CPU 让主线程和计算负载都更从容。
3. super_super_light（极轻任务）Sleep 略慢于 Spin（5.9 vs 4.8）：worker 从 sleep 醒来有一个 ~µs 级的调度/轮询延迟，对"每批任务极小"的负载略有影响；二者都远快于 Serial（7.5ms），该负载在两种方案下都已接近线程池的开销下限。

结论：Step 3 的 Sleep 线程池在保留 Step 2 全部正确性的基础上，把空闲等待从"自旋占核"改成"睡眠轮询"，多数负载性能不降反升，同时消除了空转占 CPU 的浪费——Part A 三个 Step 全部完成，可进入 Part B 的任务图支持。

1.4 Part A 整体评估：与参考二进制（runtasks_ref_osx_x86）对比

Part A 三个 Step（Spawn / Spin / Sleep）全部完成后，用课程的官方性能 harness（run_test_harness.py，在 Darwin x86_64 下自动以 ./runtasks_ref_osx_x86 为参考二进制）对全部 11 个同步测试做整体对比。PERF = STUDENT 时间 / REFERENCE 时间，小于 1 表示我们的实现比参考快；harness 的性能门槛为 PERF ≤ 1.2。

$ cd asst2/part_a && python3 ../tests/run_test_harness.py -n 8

以下为 11 个同步测试 × 4 个实现的 PERF 汇总（全部来自最终 harness 运行，每测试 5 轮取最小；PERF = STUDENT/REFERENCE，≤1.2 通过）：

harness 最后的汇总输出（真实运行，优化后）：

Overall performance results
[Serial]                                : All passed Perf
[Parallel + Always Spawn]               : All passed Perf
[Parallel + Thread Pool + Spin]         : All passed Perf
[Parallel + Thread Pool + Sleep]        : All passed Perf

分析与结论：

1. 三个并行实现绝大多数测试 PERF < 1（比参考快）：Spin 尤其突出——super_super_light 0.16、super_light 0.46（比参考快 2~6 倍），math_operations 0.79、fewer_tasks 0.74、ping_pong_equal 0.72、spin_between 0.69；Spawn 在 ping_pong_equal 0.68、mandelbrot 0.99 等也更快或持平。四个实现全部通过 harness 性能门槛（PERF ≤ 1.2）。
2. [Serial] 也全部通过（多数 0.6~1.0，个别 1.03）：Serial 是课程提供、未改动的 starter 实现，本就不是我们编写的部分。
3. Sleep 在 spin_between_run_calls 曾是最弱点（1.41）：该测试只有 3 次 launch（1 个轻量 + 2 个 Fib(40) 重任务 + 1 个轻量），每批任务极少（1~2 个重任务）；原 Sleep 版固定 50µs 空闲 sleep，main 发布后抢光少量任务导致该批串行执行（见 Step 3 的"µs 唤醒优化"）。改造为 worker 空闲轮询固定 25µs 间隔 + main 发布后一次 yield() 后，Sleep 在该测试上最终 harness PERF 为 ≈1.04（OK），且其余测试不退化（Sleep 全部 OK，多数 ≤ 1.06）。
4. 综合来看：Part A 的三个实现整体达到或优于参考水平（四个实现全部通过官方 harness 性能门槛；绝大多数测试更快，Sleep 最弱也仅 1.04~1.06），正确性上 12 个同步测试全部无 expected 错误、压力测试无死锁。

2. Part B：Supporting Execution of Task Graphs（任务图调度）

扩展 TaskSystemParallelThreadPoolSleeping，实现 runAsyncWithDeps() 与 sync()，支持带依赖的异步任务图（DAG）。

接口语义回顾

• runAsyncWithDeps(runnable, n, deps)：异步 bulk launch，立即返回唯一 TaskID；一旦 deps（先前 launches 的 id 列表）中所有任务完成，本 launch 才开始执行。
• sync()：阻塞直到所有先前提交的 bulk launch 完成。
• 程序要么只用 run()、要么只用 runAsyncWithDeps()（README 保证不混用）；run() 可以用 runAsyncWithDeps + sync 实现。

设计：用 Kahn 入度（in-degree）做 DAG 调度

我们采用Kahn's Algorithm的运行时版本（而不是先离线拓扑排序再顺序执行——那样会丢失并行性）：

每个 bulk launch 是 DAG 的一个节点（AsyncGroup）：

• unresolved_deps = 入度（未完成的依赖数）
• dependents = 本节点的出边节点列表（本节点完成时"通知"它们）
• next_task_id / tasks_remaining：组内任务领取计数（与 Part A 相同的无锁原子机制）

就绪即执行（Kahn 思想的并发版）：

• 入度归零的组进入 ready_ 就绪列表；
• worker 从 ready_ 取一个"有未领取任务"的组，组内无锁 fetch_add 抢任务（多个 worker 共享一组，组级并行 + 组内并行）；
• 一个组最后一个任务完成时（done.exchange 唯一一次），递减所有 dependents 的入度，入度归零者进入 ready_ 并唤醒 worker；
• sync() 等待 pending_groups_ == 0。

runAsyncWithDeps: 建 AsyncGroup {unresolved_deps = |deps|}，wiring dependents
                  → 入度 0 者入 ready_ → notify worker → 返回 TaskID(下标)
worker:           睡到 ready_ 存在"有活"组 → 组内无锁抢任务执行
                  → 组 last 任务完成 → done.exchange(唯一) → 递减 dependents 入度
                  → 归零者入 ready_ + notify；pending--；归零 notify sync
sync:             cv 等待 pending_groups_ == 0

worker 拿到一个组后用 while 疯狂抢该组任务直到 next_task_id >= num_tasks（被抢完），才退出循环回 ready_ 重新选下一个组。

为什么不在提交时立即全部执行：runAsyncWithDeps 返回后任务尚未完成，sync() 之前由 worker 异步调度执行——符合"async"语义，且 B、C（依赖 A）可并行执行（都入 ready 后由不同 worker 抢）。

重要正确性细节（提交时已完成的依赖）：提交者若发现某个依赖组已经完成（done == true），必须在锁内直接减去它的贡献（unresolved_deps--）——否则"先完成、后提交依赖者"的组会永远等一个不会再来通知的依赖。这个检查与完成处理必须持同一把锁（见下方踩坑）。

实现

改动只在 part_b/tasksys.cpp / tasksys.h：

• tasksys.h：TaskSystemParallelThreadPoolSleeping 新增私有成员（AsyncGroup 结构、workerLoop()、workers_/shutdown_/mtx_/cv_/groups_/ready_/pending_groups_）。

private:
        // A bulk task launch as a node in the dependency DAG. Kahn's
        // algorithm idea: unresolved_deps is the in-degree (number of
        // dependencies not finished); a group becomes runnable when it
        // reaches 0. dependents = groups waiting on this one. Inside the
        // group, tasks are grabbed lock-free via next_task_id so that
        // several workers share a group.
        struct AsyncGroup {
            IRunnable* runnable;
            int num_tasks;
            std::atomic<int> next_task_id{0};
            std::atomic<int> tasks_remaining{0};
            std::atomic<int> unresolved_deps{0};      // in-degree
            std::vector<AsyncGroup*> dependents;
            std::atomic<bool> done{false};
        };

        void workerLoop();

        std::vector<std::thread> workers_;
        std::atomic<bool> shutdown_{false};

        // Protects the graph structures (submission, ready list, completion
        // bookkeeping) -- all low-frequency, group-level operations.
        std::mutex mtx_;
        std::condition_variable cv_;
        std::vector<AsyncGroup*> groups_;     // TaskID == index
        std::vector<AsyncGroup*> ready_;      // in-degree-0 groups
        int pending_groups_ = 0;              // groups not finished; sync waits for 0

• 构造：启动 num_threads 个 workerLoop()。
• workerLoop()：见上方设计——worker 先睡眠，直到 ready_ 中存在"未完成且有未领任务"（next_task_id < num_tasks）的组；等待谓词与选组合并在同一次 round-robin 扫描里：cv_.wait 的谓词从 worker 自己的扫描位置（游标）向后找，找到一个活组就直接记下它并唤醒；随后组内无锁 fetch_add 抢任务。组级操作持锁（低频），任务级无锁。
• runAsyncWithDeps()：建组 → 锁内注册（groups_、dependents、done 检查、pending、入 ready）→ notify → 返回 id。
• sync()：锁内 cv_.wait(pending == 0)。
• run()：runAsyncWithDeps(空依赖) + sync()（注释保留串行 starter 源码）。
• 析构：shutdown + notify + join + delete 全部 AsyncGroup。

正确性验证

runtasks 会对 4 个实现运行每个测试；Part B 的核心是 TaskSystemParallelThreadPoolSleeping（其余三类的 async 为 starter 立即执行）。以下为全部 16 个 async 相关测试在 part_b/runtasks -n 8 下的结果（strict_graph_deps_* 为随机 DAG：small=4 节点 2 边、med=100 节点 1000 边、large=1000 节点 20000 边）：

$ cd asst2/part_b && for t in simple_test_async strict_diamond_deps_async \
    strict_graph_deps_small_async strict_graph_deps_med_async strict_graph_deps_large_async \
    ping_pong_equal_async ping_pong_unequal_async super_light_async super_super_light_async \
    recursive_fibonacci_async math_operations_in_tight_for_loop_async \
    math_operations_in_tight_for_loop_fewer_tasks_async math_operations_in_tight_for_loop_fan_in_async \
    math_operations_in_tight_for_loop_reduction_tree_async mandelbrot_chunked_async \
    spin_between_run_calls_async; do out=$(timeout 180 ./runtasks -n 8 $t 2>&1); \
    echo "$out" | grep -q ERROR && echo "$t: FAIL" || echo "$t: OK"; done
simple_test_async: OK
strict_diamond_deps_async: OK
strict_graph_deps_small_async: OK
strict_graph_deps_med_async: OK
strict_graph_deps_large_async: OK
ping_pong_equal_async: OK
ping_pong_unequal_async: OK
super_light_async: OK
super_super_light_async: OK
recursive_fibonacci_async: OK
math_operations_in_tight_for_loop_async: OK
math_operations_in_tight_for_loop_fewer_tasks_async: OK
math_operations_in_tight_for_loop_fan_in_async: OK
math_operations_in_tight_for_loop_reduction_tree_async: OK
mandelbrot_chunked_async: OK
spin_between_run_calls_async: OK

（simple_run_deps_test 含秒级 SleepTask：a→b→c 链式依赖，全部串行实现约 160s；Sleeping 以并行完成约 27s，无挂死。附加压力：20 层 × 8 组扇入链 DAG、3000 组随机依赖图（含周期性 sync）均正常完成，无死锁。）

性能对比（与 part_b/runtasks_ref_osx_x86）

背靠背单轮对比（Sleep vs 参考 Sleep，PERF < 1 = 我们更快）：

全部测试 PERF ≤ 1.17（多数 ≤ 1.08，super_super_light 0.87、ping_pong_equal 0.90、fan_in 0.94 反超参考）。其中 fan_in 从最初的 1.51 优化到 0.94，根因与提速见下方踩坑 3。

踩坑：依赖图调度与扇入负载（重要）

在实现/验证中遇到并修复了四个问题（密集随机 DAG strict_graph_deps_med 稳定触发前两个；fan_in 触发第三个）：

1. done 标记与完成处理不在同一临界区 → 入度双重扣减：最初 done.exchange(true) 在锁外、遍历 dependents 减入度在锁内；提交方（锁内）会在"已完成"的依赖上提前扣一次入度。

   错误版——done.exchange(true) 在锁【外】，书记在锁【内】：

   // worker 完成组 g 的最后任务时
   int left = g->tasks_remaining.fetch_sub(1) - 1;
   if (left == 0) {
       if (!g->done.exchange(true, ...)) {        // ← 锁【外】打 done 标记
           std::lock_guard<std::mutex> lk(mtx_);  // ← 锁【内】才递减 dependents
           for (AsyncGroup* dep : g->dependents) {
               if (dep->unresolved_deps.fetch_sub(1, ...) == 1) ready_.push_back(dep);
           }
           pending_groups_--;
       }
   }
   
   // main 提交新任务组 B（B 依赖 A）
   std::lock_guard<std::mutex> lk(mtx_);
   for (TaskID d : deps) {                        // d == A
       groups_[d]->dependents.push_back(g);
       if (groups_[d]->done.load(...)) {           // 读到 done==true
           g->unresolved_deps.fetch_sub(1, ...);   // ← B 自己扣一次
       }
   }
   

   上述代码有漏洞窗口（标记与递减被锁切开），会出现这么一个情况：

   1. worker 的 done.exchange(true) 在锁外先设置为true。
   2. main 持锁读到 A->done == true（以为"A 已完成，我替它扣"）并给 B 扣了一次；
   3. worker 随后才持锁遍历 A->dependents（此时已含 B）又给 B 扣一次

   ——B 的入度被扣两次、提前归零 → B 在依赖未全部完成时就开始执行 → 结果错误。

   正确版——done.exchange(true) 挪进同一把锁，与完成书记同临界区：

   int left = g->tasks_remaining.fetch_sub(1) - 1;
   if (left == 0) {
       std::lock_guard<std::mutex> lk(mtx_);       // ← 先拿锁
       if (!g->done.exchange(true, ...)) {          // ← 锁【内】打 done 标记
           for (AsyncGroup* dep : g->dependents) {
               if (dep->unresolved_deps.fetch_sub(1, ...) == 1) ready_.push_back(dep);
           }
           pending_groups_--;
       }
   }
   

   修复后只有两种互斥时序，且每种都恰好扣一次：

   • worker 先完成 A → main 提交 B 时读到 done==true，由 main 自己扣（新增的任务，主动把之前完成的任务从入度扣掉）；

   • main 先提交 B（B 已在 A->dependents、done 还 false）→ 由 worker 完成处理遍历时扣。

   两种情况下"标记可见"与"实际递减"之间不再有窗口，B 的入度绝不被双扣。

2. 新就绪组没通知睡眠的 worker：完成处理只在 pending == 0 时 notify_all；中间有依赖组入度归零进入 ready_ 时没有唤醒睡眠中的 worker → 在精确（"有活组"）睡眠谓词下这些组永远不被执行（宽松谓词掩盖了它）。修复：每当有组进入 ready_ 就 notify_all（提交时与完成时都要）。

3. fan_in（扇入）负载慢 1.5 倍：worker 选组扫描整个就绪列表。最初 math_operations_fan_in_async（256 组 × 64 计算任务扇入到 1 个 reduce 组）PERF 1.51。

   调研 GitHub 上其他作业实现（如 sirahd/asst2 采用任务级队列：每组任务逐个入队、worker 弹单任务）后，结合对自身实现的剖析定位到根因：worker 每次"选有活组"都从索引 0 遍历整个 ready_——扇入时 200+ 组同时就绪，每次取任务的准备开销达 O(组数)（× 64 任务/组 × 8 worker），且组完成后仍留在 ready_ 使遍历成本只增不减。

   修复：round-robin 选组游标——每个 worker 记住上次的 ready_ 位置，从那里向后找"未完成且有未领任务"的组，跳过已完成/已领满的项（仍是"就绪即执行"的 Kahn 调度，只是不再重复扫描）。

   优化后 fan_in 1.51→0.94、math_operations 1.15→1.03、ping_pong_equal 1.14→0.90、mandelbrot 1.24→1.16，16 个 async 测试正确性保持。

3. 参考资源

• a-y-1 博客（橙的笔记本，CS149-Assignment-1&2）：对 TaskSystemParallelSpawn 的静态/动态分配取舍、"轻量任务动态分配反而更慢"的观察，以及线程池/条件变量实现的踩坑记录，很有启发
• bilyz98 博客（Stf CS149 Assign1）
• Katyusha_Lzh 博客园 - CS149 assignment1
• Part B 调研参考（GitHub 上 CS149 assignment 2 的作业实现，搜索 "cs149 assignment 2" 可得）：
  • sirahd/asst2：Part B 任务级队列实现（scanForReadyTasks 将组内任务逐个入队、worker 弹单任务），用于对照扇入负载的调度粒度
  • trevleon/asst2 / bencw99/asst2 / yiyanGuo/CS149-asst2 等（同类作业仓库）

• Stanford CS149 作业交流（Assignment 2）——知乎/GitHub 若干实现（随进度补充具体链接）

• C++ 标准库：std::thread / std::atomic / std::mutex / std::condition_variable（https://en.cppreference.com）