Work Stealing（工作窃取）是一种 任务调度策略，用于多线程并行计算。它的核心思想是：

让空闲的线程从其他繁忙的线程那里“偷”任务，以提高 CPU 利用率。

1. 为什么需要 Work Stealing？

在 多线程程序 中，任务的执行时间通常不均衡，如果任务分配不合理，可能会导致：

• 某些线程任务繁重，其他线程空闲（CPU 资源浪费）。
• 线程间负载不均衡，导致整体计算性能下降。

a.传统调度方式

• 静态任务分配：
  任务在一开始就分配给固定线程，线程间无法动态调整 → 可能造成 某些线程任务多，某些线程空闲 的情况。

b.Work Stealing 方式

• 动态任务分配：
  线程拥有 自己的任务队列，如果执行完自己的任务，就从 其他忙碌线程的队列中“偷”任务。无论任务大小如何，Work Stealing 可以减少线程在等待任务分配时的空闲时间。线程会在执行完自己的任务后积极寻找其他可执行的任务，而不是等待任务调度器分配新任务。

优点：提高 CPU 利用率，减少线程闲置，提高整体吞吐量。
缺点：增加了一些任务“窃取”的开销（例如锁开销）。Work Stealing 需要保证线程之间的同步，防止多个线程同时修改同一个任务队列。一般通过锁或无锁队列（如双端队列）来实现。在某些极端情况下，任务窃取的过程可能会引入一些延迟，尤其是当任务队列被频繁访问时，可能导致缓存未命中或者线程间过度竞争。

2. Work Stealing 的核心机制

(1) 任务队列

1. 每个工作线程都有一个 本地任务队列，是一个双端队列。这个队列存放了待处理的任务（任务通常是计算单元，或者是分割后的大任务）。 线程从自己的队列中取任务执行。
2. 线程可以：自己消费任务（从队列前端取出），其他线程偷任务（从队列后端取出）。（有时偷任务发生在队列的头部或尾部，取决于具体实现）
3. 为什么窃取任务要从队列后端？
   • 避免与任务执行中的 Worker 线程竞争（减少锁竞争）。
   • 窃取大任务，提高效率（通常任务队列是 LIFO，栈顶是最新任务）。

(2) 任务窃取流程

1. Worker 线程开始执行任务
   • 从 自己队列的前端 获取任务并执行。
2. Worker 线程任务执行完毕，队列变空
   • 该线程进入 空闲状态，尝试窃取其他线程的任务。
3. Worker 线程从其他繁忙线程的队列中“偷”任务
   • 任务通常从 队列的后端 被窃取。
   • 窃取成功 → 执行任务。
   • 窃取失败 → 继续尝试从其他线程窃取。
4. 所有任务执行完毕
   • 所有线程最终完成所有任务，程序退出。

---

3. 具体实现：Go GMP vs Rust Rayon vs Tokio

(1) Go GMP 模型

Go 的 GMP（Goroutine、M 线程、P 处理器） 调度器使用 Work Stealing 来均衡 Goroutine 任务：

• P（Processor） 负责调度 Goroutine，拥有自己的任务队列。
• 当某个 P 没有任务时，它会从其他 P 处 Work Stealing。
• Goroutine 任务调度是非抢占式的，但垃圾回收等机制会让 Goroutine 被强制切换。（Go1.14版本后采用混合调度机制，即保留了非抢占式调度，但增加了强制抢占机制。在多数情况下仍然依赖协作式调度，但在必要时（长时间运行的 Goroutine）会强制抢占。）

---

(2) Rust Rayon

• Rayon高并发 I/O、多线程计算 使用 Fork-Join 并行模型，每个 Worker 线程都有一个 双端队列（Deque）。
• 任务的 Worker 线程会 优先执行自己任务，如果队列为空，它就会从 其他线程的队列尾部偷任务。

---

(3) Tokio

Tokio 主要使用 多线程 Work Stealing 机制 进行任务调度，类似于 Go 的 GMP 调度模型，但专门针对 Rust 的异步任务（Future） 进行了优化。

• 任务（Task）：Tokio 任务是 异步 Future，不会阻塞线程。
• 调度器（Scheduler）：负责在 多个 Worker 线程之间分发和窃取任务。
• 工作窃取（Work Stealing）：如果一个 Worker 线程执行完任务，它会尝试 从其他线程的任务队列中窃取任务，提高 CPU 资源利用率。

Tokio、Rayon 和 GMP 的 Work Stealing 机制对比

特性	Rayon（计算密集型）	Tokio（I/O 密集型）	Go GMP（通用调度）
任务类型	同步计算任务	异步任务（Future）	Goroutine 任务（M:N 调度）
任务调度方式	固定线程池（N:N 调度）	固定线程池（M:N 调度）	动态线程池（M:N 调度）
适用场景	CPU 密集型计算	I/O、网络、数据库	通用，适合高并发任务
Work Stealing 时机	任务分割后，空闲线程尝试偷取	任务完成/挂起后，空闲线程尝试偷取	P 任务不足时，从其他 P 偷取 Goroutine
任务队列	每个线程有本地队列，可偷取任务	每个 Worker 有本地队列，全局队列（Injector）用于负载均衡	每个 P（处理器）有本地队列，全局队列用于任务分发
线程模型	N:N（线程数量固定）	M:N（任务数远超线程数，任务调度到少量 Worker 线程）	M:N（Goroutine 数量远超内核线程）

*Rayon Work Stealing

适用场景：并行计算，如并行 Map-Reduce、矩阵运算、图像处理等。
机制：

1. 任务拆分（Fork-Join）：将任务拆分为子任务，每个 Worker 线程执行自己的任务队列。
2. 任务完成时 Work Stealing：空闲 Worker 线程会从其他 Worker 线程的队列尾部偷取任务。

*Tokio Work Stealing

适用场景：异步任务，如 HTTP 请求、数据库查询、定时任务等。
机制：

1. 任务采用 Future + async/await 机制，在 Worker 线程上运行。
2. 任务完成或挂起时，Work Stealing 触发：
   • 如果 Worker 线程任务执行完，它会从 其他 Worker 或全局任务队列 偷取任务。
   • 避免长时间等待 I/O 导致线程资源浪费。

*Go GMP（Goroutine Work Stealing）

适用场景：通用高并发任务，如 Web 服务器、微服务等。
机制：

1. Goroutine 任务执行在 “P” 上（调度器）。
2. M:N 调度：多个 Goroutine 共享少量 OS 线程（N）。
3. Work Stealing：
   • 如果 P 任务不足，它会从其他 P 偷取 Goroutine 继续执行。
   • 全局队列负责任务调度，防止 P 任务不均衡。

---

4. Work Stealing 适用场景

适合于：

• 并行计算（例如矩阵运算、数据处理）。Rayon（Rust）、OpenMP 等并行计算库利用 Work Stealing 机制来处理并行化的计算任务。例如，分割一个大数组，让多个线程并行处理，空闲线程会从其他线程窃取任务进行处理。
• 任务粒度不均匀（任务大小不一）。
• 异步任务调度：在异步编程模型中（如 Go GMP 模型、Tokio 等），线程池中的空闲线程会窃取任务执行，避免有线程处于空闲状态。这样可以高效调度 I/O 密集型或其他异步任务。
• 高性能计算。
• 图像处理与大数据计算。

不适合于：

• 任务粒度过小（窃取任务开销可能大于计算任务）。
• 完全静态任务分配（如果任务分配是均衡的，Work Stealing 可能不必要）。
• 强同步任务（某些任务必须顺序执行）。

---

5. 总结

• Work Stealing 通过任务窃取机制提高 CPU 利用率，减少线程空闲时间。
• 采用 Work Stealing 的库
  • Go：GMP 调度器
  • Rust：Rayon（数据并行）、Tokio（异步调度）
• Work Stealing 适用于任务时间不均衡的并行计算或异步任务调度，比如具有递归结构的任务、需要动态负载均衡的计算任务，常见的应用场景包括数据并行计算、异步任务调度、高性能计算等。