线程池

项目
07/14/2015

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

Ron Fosner

编程的难度已经变得越来越高，如果您所从事的领域要求您对应用程序进行调整以适应可能的最高吞吐量，那么这种难度变化将尤为明显。其中一个影响因素是我们在过去几年中经历了 PC 发展方式的变化。PC 的发展如今已不再依靠单个处理器速度的不断提升，而是将 PC 计算能力分散到多个内核。这是件好事。现在人们能够以相对较低的成本实现潜在处理能力的巨大提高，同时还可以大大降低能耗和冷却需求。

但是，多核系统的日益普及也有不利的一面。要使用多个处理器，就必须在并行处理领域进行深入研究。这意味着要利用这种潜在处理能力，程序员必须付出更多工作量（有时还需要经过长时间的学习）。您可以在项目中加入一些编译器提示，让编译器为您编写部分多线程代码。但是，您仍然需要对大型作业的编程方式进行一定的更改，才能充分利用多核 PC 的全部能力。

可以采用多种不同的方式将工作分散到多个内核。其中最简单可靠的一种方式叫做基于任务的编程。使用任务，您可以取得应用程序的工作并将其分散到可用的部分或全部 CPU 内核。通过精心编程，可以最大程度减少甚至完全消除数据依赖性或时间同步约束。要达到这种理想的多核状态，您必须重新审视有关如何解决编程问题的一些成见，并从基于任务编程的角度重新进行思考。

为了展示如何实现上述目标，我会为您说明各个步骤（包括失误），介绍如何将单线程应用程序转换为能够调整为可使用计算机中所有可用 CPU 的应用程序。在本文中，我将介绍多线程编程的部分概念，并介绍一些利用 OpenMP 和线程池将线程式执行引入代码中的简单方法。此外，您还将了解到如何使用 Visual Studio 2010 测量您通过这些技术获得的性能提升。在以后的文章中，我会在此基础上为您介绍更加复杂的任务多线程执行。

从线程到任务

将程序调整至 CPU 内核数量的主要难题在于，不能仅仅将某些作业投入其各自的线程，让它们自己运行。事实上，这正是大多数人的做法，而这种做法只能实现调整至应用程序设计所针对的内核数量。如果内核数量小于或大于设计针对的数量，便无法顺利实现调整，而且该方法完全忽略了其本身产生的过时性。

要确保应用程序按不同内核数量顺利实现调整，有一种更好的方法，就是将较大的作业分解为适合线程式操作的较小的子作业，这些子作业称为任务。在将整体化单线程程序或只有少量专用线程的程序转换为基于任务的作业系统的过程中，最困难的部分就是将作业分解为任务。

在将大型单线程作业转换为多线程任务时，需要牢记下面一些指导原则：

可以将大型作业任意划分为 1 到 n 个任务。
任务应当能够按任何顺序运行。
任务应相互独立。
任务必须具有关联的上下文数据。

如果以上条件都可以轻松实现，您就可以使应用程序运行于任意数量的内核。遗憾的是，并非所有问题都能如此简单地细分为符合上述原则的任务。

上述原则的重要性在于，遵循这些原则使您能够将每个任务放在一个线程上独立运行，各个任务之间没有依赖性。理论上，任务应当能够按任何顺序运行，因此要构建基于任务的系统并使其运行，消除或减少相互依赖关系是至关重要的。

现实中，大部分程序都会经过各种不同的处理阶段，而且必须完成一个阶段，才能开始下一阶段。这些同步点通常是不可避免的，但对于基于任务的系统，目标是确保您能够充分利用任何立即可用的 CPU 能力。通过将大型作业合理地分解为较小的作业，通常可以在某些初始任务仍在运行的情况下，开始将一些已完成任务的结果与它们的下一处理阶段结合在一起。

使用 OpenMP 轻松实现多线程

在将整个应用程序转换为使用任务之前，您应当了解另外一些方法，使您无需执行将所有作业变为任务的精确过程即可获得多线程化带来的优势。在应用程序中加入多线程的方法非常多，其中许多方法几乎不需要实际工作量，但却使您可以获得将多线程加入代码所带来的好处。

OpenMP 就是在程序中加入并行处理的最简单方式之一，Visual Studio C++ 编译器已自 2005 年起对其提供支持。启用 OpenMP 的方法是在代码中添加指示要在何处添加何种并行处理的编译指令。例如，可以将并行处理添加到一个简单的 Hello World 程序中：

#include <omp.h> // You need this or it won't work
#include <stdio.h>
int main (int argc, char *argv[]) {
  #pragma omp parallel
  printf("Hello World from thread %d on processor %d\n",
    ::GetCurrentThreadfID(), 
    ::GetCurrentProcessorNumber());
  return 0;
}

OpenMP 编译指令将对下一个代码块（在本例中就是 printf）进行并行处理，然后在所有硬件线程上同时运行该代码块。线程数将取决于计算机中可用硬件线程的数量。输出是运行于每个硬件线程上的一个 printf 语句。

要使任何 OpenMP 程序实现并行处理（而不是自动忽略您的 OpenMP 编译指令），您需要为程序启用 OpenMP。首先，必须包含 /openmp 编译器选项（“属性”|“C/C++”|“语言”|“OpenMP 支持”）。然后，需要包含 omp.h 头文件。

如果您的应用程序将其大部分时间用于循环处理各种函数或数据，而您希望添加多处理器支持，OpenMP 便可以显现真正的出色之处了。例如，如果有一个需要一定执行时间的 for 循环，您可以使用 OpenMP 轻松实现该循环的并行处理。下面的示例自动分解数组计算并将其分散到当前可用数量的内核中：

#pragma omp parallel for
for (int i = 0; i < 50000; i++)
  array[i] = i * i;

OpenMP 的其他构造使您可以对以下内容进行更多控制：所创建线程的数量、分散的工作是否需要在执行下一个代码块之前完成、创建线程本地数据、同步点、关键部分，等等。

正如您所见，OpenMP 是将并行处理轻松引入现有代码库的一种简便方式。不过，尽管 OpenMP 的简便性很有吸引力，但有时您也需要对应用程序的工作进行更多控制，例如当您希望程序动态调整其工作内容时，或需要确保线程留在某个特定内核上时。OpenMP 的设计可以将多线程编程的某些部分轻松集成到程序中，但它缺乏一些高级功能，这些功能是对多个内核进行最佳利用所必需的。这时，任务和线程池就派上用场了。

使用线程池

线程需要由操作系统进行大量登记，因此不宜任意创建和销毁线程。创建和销毁线程的相关成本较高，因此如果经常进行此类操作，很容易失去通过多线程化获得的所有优势。

所以，最好的方法是根据需要对所有线程式活动循环使用一组现有的线程。这种设计称为线程池，Windows 为您提供了一个可用的线程池。使用此线程池，您可以不必应对线程的创建、构造和管理，所有这些都由线程池为您处理。OpenMP 利用一个线程池将工作分散到各个线程，Windows Vista 和 Windows 7 都提供该线程池的优化版本，您可以直接使用。

虽然创建您自己的线程池是完全可以实现的（如果有一些不寻常的计划需求，您可能需要这么做），但使用操作系统或 Microsoft .NET Framework 提供的线程池会好得多。

在这里我需要将一些术语解释清楚。在谈论线程时，大多数人指的是通过单个 CPU 内核的执行流，即软件线程。而在 CPU 中，执行流（指令的实际执行）是在硬件线程上进行的。硬件线程的数量受运行应用程序的硬件的限制。过去，这种硬件通常是单线程 CPU，但如今，至少采用双核处理器的系统已经十分常见。四核 CPU 将具备运行四个硬件线程的能力，如果是超线程 CPU，则可以运行八个硬件线程。高端桌面系统提供的硬件线程多达 16 个，某些服务器配置的硬件线程甚至超过 100 个！

硬件线程用于实际运行指令，软件线程则是指在硬件线程上实际运行作业所需的整个环境 — 寄存器值、句柄、安全属性等。需要注意的是，您的软件线程数可以比硬件线程数多得多，这是构成线程池的基础。这样您可以用软件线程对任务进行排队，然后安排它们在实际的硬件线程上执行。

与创建自己的线程相比，使用线程池的优势在于操作系统将为您管理计划任务 — 您的工作就是不断将任务送入线程池，使操作系统能够令所有硬件线程保持忙碌状态。此过程如图 1 所示。框中的所有内容组成了线程池，它们不属于程序员负责的内容。由应用程序将任务送入线程池中，这些任务在池中排入线程队列，并最终被安排在某个硬件线程上运行。

图 1 线程池

现在到了比较困难的部分：要令内核保持忙碌状态并使 CPU 利用率保持在最高水平，怎样设计作业结构最好？这取决于您的应用程序需要完成的工作。

我经常与视频游戏公司合作，这是使用难度最高的一些应用程序，因为需要完成的工作非常多（通常是一些具有特定顺序的工作），而且这些工作对于延误十分敏感。程序通常以特定的帧速率进行更新，所以如果帧速率开始下降，游戏体验就会受到影响。因此，最大程度使用硬件的动机有很多。

另一方面，如果应用程序每次执行一个大型作业，那么您需要做的事就比较显而易见了，但是尝试将一个作业分散到多个内核仍然有一定的难度。

多线程排序

首先，我们看一个应用程序中常见的整体作业，并了解如何着手将其转换为更适合多线程的形式。当然，我想到了排序。排序是个很好的例子，因为它有一个主要的问题：如何进行排序并将排序分散到多个内核，才能确保一个内核上的排序独立于另一内核上的排序内容？

一种常用的简单方法是使用 mutex、semaphore 或关键部分等工具，锁定对可由多个内核访问的任何数据的访问。这是有效的。但是，如果将这种方法用作应对共享数据访问计划不正确的万灵丹，那么在最好的情况下，您最终也将失去已通过锁定其他线程的执行获得的收益。在最坏的情况下，您可能会引致某种微妙的争用状况，而且这种状况非常难以跟踪。

幸运的是，通过选择适当的排序算法，您可以将应用程序设计为消除对这些数据的大部分跨线程共享访问。

有一种更好的方法，就是为每个内核分配数组的一个子节进行排序。这种分而治之的方法是将同一数据集上的工作分散到多个内核的简单方法。类似合并排序和快速排序的算法采用分而治之的策略，直接实现了利用多核系统的方式。

图 2 显示了合并排序如何作用于随机整数字符串，我们来看一看。第一步是选择数组的中点，将数组分为两个子列表。继续如此划分，直到获得长度为零个或一个元素的列表。

图 2 随机整数字符串的排序

在大多数实现过程中，其实都有一个列表大小限制，低于该限制时可采用一种针对小型列表设计的有效算法，但如果只是不断划分直到无法再划分为止，也是有效的。需要注意的一点是，将一个列表划分为两个子列表时，这两个子列表是独立的。这一点如图 2 中红色虚线所示。当您将列表划分为子列表时，每个子列表都是独立的，可以将每个子列表分配给一个 CPU，由其自由操作而不必锁定任何内容。

为尽可能确保排序高效，应选择能够获取每个子列表并对其进行恰当排序的算法。这一点很重要，不仅是为了避免不必要的数据复制，也是为了使 CPU 的 L2 缓存中的数据保持就绪状态。在努力编写越来越高效的并行代码的过程中，您最终必须了解进出 L2 缓存 (256KB) 的数据是如何进行交换的。

很多排序算法都适用于并行处理。快速排序、选择排序、合并排序和基数排序都是细分数据并对其进行独立操作的算法。那么，我们来看一个排序例程的串行实现，并将其转换为并行实现。

理论上，只要以递归方式不断细分数组，最终都会获得单一元素。这时没有可排序的内容了，所以算法转入下一步，即合并已排序的子列表。将各个元素合并到较大的排序列表中。随后再将这些已排序的子列表合并到更大的排序列表中，直到获得具有排序顺序的原始数组。正如前面提到的，当列表大小达到某个阈值时，切换到专门用于对小型列表进行排序的算法通常会比较快。

编写排序算法的方式很多，我选择使用 C# 编写一个简单的快速排序例程，如图 3 所示。这个程序用随机数字组成的同一序列填充一个大型数组，然后使用快速排序例程对这些数字进行排序，并报告所用时间。

图 3 快速排序

using System;
using System.Threading;
using System.Threading.Tasks;
using System.Diagnostics;

namespace ParallelSort {
  class Program {
    // For small arrays, use Insertion Sort
    private static void InsertionSort(
      int[] list, int left, int right) {

      for (int i = left; i < right; i++) {
        int temp = list[i];
        int j = i;

        while ((j > 0) && (list[j - 1] > temp)) {
          list[j] = list[j - 1];
          j = j - 1;
        }
        list[j] = temp;
      }
    }

    private static int Partition(
      int[] array, int i, int j) {

      int pivot = array[i];

      while (i < j) {
        while (array[j] >= pivot && i < j) {
          j--;
        }

        if (i < j) {
          array[i++] = array[j];
        }

        while (array[i] <= pivot && i < j) {
          i++;
        }

        if (i < j) {
          array[j--] = array[i];
        }
      }

      array[i] = pivot;
      return i;
    }

    static void QuickSort(
      int[] array, int left, int right) {


      // Single or 0 elements are already sorted
      if (left >= right)
        return;

      // For small arrays, use a faster serial routine
      if ( right-left <= 32) {
        InsertionSort(array, left, right);
        return;
      }

      // Select a pivot, then quicksort each sub-array
      int pivot = Partition(array, left, right);

      QuickSort(array, left, pivot - 1);
      QuickSort(array, pivot + 1, right);
    }

    static void Main(string[] args) {

      const int ArraySize = 50000000;

      for (int iters = 0; iters < 1; iters++) {
        int[] array;
        Stopwatch stopwatch;

        array = new int[ArraySize];
        Random random1 = new Random(5);

        for (int i = 0; i < array.Length; ++i) {
          array[i] = random1.Next();
        }

        stopwatch = Stopwatch.StartNew();
        QuickSort(array, 0, array.Length - 1);
        stopwatch.Stop();

        // Verify it is sorted
        for (int i = 1; i < array.Length; ++i) 
          if (array[i - 1] > array[i - 1]) 
            throw new ApplicationException("Sort Failed");

        Console.WriteLine("Serialt: {0} ms",  
           stopwatch.ElapsedMilliseconds);
      }
    }
  }
}

如果看一下 QuicSort 函数，您会发现它是以递归方式将数组一分为二，直到达到某个阈值，这时便不再进行细分，而开始对列表进行排序。如果将这种方式变为并行版本，您只需要更改以下两行即可：

QuickSort( array, lo, pivot - 1);
QuickSort( array, pivot + 1, hi);

以下是并行版本：

Parallel.Invoke(
  delegate { QuickSort(array, left, pivot - 1); },
  delegate { QuickSort(array, pivot + 1, right); }
);

Parallel.Invoke 接口是 .NET 任务并行库中 Systems.Threading.Tasks 命名空间的组成部分。使用该接口，您可以指定一个以异步方式运行的函数。在本例中，我通过它将每个排序函数放在单独的线程上运行。

尽管有更高效的方法（只生成一个新线程并使用现有的执行线程对其他子列表进行排序），但我希望保持对称性并说明将串行程序转换为并行程序是多么简单。

内核利用率

下一个明显的问题是：这种并行处理究竟有没有提高性能？

Visual Studio 2010 提供了几种工具，可帮助您了解程序所做的工作，及其作为多线程应用程序的表现。2009 年 9 月《MSDN 杂志》中由 Stephen Toub 和 Daniel Moth 撰写的文章“在 Visual Studio 2010 中调试基于任务的并行应用程序”(msdn.microsoft.com/magazine/ee410778) 提供了使用上述工具测量多线程应用程序性能的详尽说明，另外还有一个不错的视频说明，是 Daniel Moth 在第 9 频道中提供的 (channel9.msdn.com/posts/DanielMoth/Parallel-Tasks--new-Visual-Studio-2010-debugger-window/)。

并行编程需要进行实际测量以验证是否真的提高了性能并利用了所有硬件。为了进一步了解我的应用程序示例中是如何使用并行处理的，我们来使用这些工具测量一下应用中的排序例程。首先启动 Visual Studio 2010 性能向导，对我的排序应用程序进行运行时的并发测量。

需要查看的第一项是内核利用率，它显示应用程序如何利用可用的 CPU 周期。我的测试程序先运行串行排序，休眠一秒钟，然后运行排序的并行版本。在 4 核计算机上，我得到了图 4 所示的内核利用率图。绿色表示我的应用程序，黄色表示操作系统和其他程序，灰色表示空闲。单核级别的持平线显示我在运行串行版本时单一内核上的处理完全饱和，而运行并行版本时则使用了 4 个内核中的大约 2.25 个。不出意外，执行并行排序的时间约为串行排序所需时间的 45%。仅仅更改两行代码就获得这样的结果，算是很不错了。

图 4 内核利用率

下面，让我们从 CPU 利用率图表转到图 5 所示的线程图，它显示了应用程序如何利用可用线程。请注意，在大部分执行时间内只有一个线程。直到您开始生成任务，才创建了更多线程。在此图中，浅橙色表示已被其他线程锁定的线程。

图 5 线程工作

事实上，线程图显示出尽管我确实大大提高了执行速度，但方法并不十分高效。锁定一个线程，在主线程等待任务完成时等待其他线程，这样的方法完全没错。不过，您真正希望看到的是与 CPU 内核数量一样多的任务始终呈现绿色。因此，尽管 CPU 利用率图表显示 CPU 内核利用率已提高，但如果仔细观察任务在整个线程池中的分散方式，就会发现仍有进一步优化的空间。

事实上，每次完成多线程化工作后都应该对代码进行性能测量，即便是像我完成的示例这样简单的工作也是如此。对于小型作业，您并不需要多线程操作，因为其开销将超过任何线程操作的性能。对于较大的作业，您需要将作业分解为与可用 CPU 内核数一样多的任务以免过度使用线程池。

下一步要做什么？

要尽量利用代码实现更高的性能还有很多方法，但本文的初衷不在于此。您已经了解到如何通过对代码进行使其适合线程式操作的少量更改，获得 80% 的 CPU 利用率。但我们下面要关注的不是进一步优化该代码，而是通过稍微改变作业的架构方式使系统的 CPU 实现最高性能。

我在此展示的排序方式是专门用于多线程操作的。您可以计算出要将作业划分至什么程度，然后将每个子作业分配给一个线程。当然，在获得性能提升的同时，我也放弃了部分性能。

但在真正的应用程序中，您可能会遇到这样的情况，有许多作业为您提供多组独立任务，或是您不知道任何特定任务所需的运行时间，因此不得不基于这种不确定因素计划任务。这是一个特别棘手的问题。在下一篇文章中，我会介绍一种采用整体方法进行线程操作的体系结构，使您可以分散多个可能并不相同的作业。从开始到任务和线程池的使用，我将为您展示如何构建应用程序的体系结构以使其支持多核处理。

Ron Fosner* 从事 Windows 上高性能应用程序和游戏的优化工作已有 20 年之久，并逐渐掌握了其中的诀窍。他是 Intel 的一位图形和优化专家，当他看到所有 CPU 内核全速运行时，感到非常开心。您可以通过 Ron@directx.com 与他联系。*

衷心感谢以下技术专家对本文的审阅：Stephen Toub

线程池