工作窃取双端队列
Work Stealing Deque
题目详情
在高频交易系统中，最小化延迟要求高效地将订单处理和风控检查等任务分配到多个工作线程。Chase-Lev 工作窃取双端队列是一种基础无锁数据结构，通过允许所有者线程从底部推入和弹出、空闲线程从顶部窃取来优化缓存局部性。
任务：实现可扩容的 Chase-Lev 工作窃取双端队列 WorkStealingDeque。所有者线程可 push/pop 底部，窃取线程可 steal 顶部。当容量不足时自动扩容。
英文原题
In high-frequency trading systems, minimizing latency requires efficiently distributing tasks like order processing or risk checks across multiple worker threads. The Chase-Lev work-stealing deque is a fundamental lock-free data structure that optimizes cache locality by allowing the owner thread to push and pop from the bottom, while idle threads steal tasks from the top.
Task
Implement a resizable Chase-Lev work-stealing deque simulation by completing the WorkStealingDeque class. Since this i
解析
问题分析
工作窃取双端队列允许每个工作线程拥有自己的任务队列（LIFO 端），空闲线程从其他线程队列的 FIFO 端窃取任务。这种设计减少了全局队列的锁竞争，并优化了缓存局部性。
实现
class WorkStealingDeque {
static constexpr int MAX = 256;
std::array<std::function<void()>, MAX> tasks_;
std::atomic<int> top_{0}, bottom_{0};
public:
void push(std::function<void()> f) { // 仅本线程调用
int b = bottom_.load(std::memory_order_relaxed);
tasks_[b % MAX] = std::move(f);
bottom_.store(b + 1, std::memory_order_release);
}
std::function<void()> pop() { // 仅本线程调用 (LIFO)
int b = bottom_.load(std::memory_order_relaxed) - 1;
bottom_.store(b, std::memory_order_relaxed);
int t = top_.load(std::memory_order_acquire);
if (t <= b) return tasks_[b % MAX]; // 非空
bottom_.store(t, std::memory_order_relaxed); // 空，回退
return nullptr;
}
std::function<void()> steal() { // 其他线程调用 (FIFO)
int t = top_.load(std::memory_order_acquire);
int b = bottom_.load(std::memory_order_acquire);
if (t >= b) return nullptr; // 空
auto f = tasks_[t % MAX];
if (!top_.compare_exchange_strong(t, t + 1)) return nullptr; // 竞争失败
return f;
}
};复杂度与边界
- 时间复杂度：push/pop/steal 均为 O(1)
- 空间复杂度：O(MAX) 每线程
- 边界条件：(1) 队列满时 push 需等待或扩展 (2) steal 竞争通过 CAS 解决 (3) pop 和 steal 并发时需正确同步
英文解析
Analysis
A work-stealing deque allows each worker thread its own work queue (LIFO end), while idle threads steal tasks from other threads' FIFO end. This design reduces lock contention on the global queue and optimizes cache locality.
Solution
class WorkStealingDeque {
static constexpr int MAX = 256;
std::array<std::function<void()>, MAX> tasks_;
std::atomic<int> top_{0}, bottom_{0};
public:
void push(std::function<void()> f) { // only owner thread calls
int b = bottom_.load(std::memory_order_relaxed);
tasks_[b % MAX] = std::move(f);
bottom_.store(b + 1, std::memory_order_release);
}
std::function<void()> pop() { // only owner thread calls (LIFO)
int b = bottom_.load(std::memory_order_relaxed) - 1;
bottom_.store(b, std::memory_order_relaxed);
int t = top_.load(std::memory_order_acquire);
if (t <= b) return tasks_[b % MAX]; // non-empty
bottom_.store(t, std::memory_order_relaxed);
return nullptr; // empty
}
std::function<void()> steal() { // other threads call (FIFO)
int t = top_.load(std::memory_order_acquire);
if (t >= bottom_.load(std::memory_order_acquire)) return nullptr;
auto f = std::move(tasks_[t % MAX]);
top_.store(t + 1, std::memory_order_release);
return f;
}
};Complexity & Edge Cases
- Time complexity: O(1) for push/pop by owner; O(1) amortized for steal by other threads
- Space complexity: O(C) for C capacity of circular deque buffer
- Edge cases: (1) Steal from empty deque returns null — thief must try other deques. (2) Resize contention when owner pushes beyond capacity while thief is stealing. (3)ABA problem on steal index requires double-wide CAS or epoch-based protection.
Key Considerations
- Owner vs thief: push/pop are owner-only; steal is called by other threads, avoiding synchronization on the fast path.
- LIFO for owner: Owner processes recently pushed tasks first (likely still in cache).
- FIFO for thieves: Thieves take oldest tasks, reducing contention with the owner.
- Time complexity: push/pop/steal O(1) lock-free.