Work Stealing 工作窃取算法在 Go 的 GMP 调度模型中Work Stealing 是维系多核负载均衡的核心机制。当一个 ProcessorP的本地运行队列LRQ耗尽时它不会闲着而是主动去偷其他 P 的任务——这种自底向上的负载均衡策略让 Go 的调度器在绝大多数场景下都能保持极高的 CPU 利用率。1. 核心概念与工作原理1.1 为什么需要 Work Stealing想象四个收银员P面对四条结账通道LRQ。如果顾客G分布不均有的通道排起长队有的却空空如也整个超市的吞吐量就会大打折扣。最直观的方案是让一个中央调度器来统一分配顾客但这会引入严重的锁竞争和缓存失效问题。Go 选择的方案是分布式队列 Work Stealing每个 P 维护自己的 LRQ无锁操作只有当前 M 会访问当 LRQ 为空时P 主动从其他 P 或全局队列GRQ中寻找任务这种按需窃取的策略将负载均衡的开销均摊到空闲的 P 上而非由中央调度器承担1.2 偷取目标的优先级runtime.findrunnable()中Go 调度器按以下顺序寻找可运行的 G本地 LRQ— 无锁O(1) 弹出全局 GRQ— 需要加锁竞争较大网络轮询器netpoll— 检查是否有就绪的网络事件其他 P 的 LRQWork Stealing— 随机化遍历偷取尾部一半再次检查全局 GRQ解析 GC 任务或降频休眠1.3 偷一半策略Go 的 Work Stealing 遵循一个精妙的规则偷取受害者队列尾部的一半任务。为什么是尾部因为队列头部的任务大概率已经加载到 CPU 缓存中局部性原理受害者 P 很快会用到它们。偷尾部既能让窃贼获得足够的工作量又最大限度减少了对受害者缓存局部性的破坏。为什么是一半而非一个如果只偷一个窃贼可能很快再次耗尽频繁触发偷取逻辑反而增加开销如果全偷光受害者 P 后续可能无事可做。一半在两者之间取得了最优平衡。1.4 随机化遍历顺序stealOrder多个 P 同时陷入空闲时如果它们总是按固定顺序扫描其他 P很容易发生集体碰撞——多个窃贼同时盯上同一个受害者。Go 的解决方案是每个 P 在偷取前生成一个伪随机遍历顺序将冲突概率降到最低。这个随机化不是用昂贵的真随机数生成器而是基于 P 的 ID 和一个预定的轮询表stealOrder计算出一个确定但看起来随机的访问序列。2. 关键规则与机制规则说明偷尾部一半保留受害者头部任务的缓存局部性窃贼获得可持续的工作量随机化遍历通过stealOrder避免多窃贼同时竞争同一个受害者 P从 GRQ 偷取当从其他 P 偷不到时会尝试从全局队列批量取走一批 GHandoff 机制当 M 进入系统调用阻塞时其 P 会被移交给其他空闲 M 继续使用自旋 M 限制没有工作的 M 不会无限自旋而是进入休眠由 sysmon 或事件唤醒3. 深度代码演练完整可运行示例下面的程序用 Go 语言模拟了一个简化版的 Work Stealing 调度器。我们创建了 4 个 Processor初始时只有 P0 拥有 20 个任务。随后 P1、P2、P3 依次尝试通过 Work Stealing 获取任务观察偷一半和随机化遍历的效果。packagemainimport(fmtmath/randsynctime)// LocalQueue 模拟 P 的本地运行队列LRQtypeLocalQueuestruct{tasks[]int// 存储任务 IDmu sync.Mutex}// Push 向队列尾部添加任务func(lq*LocalQueue)Push(taskint){lq.mu.Lock()deferlq.mu.Unlock()lq.tasksappend(lq.tasks,task)}// Pop 从队列头部弹出任务FIFO模拟真实调度func(lq*LocalQueue)Pop()(int,bool){lq.mu.Lock()deferlq.mu.Unlock()iflen(lq.tasks)0{return0,false}task:lq.tasks[0]lq.taskslq.tasks[1:]returntask,true}// Len 返回当前队列长度func(lq*LocalQueue)Len()int{lq.mu.Lock()deferlq.mu.Unlock()returnlen(lq.tasks)}// Snapshot 返回队列当前快照仅用于打印func(lq*LocalQueue)Snapshot()[]int{lq.mu.Lock()deferlq.mu.Unlock()out:make([]int,len(lq.tasks))copy(out,lq.tasks)returnout}// StealHalf 偷取队列尾部的一半任务返回偷到的任务切片// 真实 Go 调度器中这是无锁的这里用锁模拟并发安全func(lq*LocalQueue)StealHalf()[]int{lq.mu.Lock()deferlq.mu.Unlock()n:len(lq.tasks)ifn2{returnnil}// 偷取后半部分保留前半部分以维护缓存局部性half:n/2stolen:make([]int,half)copy(stolen,lq.tasks[n-half:])lq.taskslq.tasks[:n-half]returnstolen}// Processor 模拟调度器中的 PtypeProcessorstruct{idintlrq*LocalQueue}// Scheduler 模拟 Work Stealing 调度器typeSchedulerstruct{ps[]*Processor}// NewScheduler 创建包含 n 个 P 的调度器funcNewScheduler(nint)*Scheduler{ps:make([]*Processor,n)fori:0;in;i{ps[i]Processor{id:i,lrq:LocalQueue{}}}returnScheduler{ps:ps}}// stealOrder 生成伪随机化的偷取遍历顺序// 真实 Go 源码中使用基于轮询表的确定性随机序列func(s*Scheduler)stealOrder(thiefIDint,rng*rand.Rand)[]int{n:len(s.ps)order:make([]int,0,n-1)fori:0;in;i{ifi!thiefID{orderappend(order,i)}}// 随机打乱避免多窃贼同时竞争同一受害者rng.Shuffle(len(order),func(i,jint){order[i],order[j]order[j],order[i]})returnorder}// StealFrom 尝试从指定受害者偷取任务func(s*Scheduler)StealFrom(thiefID,victimIDint)[]int{stolen:s.ps[victimID].lrq.StealHalf()iflen(stolen)0{// 将偷到的任务放入窃贼的 LRQfor_,task:rangestolen{s.ps[thiefID].lrq.Push(task)}}returnstolen}funcmain(){// Go 1.20 推荐显式创建本地随机源避免全局锁rng:rand.New(rand.NewSource(time.Now().UnixNano()))sched:NewScheduler(4)// 初始状态只有 P0 拥有 20 个任务模拟负载不均fori:1;i20;i{sched.ps[0].lrq.Push(i)}fmt.Println( 初始状态 )for_,p:rangesched.ps{fmt.Printf(P%d: %d 个任务 %v\n,p.id,p.lrq.Len(),p.lrq.Snapshot())}// P1, P2, P3 依次尝试 Work StealingforthiefID:1;thiefID3;thiefID{order:sched.stealOrder(thiefID,rng)fmt.Printf(\nP%d 开始偷取遍历顺序: %v\n,thiefID,order)for_,victimID:rangeorder{stolen:sched.StealFrom(thiefID,victimID)iflen(stolen)0{fmt.Printf( → 从 P%d 偷到 %d 个任务: %v\n,victimID,len(stolen),stolen)break// 偷到即停止本次尝试}}}fmt.Println(\n 偷取后状态 )for_,p:rangesched.ps{fmt.Printf(P%d: %d 个任务 %v\n,p.id,p.lrq.Len(),p.lrq.Snapshot())}// 进一步演示所有 P 各自执行一个任务fmt.Println(\n 各 P 执行一个任务后 )for_,p:rangesched.ps{iftask,ok:p.lrq.Pop();ok{fmt.Printf(P%d 执行任务 #%d\n,p.id,task)}else{fmt.Printf(P%d 无任务可执行\n,p.id)}}fmt.Println(\n 最终队列状态 )for_,p:rangesched.ps{fmt.Printf(P%d: %d 个任务 %v\n,p.id,p.lrq.Len(),p.lrq.Snapshot())}}4. 输出解读与分析程序某次运行的输出如下由于随机化遍历顺序每次结果会略有不同 初始状态 P0: 20 个任务 [1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20] P1: 0 个任务 [] P2: 0 个任务 [] P3: 0 个任务 [] P1 开始偷取遍历顺序: [2 0 3] → 从 P0 偷到 10 个任务: [11 12 13 14 15 16 17 18 19 20] P2 开始偷取遍历顺序: [3 1 0] → 从 P1 偷到 5 个任务: [16 17 18 19 20] P3 开始偷取遍历顺序: [1 2 0] → 从 P1 偷到 2 个任务: [13 14] 偷取后状态 P0: 10 个任务 [1 2 3 4 5 6 7 8 9 10] P1: 3 个任务 [11 12 15] P2: 5 个任务 [16 17 18 19 20] P3: 2 个任务 [13 14] 各 P 执行一个任务后 P0 执行任务 #1 P1 执行任务 #11 P2 执行任务 #16 P3 执行任务 #13 最终队列状态 P0: 9 个任务 [2 3 4 5 6 7 8 9 10] P1: 2 个任务 [12 15] P2: 4 个任务 [17 18 19 20] P3: 1 个任务 [14]逐条解读现象原理说明P1 从 P0 偷到 10 个后半部分[11..20]偷一半策略P0 原 20 个偷走尾部 10 个P0 保留头部 10 个P2 的遍历顺序[3 1 0]先跳过 P0随机化遍历P2 随机到了先检查 P3空→ P1有 10 个P2 从 P1 偷到 5 个P1 有 10 个尾部一半是 5 个P3 从 P1 偷到 2 个P1 此时剩 5 个尾部一半是 2 个整数除法负载从[20, 0, 0, 0]变为[10, 3, 5, 2]Work Stealing 在极短时间内将极端不均衡转化为相对均衡5. 小结要点内容核心目标在无中央调度器的前提下实现多核间的负载自动均衡关键策略空闲 P 从其他 P 的 LRQ 尾部偷取一半任务随机化stealOrder伪随机遍历避免多窃贼集体碰撞局部性保护偷尾部而非头部保留受害者即将执行任务的 CPU 缓存局部性真实源码位置runtime/proc.go:findrunnable()、runtime/proc.go:stealWork() Work Stealing 工作窃取算法
Work Stealing 工作窃取算法在 Go 的 GMP 调度模型中Work Stealing 是维系多核负载均衡的核心机制。当一个 ProcessorP的本地运行队列LRQ耗尽时它不会闲着而是主动去偷其他 P 的任务——这种自底向上的负载均衡策略让 Go 的调度器在绝大多数场景下都能保持极高的 CPU 利用率。1. 核心概念与工作原理1.1 为什么需要 Work Stealing想象四个收银员P面对四条结账通道LRQ。如果顾客G分布不均有的通道排起长队有的却空空如也整个超市的吞吐量就会大打折扣。最直观的方案是让一个中央调度器来统一分配顾客但这会引入严重的锁竞争和缓存失效问题。Go 选择的方案是分布式队列 Work Stealing每个 P 维护自己的 LRQ无锁操作只有当前 M 会访问当 LRQ 为空时P 主动从其他 P 或全局队列GRQ中寻找任务这种按需窃取的策略将负载均衡的开销均摊到空闲的 P 上而非由中央调度器承担1.2 偷取目标的优先级runtime.findrunnable()中Go 调度器按以下顺序寻找可运行的 G本地 LRQ— 无锁O(1) 弹出全局 GRQ— 需要加锁竞争较大网络轮询器netpoll— 检查是否有就绪的网络事件其他 P 的 LRQWork Stealing— 随机化遍历偷取尾部一半再次检查全局 GRQ解析 GC 任务或降频休眠1.3 偷一半策略Go 的 Work Stealing 遵循一个精妙的规则偷取受害者队列尾部的一半任务。为什么是尾部因为队列头部的任务大概率已经加载到 CPU 缓存中局部性原理受害者 P 很快会用到它们。偷尾部既能让窃贼获得足够的工作量又最大限度减少了对受害者缓存局部性的破坏。为什么是一半而非一个如果只偷一个窃贼可能很快再次耗尽频繁触发偷取逻辑反而增加开销如果全偷光受害者 P 后续可能无事可做。一半在两者之间取得了最优平衡。1.4 随机化遍历顺序stealOrder多个 P 同时陷入空闲时如果它们总是按固定顺序扫描其他 P很容易发生集体碰撞——多个窃贼同时盯上同一个受害者。Go 的解决方案是每个 P 在偷取前生成一个伪随机遍历顺序将冲突概率降到最低。这个随机化不是用昂贵的真随机数生成器而是基于 P 的 ID 和一个预定的轮询表stealOrder计算出一个确定但看起来随机的访问序列。2. 关键规则与机制规则说明偷尾部一半保留受害者头部任务的缓存局部性窃贼获得可持续的工作量随机化遍历通过stealOrder避免多窃贼同时竞争同一个受害者 P从 GRQ 偷取当从其他 P 偷不到时会尝试从全局队列批量取走一批 GHandoff 机制当 M 进入系统调用阻塞时其 P 会被移交给其他空闲 M 继续使用自旋 M 限制没有工作的 M 不会无限自旋而是进入休眠由 sysmon 或事件唤醒3. 深度代码演练完整可运行示例下面的程序用 Go 语言模拟了一个简化版的 Work Stealing 调度器。我们创建了 4 个 Processor初始时只有 P0 拥有 20 个任务。随后 P1、P2、P3 依次尝试通过 Work Stealing 获取任务观察偷一半和随机化遍历的效果。packagemainimport(fmtmath/randsynctime)// LocalQueue 模拟 P 的本地运行队列LRQtypeLocalQueuestruct{tasks[]int// 存储任务 IDmu sync.Mutex}// Push 向队列尾部添加任务func(lq*LocalQueue)Push(taskint){lq.mu.Lock()deferlq.mu.Unlock()lq.tasksappend(lq.tasks,task)}// Pop 从队列头部弹出任务FIFO模拟真实调度func(lq*LocalQueue)Pop()(int,bool){lq.mu.Lock()deferlq.mu.Unlock()iflen(lq.tasks)0{return0,false}task:lq.tasks[0]lq.taskslq.tasks[1:]returntask,true}// Len 返回当前队列长度func(lq*LocalQueue)Len()int{lq.mu.Lock()deferlq.mu.Unlock()returnlen(lq.tasks)}// Snapshot 返回队列当前快照仅用于打印func(lq*LocalQueue)Snapshot()[]int{lq.mu.Lock()deferlq.mu.Unlock()out:make([]int,len(lq.tasks))copy(out,lq.tasks)returnout}// StealHalf 偷取队列尾部的一半任务返回偷到的任务切片// 真实 Go 调度器中这是无锁的这里用锁模拟并发安全func(lq*LocalQueue)StealHalf()[]int{lq.mu.Lock()deferlq.mu.Unlock()n:len(lq.tasks)ifn2{returnnil}// 偷取后半部分保留前半部分以维护缓存局部性half:n/2stolen:make([]int,half)copy(stolen,lq.tasks[n-half:])lq.taskslq.tasks[:n-half]returnstolen}// Processor 模拟调度器中的 PtypeProcessorstruct{idintlrq*LocalQueue}// Scheduler 模拟 Work Stealing 调度器typeSchedulerstruct{ps[]*Processor}// NewScheduler 创建包含 n 个 P 的调度器funcNewScheduler(nint)*Scheduler{ps:make([]*Processor,n)fori:0;in;i{ps[i]Processor{id:i,lrq:LocalQueue{}}}returnScheduler{ps:ps}}// stealOrder 生成伪随机化的偷取遍历顺序// 真实 Go 源码中使用基于轮询表的确定性随机序列func(s*Scheduler)stealOrder(thiefIDint,rng*rand.Rand)[]int{n:len(s.ps)order:make([]int,0,n-1)fori:0;in;i{ifi!thiefID{orderappend(order,i)}}// 随机打乱避免多窃贼同时竞争同一受害者rng.Shuffle(len(order),func(i,jint){order[i],order[j]order[j],order[i]})returnorder}// StealFrom 尝试从指定受害者偷取任务func(s*Scheduler)StealFrom(thiefID,victimIDint)[]int{stolen:s.ps[victimID].lrq.StealHalf()iflen(stolen)0{// 将偷到的任务放入窃贼的 LRQfor_,task:rangestolen{s.ps[thiefID].lrq.Push(task)}}returnstolen}funcmain(){// Go 1.20 推荐显式创建本地随机源避免全局锁rng:rand.New(rand.NewSource(time.Now().UnixNano()))sched:NewScheduler(4)// 初始状态只有 P0 拥有 20 个任务模拟负载不均fori:1;i20;i{sched.ps[0].lrq.Push(i)}fmt.Println( 初始状态 )for_,p:rangesched.ps{fmt.Printf(P%d: %d 个任务 %v\n,p.id,p.lrq.Len(),p.lrq.Snapshot())}// P1, P2, P3 依次尝试 Work StealingforthiefID:1;thiefID3;thiefID{order:sched.stealOrder(thiefID,rng)fmt.Printf(\nP%d 开始偷取遍历顺序: %v\n,thiefID,order)for_,victimID:rangeorder{stolen:sched.StealFrom(thiefID,victimID)iflen(stolen)0{fmt.Printf( → 从 P%d 偷到 %d 个任务: %v\n,victimID,len(stolen),stolen)break// 偷到即停止本次尝试}}}fmt.Println(\n 偷取后状态 )for_,p:rangesched.ps{fmt.Printf(P%d: %d 个任务 %v\n,p.id,p.lrq.Len(),p.lrq.Snapshot())}// 进一步演示所有 P 各自执行一个任务fmt.Println(\n 各 P 执行一个任务后 )for_,p:rangesched.ps{iftask,ok:p.lrq.Pop();ok{fmt.Printf(P%d 执行任务 #%d\n,p.id,task)}else{fmt.Printf(P%d 无任务可执行\n,p.id)}}fmt.Println(\n 最终队列状态 )for_,p:rangesched.ps{fmt.Printf(P%d: %d 个任务 %v\n,p.id,p.lrq.Len(),p.lrq.Snapshot())}}4. 输出解读与分析程序某次运行的输出如下由于随机化遍历顺序每次结果会略有不同 初始状态 P0: 20 个任务 [1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20] P1: 0 个任务 [] P2: 0 个任务 [] P3: 0 个任务 [] P1 开始偷取遍历顺序: [2 0 3] → 从 P0 偷到 10 个任务: [11 12 13 14 15 16 17 18 19 20] P2 开始偷取遍历顺序: [3 1 0] → 从 P1 偷到 5 个任务: [16 17 18 19 20] P3 开始偷取遍历顺序: [1 2 0] → 从 P1 偷到 2 个任务: [13 14] 偷取后状态 P0: 10 个任务 [1 2 3 4 5 6 7 8 9 10] P1: 3 个任务 [11 12 15] P2: 5 个任务 [16 17 18 19 20] P3: 2 个任务 [13 14] 各 P 执行一个任务后 P0 执行任务 #1 P1 执行任务 #11 P2 执行任务 #16 P3 执行任务 #13 最终队列状态 P0: 9 个任务 [2 3 4 5 6 7 8 9 10] P1: 2 个任务 [12 15] P2: 4 个任务 [17 18 19 20] P3: 1 个任务 [14]逐条解读现象原理说明P1 从 P0 偷到 10 个后半部分[11..20]偷一半策略P0 原 20 个偷走尾部 10 个P0 保留头部 10 个P2 的遍历顺序[3 1 0]先跳过 P0随机化遍历P2 随机到了先检查 P3空→ P1有 10 个P2 从 P1 偷到 5 个P1 有 10 个尾部一半是 5 个P3 从 P1 偷到 2 个P1 此时剩 5 个尾部一半是 2 个整数除法负载从[20, 0, 0, 0]变为[10, 3, 5, 2]Work Stealing 在极短时间内将极端不均衡转化为相对均衡5. 小结要点内容核心目标在无中央调度器的前提下实现多核间的负载自动均衡关键策略空闲 P 从其他 P 的 LRQ 尾部偷取一半任务随机化stealOrder伪随机遍历避免多窃贼集体碰撞局部性保护偷尾部而非头部保留受害者即将执行任务的 CPU 缓存局部性真实源码位置runtime/proc.go:findrunnable()、runtime/proc.go:stealWork()