工作窃取队列为什么常用双端队列实现？
简化版
工作窃取中，每个工作线程通常有自己的双端队列：本线程从一端 push/pop 本地任务，其他空闲线程从另一端 steal 任务。这样本地操作快，窃取冲突少，也能在任务不均衡时自动分摊负载。
详细版
工作窃取用于并行任务调度。每个线程维护一个 deque：
- 本地线程把新任务放到队尾，也从队尾取任务。
- 其他线程空闲时，从队头偷任务。
- 两端分离可以减少本地执行和外部窃取的竞争。
- 常见于 Fork/Join、任务并行框架、线程池调度。
它不是普通 FIFO 队列，因为普通队列所有线程抢同一端，竞争更集中。双端队列让“自己用”和“别人偷”分开。
完整版教学
一、为什么需要工作窃取
并行任务常常不均衡。一个线程可能分到很多子任务，另一个线程很快做完变空闲。如果空闲线程只是等待，总体 CPU 利用率会下降。
工作窃取的思想是：
自己队列有任务 -> 做自己的
自己队列空了 -> 去别人的队列偷一个这样任务多的线程可以被帮忙，任务少的线程不会闲着。它适合递归分治、图计算、并行搜索等任务数量动态变化的场景。
二、为什么每个线程一个队列
如果所有线程共享一个全局队列，入队出队都会竞争同一把锁或同一组原子变量。线程越多，争抢越明显。
每个线程一个本地队列后，常见路径变成“访问自己的队列”。大多数 push/pop 都是本地操作，冲突少。
worker1: deque1
worker2: deque2
worker3: deque3只有某个 worker 空闲时，才会访问别人的队列进行 steal。这样把竞争从“每次任务操作”降低为“不均衡时才发生”。
三、为什么用双端队列而不是普通队列
双端队列有两个端。工作窃取通常让 owner 线程在一端操作，让 thief 线程在另一端操作。
head <- thief steal owner push/pop -> tail两端分离有两个好处。第一，减少竞争热点；第二，本地线程可以用 LIFO 方式优先处理刚生成的子任务，提高缓存局部性。偷任务的一方从另一端拿较老任务，往往任务粒度更大，更适合分摊。
四、LIFO 和 FIFO 在这里各有什么意义
owner 从 tail 取最近产生的任务，接近栈的行为。最近任务通常和当前上下文相关，数据可能还在缓存里。
thief 从 head 偷较早的任务，接近队列另一端。较早任务通常代表更大或更独立的工作单元，偷走后更容易让另一个线程持续忙一阵。
| 角色 | 操作端 | 行为 | 目的 |
|---|---|---|---|
| owner | tail | LIFO | 局部性好 |
| thief | head | FIFO 方向偷旧任务 | 降低冲突、分摊大任务 |
| 空闲线程 | 随机选 victim | steal | 负载均衡 |
五、并发实现难在哪里
工作窃取 deque 的难点在并发安全。owner 和 thief 可能同时操作同一个队列，尤其当队列只剩 1 个任务时，pop 和 steal 会竞争同一个元素。
实现通常需要锁或 CAS 来处理边界：
多个任务：两端操作冲突小
一个任务：owner pop 和 thief steal 必须只有一个成功
空队列：steal 失败所以概念上很优雅，工程实现却需要严谨的并发控制。
六、适用场景和限制
工作窃取适合任务可以拆分、任务量不均衡、任务之间依赖较少的场景。如果任务必须严格按顺序执行，或者每个任务都依赖共享锁，工作窃取收益会下降。
记忆钩子：工作窃取 deque 是“自己从一头拿，别人从另一头偷”，把本地效率和负载均衡同时照顾到。
七、常见误区与追问
- 误区：工作窃取就是所有线程抢一个队列。 典型设计是每个线程一个 deque，空闲时才偷别人的。
- 误区：双端只是为了功能更多。 两端分离是为了减少 owner 和 thief 的竞争。
- 误区：偷最新任务更好。 常见做法偷较老任务，让 owner 保留局部性，thief 拿到较大工作单元。
- 追问：什么时候偷任务最容易冲突？ 队列只剩一个任务时，owner pop 和 thief steal 需要原子协调。
- 追问：适合 IO 密集任务吗？ 不一定；它更典型用于可拆分的 CPU 并行任务，IO 场景还要看阻塞模型。
八、加强记忆
工作窃取的关键词是本地队列、双端分离、空闲偷取。owner 在一端快速处理自己的任务，thief 在另一端偷任务做负载均衡。它用 deque 不是为了炫技，而是为了减少竞争、保住局部性，同时让闲线程有活干。