為什麼單一共享佇列不夠用
上一篇建構了一個執行緒池：一組固定的工作執行緒，全都從單一一條共享的任務佇列上拉取工作項目。那個設計是正確的，也是個很好的起點。但想像有八個工作者全都伸手探進由單一一把鎖保護的同一條佇列。每當任何一個執行緒想要一個任務，它都得拿那把鎖；八個核心最後只能在同一道門前輪流。佇列的頭部變成了瓶頸，更糟的是，存放它的那條快取行在各核心之間來回彈跳——這是熱門快取行上爭用的教科書案例。你加越多核心，它們就越是爭搶同一個把手，吞吐量於是停止隨之擴展。
第一個直覺是給每個工作者一條自己私有的佇列，讓執行緒不再相撞。那漂亮地消除了爭用——卻製造出一個同樣致命的新問題。任務很少剛好分成八堆完全均等的量。某個工作者可能被交付一千個項目，另一個卻只坐擁三個。現在七個核心提早完工去睡覺，第八個卻獨自啃著它那座大山。你把一個爭用問題換成了一個負載失衡問題：閒置的執行緒緊挨著一個被淹沒的執行緒，而這正是執行緒池存在所要防止的事。
一個工作竊取排程器用一條看似簡單得令人起疑的規則化解了這個張力。保留每個工作者私有的佇列——好讓常見、無爭用的情況維持快速——但當一個工作者清空了自己的佇列，它不去睡覺，而是走向隨機選中的另一個工作者，從那個受害者佇列的遠端偷走一個任務。多數時候每個人都從自己的佇列出貨，完全不必同步；竊取只在失衡出現的那一刻發生，而且是自動發生的，沒有任何中央協調者決定誰需要幫忙。
雙端佇列：一端推入與彈出，另一端竊取
整個把戲全繫於每個工作者佇列的形狀。它不是一條普通的先進先出佇列，而是一條雙端佇列（deque），擁有扮演不同角色的兩端。擁有者執行緒把新任務推入其中一端（叫它底端），並從同一端彈出它的下一個任務——所以對擁有者而言它表現得像個堆疊，後進先出。相對地，竊賊伸手探向相反的那一端（頂端），取走那裡最老的任務。擁有者與竊賊碰觸的是相反的兩端，而這正是它為何如此便宜的幾何核心。
worker's own deque TOP BOTTOM | | v v [ t0 ][ t1 ][ t2 ][ t3 ][ t4 ][ t5 ][ t6 ] ^ ^ | | thieves steal here owner push/pop here (oldest task) (newest task, LIFO)
為什麼讓擁有者走後進先出，而竊賊走先進先出？這不是隨意的選擇——它直接源自遞迴式平行工作的行為方式。當一個任務分裂成子任務，擁有者剛剛建立的最新那個子任務，正是其資料仍在快取裡發燙的那個，因此接著彈出它能得到最好的區域性。同時，遠端那個最老的任務，通常是一大塊尚未展開的工作的根——恰恰是值得付出竊取成本的那塊肥肉。於是雙端佇列把適合各邊的東西交給各邊：溫熱、細粒度的工作給擁有者；龐大、粗粒度的工作給竊賊。
那幅圖裡藏著一個真實的微妙之處，把它揮手帶過會不誠實。當雙端佇列裡有很多任務時，擁有者與竊賊碰觸不同的端、永不相互干擾——所以那些操作完全不需要鎖，只要幾次原子讀寫。但當雙端佇列縮到只剩單一一個任務時，兩端就是同一個任務，擁有者的彈出可能會與竊賊的竊取爭搶那最後一項。正確處理這個邊界情形——通常是在共享索引上做一次比較並交換，也就是先前無鎖那一篇裡的同一個原語——就是一個真實工作竊取雙端佇列裡那整塊精細的部分。著名的 Chase–Lev 雙端佇列於 2005 年發表，是這個問題的標準答案。
一個工作者的一生：執行、竊取、沉睡
把這些零件拼起來，單一一個工作執行緒的主迴圈會變得簡單到幾乎令人不好意思。它就是你在第一篇看過的那個外層迴圈，只多焊上了一條新分支：在放棄並去睡覺之前，先試著偷。那一條分支，正是「浪費閒置核心的池」與「讓每個核心都忙到工作真正耗盡為止的池」之間的差別。
- 從你自己雙端佇列的底端彈出一個任務（後進先出，常見情況不必加鎖）。若拿到了，就執行它再迴圈。執行它可能會把新鮮的子任務推回你自己的雙端佇列——平行工作就是這樣擴散開來的。
- 若你的雙端佇列空了，就隨機挑選另一個工作者，試著從它雙端佇列的頂端偷走一個任務。隨機選擇很重要：它讓竊取的嘗試平均分散，避免一窩蜂全去突襲同一個受害者。
- 若那次竊取失敗了（受害者也空了，或某個對手竊賊搶先了你一步），就再試另一個隨機的受害者。在幾個受害者之間自旋是正常且便宜的。
- 若反覆竊取全都撲空，系統就是真的沒工作了。此時——而且只在此時——把執行緒停泊去睡覺，讓它停止空燒一個核心，等到新任務抵達時再被喚醒。
分叉合併：工作竊取為之而生的工作型態
工作竊取在分叉合併式的平行上最為耀眼，那是一種問題遞迴地分裂成獨立的子問題、答案再合併回來的型態。想想對一個百萬元素的陣列做平行加總：把它分叉成兩半，把每一半再分叉，一直切分到每塊都小到足以直接處理，然後把部分和沿著樹往上加回去。每一次分叉只是往工作者自己的雙端佇列上做一次 `push`；每個子任務執行，若仍嫌太大就再分叉下去。工作的樹隨著計算進行在雙端佇列上具現出來，不需要任何全域計畫。
現在看著負載平衡免費地發生。啟動加總的那個工作者把陣列分叉，立刻一頭栽進其中一半（後進先出——最新、最發燙的任務優先），把另一半留在它雙端佇列的底端。另一個核心上某個閒置的工作者從頂端偷走那另一半，把它分叉，再栽進去。不出幾次竊取，全部八個核心都忙在陣列互不相交的切片上，各自在本地工作，只在自己的切片耗盡時才再次竊取。沒有人計算過任何排程；失衡只是透過隨機的竊取自行排乾了。這就是 Cilk 與 Java 的 ForkJoinPool 背後那個著名的結果：在 P 個處理器上，對結構良好的分叉合併工作，工作竊取可被證明地逼近完美的 P 倍加速。
它住在哪裡，又不住在哪裡
你幾乎肯定在不知情的情況下跑過工作竊取排程器。它是 Intel TBB、Java 的 ForkJoinPool 與平行串流、.NET 的 Task Parallel Library、Apple 的 Grand Central Dispatch、Rust 的 Rayon，以及 Go 與 Tokio 裡那些非同步執行器內部的引擎。尤其在非同步執行期裡，這正是第一篇所說「執行器把任務分配到工作執行緒上」的意思——而它是M:N 排程的一種常見實作，許多輕量任務在那裡被多工到一小組固定的作業系統執行緒上。工作竊取就是那個讓那寥寥幾條作業系統執行緒在眾多任務來來去去之際維持均勻負載的機制。
不過要誠實面對它的限制，因為工作竊取並非免費的魔法。當任務彼此獨立、且大致短小，使得一個被偷來的任務能跑到完成而不阻塞時，它壓倒性地勝出。它並不自動解決一切。若你的任務呼叫了一個會阻塞的系統呼叫——一個緩慢的 read()、一次鎖的等待——那個正在竊取的執行緒就卡在那個任務裡，無法去別處幫忙，而這正是非同步那幾篇一再回頭談的別阻塞執行器危害。而若任務之間有相依（B 必須等 A），無論排程器偷得多巧妙都無法讓它們平行執行；那是你問題本身的性質，不是排程器能轉動的旋鈕。
把這個點子的形狀握住。給每個工作者一條私有的雙端佇列，讓常見情況不必同步；讓閒置的工作者從隨機選中的忙碌同儕那裡偷走最老、最肥的任務，讓負載在沒有中央計畫者的情況下自我平衡；並讓擁有者以最新優先工作以求快取的溫熱，竊賊則以最老優先取走大塊。就是這單一一個結構，讓一個執行緒池能在不規則的工作上把八個、甚至六十四個核心維持得真正繁忙。下一篇接起這一篇留著沒收的線頭——當一個任務因為正在等待某樣東西而此刻無法完成時會怎樣——那也正是期約（futures）、承諾（promises）與 async/await 登場的地方。