• 發行項

本文章是由機器翻譯。

以工作為基礎的程式設計

利用工作進行可擴充的多執行緒程式設計

Ron Fosner

PC 不再追求越來越快的處理器，而是朝著越來越多的內核發展。這意味著人們能夠以相對較低的成本實現潛在處理能力的巨大提高。但同時也意味著，在這些系統中進行程式設計以利用這種潛在的處理能力，將更具挑戰性。要使用全部處理器，就必須在並行處理領域進行深入研究。

可以採用多種不同的方式將工作分散到多個內核。在 MSDN 雜誌 10 月刊（msdn.microsoft.com/magazine/gg232758）中，我介紹了有關多執行緒程式設計的一些概念，並展示了利用 OpenMP 和執行緒池將執行緒式執行引入代碼中的方法。同時，我還演示了如何使用 Visual Studio 2010 中的工具來測量內核和執行緒的利用率，將其作為衡量執行緒實現在改善應用程式性能方面的指標。

在本文中，我將介紹一種更為複雜的多執行緒技術 - 基於任務的程式設計。使用任務，您可以將應用程式的工作分散到可用的部分或全部 CPU 內核。通過精心程式設計，可以最大程度減少甚至完全消除資料依賴性或時間同步約束。

在上一篇文章的基礎上，我將繼續為您介紹更加複雜的、使用任務的多執行緒應用程式。借助任務，應用程式能夠針對可用的內核數量和需要完成的工作量自行進行擴展。

迷宮中的老鼠

當我開始撰寫本文時，曾試圖想出一個雖然複雜到需要執行並行化，但還是能夠輕鬆想像其運行效果的問題。我想出了這個主意：創建一個能夠破解 2D 迷宮的解決方案。雖然乍看之下可能有點簡單，但真正實現起來卻相當有挑戰性，我可是試了三次才成功的。

图 1 顯示了一個正在運行中的、簡單的串列迷宮求解程式。迷宮的解決方案就是一條很長的曲折路徑，帶有眾多導向死胡同的岔路。Not surprisingly, I called the solution algorithm a “mouse.” The mouse will observe its current cell and try to go forward to the next cell.如果碰到了牆，就會嘗試左轉。如果無法左轉，它會嘗試右轉。如果既無法左轉也無法右轉，它會把當前的路徑標記為死胡同，然後退回去。

图 1 单线程迷宫

當老鼠前進到一個新的儲存格，就會記錄所有還沒有走過的路徑。例如，如果老鼠能夠前進，也能夠左轉，就會記住這個儲存格和這個方向。因此，當老鼠沿著走廊前進時，會記錄兩側的出口，並將記錄推送到堆疊中。當老鼠到達一個死胡同時，就會取出其中一個位置，後退，然後朝著保存過的方向前進。最終，它會到達終點，不過這全靠毅力堅持。

當老鼠往回退時，有必要防止它嘗試已走過的路線。我的方法是：當老鼠成功進入到一個儲存格時，就將該儲存格標記為“已訪問”。因此，當老鼠嘗試向新的方向前進時，會首先查看是否有牆。如果沒有牆，就會查看該方向以前是否訪問過。老鼠會放棄進入任何已經訪問過的儲存格。如圖 1 中標記為灰色的路徑所示。

老鼠解決方案

這個解決方案非常容易想像，因此，也很容易理解搜索背後的邏輯。它看起來也有點讓人眼暈 - 至少有那麼一小會兒會讓人眼暈。图 2 顯示了串列老鼠的簡化流程圖。

图 2 老鼠行为流程图

雖然從概念上很容易理解這個問題，但還是有一些不受約束的元素讓它變得富有挑戰性。首先，您不清楚老鼠在碰到一個死胡同之前要跑多長時間。其次，您不清楚它沿路會發現多少岔路。

當您嘗試在多執行緒上運行這個解決方案時，這個問題會變得倍加有趣。讓這個問題適合多核處理的最直接方法就是使用多隻老鼠，分別給每只老鼠單獨的執行緒，這也是我採用的方法。意外的收穫就是它提高了直觀性，因為我可以在一個新執行緒取得執行權時，切換處於活動狀態的老鼠的顏色。

事實上，這比我最初設想的要難了點兒。在我有了可運行的單線程版本後，我犯了一個錯誤，就是試圖改寫這個版本，使其成為多執行緒版本。這是我在體系結構方面犯的最大錯誤。我先後進行了三次不同的修改，然後退後一步，重新設計體系結構，讓其更適合完成任務。

我不想一一陳述付出的失敗努力，只想聲明一點：所做的一切都是為了優化性能 - 不是通過複製資料，而是通過嘗試盡可能減少記憶體使用量，並優化各個執行緒對共用資料的訪問方式。從根本上來說，在我最初的設計中，我使用了一個可以鎖定的全域堆疊，然後在走過各個岔路時，將未走過的岔路的位置推送到堆疊中。當一個執行緒完成了其工作，開始尋找更多的工作進行處理時，我會鎖定堆疊（以防止其他執行緒同時訪問堆疊），彈出位置和方向，然後將堆疊解鎖。儘管這個方案在一定程度上有效，但還是過於笨拙，我不得不考慮在每只老鼠中添加新資料來記錄走過的路，以便生成一條從起點到當前位置的路。

如果您發現自己需要在多執行緒程式中添加中間狀態資訊，以補充某些起始狀態或特殊情況的處理行為，或者您發現所做的事情對於任務處理代碼在總體上不具有普遍性，就需要重新思考您的設計了。

最後，我將當前路徑資訊放到每只老鼠裡，並將其作為老鼠的初始化資訊的一部分。到達一個岔路口時，我會創建一個老鼠資料結構，並使用當前老鼠的資訊將其初始化 - 也就是說，創建一隻克隆鼠，假如原來的老鼠向右轉，那麼這只克隆鼠就向左轉。克隆鼠包含原始鼠的記憶。每只老鼠的唯一不同之處就是計數器，該計數器記錄創建的老鼠的數量，以便老鼠能分配到一種顏色。

我也曾經改變想法，製作了一個全域的迷宮副本，其中包含各個儲存格的狀態資訊，並且在編寫狀態資訊時，不 放任何鎖。權衡利弊，我採用了一種簡單的方案 - 每只老鼠將獨自在一條路徑上工作。在進入儲存格之前，它會先查看該儲存格是否標記為“已訪問”。

因為在全域儲存格資料中沒有任何鎖，所以會有這種可能（儘管可能性不大）：兩只老鼠同時在一條路上前進。如果出現重複的堆疊項或者環形的路徑，兩只老鼠就會相遇，從而出現這種可能性。無論在哪種情況下，老鼠都可能會繼續沿路徑跑下去，它的執行緒可能會掛起，當執行緒恢復時，老鼠會發現其他老鼠已經走過了該路徑。在這種情況下，老鼠會當做碰到牆而返回，因為走過這條路的老鼠正在成功沿著一條路徑前進。掛起的老鼠錯過了機會，並做了一些無用功。

如果在標記儲存格時執行了大量處理，那麼我更不願意接受的事實就是可能做了一些無用功。取消共用資料中的鎖意味著我不得不讓演算法變得更強大一些。設計演算法來處理這種情況意味著更不允許犯錯。在多執行緒程式中，最可能出錯的原因通常涉及某種形式的鎖定錯誤，例如爭用問題或者對資料或計數器何時更新做出假設。

如果您的演算法足夠強大，即使資料稍微過時也能處理，還能夠從上述情況中恢復過來，那麼您構建的多執行緒體系結構將具備足夠的彈性。

任務佇列和依賴關係

Windows Vista 引入了新的調度演算法和新的基元，為許多 Microsoft .NET Framework 4 功能提供了底層支援。其中一項功能就是任務並行庫 (TPL)，該功能提供了許多更通用的並行程式設計演算法，包括分叉/彙集、並行 for、工作竊取和任務內聯。如果您使用非託管 C++ 編寫代碼，可以利用 Intel 執行緒構建塊 (TBB) 或 Microsoft 並行模式庫 (PPL)。

這些庫附帶的類可以為作業和任務提供多執行緒程式設計支援。它們還包含很多執行緒安全的容器類。這些類已經過測試並針對性能進行了優化。因此，除非您出於某種原因而強烈需要編寫自訂的變體，否則最好還是使用經過測試的可靠代碼。

由於本文是一篇關於執行緒和任務的介紹性文章，對這些執行緒庫的工作原理有所瞭解可能會使您從中受益，因此我就 Windows Vista 中的兩項新功能編寫了自己的一套包裝程式：ThreadPool 和 SlimReaderWriterLock (SRWLock)。如果您有一個寫入器和多個讀取器，並且資料通常不會長時間鎖定，則上述兩個包裝程式都是保持資料執行緒安全的低成本方法。請注意，本文的目的是讓您逐步瞭解我怎樣選擇實現一個使用任務（可以有依賴關係的任務）的執行緒池。為了說明基本的機制，我對代碼進行了一些修改，以便於理解。儘管此代碼可以正常運行，但在實際實現中，您最好還是從執行緒庫中選擇現成的代碼。

對於我的迷宮演算法，我選擇使用最通用的多執行緒演算法：可具備依賴關係的任務（使用 SRWLock 實現）和任務計畫程式（使用作業系統的 ThreadPool）。這是最通用的演算法，因為任務基本上就是某種需要完成的工作，而任務計畫程式則負責與作業系統通信，確保任務線上程上運行。它們之所以通用，是因為可使用任何需要執行的代碼創建任務，然後將其置於 ThreadPool 中。

問題是怎樣創建任務，使得其完成時間能夠超過用在任務安排上的開銷。如果您有一些大型整體任務需要執行，可以隨意創建一些執行緒，在上面執行代碼。而另一方面，在許多應用中有多組任務需要完成，其中一些是串列任務，另一些不是。有時候，您會預先知道需要完成的工作量；而另一些時候，特別是在獲取或回應使用者輸入或通信時，您只是在對某些偶爾需要進一步處理的物件進行輪詢。ThreadPool 及其關聯任務佇列的通用性就可以輕鬆解決此問題。

自訂 ThreadPool

為了讓您清楚瞭解如何基於 ThreadPool 構建任務系統，我只需要使用 ThreadPool 的三個介面：

CreateThreadpool();
CloseThreadpool();
TrySubmitThreadpoolCallback();

前兩個只是記帳函數。 TrySubmitThreadpoolCallback 主要接受一個指標（指向要執行的函數）和一些上下文變數。 您反復調用此函數，線上程池中裝載要執行的任務，隨後執行緒池會採用先入先出 (FIFO) 的方式為任務服務（此時無法保證能夠實現此效果）。

為了讓它適用于我的任務，我針對 ThreadPool 編寫了一個簡短的包裝程式，用於自訂執行緒池中的執行緒數（請參見圖 3）。 我還編寫了一個 submit 函數，用來跟蹤與任務關聯的上下文變數。

圖 3 ThreadPool 包裝程式

class ThreadPool {
  PTP_POOL m_Pool;
public:
  static VOID CALLBACK WorkCallback(
    PTP_CALLBACK_INSTANCE instance,
    void* Context);
  ThreadPool(void);
  ~ThreadPool(void);
  
  static unsigned GetHardwareThreadsCount();

  // create thread pool that has optimal 
  // number of threads for current hardware
  bool create() { 
    DWORD tc = GetHardwareThreadsCount(); 
    return create(tc,tc); 
  }
  bool create(
    unsigned int minThreads, 
    unsigned int maxThreads = 0);
  void release();
  bool submit(ITask* pWork);
};

有趣的是，您通常只需要創建與硬體執行緒數一樣多的軟體執行緒。 有時候，如果您讓某個主執行緒停止執行其他任務，則軟體執行緒數可能會比硬體執行緒數少一個。 請注意，您創建的執行緒數與任務佇列的大小沒有關系，您完全可以創建一個包含四個執行緒的 ThreadPool，然後提交幾百個任務。 但是，採用單個串列作業並將其分成幾千個任務，這可能不是一個好主意。 這表明您的任務分得過細了。 如果您發現存在這種情況，只需創建一個任務來安排接下來的 100 個任務。如果您使用的是某種任務庫，則可以創建一個工作竊取、內聯或後續任務。

我的 Task 類（請注意大寫的 T，如圖 4 所示，用來表示我的任務包裝程式類）的功能依賴于其他 Task。 因為作業系統的 ThreadPool 不具備此功能，所以我需要添加此功能。 因此，當 Task 開始線上程上執行時，首先就是確保自己沒有未解決的依賴關係。 如果有，則執行任務的執行緒將被阻止，在 SRWLock 上等待。 當 SRWLock 被釋放時，Task 只會被重新安排。

圖 4 Task 包裝程式

class ITask {
protected:
  vector<ITask*>    m_dependentsList;      // Those waiting for me
  ThreadSafe_Int32  m_dependencysRemaining;// Those I'm waiting for

  // The blocking event if we have dependencies waiting on
  SRWLOCK m_SRWLock; 
  CONDITION_VARIABLE m_Dependencies;

  void SignalDependentsImDone();
  ITask(); 
  virtual ~ITask();

public:  
  void blockIfDependenciesArePending();
  void isDependentUpon(ITask* pTask);

  unsigned int queryNumberDependentsRemaining()

  // A parent Task will call this
  void clearOneDependency();
  virtual void doWork(void*) = 0;
  virtual void* context() = 0;
};

同樣，我想說的是，這段代碼不是我想在非實驗性應用程式中看到的代碼，將這個塊放到這裡，只是為了讓您看看到底發生了什麼。作業系統會注意到這次阻止，然後安排另一個 Task。最後，除非存在程式設計錯誤，否則被阻止的任務將會解除鎖定，然後被重新安排運行。

一般來說，安排一個馬上就要被掛起的 Task 不是好主意。因為總的來說，ThreadPool 的任務佇列是先入先出的，您需要首先安排沒有依賴關係的任務。我寫的這段代碼是為了給大家做演示，否則，如果為了獲得最佳性能，我會增加一個層，只將沒有依賴關係的任務提交到執行緒池。我可以這樣結束，因為被阻止的執行緒最終會被置換出。在任何情況下，您都會需要通過執行緒安全的方式來通知任務已經完成，而 SRWLock 就可以在這種情況下使用。將其合併到我的 Task 類中很自然，這樣就不用編寫專門的代碼來處理每種情況。

按照設計，Task 可以有任意數量的 Task 依賴關係。通常，您想要儘量減少或完全避免等待，使用 Visual Studio 任務清單或 Intel Graphics Performance Analyzers 這樣的工具可以説明您實現這個目的。我在這裡展示的實現方案是一個非常基本的任務系統，不應當將其用於需要高性能的代碼中。它是一個很好的沙箱代碼，可説明您嘗試一下多執行緒程式，但您應當通過 TBB、TPL 或 PPL 來獲得更為有效的代碼。

ThreadPool 會調用 WorkCallback 函數來執行一些首碼代碼，以便查詢 Task 資料結構，就像這樣：

VOID CALLBACK ThreadPool::WorkCallback(
  PTP_CALLBACK_INSTANCE instance, void* pTask) {

  ITask * pCurrentTask = (ITask*) pTask;
  pCurrentTask->blockIfDependenciesArePending( );
  pCurrentTask->doWork(pCurrentTask->context() );
  pCurrentTask->SignalDependentsImDone();
}

基本的操作為：

  1. ThreadPool 從其內部任務佇列載入 WorkCallback。
  2. 代碼查詢 Task，查看是否存在任何依賴關係（父依賴關係）。如果找到了依賴關係，則阻止其執行。
  3. 如果不再有任何依賴關係，則調用 doWork。doWork 是 Task 代碼的實際組成部分，對於每個 Task 都是唯一的。
  4. 從 doWork 返回時，清除此 Task 上存在的任何子依賴關係。

有一點需要特別注意，我的 ThreadPool 類中有一些前導和後續代碼，用於檢查和清除 Task 中的依賴關係。此代碼在每個執行緒上運行，但是只有一個唯一的 Task 與其相關聯。一旦前導代碼開始運行，實際的 Task 工作函數就會被調用。

創建自訂 Task 類包裝程式

任務的基本工作是提供一些上下文和一個函數指標，讓執行緒池執行任務。因為我想要創建能夠具有依賴關係的 Task，我需要一些代碼來處理跟蹤阻止的記帳，以及對依賴關係的解鎖（請參見圖 4）。

創建完 Task 後，您可以提供指向其依賴的 Task 的指標，指定其依賴于其他任務。Task 包含一個計數器，記錄它要等待的 Task 的數量，還包含一個指向要等待它的 Task 的指標陣列。

如果 Task 沒有任何依賴關係，就會調用其工作函數。工作函數返回後，會遍歷陣列中的所有 Task 指標，調用每個類的 clearOneDependency，該函數用於遞減該 Task 的剩餘依賴關係數。當依賴關係的數量降到零時，會釋放 SRWLock，解鎖用來執行需要等待這些依賴關係的任務的執行緒。運行任務的執行緒將解鎖，並繼續執行下去。

以上是我如何設計 Task 和 ThreadPool 類的基本概述。我最終採用這種設計，是因為作業系統的本機執行緒池並不具備這樣的行為，而我想為您提供一些代碼，説明您嘗試控制一下依賴關係機制。對於 ThreadPool，我最初有一個複雜得多的包裝程式，其中包含一個優先順序佇列。但後來我意識到沒有必要將事情複雜化，一個簡單的父子依賴關係就足夠了。如果您真的想要瞭解如何自訂執行緒計畫程式，可以參考 Joe Duffy 的文章“構建自訂執行緒池（第 2 部分）：工作竊取佇列”，位址為 tinyurl.com/36k4jcy。

我傾向于編寫更保守的代碼。我傾向于編寫簡單而有效的實現，然後在此過程中反復檢查以重構和增加功能，確保我沒有犯任何錯誤。遺憾的是，我還喜歡編寫將引用傳遞給其他變數的代碼 - 如果您不夠細心，這對於多執行緒程式來說可是個壞習慣。

在將我的單線程迷宮解決方案代碼轉換為多執行緒解決方案代碼時，我曾經不止一次地撤銷操作。最後，我不得不重新過一遍，以便確保如果值有可能線上程中被修改，我會將資料的副本傳遞出去。

我還嘗試過更為保守的方式，以單線程的版本開始，其中只保留了當前老鼠的路徑。然而，這帶來的問題就是無法跟蹤更多的狀態資料。正如前文所述，我通過克隆老鼠，讓它們具備原始鼠的所有資料來解決這個問題。我還選擇不使用區分優先順序的 ThreadPool 包裝程式，也不對全域迷宮儲存格資料使用鎖。我很可能引入了一些額外的工作，但由於大大簡化了代碼，因此也避免了很多錯誤的發生。

ThreadPool 包裝程式和 Task 類的運行完全符合設計。我在一些單元測試中使用了這些類，確保它們能展現我預期的行為。我還使用 Intel Graphics Performance Analyzers 任務工具對這些類進行了檢測，該工具提供了一項功能，可以讓您動態標記執行緒並檢查哪些程式碼片段正在某個特定執行緒上執行。執行緒的執行也由此變得直觀，我可以驗證執行緒是否如預期的那樣執行、阻止或重新安排。

在我將老鼠改為原始鼠的克隆後，就大大簡化了類比所需的記帳工作，因為每只老鼠都是獨立的。我唯一需要的共用資料就是全域儲存格陣列，該陣列指示了儲存格是否被訪問過。能夠直觀瞭解您的任務是如何安排的，這一點的重要性怎麼強調都不為過。

老鼠池

我選擇迷宮難題是因為它能展現將單線程演算法轉換為多執行緒演算法時出現的問題。最讓我驚奇的是，當我硬著頭皮重寫演算法，來減少之前試圖保留的某些記帳工作時，迷宮求解演算法突然就變得簡單多了。事實上，它變得比單線程演算法還簡單，因為沒必要保留關於岔路的堆疊，這些資訊會衍生到新老鼠中。

按照設計，每只老鼠都是原始鼠的克隆，因此每只老鼠都會繼承路徑資訊，可以回溯到它的衍生點。老鼠不知道這一點，但是我故意將迷宮生成演算法設計為選擇盡可能遠的路徑。讓老鼠感覺輕鬆沒什麼意義。測試程式可以讓我們在多種迷宮生成演算法中進行選擇，從原始的演算法（很長的走廊，偶爾有最終導向死胡同的岔路），一直到有很多岔路、走廊很短的演算法。展現了這麼多不同的迷宮，您可以發現從單線程解決方案到多執行緒解決方案，行為方式的差異可以有多大。

當我應用多執行緒方法來解決原始的迷宮演算法時，我通過使用包含 4 個 CPU 的系統，將搜索時間縮短了 48%。這是因為該演算法包含很多長走廊，因而沒有很多機會來衍生額外的克隆鼠（請參見圖 5）。

圖 5 解決原始的長迷宮演算法

图 6 顯示的迷宮包含更多岔路。現在，就有更多機會來衍生克隆鼠，讓它們同時搜索。图 6 顯示了針對此短路徑迷宮的多執行緒解決方案。在這個解決方案中，我通過使用更多工，將所用時間減少了 95%。

圖 6 多隻老鼠在更短的時間內解決了迷宮難題

這正好說明某些問題比其他問題更容易分解。我認為有必要指出：迷宮程式看起來很有趣，也就是說，你可以看到老鼠是怎樣一步一步前進的。如果我只是想在最短的時間內找到迷宮的解決方案，就會分開討論老鼠及其呈現方式，但這樣就不那麼有趣了。

後續話題

當我説明別人提高應用程式的運行速度時，看到的最大問題就是不願意嘗試多執行緒。我理解這種情緒。在您添加多執行緒時，會突然增加一層複雜性，而大多數程式師不習慣在陌生的領域中工作。

遺憾的是，如果您回避使用多執行緒，就放棄了相當一部分未利用的計算能力。

我已經介紹過任務系統的基本工作原理，以及如何將大的作業分成任務的基本知識。然而，當前的方法雖好，卻不是發揮當今和未來多核硬體最大性能的最佳途徑。如果有興趣提高您的應用程式在其可能會使用的硬體上的性能，則需要在構建應用程式時牢記這一點。

在應用程式中實現最大的可擴展性能的最好方法，就是利用某種現有的並行庫，並尋找如何利用這些庫提供的各種體系結構來滿足您的應用程式需求的最佳方法。使用 TBB 提供的某個介面通常可以最好地滿足非託管即時應用程式或性能關鍵性應用程式的需求，但是 .NET Framework 4 為託管的應用程式提供了更為廣泛的多執行緒選擇。無論在哪種情況下，選擇一種執行緒化 API 將決定您的應用程式的整體結構，以及您設計任務的工作和共存的方法。

在以後的文章中，我將介紹利用這些技術的實際實現案例，並展示如何圍繞這些執行緒庫構建應用程式，這樣您就可以設計自己的實現來使用這些技術。

無論如何，您已經瞭解基本知識，可以嘗試一些基本的執行緒方法，但是還應當瞭解一下執行緒庫，開始思索設計未來應用程式的最佳方法。儘管多執行緒可能極具挑戰性，要想充分發揮當今和未來硬體的最大性能，還是應該使用這些可擴展的庫。

Ron Fosner 從事 Windows 上高性能應用程式和遊戲的優化工作已有多年，並逐漸掌握了其中的訣竅。.他是 Intel 的一點陣圖形和優化專家，當他看到所有 CPU 內核全速運行時，感到非常開心。您可以通過 Ron@directx.com 與他聯繫。

衷心感謝以下技術專家對本文的審閱：Aaron Coday、Orion Granatir 和 Brad Werth