題幹與適用情境
請實作一個固定 N 個 worker 的調度器。公開 API 為 submit(task)、shutdown() 與 awaitTermination()。每個 worker 有自己的 deque：擁有者從本端 LIFO 取任務；閒置 worker 從其他佇列的另一端 FIFO 竊取。任務可以產生新任務，但關閉後不得接受新任務。
本題允許先用互斥鎖實作正確基線，再說明如何替換為 Chase–Lev 類型的無鎖 deque。要求不得遺失任務、不得執行兩次、任務例外不能殺死整個調度器，並處理佇列為空、沒有可偷目標、關閉競態與 worker 阻塞。
面試官在考察什麼
強回答會明確「擁有者端」和「竊取端」的並行邊界，而不是只說「使用執行緒池」。本地 LIFO 保留快取區域性和深度優先行為，遠端 FIFO 讓竊取者拿到較舊、通常較大的工作區塊。面試官還會檢查你是否把提交、停止接收、排空佇列和 worker 離開拆成狀態機，以及是否能證明每個任務只被認領一次。
回答前需要釐清的問題
- 任務是否允許阻塞 I/O？若允許，需要獨立 I/O 池或可計數的阻塞補償；增加竊取次數無法解決執行緒被占滿。
submit是否回傳 future？若回傳，需要傳遞任務例外和取消語意；本題先回傳 future，但取消只保證尚未開始的任務不會執行。- 是否要求無鎖和無界佇列？沒有的話先做加鎖 deque；只有競爭成為瓶頸且記憶體回收模型明確時才升級。
- shutdown 是立即停止還是優雅排空？本文採用優雅排空：停止接收新任務，已提交任務完成後離開。
30 秒回答框架
我為每個 worker 分配一個 deque，規定擁有者在一端以 LIFO 操作，竊取者在另一端以 FIFO 操作。先用每個 deque 的鎖建立正確基線：submit 選擇佇列並喚醒 worker，worker 先取本地任務，為空再從其他佇列竊取。任務成功移出佇列後才執行，因此不會重複認領。shutdown 進入停止接收狀態，計數歸零且所有佇列為空後離開。測試涵蓋並行 submit、竊取競態、任務產生任務、例外、關閉和無任務空轉。
逐步深入解答
先定義狀態：accepting、draining、terminated。提交在 accepting 時把任務放入負載較低的 deque，原子增加 outstanding 計數並喚醒一個 worker；draining 只允許既有任務繼續產生子任務，是否允許子任務取決於題目契約，本文允許由執行中的任務產生，但在計數歸零前保持 draining。
type Task = () => void;
class WorkStealingScheduler {
private readonly queues: Array<Deque<Task>>;
private accepting = true;
private outstanding = 0;
submit(task: Task): void {
if (!this.accepting) throw new Error("scheduler is shutting down");
const queue = this.chooseQueue();
queue.pushBottom(task);
this.outstanding += 1;
this.wakeOneWorker();
}
run(workerId: number): void {
while (true) {
const task = this.queues[workerId].popBottom()
?? this.stealFromOtherQueues(workerId);
if (!task) {
if (!this.accepting && this.outstanding === 0) return;
this.parkBriefly();
continue;
}
try { task(); } finally { this.outstanding -= 1; }
}
}
}範例把計數和 deque 操作寫成單執行緒虛擬碼；真正實作必須讓 submit、outstanding、關閉條件和喚醒機制使用同一套同步協定。為避免「檢查為空後立即有任務」的遺失喚醒，通常使用條件變數、信號量或事件計數，而不是裸 sleep。
加鎖基線的不變量是：任務只在從某個 deque 成功移除後才執行；同一時間只有一個操作能移除該任務；outstanding 等於已入佇列但尚未完成的任務數。若任務在執行中產生子任務，應先登記子任務再減少父任務計數，避免計數短暫歸零而錯誤離開。
調度公平性來自目標選擇和批量竊取策略。完全隨機可能長期偏斜，固定輪詢又可能在熱點佇列產生同步；可以記錄連續失敗次數、隨機起點和竊取批量。輕量、均勻任務適合竊取單個或小批量；遞迴產生的大任務更適合從遠端拿較大的舊任務。
無鎖升級不是預設答案。Oracle 的 ForkJoinPool 採用 work-stealing，並提供 steal count 等觀測；Chase–Lev 類型 deque 需要原子索引、記憶體序與安全回收。若沒有明確的單 owner/多 thief 假設、擴容和回收方案，手寫「無鎖」比加鎖基線更容易造成重複執行或 use-after-free。
複雜度：本地 push/pop 平均 O(1)，一次竊取為 O(1) 或 O(batch)，選擇 V 個目標的樸素掃描為 O(V)。空間為 O(T + N)，T 是未完成任務數，N 是 worker 數。阻塞 I/O 會破壞「worker 閒置即可竊取」的假設，應隔離阻塞任務或限制其並行度。
高品質示範回答
我會先交付加鎖的正確版本，再討論無鎖最佳化。每個 worker 有獨立 deque，擁有者從 bottom 做 LIFO，竊取者從 top 做 FIFO；兩個方向分別由 owner lock 和 steal lock 保護。任務只有在成功 pop/steal 後才進入執行階段，所以認領是唯一線性化點。
提交狀態和關閉狀態分開處理。shutdown 先禁止新提交，再等待 outstanding 歸零；執行中的任務產生子任務時，要麼在 draining 期間明確允許並計數，要麼直接拒絕並讓任務處理錯誤。worker 取不到任務時使用條件變數或信號量等待，避免忙等和遺失喚醒。任務例外封裝到 future/監控，不傳出 worker 主迴圈。
最後我會用並行屏障同時提交大量短任務和少量長任務，驗證每個任務恰好執行一次、確實發生竊取、佇列最終歸零。再注入任務產生子任務、worker 在 steal 時關閉、阻塞任務、例外任務和重複 shutdown。只有鎖競爭與指標證明必要時，才替換為具備明確記憶體序與回收方案的 Chase–Lev deque。
常見錯誤
- 只用一個全域佇列 → 所有 worker 在同一把鎖上排隊 → 先實作 per-worker deque，再讓竊取承擔不均衡。
- 先查看佇列非空再單獨 pop → 檢查與移除之間會發生其他 thief 的競態 → 把成功移除作為原子操作。
shutdown看到佇列暫時為空就離開 → 執行中的父任務可能立刻產生子任務 → 用 outstanding 與明確 draining 狀態判斷。- 任務例外直接逃出 worker 主迴圈 → 一個壞任務降低有效並行度 → 把例外封裝到 future 並繼續調度。
- 盲目手寫無鎖 deque → 忽略記憶體序、擴容和回收 → 先用鎖驗證語意，再按成熟演算法和測量升級。
- 使用固定單一 victim → 熱點佇列持續被爭搶 → 結合隨機起點、失敗退避和批量竊取，並以監控調整。
追問及應對
如何避免阻塞任務拖垮所有 worker？
如何證明關閉不會遺失子任務？
什麼時候批量竊取優於單任務竊取？
阻塞 I/O 應進入獨立池，或使用可計數的 managed blocking 機制補充 worker；否則竊取只能搬運等待中的任務。關閉證明依賴狀態機和計數不變量：停止新根任務、子任務登記先於父任務完成、只有 draining 且 outstanding 為零才終止。批量竊取適合任務生成密集且單任務成本較高的場景，可攤薄同步成本；任務很小或佇列很短時，批量搬運會增加快取和公平性代價。