本文是 Scheduling Multithreaded Computations by Work Stealing 的笔记，该论文提出了基于 work stealing 思想的线程分配算法。

work stealing 的定义

  • Work-sharing 产生新线程的时候，进程将已有的线程分配出去。
  • Work-stealing 利用率低的进程从别的进程那里“偷”线程。

吐槽，资本主义不但压榨人，也压榨进程。

多线程模型

将多线程计算抽象成一个 DAG，每个指令是一个节点，指令的依赖关系构成边，这种边被称为 continue 边。线程会 spawn 出新的线程，这在图中增加了新类型的边，我们称这种边为 spawn 边。没有 spawn 边出去的线程被称为叶子线程。不同的指令之间可能会有数据的依赖，若指令 b 依赖指令 a 的数据，则 a 到 b 存在一条 join 边。

一个 fully strict 的计算模型就是所有 join 边都是从子线程指向父线程（不会从父线程到子线程，也不会从子线程到祖父线程）。

子线程、父线程和祖父线程这种说法比较不女权，但是也没有更好的术语用。

the busy-leaves property

The busy-leaves property：运行中，every leaf has a processor working on it.

不知道怎样翻译才好。

The Busy-Leaves Algorithm （后面简称 BL 算法）有几条规则：

  1. 如果线程 a spawn 了线程 b，processor 将 a 放回线程池，开始执行线程 b 的指令。
  2. 如果线程 a stalls （等待它依赖的线程的数据），processor 将 a 放回线程池，然后开始闲置。
  3. 如果子线程 a 死了，检查它的父线程 b 是否有其他子线程，如果 b 既没有活着的子线程也没有别的 proccessor working on it，那么 proccessor 执行 b，若否， proccessor 闲置。

strict 的计算模型可以保持 the busy-leaves property。 证明就省下了。但是 BL 算法不够高效。

随机化 work-stealing 算法

首先，每个 proccessor 都会维护一个 dequeue。对 proccessor 来说，这个 dequeue 和 stack 一样，是后进先出的，但是可以在头部移走线程（这样就可以”偷“线程了）。

WS 算法的规则如下：

  1. 如果线程 a spawn 线程 b，把线程 a 放入 ready queue 的底部， proccessor 开始处理 b 的指令。
  2. 如果线程 a stalls，proccessor 检查 ready queue，如果里面有线程，那么取出线程开始处理。如果没有，开始 work stealing：从随机选择的 proccessor 的 queue 的顶部取线程。
  3. 如果线程 a 死了，按照规则2的方案走。
  4. 如果线程 a enable 了线程 b，线程 b 被放入线程 a 的 proccessor 的 queue 里面。

定理和证明略。

剩下的部分都是算法分析和定理证明。略过不看。