基于任务的编程

  • 项目

使用任务实现可缩放的多线程编程

Ron Fosner

PC 不再追求越来越快的处理器，而是朝着越来越多的内核发展。这意味着人们能够以相对较低的成本实现潜在处理能力的巨大提高。但同时也意味着，在这些系统中进行编程以利用这种潜在的处理能力，将更具挑战性。要使用全部处理器，就必须在并行处理领域进行深入研究。

可以采用多种不同的方式将工作分散到多个内核。在 MSDN 杂志 10 月刊（msdn.microsoft.com/magazine/gg232758）中，我介绍了有关多线程编程的一些概念，并展示了利用 OpenMP 和线程池将线程式执行引入代码中的方法。同时，我还演示了如何使用 Visual Studio 2010 中的工具来测量内核和线程的利用率，将其作为衡量线程实现在改善应用程序性能方面的指标。

在本文中，我将介绍一种更为复杂的多线程技术 - 基于任务的编程。使用任务，您可以将应用程序的工作分散到可用的部分或全部 CPU 内核。通过精心编程，可以最大程度减少甚至完全消除数据依赖性或时间同步约束。

在上一篇文章的基础上，我将继续为您介绍更加复杂的、使用任务的多线程应用程序。借助任务，应用程序能够针对可用的内核数量和需要完成的工作量自行进行扩展。

迷宫中的老鼠

当我开始撰写本文时，曾试图想出一个虽然复杂到需要执行并行化，但还是能够轻松想象其运行效果的问题。我想出了这个主意：创建一个能够破解 2D 迷宫的解决方案。虽然乍看之下可能有点简单，但真正实现起来却相当有挑战性，我可是试了三次才成功的。

图 1 显示了一个正在运行中的、简单的串行迷宫求解程序。迷宫的解决方案就是一条很长的曲折路径，带有众多导向死胡同的岔路。无需诧异，我称这个求解算法为“老鼠”。老鼠会观察它当前所在的单元格，然后设法进入到下一个单元格。如果碰到了墙，就会尝试左转。如果无法左转，它会尝试右转。如果既无法左转也无法右转，它会把当前的路径标记为死胡同，然后退回去。

图 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