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 两端操作冲突概率低)。