利用并发操作实现可伸缩性（中）

admin

了解成本
        线程不是免费的午餐。它们会产生 CPU及内存成本，这一点您应铭记在心。如果您的目标是利用并发操作来提高算法的可伸缩性，大概您还要花费同样多（甚至更多）的时间来进行传统的性能剖析工作。并行运行结构松散的算法不会产生任何结果，只会使其用尽更多的系统资源。要充分利用并行伸缩性，确保代码最重要的热数据部分在序列情况下尽可能高效是至关重要的。
        要确定您可以承担的成本，有一些通用的经验法则可以遵循。创建一个 Windows 线程的成本约为 200,000 个周期，而终止一个 Windows 线程的成本约为 100,000 个周期。那么，此时您知道了如果要创建一个新线程以执行 100,000 个周期的工作，将要付出巨大的额外开销，而且，如果我必须猜测的话，您也不会观察到任何类型的加速。
        内存额外开销因配置而异。但多数受管理线程将保留 1MB 的用户堆栈空间并将调拨全部数量的空间，这意味着必须在实际 RAM 或页面文件中物理备份内存中的数据。还需要一个小型的内核堆栈页面集，在 32 位系统上为三页，在 64 位系统上为六页。其他数据结构使用另外的 10-20KB 虚拟内存，但相对于堆栈所需的内存而言，这是微不足道的。GUI线程的成本还要略高一些，因为它们必须建立额外的数据结构，如消息队列。
        现在，如果您最终创建过多的优先级相等的线程，则必须经常进行上下文切换。进行一次上下文切换的成本是 2,000–8,000 个周期（具体视系统负荷和体系结构而定），其中还要涉及保存当前易失状态、选择要运行的下一线程以及恢复下一线程的易失状态。这听起来好像没有花费太多成本，尤其与时间片的持续时间和随后高速缓存缺失的成本相比更是如此，但它表示从应用程序代码执行过程中减去的纯额外开销。
        假定您要使引入和终止新OS 线程的成本以及意外引入“过多”工作而产生的负面后果降至最低，则应考虑使用CLR 的线程池。它将智能化线程注入和引退算法隐藏在一个简单接口之下，在整个程序生命周期内分摊创建和终止线程的成本。使用 ThreadPool 类很简单。
        尽管如此，使用 ThreadPool 仍要花费一些成本。调用 QueueUserWorkItem 会对调用方产生连续成本，并且从待处理工作项目队列中分派工作的基础设施也会为正在执行的并行工作带来额外开销。对于大粒度的并行性，这些成本微不足道，以至于您可能不会注意到它们。但对于粒度极其精细的并行性，这些成本可能会成为明显的可伸缩性瓶颈。您可能会考虑从无锁数据结构构建自己的轻型 ThreadPool，以避免由一般用途的 ThreadPool 导致的一些成本，如确保 AppDomains 间的公平性、捕捉和恢复安全性信息等等。但对多数使用情况来说，可在任务中使用普通的 ThreadPool。
定义界限
        确定如何拆分工作并不是一项无足轻重的活动。当处理受 CPU 限制的工作负荷时，该工作更多集中于避免产生与并发执行相关的性能开销。但多数工作负荷不受 CPU 限制，它们结合了各种形式的 I/O 以及 CPU 工作间的同步，其中任意一项都可能导致不可预测的阻塞模式。因此，对于多数代码，与其说并发执行与低级性能相关，还不如说它涉及的是如何巧妙安排复杂的协调模式。
        也许分割工作的最简单方法是使用并发操作的服务器模型。在 SQL Server™ 或 ASP.NET 之类的服务器中，每个外来请求都被视为一个独立任务并因此在其自己的线程上运行。宿主软件通常会限制使用的实际 OS 线程数，以免过多引入并发操作。多数此类工作负荷都由访问数据和资源的不相交集的完全独立的任务组成，从而产生高效率的并行加速。但对于客户端程序，很少有工作负荷会完全适合该模型。例如，可通过该模型完成对等通信的区段划分和响应，但除非预期有大量工作密集型的外来请求，否则此时可能达到的加速上限将受到很大限制。
        另一个备选方法是使用更具逻辑性、更主观的“重要任务”定义在代码中划分出任意子任务，这往往更有利于客户端工作负荷。一次复杂的软件运算通常包含多个逻辑步骤，例如，这些步骤可能在程序中表示为独立的函数调用，而这些函数调用自身又包含多个步骤，以此类推。您可考虑将各函数调用表示为一个独立任务，至少对于那些足够重要的函数调用是如此。从必须考虑排序从属性的意义上来讲，这相当棘手，因为这为此想法增添了很多复杂性。多数现代命令式程序充满了无组织的循环、通过不透明指针进行的数据访问（这些不透明指针在内存中可能不紧靠一起）以及各种函数调用（其中没有任何函数能够清楚说明存在哪些从属性）。当然，还有您可能不知道的隐藏的线程相似性。因此该技术显然需要您深入了解您的代码试图解决的问题，并产生关于并行执行代码的最有效方式的一些思路，从而消除尽可能多的从属性。
        一种常见的相关模式是派生/联结式并行性，其中一个主任务派生出多个子任务（这些子任务自身也可派生出子任务），接着每个主任务在一些定义明确的点与自己的子任务联结。例如，假定有一个称为派生/联结式 future 的任务级并行性模型，它作为任务单元基于函数调用来封装此模式。这可通过一些新类型 Future <T> 加以说明（可从 MSDN?Magazine 网站下载 Future <T> 的实现代码）：

1. int a() { /* 一些工作 */ }
   
2. int b() { /* 一些工作 */ }
   
3. int c()
   
4. {
   
5.     Future<int> fa = a();
   
6.     Future<int> fb = b();
   
7.     // 做一些工作
   
8.     return fa.Value + fb.Value;
   
9. }
   

复制代码

       该代码的含义是 a 和 b 的调用可随 c 的主体并行执行，对此的决策由 Future<int> 引擎的实现来做出。当 c 需要这些调用的结果时，它会访问 future 的 Value 属性。这所产生的结果是：等待工作完成；或者，如果工作还未开始异步执行，则在调用线程上本地执行函数。该语法与现有 IAsyncResult 类很相似，但多出了一个优点，就是在有关将多少并发操作引入程序方面更加智能化。尽管很容易就可以设想出更多智能化的实现方法，但此代码的直接译文可能如下所示：

1. int a() { /* 一些工作 */ }
   
2. int b() { /* 一些工作 */ }
   
3. delegate int Del();
   
4. int c()
   
5. {
   
6.     Del da = a; IAsyncResult fa = da.BeginInvoke(null, null);
   
7.     Del db = b; IAsyncResult fb = db.BeginInvoke(null, null);
   
8.     // 做一些工作
   
9.     return da.EndInvoke(fa) + db.EndInvoke(fb);
   
10. }
    

复制代码

       还可以采用其他方法，如使用运行时间更长的子任务，而不是要求子任务的生命周期绝不能超过父任务。这通常需要更复杂的同步和会合模式。派生/联结模式很简单，因为单个工作单元的生命周期显而易见。
        以上围绕代码对并行性进行了讨论。另一项技术通常更简单：数据并行性。该项技术通常适用于数据和计算密集型的问题和数据结构，或其各运算往往要频繁访问不相交数据的问题和数据结构。
        一种常见的数据并行性技术称为分区。例如，基于循环的并行性使用此方法将计算分布于一系列元素。假定您有 16 个逻辑 CPU、一个包含 100,000 个元素的数组和一段以微乎其微的从属性执行并往往阻塞 20% 的时间的工作。您可以将数组分割为各有 5,000 个元素的 20 个连续块（稍后我将说明如何计算出该数字），派生出 19 个线程（重复使用一个分区的当前线程），并安排各线程并行执行各自的计算。数据库（如 SQL Server）中的并行查询处理使用的是类似方法。此技术在图 2 中进行说明。

图 2 基于分区的并行性

        该例显示了一个分布于四个线程上的由 100,000 个元素组成的数组。您会留意到，为进行数组分割连续支付了一定的额外开销。在需要合并时，经常要为合并结果支付附加成本，包括连接待处理线程。
        For-all 循环通常是以编程语言表示基于分区的并行性的一种传统方式。图 3 中显示了 ForAll<T> API 实现的示例。也可使用类似方法将循环并行化 — 例如，可以不采用 IList<T>，而改为采用 int from 和 int to 参数集，然后将循环迭代数馈入 Action<int> 委托。
        此代码做出了一个可能具有灾难性的重大假定：预期传入的 Action<T> 委托会安全地并行执行。这意味着如果它指的是共享状态，则需要使用适当的同步来消除并发操作程序错误。如果不是，则可以预期我们程序的正确性和可靠性都相当差。
        另一个数据并行性技术是管道操作，其中多个运算并行执行，使用一个快速的共享缓冲区来相互输送数据。这类似于装配线，其中流程中的每个步骤都有机会与一些数据交互，然后将其传递给装配线中的下一步骤。此技术需要巧妙的同步代码以尽量缩短花费在明显瓶颈处的时间：在瓶颈处，管道中的相邻阶段通过一个共享缓冲区进行通信。
多少任务？
        选择要创建的任务数也是一个棘手的因素。如果吞吐量是唯一的优先考虑因素，则可以使用如下所示的一些理论目标，其中 BP 是任务将阻塞的时间百分比：

1. NumThreads = NumCPUs / (1 &ndash; BP)
   

复制代码

       也就是说，线程数最好等于 CPU 数与任务要花费在实际工作上的时间百分比的比率。这已在先前的 ForAll 示例中进行了说明。可惜的是，尽管理论上这是一个良好起点，但它不会带给您准确的答案。例如，它没有解释采用 HT 的原因（其中高内存滞后时间允许引发并行计算），但在其他方面它不应该是使用完整处理器的原因。而且它相当天真地假定您实际可以预测 BP 值，这一点我可以保证是相当困难的，特别是对于试图调度异类工作的组件，这非常像 CLR 的线程池。如果有疑虑，最好依靠线程池将任务调度给 OS 线程，并倾向于过度表示并发操作。
        任何算法都有一个自带的加速曲线。关于这条曲线，有两点特别重要的问题要考虑。首先，可从计算并行化获益的最少任务数是多少？对于小型计算，情况可能会是这样：使用少量任务会导致过多的额外开销（线程创建和高速缓存缺失），但使用大量任务会使执行进度赶上相继的版本并超过它。其次，假定硬件线程的数量无穷大，则在开始发现性能下降而不是持续上升之前可以分配给某问题的最多任务数是多少？所有问题都会达到这一递减返回点。随着继续细分问题，最终将达到单个指令的粒度。
        线性加速意味着使用 p 个处理器执行问题花费的时间是使用一个处理器执行问题所花费时间的 1/p。Amdahl 定律往往限制了实现这种加速的能力。它相当简单地指出最大加速受到采用并行性后保持的序列执行量的限制。更正式地说，此定律指出，如果 S 是必须保持有序的问题（无法并行化）的百分比，p 是所使用 CPU 的数量，则预期的近似加速可如下表示：

1. 1/(S + ((1 &ndash; S)/p))
   

复制代码

       随着处理器数量的增加，此表达式接近于 1/S。因此，如果只能并行化问题的（例如）85%，则只能达到 1/.85（大约 6.6）的加速。与同步化和采用并发操作相关的任何额外开销往往都成为 S 的一个因素。但是，在现实中还是有一个好消息：在多个处理器之间分配工作也具备难以量化和测度的好处，例如，使并发线程可以保持其（各自的）高速缓存随时可用。
        任何管理实际资源的算法还必须考虑跨计算机使用情况。完全进行本地决策以最大化并行性的软件（特别是在 ASP.NET 之类的服务器环境中）可能会（并且总会！）导致混乱并增加对资源（包括 CPU）的争用。例如，ForAll 式循环在动态决定最佳任务数之前可能会查询处理器使用情况。可考虑使用图4 中所示的 GetFreeProcessors 函数，而取代图3 中使用的依赖于 System.Environment.ProcessorCount 属性的算法。
        该算法并非十全十美。它只是在其运行时的计算机状态的一个统计快照，而并未表明在其返回结果之后出现的任何情况。它可能过度乐观或过度悲观。并且它当然不会解释这样的事实，被查询的某一处理器就是执行 GetFreeProcessors 函数的处理器本身，这会是一项有帮助的改进。另一个要考虑的值得关注的统计度量标准是系统处理器队列长度性能计数器，它可以告诉您在调度队列中有多少线程正在等待空闲处理器。如果结果是一个很大的数字，则表示引入的新工作只能等待队列清空（假定所有线程都具有同等优先级）。
        存在一些重要理由来创建过多而不是过少的并发操作。如果正在考虑异类任务，则让每个任务在某一线程上一直执行到完成的模型会带来公平性问题。如果不释放另外的资源，则运行时间远多于任务 B 的任务 A 会导致任务 B 资源缺乏。如果 A 决定阻塞而您的算法没有考虑到这一点，则这种情况会更加糟糕。
        有意过度并行化的另一个原因是针对异步 I/O。Windows 为实现高可伸缩性提供了 I/O 完成端口，在这种情况下，待处理的 I/O 请求甚至不需要使用 OS 线程。I/O 开始异步执行，一旦完成，Windows 即会向下层端口发布一个完成数据包。通常情况下，有效设定大小的线程池会被绑定到端口（在 CLR 上由该线程池负责此端口），等到完成数据包一旦可用就对它们进行处理。假定完成率不足，则尽可能快地并行创建大量 I/O 请求比起让每个任务排在其他任务后面等待轮流启动异步 I/O 会实现更好的可伸缩性。这适用于文件、网络和内存映射 I/O，但应始终认识到这一事实，计算机上共享资源的数量有限，过度争用这些资源只会降低而不是增强伸缩性。