---
title: 工作窃取总览
date: 2025-01-17 08:34:00
author: loongs-zhang
---
# 工作窃取总览
[English](../en/work-steal.md) | 中文
## 为什么需要工作窃取？
在现实世界中，总是有一些线程先完成自己的任务，而其他线程还有任务需要处理。于是，就会出现一核有难、多核围观的壮观场景。
<div style="text-align: center;">
<img src="../../../docs/img/watching.png" width="50%">
</div>
显然，我们不希望这种情况发生。对于空闲的线程，与其让它们围观其他线程工作，不如让它们帮助其他线程工作。
## 什么是工作窃取队列？
工作窃取队列由一个全局队列和多个本地队列组成，全局队列是无界的，而本地队列是一个有界的环形缓冲区（RingBuffer）。为了确保高性能，本地队列的数量通常等于线程的数量。值得一提的是，如果所有线程都优先处理本地任务，可能会出现一种极端情况，即共享队列上的任务永远没有机会被调度。为了避免这种不平衡，参考goroutine的设计，每次线程从本地队列调度了60个任务后，强制从共享队列中弹出一个任务。
## `push`的工作原理
```mermaid
flowchart TD
Cond{本地队列是否已满?}
PS[将任务推入本地队列]
PTG[将本地队列中一半的任务推入全局队列]
PG[将任务推入全局队列]
push --> Cond
Cond -- 否 --> PS
Cond -- 是 --> PTG --- PG
```
## `pop`的工作原理
```mermaid
flowchart TD
Cond1{本地队列中是否有任务?}
Cond2{其他本地队列中是否有任务?}
Cond3{全局队列中是否有任务?}
PS[弹出一个任务]
ST[从其他本地队列窃取任务]
PF[未找到任务]
pop --> Cond1
Cond1 -- 是 --> PS
Cond1 -- 否 --> Cond2
Cond2 -- 是 --> ST --> PS
Cond2 -- 否 --> Cond3
Cond3 -- 是 --> PS
Cond3 -- 否 --> PF
```