Work Stealing 调度：实现负载均衡的协程调度器

说实话，协程调度器做到一定程度，你一定会遇到这个问题：有的核心忙死，有的核心闲死。

我在做嵌入式网络协议栈的时候，就吃过这个亏。8核处理器，4个核跑协程，结果3号核负载90%，1号核只有20%。你说这算不算资源浪费？

Work Stealing 就是来解决这个问题的。它不搞全局队列那一套，而是让每个线程自己管自己的活儿。谁干完了，就去偷别人的活儿干。嗯，说白了就是「各扫门前雪，顺便帮邻居扫扫」。

为什么需要 Work Stealing？

先想想传统的调度方式。全局一个任务队列，所有工作线程都去抢。这有什么问题？

• 锁竞争激烈：每次取任务都要加锁，线程多了就是灾难
• 缓存不友好：任务在内存里乱跳，CPU缓存命中率低
• 负载不均衡：有的线程抢得快，有的抢得慢，全靠运气

我早期做的一个协程库就用的全局队列。8线程压测，锁开销占了30%的CPU时间。后来改成 Work Stealing，同样的硬件，吞吐量直接翻倍。

核心思想：每个线程一个本地队列

Work Stealing 的架构其实很简单：

1. 每个工作线程维护一个双端队列（deque）
2. 线程自己从队列尾部取任务（LIFO，后进先出）
3. 空闲线程从其他线程队列的头部偷任务（FIFO，先进先出）

为什么要这样设计？

你想想看，自己取任务用 LIFO，是因为刚生成的任务很可能还在缓存里，执行起来快。偷任务用 FIFO，是因为偷的是最老的任务，避免跟原线程抢同一个任务，减少冲突。

数据结构设计

先看一个简单的 Work Stealing 队列实现：

// 无锁双端队列，用于 Work Stealing
typedef struct {
    struct task *tasks;    // 任务数组
    int capacity;          // 容量
    atomic_int top;        // 头部索引（偷任务用）
    atomic_int bottom;     // 尾部索引（自己取任务用）
} ws_deque_t;

// 初始化队列
void ws_deque_init(ws_deque_t *q, int cap) {
    q->tasks = malloc(cap * sizeof(struct task));
    q->capacity = cap;
    atomic_init(&q->top, 0);
    atomic_init(&q->bottom, 0);
}

// 自己压入任务（从尾部）
void ws_deque_push(ws_deque_t *q, struct task t) {
    int b = atomic_load(&q->bottom);
    q->tasks[b % q->capacity] = t;
    atomic_store(&q->bottom, b + 1);
    atomic_thread_fence(memory_order_release);
}

// 自己取任务（从尾部）
struct task ws_deque_pop(ws_deque_t *q) {
    int b = atomic_load(&q->bottom) - 1;
    atomic_store(&q->bottom, b);
    atomic_thread_fence(memory_order_seq_cst);
    int t = atomic_load(&q->top);
    
    if (t <= b) {
        // 队列非空，取任务
        struct task task = q->tasks[b % q->capacity];
        if (t == b) {
            // 只剩一个任务，需要 CAS 竞争
            if (!atomic_compare_exchange_strong(&q->top, &t, t + 1)) {
                // 竞争失败，队列已被偷空
                atomic_store(&q->bottom, b + 1);
                return EMPTY_TASK;
            }
        }
        return task;
    } else {
        // 队列已空
        atomic_store(&q->bottom, b + 1);
        return EMPTY_TASK;
    }
}

// 偷任务（从头部）
struct task ws_deque_steal(ws_deque_t *q) {
    int t = atomic_load(&q->top);
    atomic_thread_fence(memory_order_seq_cst);
    int b = atomic_load(&q->bottom);
    
    if (t < b) {
        struct task task = q->tasks[t % q->capacity];
        if (atomic_compare_exchange_strong(&q->top, &t, t + 1)) {
            return task;
        }
    }
    return EMPTY_TASK;
}

调度器整体架构

有了队列，调度器就好办了。每个工作线程一个队列，再加一个全局的「后备队列」处理新创建的协程。

下面这张图展示了 Work Stealing 调度器的核心流程：

流程是这样的：

1. 新协程先扔到全局后备队列
2. 每个线程从全局队列取一批任务，塞到自己本地队列
3. 线程优先从本地队列尾部取任务执行
4. 本地队列空了，就去偷其他线程队列头部的任务
5. 都偷不到，再从全局队列取

调度策略的细节

这里有几个细节，我当年调优的时候反复试过：

策略	做法	我的评价
随机偷	随机选一个受害者线程去偷	简单，但可能偷到空队列
轮询偷	按顺序轮流偷	公平性好，但实现略复杂
工作量感知	先偷队列最长的	负载最均衡，但需要维护全局信息

我个人习惯用随机偷。为什么？因为简单，而且在实际测试中，随机偷的效果跟轮询差不多。你想想看，线程数一多，随机性反而能避免「大家一起偷同一个线程」的尴尬。

避坑指南：ABA 问题

// 带版本号的 top，避免 ABA
typedef struct {
    struct task *tasks;
    int capacity;
    atomic_llong top;      // 高32位版本号，低32位索引
    atomic_int bottom;
} ws_deque_safe_t;

// 偷任务时，版本号一起 CAS
long long old_top = atomic_load(&q->top);
int idx = (int)(old_top & 0xFFFFFFFF);
int ver = (int)(old_top >> 32);

long long new_top = ((long long)(ver + 1) << 32) | (idx + 1);
if (atomic_compare_exchange_strong(&q->top, &old_top, new_top)) {
    // 偷成功
}

性能调优：批量偷取

还有一个优化点：不要一次只偷一个任务。

我在项目中测试过，一次偷一个任务，偷操作的次数太多，CAS 竞争反而更激烈。更好的做法是一次偷一批（比如 4 个或 8 个），然后放到自己队列里慢慢执行。

// 批量偷取：一次偷 half 个任务
int ws_deque_steal_batch(ws_deque_t *victim, struct task *buf, int half) {
    int t = atomic_load(&victim->top);
    atomic_thread_fence(memory_order_seq_cst);
    int b = atomic_load(&victim->bottom);
    
    int available = b - t;
    if (available <= 0) return 0;
    
    int steal_cnt = (available < half) ? available : half;
    
    // 偷 steal_cnt 个任务
    for (int i = 0; i < steal_cnt; i++) {
        buf[i] = victim->tasks[(t + i) % victim->capacity];
    }
    
    // 一次 CAS 更新 top
    long long old_top = ((long long)t) | (((long long)version) << 32);
    long long new_top = ((long long)(t + steal_cnt)) | (((long long)(version + 1)) << 32);
    if (atomic_compare_exchange_strong(&victim->top, &old_top, new_top)) {
        return steal_cnt;
    }
    return 0;
}

什么时候不适合 Work Stealing？

说实话，Work Stealing 不是万能的。我遇到过几种场景，它反而表现不好：

• 任务粒度太细：每个任务执行时间不到 1 微秒，偷任务的开销比执行还大
• CPU 核心数很少：2 核以下，偷来偷去没意义，全局队列更简单
• 任务之间有强依赖：一个任务必须等另一个任务完成，偷了也没用

遇到这些情况，我建议你老老实实用全局队列，或者干脆单线程跑协程。别为了炫技而用 Work Stealing。

写在最后

Work Stealing 调度器，说白了就是「让每个线程先管好自己的事，闲下来再去帮别人」。它把锁竞争降到了最低，缓存命中率提到了最高。

我做了这么多年嵌入式，从裸机到 RTOS，再到协程调度，越来越觉得：好的调度器不是让所有核心都忙，而是让所有核心都忙得有价值。

嗯，Work Stealing 就是朝着这个方向走的一步好棋。

---

公众号:蓝海资料掘金营，微信deep3321