本文章是由機器翻譯。

.imgright1 { margin: 5px 0px 10px 10px; width:353px; font-weight: normal; font-size: 14px; color: #003399; font-family: "Segoe UI", Arial; }

.NET 很重要

平行處理作業與相依性

Stephen Toub

問:我有的系統的多個元件需要會執行,但這些元件可能相依於彼此。 我希望能夠平行地執行這些元件有可能。 我如何可以繼續關於這樣做?

這是很常見問題的軟體,開發序列或平行 A 。在一個連續的實作一般的方法是為圖形模型相依性。每個元件表示由一個節點的 Graph 中,並在要求的邊緣,共用相依性的兩個節點之間所表示的每個相依性]。這會建立內容的已知為一個要求非循環圖表 (DAG),假設有沒有循環 (例如,元件 1 相依元件 2,3 的元件而定的元件 1 回而定)。拓樸的排序可以再用來建立一個部分排序這些元件之間以便如果您執行元件依循序進行所有的元件的相依性的順序將已完成時,會執行該元件。

fig01.gif

[圖 1 A 直接非循環圖表

讓我們假設您有 8 個元件,具有下列的相依性 (我會參考到此資料行在這個範例):

  • 1、 2 和 3 的元件依存在其他任何
  • 元件 4 取決於元件 1
  • 元件 5 依存 1、 2 和 3 的元件上
  • 元件 6 3 和 4 的元件而定
  • 元件 7 5 和 6 的元件而定
  • 元件 8 取決於元件 5

這組相依性在 DAG 如 [圖 1 ] 所示。在循序的應用程式中,執行拓樸的排序,透過這個圖表,您可能有設定包括只執行它們,以遞增順序 (1,2,3,4,5,6,7,8),以滿足此處所述的相依性所發生的數個部分 orderings 的其中一個。其他 orderings 當然是可能例如 3,2,1,5,8,4,6,7。

能夠平行執行某些像這個圖形中的元件可能會產生速度有價值的增加。想像一下,只是為了的圖,每個元件會接受一秒鐘來執行,每個元件是本身的特性具有處理核心,無限數目的電腦上執行應用程式的循序] 和 [沒有零以外的執行 (沒有額外負荷) 元件所需的處理。如果是循序執行的所有元件,它會取得八秒鐘。但您可以以平行方式更好做。您可以執行元件 1、 2 和同時,3 取得一秒鐘總數。您可以再執行 4 和 5 同時,採取其他第二個。當這些完成您可以執行 6 和 8 同時,採取其他第二個。並最後,您可以執行 7,四個的秒數的總計。使用平行處理原則,您已因此縮短範例問題的執行時間的一半。

如同所提到的這種類型的問題顯示在許多不同的軟體問題的網域。請考慮,例如,MSBuild。Microsoft.NET Framework–based 專案通常會參考在相同的方案因此設定之間的兩個專案相依性的其他.NET] 專案。.NET Framework 3.5 的 MSBuild 啟動提供 / m 參數,平行處理建置 (Build) 程序在電腦中使用可用處理器利用像剛剛提到的專案參考的相依資訊。

這個資料行的其餘部分中, 我將建置小型的 DependencyManagement 類別來協助解決這類問題。以下是公用 API 的大綱:

public class DependencyManager 
{
  public void AddOperation(
    int id, Action operation, params int [] dependencies);
  public event EventHandler<OperationCompletedEventArgs> 
    OperationCompleted;
  public void Execute();
}

型別主要起點是 AddOperation 方法接受您提供給代表作業,委派,以針對該項作業執行唯一識別碼和一組其完成這項作業所需要的相依性。 如果作業沒有相依性參數陣列會是空的。

其中一個構成作業完成,提供的作業,以及啟動識別碼和終止時間執行的任何時間引發 OperationCompleted 事件。

和最後,Execute 方法會啟動關閉處理序,並等候的所有作業完成。 DependencyManager 類別將會執行作業平行,API 本身並不是執行緒安全也就是說,只有一個執行緒應該用來存取 AddOperation,並將執行一次。

這個類別可讓我 Express 前一個範例問題,下列的方式:

Action oneSecond = () => { ComputeForOneSecond(); };
DependencyManager dm = new DependencyManager();
dm.AddOperation(1, oneSecond);
dm.AddOperation(2, oneSecond);
dm.AddOperation(3, oneSecond);
dm.AddOperation(4, oneSecond, 1);
dm.AddOperation(5, oneSecond, 1, 2, 3);
dm.AddOperation(6, oneSecond, 3, 4);
dm.AddOperation(7, oneSecond, 5, 6);
dm.AddOperation(8, oneSecond, 5);
dm.Execute();

在內部,每個已註冊的作業的資訊儲存在 OperationData 類別中:

private class OperationData {
  internal int Id;
  internal Action Operation;
  internal int [] Dependencies;
  internal ExecutionContext Context;
  internal int NumRemainingDependencies;
  internal DateTimeOffset Start, End;
}

識別碼、 作業和相依性欄位會存放在對應的資料做為參數,傳入 AddOperation 方法,並將內文欄位會儲存在呼叫 AddOperation 時擷取,ExecutionContext (如需為什麼這點很重要的詳細資訊,請參閱我最後幾個.NET 很重要的資料行)。 此外,OperationData 所儲存的剩餘的相依性,需要先執行完成的號碼。 最後,它會追蹤啟動並結束時間,這項作業,以及這些會回報至 DependencyManager 的消費者,此特定的作業會引發 OperationCompleted 事件。

兩個集合用來維護一組加入至 DependencyManager 執行個體的作業:

private Dictionary<int, OperationData> _operations  =
  new Dictionary<int, OperationData>();private Dictionary<int, List<int>> _dependenciesFromTo;

先前的字典包含一個項目,為每個加入的作業,和對應的作業識別碼,到 [其 OperationData 執行個體的是,這樣就可以快速又簡單,來查詢資料的作業,指定其 ID。 雖然的第一個字典不包含的所有資訊您只需要在您的工作,它不包含該格式,讓工作簡單或有效的資訊。 後者的字典會修正這藉由提供作業的識別碼給所有的作業,直接依賴 ID 的對應。 執行個體,在稍早所示範例問題的識別碼 1 這個字典中的項目會對應到一個包含識別碼 4 和 5 中,因為兩個作業會直接依賴識別碼 1 完成清單。 這個字典變得快速而輕鬆傳送完成通知給它依賴的其他作業的完成作業。

DependencyManager 類別會包含三個的更私用欄位,除了字典:

private object _stateLock = new object();
private ManualResetEvent _doneEvent;
private int _remainingCount;

_stateLock 欄位用來非同步執行已登錄的作業期間中,保護共用的狀態,來處理這些作業也就是 「 字典 」 及 「 包含的資料的存取。 在 ManualResetEvent 是只用於做為執行方法的機制等候所有作業完成。 最後一個作業完成,將事件,允許 Execute 方法,以結束。 作業會知道的最後完成,因為它們完成時的所有作業會遞減 _remainingCount 欄位。 因此,如果發現它與值現在為零的作業會遞減,作業會知道最後一個,可以設定 _doneEvent。 (為的另外,這類的倒數計時邏輯通常位於分叉 / 聯結的平行處理問題並,.NET Framework 4.0 中的,新 CountdownEvent 使這類問題更容易實作)。

AddOperation 方法的程式碼很簡單。

public void AddOperation(
    int id, Action operation, params int[] dependencies) {
  if (operation == null) 
    throw new ArgumentNullException("operation");
  if (dependencies == null) 
    throw new ArgumentNullException("dependencies");

  var data = new OperationData {
    Context = ExecutionContext.Capture(),
    Id = id, Operation = operation, 
      Dependencies = dependencies
  };
  _operations.Add(id, data);
}

之後驗證的引數是有效、 方法,擷取的所有資料到 OperationData,類別的執行個體,及該執行個體取得儲存追蹤所有作業的字典。

之後所有的作業已經加入,您可以執行 Execute 方法,以 [圖 2 ,顯示,取得要在處理序。 在方法開頭設定執行,調換,您可以輕易地查詢作業,具有相依性目標作業指定為目標的識別碼。,每個 OperationData 中所儲存的相依性資訊,也就是相依性資訊

[圖 2] 啟動處理程序

public void Execute() {
  // TODO: verification will go here later
  // Fill dependency data structures
  _dependenciesFromTo = new Dictionary<int, List<int>>();
  foreach (var op in _operations.Values) {
    op.NumRemainingDependencies = op.Dependencies.Length;

    foreach (var from in op.Dependencies) {
      List<int> toList;
      if (!_dependenciesFromTo.TryGetValue(from, out toList)) {
        toList = new List<int>();
        _dependenciesFromTo.Add(from, toList);
      }
      toList.Add(op.Id);
    }
  }

  // Launch and wait
  _remainingCount = _operations.Count;
  using (_doneEvent = new ManualResetEvent(false)) {
    lock (_stateLock) {
      foreach (var op in _operations.Values) {
        if (op.NumRemainingDependencies == 0) 
          QueueOperation(op);
      }
    }
    _doneEvent.WaitOne();
  }
}

private void QueueOperation(OperationData data) {
  ThreadPool.UnsafeQueueUserWorkItem(state => 
    ProcessOperation((OperationData)state), data);
}

在方法,然後藉由尋找所有具有零的相依性的作業,並將這些佇列的.NET ThreadPool 執行運作的其餘部分。

先前,述的 Execute 方法,並在 AddOperation 無法彼此,相對於執行緒安全也就是說這些方法都必須依序呼叫,第一次使用 AddOperation 加入的所有作業執行時,然後呼叫的執行。 結果,請注意 AddOperation 會存取字典沒有任何鎖定或其他的共用的狀態同步處理的機制。 在一個鎖定,但是,執行不會換行部分的主體。 這是因為一次的佇列上第一個工作項目,以執行的工作項目可能會存取和修改,同時與執行本文其餘的字典。 若要防止發生這種競爭,受到保護的執行本文的其餘部分。 已加入佇列所有相關的工作時 Execute 方法就會封鎖等待完成工作。

QueueOperation 只會佇列在的 ThreadPool ProcessOperation 方法],並 ProcessOperation 會執行指定的作業。 這個方法如 [圖 3 ] 所示。 方法的第一個部份只會執行儲存在所提供的 OperationData 的委派,如此在提供的 ExecutionContext (如果有一個無法被擷取),並執行,儲存結果的時間回更新報告資料結構。 (如需詳細的時間資訊 System.Diagnostics.stopwatch 可能會使用代替 DateTimeOffset)。

[圖 3] 處理的作業

private void ProcessOperation(OperationData data) {
  // Time and run the operation's delegate
  data.Start = DateTimeOffset.Now;
  if (data.Context != null) {
    ExecutionContext.Run(data.Context.CreateCopy(), 
      op => ((OperationData)op).Operation(), data);
  }
  else data.Operation();
  data.End = DateTimeOffset.Now;


  // Raise the operation completed event
  OnOperationCompleted(data);

  // Signal to all that depend on this operation of its
  // completion, and potentially launch newly available
  lock (_stateLock) 
{
    List<int> toList;
    if (_dependenciesFromTo.TryGetValue(data.Id, out toList)) {
      foreach (var targetId in toList) {
        OperationData targetData = _operations[targetId];
        if (--targetData.NumRemainingDependencies == 0) 
          QueueOperation(targetData);
      }
    }
    _dependenciesFromTo.Remove(data.Id);


    if (--_remainingCount == 0) _doneEvent.Set();
  }
}

private void OnOperationCompleted(OperationData data) {
  var handler = OperationCompleted;
  if (handler != null)
    handler(this, new OperationCompletedEventArgs(
      data.Id, data.Start, data.End));
}

public class OperationCompletedEventArgs : EventArgs {
  internal OperationCompletedEventArgs(
    int id, DateTimeOffset start, DateTimeOffset end) {
    Id = id; Start = start; End = end;
  }
  public int Id { get; private set; }
  public DateTimeOffset Start { get; private set; }
  public DateTimeOffset End { get; private set; }
}

一旦完成作業之後,您必須通知相關的任何作業。 以下是其中 handy_dependenciesFromTo 字典派上用場。 您只要列舉的所有作業依賴這個特定的檔案、 查詢其 OperationData,執行個體並減少其 NumRemainingDependencies 一。 如果其數目剩餘 dependences 會變成零,它們現在可供執行,並用 QueueOperation 啟動每個合格的作業。

您也可以進行一些 housecleaning:,立即在作業完成您不需要其項目 in_dependenciesToFrom 再次,讓您可以將它移除。

最後,您通知,DependencyManager 其中的多個作業完成的上一個作業,可能會設定 the_doneEvent (以喚醒 Execute 方法)。

沒有例外處理會顯示這個的實作,但加入一些可能是很重要,視類別使用方式。 例如,如果 OperationCompleted 事件處理常式的其中一個擲回例外狀況的例外狀況會傳播出 OnOperationCompleted (它只會引發事件),防止被通知,並可能掉系統的這項操作的任何相依性。 取得一個強固實作,需要加以處理。

您已經知道到目前為止,表示大量的實作。 不過,仍有有些有趣的事情可以完成。 例如,實作會假設所有的其他作業的相依性已註冊的時間) 執行的作業會呼叫。 如果它們不這樣做,絕不會引發完成的相關通知,然後執行將永遠不會傳回,因為某些相依性不會已符合,並因此不會曾經執行某些作業。 為了解決這個問題,您可以實作 VerifyThatAllOperationsHaveBeenRegistered 方法,可攔截這類的濫用,並在 Execute 方法的開頭中撥打給它:

private void VerifyThatAllOperationsHaveBeenRegistered() {
  foreach (var op in _operations.Values) {
    foreach (var dependency in op.Dependencies) {
      if (!_operations.ContainsKey(dependency)) {
        throw new InvalidOperationException(
          "Missing operation: " + dependency);
      }
    }
  }
}

同樣地,您可以確認沒有實際上沒有循環在圖形中。 如果有個循環,Execute 方法會永遠不會完成,因為某些相依性會維持 unsatisfied。 例如,請想像您錯誤輸入元件 2 依賴元件 8。 這會造成循環 (5 => 2 => => 2 8),會防止元件 2、 5、 7 和 8 執行。 您可以使用方法 VerifyThereAreNoCycles,重新放置呼叫這個方法,在執行的開頭 (之後 VerifyThatAllOperationsHaveBeenRegistered),偵測到這類的週期。

有圖形中的尋找週期的數個適當的演算法。 一,是從圖形 (在的情況下本文的作業,在 [我的範例中有沒有相依性例如 1、 2 和 3 的元件) 中的每個項目] 節點中進行深度的第一個搜尋在圖形上。 一樣深度的第一個搜尋,您標示節點,當您造訪它時。 如果您造訪的已標示節點時,您已經找到週期。

另一個解決方案,根據拓樸在這個資料行的開頭所提到的排序。 如果拓樸的排序失敗,圖形就會有一個週期。 由於有拓樸的排序也是有用一般來說 (例如,如果您想要選擇性地使用 DependencyManager 循序執行),我選擇的方法。

[圖 4] 會顯示 CreateTopologicalSort 方法會傳回作業識別碼的部分排序的清單的實作。 程式 (碼也顯示 VerifyThereAreNoCycles 方法只是呼叫 CreateTopologicalSort 並如果方法傳回 null,表示排序失敗會擲回例外狀況)。 在第一個就是作業字典中轉換的排序作業的暫存的字典資料結構。 在概念字典您稍早所見,對應這些暫存的字典。 事實,dependenciesToFrom 會對應的作業識別碼,到的所有作業而定 (傳入的邊緣) 的 ID。 相較之下,dependenciesFromTo 會對應的作業識別碼,到的所有作業,依賴它 (輸出的邊緣) 的 ID。 演算法執行,您將會慢 pare 直到,這些字典的內容下希望,沒有左。

[圖 4 拓樸的排序及週期的偵測

private void VerifyThereAreNoCycles() {
  if (CreateTopologicalSort() == null) 
    throw new InvalidOperationException("Cycle detected");
}

private List<int> CreateTopologicalSort() {
  // Build up the dependencies graph
  var dependenciesToFrom = new Dictionary<int, List<int>>();
  var dependenciesFromTo = new Dictionary<int, List<int>>();
  foreach (var op in _operations.Values) {
    // Note that op.Id depends on each of op.Dependencies
    dependenciesToFrom.Add(op.Id, new List<int>(op.Dependencies));

    // Note that each of op.Dependencies is relied on by op.Id
    foreach (var depId in op.Dependencies) {
      List<int> ids;
      if (!dependenciesFromTo.TryGetValue(depId, out ids)) {
        ids = new List<int>();
        dependenciesFromTo.Add(depId, ids);
      }
      ids.Add(op.Id);
    }
  }

  // Create the sorted list
  var overallPartialOrderingIds = new List<int>(dependenciesToFrom.Count);
  var thisIterationIds = new List<int>(dependenciesToFrom.Count);
  while (dependenciesToFrom.Count > 0) {
    thisIterationIds.Clear();
    foreach (var item in dependenciesToFrom) {
      // If an item has zero input operations, remove it.
      if (item.Value.Count == 0) {
        thisIterationIds.Add(item.Key);

        // Remove all outbound edges
        List<int> depIds;
        if (dependenciesFromTo.TryGetValue(item.Key, out depIds)) {
          foreach (var depId in depIds) 
{
            dependenciesToFrom[depId].Remove(item.Key);
          }
        }
      }
    }

    // If nothing was found to remove, there's no valid sort.
    if (thisIterationIds.Count == 0) return null;

    // Remove the found items from the dictionary and 
    // add them to the overall ordering
    foreach (var id in thisIterationIds) dependenciesToFrom.Remove(id);
    overallPartialOrderingIds.AddRange(thisIterationIds);
  }

  return overallPartialOrderingIds;
}

一旦這些字典會填入,您會開始執行演算法。 其概念是您 cull 從圖形,所有具有為零的傳入的邊緣節點 — 這篇文章的內容中,,這表示對其他作業的任何相依性的作業。 當您找到這類作業時,您將它們加入至已排序的結果 (的順序在其中您加入它們至結尾不重要,因此 「 部分排序 」 的 nomenclature) 的結尾,並您將它們從圖表中移除。 您也需要移除這些您可以輕鬆地的作業上的所有輸出的邊緣使用 dependenciesFromTo 字典的尋找。 您執行此程序重複後圖形包含零的節點,在這點演算法是完成您傳回的順序建置您。 如果得到至不過,圖形包含週期,的點的所有圖形中的節點有輸入邊緣還有更多任何您可以執行。

與,實作已完成的。 向這個資料行開頭我會介紹與 DependencyManager 類別可用來執行範例問題,我已經被參考到整個程式碼。 如果將 [記住我會建議您無法取得到四個的秒數執行時間。 確實,當我在我的筆記型電腦上執行該範例程式碼,我會收到暫留的四個秒幾毫秒之內) 的時間。

這是部分幸運,但是。 假設我 postulated 的環境,包含具有無限數目核心電腦。 我的膝上型電腦不幸,會並未因此,設定,而受限於使用兩個核心。 但是,指定正確的順序,問題可以仍然執行以兩個處理器使用的四個秒為單位。 如果作業 1 和 2 開始執行,然後第二個的更新版本 3 和 4 可以開始執行,然後第二個的更新版本 5 和 6 可以啟動執行,然後第二個更新版本 7 和 8 可以啟動執行。

但是,如果 2 和 3 的作業會發生執行第一個,而非 1 和 2 的作業,會發生什麼事? 所有作業 1、 2 和 3 有沒有相依性,這是當然可以。 如果作業 2 和 3 執行第一個,然後中的下一個反覆項目 1 和 5 的作業可執行。 它們之後,4 和 8,作業將能夠進行。 但是下, 一個的反覆項目上只能操作 6 可,因為作業 7 完成的作業 6,而定,並因此整個計算才能大約 5 秒而不是四個。

在我的範例應用程式時我變更了,我 3 和 2,第一個登錄作業呼叫 AddOperation 的順序輸出時間會確認這個項問題只是超過 5 秒的執行時間。 如果身為開發人員,您有在 priori 瞭解每個作業將會花多少時間,您可以使用,以建構一個更好順序的方式啟動作業。 是為您保留的練習。

當然有其他有趣許多您可以建置這個的實作的使用做為起點。 如沒有相依性的作業可以那些能夠啟動,如同它們將它加入的 DependencyManager 至執行而不需等到執行呼叫。 您可能要能夠以非同步方式執行,DependencyManager 和更新版本會等候其的結果,或另外執行其他動作完成時。 您可能會想要能夠建置 DependencyManagers 的圖形。 您可能需要作業能夠傳回資料,以及傳遞至相依性,因此建置大型的資料流程的網路設定。 以此類推。 有許多有趣且有用的可能性。 享受 !

您提出問題或意見寄到重要的.NET 的 netqa@Microsoft.com.

Stephen Toub 將是 Microsoft Parallel Computing Platform 小組為資深專案經理負責人。 他也是主筆 MSDN Magazine 的。