需手动构建基于无锁双端队列与原子操作的工作窃取调度器:每个线程独占ConcurrentDeque,支持本地pop_back/push_back及跨线程pop_front窃取;worker线程优先执行本地任务,本地空时随机尝试窃取,失败则yield;submit优先入本地队列,spawn支持steal_hint优化;shutdown前须确保无新任务并等待所有队列清空。

在多核CPU上高效利用闲置线程执行待处理任务,避免主线程阻塞、减少锁竞争并提升整体吞吐量,需要一套能动态平衡负载的并发调度机制。C++标准库不提供原生工作窃取调度器,必须基于双端队列(deque)与原子操作手动构建线程局部任务队列和跨线程窃取逻辑。
设计核心数据结构:无锁双端队列
每个工作线程维护一个 ConcurrentDeque,支持线程本地的高效压栈(push_back)和弹栈(pop_back),同时允许其他线程从对端安全地窃取(pop_front)。底层用环形缓冲区 + 原子索引实现,避免锁开销。
定义模板类 ConcurrentDeque<T>,内部使用 std::atomic_size_t m_head 和 m_tail 管理边界;缓冲区大小必须为 2 的幂,便于位运算取模;元素存储于 std::unique_ptr<T[]> 分配的连续内存中。
push_back 操作先读取 tail,计算新位置,用 compare_exchange_weak 尝试更新;失败则重试。pop_back 同理,但需额外检查 head 是否已追上 tail 防止空队列误弹。
立即学习“C++免费学习笔记(深入)”;
pop_front 是窃取入口,必须严格满足:仅当 tail > head + 1 时才允许执行(预留至少一个元素防止与 pop_back 竞态),且使用 acquire-release 内存序保证可见性。
初始化工作线程池与任务分发器
构造 WorkStealingScheduler 对象时,传入期望线程数 N(通常设为硬件并发数 std::thread::hardware_concurrency()),启动 N 个 std::thread,每个绑定独立 ConcurrentDeque<std::function<void()>> 实例,并保存在线程局部指针数组中。
主线程调用 submit(std::function<void()> task) 时,将任务推入当前线程的 deque 尾部;若当前无可绑定线程(如在非工作线程中调用),则轮询选择负载最轻的 worker deque 进行 push_back。
【必须确保 submit 调用前 scheduler 已 fully constructed 且所有 worker 线程处于运行状态】
实现窃取循环:worker 线程主逻辑
每个 worker 线程执行以下循环:
步骤一:尝试从本地 deque 弹出任务(pop_back),成功则立即执行;
步骤二:若本地为空,进入窃取阶段——随机选取一个其他 worker 索引(排除自身),对其 deque 调用 pop_front;
步骤三:若窃取成功,执行该任务;若失败,按固定步长偏移重新选目标(避免所有线程集中攻击同一空队列),最多尝试 log₂(N) 次;
步骤四:若所有窃取均失败,调用 std::this_thread::yield() 让出 CPU 时间片,避免忙等耗尽周期。
这一步的随机起始偏移和对数级重试上限是关键,能显著降低多线程同时窃取时的冲突概率。直接顺序遍历所有其他线程会导致严重的缓存行颠簸和 CAS 失败风暴。
嵌套任务提交与 steal hint 优化
方法一:在任务体内调用 spawn 提交子任务时,优先推入当前线程本地 deque 尾部,而非全局队列。这符合局部性原理,提高后续被同线程复用的概率。
方法二:为支持深度递归分治(如 parallel_for),在 spawn 时可附加 steal_hint = true 标志,强制将该子任务 push_front 到本地 deque——这样它更可能被其他线程窃取,避免本线程立即执行造成栈深度激增。
注意:push_front 在 ConcurrentDeque 中不对外暴露,仅限 spawn 内部使用,且仅当 steal_hint 为真时触发;否则一律 push_back。
安全关闭与等待完成
调用 shutdown() 时,设置全局停止标志 m_shutdown_requested(std::atomic_bool),然后对每个 worker 线程调用 join()。
每个 worker 在循环开头检查该标志,若为 true 且本地 deque 与所有其他 deque 均为空,则退出循环;否则继续处理剩余任务。
【shutdown 前必须确保无新任务提交,否则 join 可能永久阻塞】



















