Enter your search text in the box above

Select a result to preview

工作竊取與佇列爭用 (Work Stealing and Queue Contention)

#cpp-concurrency #concept #advanced-thread-management #work-stealing #thread-pool

Overview Table

概念 重點
全域佇列的爭用問題(9.1.4) 處理器越多,單一佇列爭用越嚴重;無鎖佇列也躲不掉快取乒乓 (cache ping-pong)
thread_local 本地佇列(代碼 9.6) 池內執行緒各有私有 std::queue,無爭用;非池執行緒的 submit 進全域佇列
本地佇列的缺點 任務分配不均:某執行緒本地佇列爆滿,其他執行緒閒置
工作竊取佇列(代碼 9.7) std::deque + mutex;擁有者從前端 push/pop(LIFO)、竊取者從後端 steal(FIFO)
可竊取任務的執行緒池(代碼 9.8) 取任務順序:本地 → 全域 → 竊取他人;從 my_index+1 開始輪流竊取

全域佇列的爭用問題(9.1.4)

09-Advanced-Thread-Management/01-Thread-Pools 的池只有一個全域任務佇列:每次 submit() 推任務、每個 worker 取任務,全都碰同一個佇列。

thread_local 本地任務佇列(代碼 9.6)

thread_safe_queue<function_wrapper> pool_work_queue;        // 全域佇列
typedef std::queue<function_wrapper> local_queue_type;
static thread_local std::unique_ptr<local_queue_type>
    local_work_queue;                                        // 每執行緒一份
本地佇列不需要鎖

本地佇列可以用普通 std::queue<>,因為只有擁有它的執行緒會存取,不存在競爭 —— 這正是消除爭用的關鍵。

新問題:任務分配不均

以快速排序為例:第一個資料塊進了全域佇列,但後續遞迴切出的所有子任務都堆在某一個 worker 的本地佇列,其他執行緒無事可做 —— 違背使用執行緒池的初衷。解法:工作竊取。

工作竊取佇列(代碼 9.7)

讓閒置執行緒能從其他執行緒的本地佇列竊取 (steal) 任務。本地佇列因此必須可被其他執行緒存取,需要適當同步。書中用 mutex 保護的 std::deque<function_wrapper> 證明可行性(無鎖版本超出範圍);預期竊取是少見事件,mutex 爭用因此很低。

void push(data_type data);       // 前端 push_front —— 擁有者
bool try_pop(data_type& res);    // 前端 pop_front  —— 擁有者 (LIFO)
bool try_steal(data_type& res);  // 後端 pop_back   —— 竊取者 (FIFO)

              work_stealing_queue(一個 deque,兩端操作)
              ┌───────────────────────────────────────┐
  擁有者       │ front                            back │      竊取者
  push() ────►│ [最新任務][ ...較新... ][ 最舊任務 ]   │◄──── try_steal()
  try_pop()◄──│ (LIFO:剛推入的先做)    (FIFO:拿最舊的)│────► 其他執行緒
              └───────────────────────────────────────┘

為什麼擁有者取前端、竊取者取後端?

設計 理由
擁有者 LIFO(前端) 快取親和性:最新任務的相關資料還熱在快取中;對快速排序這類遞迴演算法,先處理最新子塊可減少活動任務數量與堆疊使用
竊取者 FIFO(後端) 減少與 try_pop() 的競爭:兩者操作 deque 不同端,幾乎不相撞;搭配第 6、7 章技術甚至可讓兩者真正並發執行

使用工作竊取的完整執行緒池(代碼 9.8)

std::vector<std::unique_ptr<work_stealing_queue>> queues;   // 池持有全部本地佇列
static thread_local work_stealing_queue* local_work_queue;  // 指向自己的佇列
static thread_local unsigned my_index;                      // 自己的序號

run_pending_task()
   │ (1) pop_task_from_local_queue()        自己的本地佇列 (前端)
   │ (2) pop_task_from_pool_queue()         全域佇列
   │ (3) pop_task_from_other_thread_queue() 竊取他人佇列 (後端)
   └─ 都失敗 → std::this_thread::yield()

                    ┌──────────────────────────┐
   外部 submit ───► │  pool_work_queue(全域)   │
                    └────────────▲─────────────┘
                                 │ (2)
      Worker 0                   │                  Worker 1(閒置)
   ┌─────────────┐               │               ┌─────────────┐
   │ (1) 本地取   │───────────────┘               │ (3) 竊取     │
   └──────┬──────┘                               └──────┬──────┘
          │ front (try_pop)                             │ back (try_steal)
          ▼                                             ▼
   ┌────────────────────┐  try_steal(從 index+1 輪詢) ┌────────────────────┐
   │ queues[0] (deque)  │◄───────────────────────────│ queues[1] (deque)  │
   └────────────────────┘                             └────────────────────┘
三層取任務順序是效能設計

本地(零爭用、快取熱)→ 全域(低爭用)→ 竊取(最貴、預期少見)。順序反映成本由低到高。

這仍不是終極執行緒池

書中留下的改進方向:動態調整池大小(即使執行緒因 I/O 或互斥鎖阻塞,仍維持 CPU 最佳使用率)、每用途特化的效能調校等。

Exam/Test Patterns

情境/關鍵字 答案
「執行緒變多,單一任務佇列變慢」 佇列爭用;即使無鎖佇列仍有快取乒乓 → 本地任務佇列
「本地佇列為何可用普通 std::queue?」 只有擁有者執行緒會存取,無競爭不需鎖
「為何本地佇列用 std::unique_ptr + thread_local?」 非池內執行緒不該有本地佇列;指標空 ↔ 外部執行緒,submit 落全域佇列
「本地佇列滿、其他執行緒閒置」 任務分配不均 → 工作竊取 (work stealing)
「擁有者從哪端取?竊取者從哪端取?」 擁有者前端 (LIFO,快取親和);竊取者後端 (FIFO,減少競爭)
「run_pending_task() 的取任務順序」 本地 → 全域 → 竊取他人,失敗則 yield()
「竊取時為何從 my_index+1 開始遍歷?」 避免所有執行緒都先竊取第一條佇列,分散竊取壓力
「為什麼書中竊取佇列用 mutex 就夠?」 竊取被假設為少見事件,mutex 爭用低、實作簡單(無鎖版超出範圍)