文档目录

Work-Stealing 的核心思想:每个线程有自己的任务队列,线程优先处理自己的任务。自己的队列空了,才去"偷"别人的。

线程 1                   线程 2                   线程 3
┌──────────────┐        ┌──────────────┐        ┌──────────────┐
│ deque<任务>   │        │ deque<任务>   │        │ deque<任务>   │
│ [t1][t2][t3] │        │ [t4][t5]     │        │ 空            │
│  ↑pop_front  │        │  ↑pop_front  │        │              │
└──────────────┘        └──────────────┘        └──────────────┘
      │                                               │
      │ 自己取自己的任务                                 │ 自己的空了,
      │ top_front 是热点                               │ 去偷别人的
      ▼                                               ▼
  执行 t1                                        从线程 2 的
                                                 尾部偷 t5

每个队列是双端队列(deque):

  • 自己:从 front 取任务(pop_front)——热点
  • 别人偷:从 back 取任务(pop_back)——减少冲突

为什么自己从 front 取、别人从 back 偷?

  • 如果任务有父子关系(父任务生成子任务),子任务在 front,父任务优先处理自己刚生成的子任务,利用缓存局部性。
  • 偷取从 back,减少与线程自己取任务的冲突概率(同一 deque 两端操作冲突概率低)。