C++实现高性能优先级任务调度 _ 基于跳表的高并发实现【源码】-C++-PHP中文网

因为std::priority_queue非线程安全且不支持o(log n)随机删除，无法满足高并发调度中任务取消、降级等需求；应选用支持并发操作、无锁可选、允许重复优先级并带引用计数的跳表实现。

c++实现高性能优先级任务调度 _ 基于跳表的高并发实现【源码】

为什么不用 `std::priority_queue` 做高并发任务调度

因为它是非线程安全的，且不支持 O(log n) 时间内随机删除任意节点——任务超时取消、动态降级、抢占式中断等场景必须能快速移除指定任务。每次用 std::priority_queue 都得加锁 + 全量重建或标记延迟删除，吞吐直接掉一个数量级。

常见错误现象：std::priority_queue 封装成线程安全 wrapper 后，压测下 CPU 消耗集中在锁争用，QPS 卡在 10k 以下；或者用 std::set 替代，但迭代器失效风险高，erase(iterator) 后误用旧迭代器导致崩溃。

真正需要的是：支持并发插入/删除/取顶、无锁路径（lock-free path）可选、key 可重复（同优先级任务多）、支持按 ID 查找
std::set 虽有序但 key 必须唯一，任务 ID 和优先级常分离，硬塞进 pair 容易引发比较逻辑歧义
跳表（SkipList）天然满足：平均 O(log n) 插入/删除/查找、易实现无锁变体、允许重复 score、结构清晰利于调试

跳表节点设计必须带唯一 ID 和引用计数

任务调度不是纯排序问题，而是生命周期管理问题。只存 priority 和 task_func 会导致无法安全回收——比如任务已执行完毕，但还在跳表里等待被 pop，此时若线程池直接析构，函数指针就悬空了。

正确做法是每个节点持有一个 std::shared_ptr<task></task>，而 Task 内部含 id（uint64_t）、score（int64_t，时间戳或优先级值）、exec（std::function<void></void>），并重载 operator 仅基于 <code>score 比较（允许相同 score）。

跳表比较函数不能用 id 参与排序，否则破坏优先级语义；但插入时需用 id 做二次哈希索引，供 Cancel(uint64_t id) 快速定位
引用计数防止任务对象在跳表遍历中途被析构；若用裸指针 + weak_ptr 管理，需在 pop 时先 lock() 成功才执行，否则跳过
节点内存布局建议把 id 放最前，便于后续用 memchr 或 SIMD 批量扫描（调试或统计时有用）

`SkipList<task></task>` 的并发插入要避免 ABA 问题

纯无锁跳表插入时，多个线程可能同时读到同一层的 next 指针为 A，各自构造新节点后 CAS 更新，但第二个 CAS 成功时，第一个线程的局部变量仍指向已被替换的旧 A —— 若它继续往下层操作，就会链入错误位置。这是典型 ABA 问题。

C++ Code Review Master

组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。

下载

实操建议：不要手写全无锁跳表。生产环境优先用 folly::AtomicUnorderedMap + 分段跳表（per-CPU slab），或基于 absl::container::inlined_vector 实现带 epoch-based reclamation 的跳表。若必须自研，至少对每层 head 使用 std::atomic<node></node> + ABA-safe pointer（如 std::atomic<uintptr_t></uintptr_t> 存地址+版本号）。

简单方案：用 std::mutex 保护整个跳表，但粒度改为「按 score 区间分段加锁」，例如 [0, 1000) 一把锁、[1000, 2000) 一把锁，冲突率下降 70%+
禁止在插入回调里调用 schedule() 自身，否则可能死锁（同一段锁重入）；应改用 lock-free ring buffer 中转
插入失败时别直接重试，先 std::this_thread::yield()，避免忙等耗尽 CPU

调度循环怎么避免「饥饿」和「惊群」

单纯 while(true) { if (!list.empty()) exec(list.pop()); else sleep(1ms); } 会出问题：低优先级任务永远等不到机会（饥饿）；多个工作线程同时发现非空就抢，但只有一个能成功 pop，其余白唤醒（惊群）。

正确模式是「双队列 + 信号量」：跳表只负责有序存储，另起一个 lock-free moodycamel::ConcurrentQueue<task></task> 作 ready queue。定时器线程按 score 扫描跳表，把到期/可执行任务 push 到 ready queue；工作线程只从 ready queue 消费。

扫描跳表不能每次从头开始，要维护一个 min_score_hint（上次扫到的最小 score），下次从该位置 resume，避免重复遍历
ready queue 长度超过阈值（如 1024）时，暂停扫描，防止 backlog 积压；同时触发告警而非 crash
惊群本质是 condition variable 唤醒粒度太粗，改用 sem_t 或 std::counting_semaphore（C++20）精确控制唤醒线程数

跳表本身不解决调度策略复杂性——它只是个高效容器。真正的难点在 score 设计（是否融合 deadline、SLA 权重、资源占用预估）、取消路径的原子性、以及跨进程/跨机器协同时的一致性。这些没法靠数据结构一劳永逸。