文章目录
  1. 1. 概述
  2. 2. 问题分析
  3. 3. 分工原则
    1. 3.1. 确定线程数
    2. 3.2. 确定任务的数量
  4. 4. 共享可变性
  5. 5. 小结
  6. 6. 参考资料

概述

  大家对并发(concurrency)、多线程(Multi-Threading)程序设计肯定不陌生,因为在当今多核CPU时代到处可见,从底层的操作系统(OS)到上层的应用程序,从服务端到客户端,从低级语言到高级程序语言、从分布式集群到大数据处理等等,都可以看到并发程序的身影。可以这样说,只要有计算机软件的地方,就会存在并发程序。大家肯定知道,为何到处都有并发程序?就是因为它能够加快我们程序的运行速度,减少运行时间,从而提高软件的性能,更快地响应用户,以达到更好的用户体验。大家肯定见到过人们为了吃饭、办理银行业务而耐心等待,却经常因为打开网页慢或软件运行慢而感到抓狂,如果这个网站或软件对提供商来说无关紧要那也许没什么问题,但是如果这网站或软件要为了盈利或者有更远大的理想,那有时候可能是致命,因为人们很可能因为慢,下次再也不来访问网站或使用软件。所以,并发程序使得程序运行更快,更快速响应客户操作,从而使软件产品的用户体验提高了,这将会带来更好的经济效益。因此,并发程序设计在软件开发中才会运用得如此广泛。但是,您真的了解并发程序设计么?您可能认为,并发程序设计不就是按照很多操作系统或平台(JAVA.NET等)及语言(JAVA,C#,ruby,scala,go等)提供的类(Thread)、框架(akka等)、设计方法(共享变量,软件事务内存[STM]、actor)及并发模式与模型(reactorproactorselectpollepoll)来开发,主要处理好线程同步的问题就应该差不多了,其他的都是具体实现细节问题。不错,但是您说的只是并发程序设计的具体实现技术,也是我们在设计与开发并发程序时具体应用并需要掌握的技术,但是这些只是战术,是具体实现。不是战略或设计策略,不是指导思想。那么我们就先从并发程序设计的战略或策略层面开始讨论如何进行并发程序设计,这些方法与具体平台或语言无关,可以在各种平台上用具体语言去实现,后面再讨论具体的实现技术与框架,以便能做到战略与战术相结合,这样才能真正掌握并发程序设计。

问题分析

  在做很多事情之前,都应该对现有问题进行具体分析,以便能更好的把握问题,进行合理适当的设计。当然,我们在进行并发程序设计时也应该如此。那么在并发程序设计之前,通常需要分析问题的哪些方面呢?大家都知道,设计并发程序的目的就是为了使程序运行得更快(时间就是金钱、生命),提高软件的性能。并发程序之所以能快,就在于这个“并”字,因为程序能并发(单核)或并行(多核、多CPU)执行,当然能快。这就好比工人搬砖块,人当然是越多越快。但是,这之中有个关键问题,大家是否想到,那就是这个事情(如搬砖块)可以并发或并行来做。又例如每个人乘车去上班这件事就没法并发来做,因为从起点到终点,公交车只能是一站一站到达,同一辆车不可能同时达到几个站,也不可能给你增加几台公交车(多核,多线程),你的乘车时间因此减少了,所以这个时候,给你再多的车(增加CPU或核心数),你的乘车时间也不会减少(程序性能提高不了),因此这个时候,你只能希望汽车跑得更快(提高单个CPU或核心的运算速度),这样才能达到减少时间提高程序性能的目的。这就说明了,并发程序设计的一个本质问题,就是首先要分析问题能不能让程序去并发或并行执行?如果这个问题(乘公交车上班)本身就只能串行去做,那么您就不用考虑使用并发编程技术了,因为这不但不能提高效率反而会使程序开发变得更加复杂,得不偿失。如果这个问题可以并发执行,并发程序当然能提高程序的性能,但是我们也不能高兴的太早,认为只要是这种情况,我就要立即运用并发编程技术,也不考虑编程的复杂性及掉头发的危险,反正就是为了程序运行速度提高0.001秒的那种快感(真正在设计并发程序时需要权衡很多因素,这些以后的章节中具体讨论)。在确定需要使用并发编程技术来解决问题后,我们应该进一步分解问题,其实现实世界中广泛存在两类可以并发处理的问题场景:一种是可以完全并发或并行(如访问网站,银行窗口办业务等),这当然是绝佳的并发编程应用场景;还有一种则是总体需要串行,但中间有些步骤可以并发执行(事实上所有能并发处理的问题都是这种类型,只是看具体问题规模及分解情况),这个时候就需要处理依赖(前置步骤)与等待(同步)问题,最终按顺序完成。所以我们需要把问题进行逐步分解,以便最大化利用并发编程的优势
  我们知道,当引入并发程序解决问题时,目的是为了加快程序运行速度,减少时间。但是你肯定想知道快了多少,是否达到你的预期。这个数据不难得出,只要在同等条件下,把并发之前与之后的程序运行时间对照一下就能看出来。通常人们把程序优化之前运行时间与优化之后的时间的比值称之程序加速比。它是用来衡量程序优化效果的一个关键参数。
              程序加速比 = 优化前耗时 / 优化后耗时
  从上述的说明中,可以得知在同等条件下影响加速比的两个因素是:问题的可并行化程度与CPU个数或核心数,其中问题的可并行化程度,可简单理解为问题中可以并行部分与串行部分的比重(如某问题一共需要5步完成,其中有2步可以并行其余3步必须串行,那么该问题的可并行化程度为2/5)。另外,这里需要说明一下,什么是同等条件,简单地说就是优化前与优化后的程序是在相同环境(问题不变,CPU计算速度不变)中运行。因为如果不在同等条件下比较的话就失去一般性意义,看不到问题的本质,当你把程序从低性能的CPU转向高性能的CPU上运行时,当然也能提高加速比,但是你可能很难看出可并行化程度与CPU个数或核心数跟加速比之间的内在联系。由此,我们引入计算机科学中非常重要的定律——Amdahl定律。它定义了串行系统并行化后加速比的计算公式与理论上限,并给出了加速比与系统并行程度和处理器(CPU)数量的关系。设加速比为Speedup,系统内必须串行化的部分比重为F ,CPU数量为N ,则有公式:
            img-amdahl
  当处理器(CPU)的数量N 趋于无穷大时,Speedup 的最大值无限趋近1/F ,那么加速比与系统的串行化率成反比。这意味着如果程序中有50%(F)的处理都需要串行进行的话,Speedup 只能提升2倍;如果程序中有10%(F)需要串行进行,Speedup 最多能够提高近10倍。
  Amdahl定律同时量化了串行化的效率开销。在拥有10个处理器的系统中,程序如果有10%是串行化的,那么最多可以加速5.3倍(53%的使用率),在拥有100个处理器的系统中,这个数字可以达到9.2(92%的使用率)。即使有无限多个CPU(N),程序加速比也不可能为10。
  我们可以通过下面示例来说明,假设某一程序分为5个步骤执行,每个执行步骤耗时10秒。其中,只有步骤2与步骤5可以并行执行,步骤1、3、4必须串行,如图1.1所示,该程序在全串行的情况下总耗时为50秒。
img-1-1
                        图1.1
  若将步骤2与步骤5并行执行,假设在双核处理器上,则有如图1.2所示的处理流程。在这种情况下,步骤2与步骤5分别耗时5秒。根据加速比定义:加速比 = 优化前耗时 / 优化后耗时 = 50 / 40 = 1.25 ,或者我们再用Amdahl公式计算加速比,由于5个步骤中,有3个步骤需要串行化执行,则该程序的串行化比重(F)为3/5(即0.6),且处理器为双核CPU,即N为2。代入公式得:加速比 = 1/(0.6+(1-0.6)/2) = 1/0.8 = 1.25
img-1-2
                        图1.2
现在我们再假设处理器个数(N)为无穷大,则如图1.3所示,步骤2与5的执行时间接近于0,但即使是这样,程序的总体执行时间仍然大于30秒,即加速比的极限为:50/30 = 1.67。使用Amdahl公式同样可以得出加速比为:1/F = 1/0.6 = 1.67
img-1-3
                        图1.3
  由此可见,为了提高系统的运行速度,减少执行时间,仅仅依靠增加处理器(CPU或核心数)数量并不一定能起到有效的作用,还需要提高系统可并行化程度,即减少系统串行化比重,然后再合理增加处理器的数量,才能达到最佳性价比。根据Amdahl定律,使用并发编程技术解决问题时,系统运行速度的快慢主要取决于CPU或核心的数量及系统中串行化程序的比重。CPU或核心数量越多,串行化比重越低,则系统运行速度越快。仅提高CPU或核心数量而不降低系统串行化程序的比重,也是无法加快系统的运行速度,提高系统的性能
  同时,从上面示例,我们也可以看出,当能并行执行的步骤(2、5)运行速度接近极限(0秒)时,还想提高系统性能,就只能去优化系统的串行步骤(1、3、4),如使用更高效的算法、采用更快运算速度的处理器,或者再想办法看能否把步骤分解成可以部分并行执行等等方法。这也为我们在优化程序时提供了一些指导思想,使我们能够更加有效的利用并发编程技术。

分工原则

  从上一节,我们得知程序从顺序执行转向并发(并行)执行,其效率的提高主要取决于整个系统可并行化程度与处理器(CPU或核心)的数量。现在我们把问题再细化一下,只关注系统中那些可并行的部分(如上一节示例的步骤2与5),既然这部分能够并行,那我们应该想方设法让它运行的更加快,最好能让它快到接近于0(当然这是不可能的)。这个时候您肯定也想到了一些办法,如增加更多的处理器或用更多核心(128核)的CPU(横向扩展),这样你就可以开启更多的线程,又或者更换运算速度更快的CPU(纵向扩展)。如果单机性能达到极限(即不能增加更多的CPU或核心数,又不能更换更快速度的CPU时),你就采用多机,分布式处理等方法让程序能以并行、可伸缩方式运行,目的就是让它跑得更快。现在我们暂不讨论多机、分布式方式,先把问题锁定在单机多核的情况下,因为我们的计算机不可能增加无限多个CPU或核心,通常情况下,都是有限的(4核,8核,16核等)。也就是说,我们在设计并发程序时,只能是在有限的处理器(CPU或核心)数量条件下,启用多个线程或在有些语言中启用多个协程(routine,一种更轻量级的线程),或在分布式情况启用多个进程的方式来解决问题。那现在就产生了新的问题:启用多个线程,这大概是多少?是否越多越好?如果不是,那应该是多少?它受哪些主要因素的影响?要回答这些问题,我们就从具体问题具体分析开始,先来看看下面两个应用场景:
    (1)要求实时计算某土豪所持股票的总资产净值;
    (2)计算出[1-1000万]内素数(质数)的个数;
  我们先来分析第1个问题,它具体需求是这样的:一些有钱人他可能购买了很多支股票,他想实时查看他这些股票当前的总价值(即总资产净值)是多少,即把他每支股票所拥有的数量乘以当前价格,然后再累加起来就是他所持股票的总资产净值。由于股价是变化的,所以需要程序从一些财经网站(如新浪财经)的股票数据接口中实时获取每支股票的股价。现在我把该问题具体细化成按如下步骤完成:
    (1)输入或导入某土豪所有的股票代号及购买的数量;
    (2)根据每支股票的代号请求财经网站的数据接口获取当前开盘价(假设网站没有提供批量获取股票数据的接口);
    (3)根据每支股票的购买的数量乘以当前开盘价计算出每支股票的价值;
    (4)把步骤3中每支股票的价值求和计算出总价值即总资产净值;
  我们先用顺序计算方法实现,现假设某土豪购买了2000支股票(特有钱),核心代码(JAVA语言)如下(所有代码可从github下载):
code-1-1
                        代码1.1
code-1-2
                        代码1.2
code-1-3
                        代码1.3
  其中[代码1.1]的computeNetAssetValue方法就是计算出所有股票的总价值,方法中tickers参数传入所有股票代号,然后遍历每支股票代码,根据股票代码从新浪财经的股票接口中获取当前开盘价[代码1.2],再乘以购买数量(为了简化问题,假设每支股票他都购买了1000股),最后求和。[代码1.3]的run方法是用来统计程序运行时间及显示计算结果。现在让我们看看程序执行结果(我的笔记本电脑配置是:ThinkPadX240 Intel-i3 1.7G双核4线程,8G内存),为了减少误差(如网络不稳定、web请求缓存等因素),我执行了4次,结果如下表所示:

次序 结果 耗时(秒) CPU(逻辑4核)使用率
第一次 27,309,400.00 35.864706098 3%-10%
第二次 27,309,400.00 34.693427806 2%-10%
第三次 27,309,400.00 34.355382928 3%-10%
第四次 27,309,400.00 34.987066194 2%-10%

  从表格中我们看到,每次运行的结果是一致,这说明程序执行过程中没有出现某个请求中断的情况。再看耗时平均在34.5秒左右,这也说明每次执行网络请求与速度是基本稳定的,所以这个结果是可信的。对于这个结果,您可能觉得还行,34.5秒对你来说,这都不是个事儿,咱有的是时间,反正又不着急。但是,如果是一个炒股软件,很多用户都在用,每当他查看总资产净值时需要30多秒(也许客户机器配置好,可能快点),我想客户的心里是很不爽的,因此你为了使客户爽一爽,肯定希望让程序运行得更快些,这个时候你一定会想到用并发执行代替顺序执行,于是就开始进一步分析问题。
  要使用并发(并行)代替顺序执行,我们从上一节就知道,首先这个问题得能并发进行,显然问题1是可以的,我们看看问题1的步骤2与3,这两步中计算每支股票的资产净值是完全独立,也就是说它不依赖其他股票的计算结果,所以这部分就让他并发(并行)执行。既然这样,那我们就快点开始动手吧!哦,等等,有个问题——你打算启用多少个线程来处理它?1个、2个、4个、2000个…,你沉思了片刻,突然说出:4个线程!你当然不是信口开河,你是有依据的,因为你的机器是4核心,少于4个你认为CPU没充分利用(看看顺序执行结果,CPU利用率10%都不到),成百上千的话CPU肯定忙不过来(因为大部分情况在处理线程上下文切换了,自己把自己累死了,这个以后的章节专门讨论),所以4个刚刚好,而且你也知道,同一时刻最多只能4个线程可用(因为CPU是双核4线程),因此4个也许就是最佳线程数。好!那还等什么呢?马上Coding。很快并发版就搞定,让我们看看[代码1.4]:
code-1-4
                        代码1.4
  我们先把计算每支股票的资产净值抽象成一个任务(task),在代码30-38行把2000支股票资产净值的计算逻辑抽象成2000个任务。然后在代码41行开启多个线程(本例为4个,该处使用JAVA并发包的线程池类,具体用处以后章节讨论),代码42行开始并发调用2000个任务,代码45-48行阻塞程序主线程直到所有任务都处理完成并把每个任务的计算结果进行汇总。我们同样执行4次,看看结果如下表所示:

次序 结果 耗时(秒)/4线程 CPU(逻辑4核)使用率
第一次 27,309,400.00 8.551527841 5%-20%
第二次 27,309,400.00 8.467957693 3%-25%
第三次 27,309,400.00 8.612325121 6%-21%
第四次 27,309,400.00 8.563007854 7%-20%

  从上表结果列中可以看出程序改成并发后结果与顺序执行是一致,这说明程序逻辑上没有问题,是正确的。再看耗时,哇!快了4倍,你欣喜若狂,8.5秒,2000个任务,每秒处理了240多个任务,而且这似乎也印证了你之前的结论,顺序执行时,每秒大概处理了60多个请求,相当于一个CPU核心能处理60多请求,现在CPU是4核并行,理论上应该是顺序执行的4倍,现在刚好也是4倍,你可能认为这应该是最佳结果了,因为同一时刻只能有4核心一起工作,而每个核心处理能力的上限是每秒60个任务,现在执行的结果与我们的分析也相符合,所以你可能就得出一个经验:就是在设计并发程序时,线程个数应该与CPU或核心的数量相当,这样就可以达到最佳并发效果。但是我们忽略了一个事情:你是否发现CPU的利用率还很低,最高只有25%,这说明CPU还比较闲,还没充分使用CPU,程序应该还能更快点。那我们再多开启一些线程试试,[图1.4]显示了线程数量与程序运行时间的关系(横轴为线程数,纵轴为执行时间):
img-1-4
                    图1.4
  从上图我们发现,原来程序真的还能更快些,接近2秒就能处理完2000个任务,与顺序执行相比快了15倍,有时真的不敢相信自己的眼睛,程序1秒钟就能完成800-1000支股票的计算任务,这与之前分析的单个核心的上限是每秒60个任务不相符,因为现在达到每秒200多个任务(800/4核心),那这又是什么原因呢?而且线程数量也不是越多越快,而是达到一定的量之后运行时间趋于稳定,也就是说不能再快了。我先暂且不回答这个问题,读者可以再仔细想想。接下来我们要分析第2个问题。
  第2个问题逻辑很简单,大家在学习编程语言时都遇到过。我们还是按处理问题1的方式先顺序执行再改成并发执行来解决此问题。请看[代码1.5]素数数量顺序计算方法(数字范围为1-1000万):
code-1-5
                        代码1.5
  上面代码中countPrimesInRange方法传入1与1000万两个数字,然后按顺序遍历1到1000万中的每个数字,并调用isPrime方法来判断每个数字是否为素数,如果是素数则计数器total就加1,最后total的值就为1到1000万内中素数的总量。我们看一下程序运行结果:

次序 结果 耗时(秒)/4线程 CPU(逻辑4核)使用率
第一次 664579 17.911828934 25%-30%
第二次 664579 18.104362216 24%-30%
第三次 664579 18.497043174 25%-30%
第四次 664579 18.294268014 24%-30%

  现在我们再把程序改成并发版,然后按照问题1的思路,首先要确定该问题是否能并发进行,我们发现在判断某个数字是否为素数这个方法(isPrime)是完全独立的,因此我们就可以把这样的计算逻辑抽象成可以并发执行的任务(Task),按问题1的处理方法,我们创建将要创建1000万个任务,然后开启4个线程,也就是要让4个线程去处理1000万任务。我们来看看程序运行结果:29.486831564秒。你肯定不敢相信这个结果,因为他比顺序执行还要慢。于是我又参考了问题1,认为是否因为线程数量没设置到最佳的原因引起的,所以把线程设置到最佳范围15-40个线程,我逐个试验,结果还是令我沮丧,程序运时间全都在28-32秒左右。也就是说,没任何变化。关键问题是,并发程序不但没有让程序变快,反而变慢了。但是明明该问题是可以并发进行的,于是我再次认真分析并对比问题1与问题2,发现了三个不同之处:
  (1)问题1任务只有2000个,问题2有1000万个任务;
  (2)问题1任务是执行I/O处理逻辑,CPU占用率低(I/O密集型),问题2是执行计算逻辑,CPU占用率高(计算密集型);
  (3)问题1每个任务的执行代价是一样,即每个任务的计算量是一样大(不考虑网络条件不稳定的情况),所以每个任务的运行时间基本相同。问题2任务的执行代价是不一样的,根据isPrime方法可知,偶数可以很快就识别出不是素数,而其他数字随着数值越大,计算量就越大,花费的时间就多一些;
  现在我们根据这三个不同来深入分析问题,通常,为了加快程序处理速度,我们需要将问题分解成若干个并发执行的任务。于是我们创建任务并将其委派给线程,以便使它们可以并发地执行。但是有一个很大的问题摆在我们面前,即我们希望尽可能多地创建任务,但由于资源所限我们又不能创建过多的线程。同时,创建过多的任务也增加系统其他方便的消耗(如任务队列调度,内存等),这样反而让程序性能下降,如问题2创建了1000万个任务,而且大部分任务是计算时间长,这个时候95%的任务都在排列等待。因此,在并发程序设计时,问题类型、任务数与线程数三者之间存在相互关系,我们需要针对不同问题类型来确定相应的任务数与线程数,否则并发程序不但加快不了程序运行速度,反而适得其反,同时还增加程序设计的复杂性。下面我们讨论这三者的关系,然后再根据这些结论去优化问题2看是否能验证这些结论。

确定线程数

  为了解决上述难题,我们希望至少可以创建处理器核心数那么多个线程。这就保证了有尽可能多地处理器核心可以投入到解决问题的工作中去。很多平台或语言可以很容易地获取到系统可用的处理器核心数:
   (1)JAVA: Runtime.getRuntime().availableProcessors();
   (2).NET: Environment.ProcessorCount;
  所以,并发程序的最小线程数应该等于可用的处理器核数。如果所有的任务都是计算密集型的(问题2),则创建处理器可用核心数那么多个线程就可以了。在这种情况下,创建更多的线程对程序性能而言反而是不利的。因为当有多个任务处于就绪状态时,处理器核心需要在线程间频繁进行上下文切换,而这种切换对程序性能损耗较大。但如果任务都是I/O密集型的(问题1),那么我们就需要开更多的线程来提高性能。
  当一个任务执行I/O操作时,其线程将被阻塞,于是处理器可以立即进行上下文切换以便处理其他就绪线程。如果我们只有处理器可用核心数那么多个线程的话,则即使有待执行的任务也无法处理,因为我们已经拿不出更多的线程供处理器调度了。如果任务有50%的时间处于阻塞状态,则程序所需线程数为处理器可用核心数的两倍。如果任务被阻塞的时间少于50%,即这些任务是计算密集型的,则程序所需线程数将随之减少,但最少也不应低于处理器的核心数。如果任务被阻塞的时间大于执行时间,即该任务是I/O密集型的,我们就需要创建比处理器核心数大几倍数量的线程(像nginx,iis7netty等)。我们可以计算出程序所需线程的总数,总结有如下公式:
     线程数 = CPU可用核心数/(1 –阻塞系数),其中阻塞系数的取值在0和1之间
  计算密集型任务的阻塞系数为0(因为CPU一直很忙),而I/O密集型任务的阻塞系数则接近1。一个完全阻塞(阻塞系数为1)的任务是注定要挂掉的。因此,为了更好地确定程序所需线程数,我们需要知道下面两个关键参数:处理器可用核心数与任务的阻塞系数。第一个参数很容易确定。但确定阻塞系数就稍微困难一些。我们可以先试着猜测,或采用一些性能分析工具(如:jprofilervisualvmjconsole等)或java.lang.management API来确定线程花在系统I/O操作上的时间与CPU密集任务所耗时间的比值。

确定任务的数量

  前面我们已经知道如何计算并发应用程序所需的线程数量,现在我们需要确定如何分解问题。每一个子任务都将并发地运行,所以我们脑中第一个念头可能是希望子任务的数量和线程数保持一致(问题1中的4个线程)。虽然想法不错,但还远远不够,因为这种做法忽略了待解决问题本身的特性。在问题1的那个程序中,获取每一只股票价格的代价是相同的,所以我们将任务分成和线程数量一样多的组,每个组委派一个线程来处理就可以了。(问题1程序中虽然定义了2000个任务,但是由于是I/O密集型且任务代价相同,所以程序可以开启更多的线程,从图1.4中可以看出在15-20个线程时性能最好,其实这相当于2000个任务均分成15-20组,具体如何分配是JAVA线程池类从任务队列的自动调度的)但是在计算素数数量的程序中,计算某个数是否为素数的代价是各不相同的。偶数可以被很快识别出不是素数,而识别较大的素数要比识别较小的素数更耗时。所以将数的计算范围(如:1-250万,251万-500万,501万-750万,751万-1000万各4组)分成线程数那么多个子区间并分别处理并不会带来显著的性能提升。这种做法会使得某些任务比其他任务完成得快,从而造成处理器核心使用上的不均衡。换句话说,我们希望各个子任务的工作量是均匀分布的。所以我们可能需要花大量的精力和时间来进行问题分解,以便使子任务的负载保持均匀分布。但这会带来两个问题,首先,要做到这点是十分困难的,因为很难保证每个数据分组的代价是相同。其次,将问题分解成彼此相等的子问题,并将工作量等量均摊到各个线程之间的代码将会非常复杂。
  事实证明,在解决问题的过程中使处理器一直保持忙碌状态比将负载均摊到每个子任务要实惠得多。从处理问题的角度来看,我们需要保证:只要还有待完成的任务,就不可能有空闲的处理器核心。所以,与其斤斤计较于如何将负载平摊到每个子任务上,不如将任务拆得比线程数多,以使处理器一直不停工作来得更有效。我们应该尽可能地对问题进行拆分,以产生足够多的工作供所有处理器可用核心来执行。这就好比,我们在工作中老板分配两个不同工作量的任务给水平差不多的两个员工做(不考虑走捷径),显然工作量大的员工要累些忙些,另一个人要闲一些,这就相当于两个CPU核心工作不均,没有最大化发挥员工的能力,所以这个时候就需要把工作量再细分一下,即活(任务)分得更细一些,以便两个人的工作量都差不多。
  我们根据上述结论来优化问题2,由于问题2是计算密集型,所以线程数可确定为CPU核心数,即4个线程。再来确定问题2的任务数,之前的1000万任务数肯定不行,分得太细了,大部时间浪费在任务调度上。我们可以按上述方法,先把任务分成4组,每组250万个数字,然后看看程序运行时间是否提高了4倍。我们仍然运行4次结果如下表:

次序 结果 耗时(秒)/4线程 CPU(逻辑4核)使用率
第一次 664579 8.86371334 25%-100%
第二次 664579 8.996631744 25%-100%
第三次 664579 9.18650138 25%-100%
第四次 664579 8.778619456 25%-100%

  现在程序终于运行变快,比顺序执行快了2.5倍,这是个好消息,至少说明了我们之前的分析结论是成立。但是我们这个结果还没有到理想结果,理论上4核心CPU并发计算,应该比顺序方法快4倍,现在只快了2.5倍,那么我们的程序的运行速度是否能接近预期呢?先让我们打开活动监视器(在Windows上是任务管理器,在Linux上是系统或资源监视器)来观察处理器核心的活动。在用顺序模式和并发模式的CPU使用情况对比结果如图1.5与1.6所示。
    img-1-5
      图1.5 顺序计算素数
    img-1-6
      图1.6 分4个区间4线程并发计算素数
  采用顺序方法实现的程序的CPU利用率曲线和我们之前预想的一样,基本上就CPU0在计算,其它几个都闲着,只有25%差不多在1/4左右的利用率,也就是说基本只有1个核心在处理。采用并发方式实现的程序则有所不同,即在大多数情况下CPU的4个核都是满负载运转的,但从图1.6中CPU0、CPU1、CPU2的趋势来看没有CPU3那么平稳,这一现象告诉我们,CPU工作负载并非均匀分布的,即前3个区间计算任务要比最后1个区完成得快。如果我们仔细考虑一下所给问题的性质,这个现象就很容易以理解了,根据我们之前的划分方式,最后1部分(751万-1000万)任务中所含数字的值要比前3部分大,而数字的值越大则判断其是否素数的计算量也越大,所以最后1部分任务执行就会比较慢,而对应的那个执行线程CPU就可能一直在繁忙中,所以CPU的趋势就相对平稳(注:4个任务不一定与CPU的顺序一一对应,有可能CPU0处理任务3,CPU1处理任务2)。为了追求加速极限,我们需要为4个线程分配等量的工作负载。
  一般来说,为每个子任务分配均匀的工作负载是比较困难的,因为这需要对问题本身以及程序在整个输入数据范围内的行为都有相当深入的理解。单就计算素数数量这个问题来说,我们之前采用的方法是将数据按其串行顺序,即自然顺序(从1到1000万)分成4等份,每份250万个数字。而现在我们可以尝试将输入数据里的大小数字进行重新组合,以达到负载均匀分布的效果。例如,我们仍将输入数据分为4部分,然后考虑将区间3与4中前125万个数字与区间1与2前125万个数字对换,这样就把大小数字分散到4个区间。我们原来的代码并不是这样划分的,如果把之前写的那个并发计算的代码改成这种划分方式,就会发现程序运行时间减少了。更进一步地,如果想把程序放在拥有更多处理器核心的机器上跑,我们可能需要把输入数据划分成更多子区间。虽然子区间数目越多划分难度也就越大,但幸运的是我们找到了一个简单的解决方案。
  只将输入数据划分成少量子区间(如4个)的主要问题是可能会导致一个CPU核心干了太多活而其他CPU核心则很无所事事。所以我们将问题拆分得越好,也就是尽量做到公平分配,程序就越容易保持所有处理器核心都一直忙碌的状态。我们将输入数据拆成若干个小的子区间,并使子区间数量超过线程数。当线程完成子区间数据的计算之后,就可以继续挑选其他子区间数据执行运算。在总体的计算过程中,某些处理器核心可能执行了一个需要跑很久的任务,而其他处理器核心则可能挑了若干个耗时相对较短的任务来执行。让我们看一下线程池大小和子区间划分数的变化将对性能产生怎样的影响。我们把线程池大小设为4并将子区间划分数如下份(横轴为任务数,纵轴为执行时间),结果如下:
img-1-7
                      图1.7
    img-1-8
                      图1.8
  进行上述调整之后,运行速度提高了3倍(大部分在7.5秒)。虽然仍未达到提速4倍的预期结果,但已经十分接近了,同时我们还发现当任务数超过200万时程序性能开始下降,原因是由于任务过多JAVA虚拟机内部在调度任务时花了很多时间。我们可以尝试调整子区间划分数或调整划分策略来进一步提高运行速度。例如,采用完全随机划分方式,我们将会获得相当好的速度提升。然而完全随机划分也并非对所有情况都适用,所以问题的关键还是为了有更高的利用率需要确保每个处理器核心都能分摊到均匀的工作负载。也就是说,把任务分得更细些,让CPU一直都有活可以做,这样它的空闲时间就相当较少,利用率就提高,程序的并发效率也同样提高了。图1.8中显示任务数分别为100、500、1000、2000时CPU的占用率曲线,从图中可以看出4个核心的形状都差不多,说明它们在计算过程中被充分利用。
  虽然线程数是影响性能的一个关键因素,但却并非是唯一要素。每个子任务的工作负载以及完成每个子任务相对于其他子任务的耗时,亦是非常重要的。对问题进行统一划分需要花费非常多的精力,且不一定比随机划分的结果来得更好。权衡投入与产出之后,我们应该尝试去通过一种简单的划分方式来实现子任务的均衡工作负载。在任何情况下,只有深入理解问题的本质以及问题在不同输入情况下的行为才能设计出好的划分方式。此外,划分的复杂度一般取决于问题的复杂度。

共享可变性

  并发编程可以帮助应用程序提高响应速度、减少等待时间并增加吞吐量。我们可以充分利用多核处理器的性能优势以及多任务并发的方法来提高程序运行效率和响应速度。但正如我们在上一节讨论的那样,在真正享受这些并发编程所带来的好处之前,我们应该认真分析问题特点、任务分解、并发策略等,在现实情况中,还要考虑更多的东西,像网络条件、内存情况等,还有一些其他非功能因素,如系统可靠性、可维护性、可用性等这些都是要认真考虑与分析的。在使用并发编程技术之前,首先要确定系统或程序的确存在性能瓶颈,然后在保证正确性前提下最大化利用并发编程技术,以达到让系统运行得更快,切忌为了技术而改用并发
  你可能会想“只要把任务进行分解并分派到多个线程中执行,程序就能获得更高的吞吐量”。但遗憾的是,绝大多数问题都无法被分解为彼此完全独立的几个子问题。更普遍的情况是,我们可以独立地执行某些操作,但最终还是需要将这些操作所得到的部分结果进行归并才能得到完整的结果(问题1与2,最后还是要统计股票总价与素数总个数。现实中绝大部分都是这样的情况,像MapReduce、任务调度队列等)。所以线程之间需要能够相互交换彼此的数据,并且有时候某些线程还需要等待其他线程的结果出来之后才能继续运行。于是我们就需要在线程之间进行协调,并由此引出同步和锁等一系列令人头痛的问题。在开发并发应用程序的时候,我们通常会遇到3类问题:饥饿死锁以及竞争条件,这三类问题都与线程同步及锁有很大的关系,其中前两个问题还算比较易于检测甚至避免,而竞争条件则是一个需要彻底根除的棘手问题(因为它是很容易让并发程序产生bug,而且很多时候很难跟踪与调试)。
  我先简单说明一下什么是竞争条件?如果两个线程竞争使用相同的资源或数据,那么我们就将这种情况称为竞争条件(race condition)。竞争条件不仅仅会发生在两个线程同时更改相同数据的场景中,还可能发生在一个线程正在修改某数据而另一个线程同时在读这个数据的时候(如并发访问数据库同一个表某行记录)。竞争条件可能会导致程序行为不可控、执行逻辑异常并产生错误的结果。我们知道大多数语言或平台都提供相应的同步机制来处理这类问题(如lock,synchronized、读写锁等,这些将在并发基础知识章节讨论),但其实核心问题并非我们只需加些锁、做些同步这件事本身,而是因为我们正在处理共享可变性(Shared Mutability)。大部多数情况下,我们已经习惯于使用可变性来开发各类应用程序,即通过更改其字段的方式来创建和变更一个对象状态,但是当程序并发访问/修改共享变量时,很容易造成结果不一致,同时由于为了控制并发访问/修改使用加锁机制来处理,这往往又会使程序性能下降,如果处理得不好,可能造成性能瓶颈,严重影响程序总体的性能。
  那么,在使用并发方法的时候,我们一方面希望保证一致性和正确性,另一方面又希望程序在给定的硬件环境下达到最佳性能。在实际情况中是否有两全其美的方法?这就要求我们采取什么方法或策略来对待共享可变性问题。
  一旦完全消除了共享可变状态,我们就可以很容易地避免竞争条件或一致性问题。因为当线程不再竞争访问可变数据的时候,同时,我们也无须担心如何控制线程的执行序列。因为在这种情况下线程之间不存在竞争关系,所以代码中也无需针对互斥访问的部分进行保护。
  我们应该尽可能地提供共享不可变性(如.NETJAVA的String类,像scala,F#这些函数编程中提供的不可变类型或集合),否则就应该遵循隔离可变性原则,即保证总是只有一个线程可以访问可变变量,而不是使用共享可变性方法。这三种原则正好为我们提供解决操纵变量状态三种策略:
  (1)共享可变性(shared mutability);
  (2)隔离可变性(isolated mutability);
  (3)纯粹不可变性(pure immutability);
  共享可变性方法,也是我们常用的方法,我们创建的变量允许所有线程修改,当然是在一个可控的模式下。使用共享可变性来进行编程虽然看似简单,但却可能会导致同步问题。为了使用共享可变性,我们必须保证不会有两个线程同时修改同一个字段,并且对多个字段的修改必须满足一致性原则,因为这样写出来的程序在同步方面太容易出错了。
  隔离可变性方法是一个可选的折中方案。在该方法中,变量是可变的,但在任意时刻只有不超过一个线程可以看到该变量(如问题1的netAssetValue变量与2中的total变量;scala中的基于actor模型)。在使用该方法时,我们保证任何在多个线程之间共享的事物都是不可变的。
  纯粹不可变性方法,该方法中所有事物都是不允许更改的。要使用这样的设计可不大容易,部分原因是由问题的性质决定的,但更主要的原因还是我们对这种方法缺乏设计使用经验。这是一种范式的转变,可能需要设计一些特殊的数据结构和方法(像scala,F#,Haskell函数编程语言)。然而,如果我们真的能够将这种方法付诸实现,我们将得到丰厚的回报,即实现简单且安全的并发。

小结

  本章主要让读者从总体上来把握并发程序设计,它是一些方法论的东西。这样可以使你在设计并发程序时不会犯思想上的错误,具体的并发程序设计技术有很多,如同步、锁、无锁(lock-free)、线程池,调度框架等,而且各种语言或平台具体设计与实现也不尽相同,而本章中的方法可以适应于各种具体平台。以下是一些利用多核处理器并发能力来提升性能的方法总结:
  (1)我们需要将程序拆分成可以并发运行的多个子任务;
  (2)我们应该至少开处理器核心数那么多个线程,倘若问题的规模大到可以享受这么多线程带来的好处的话(如果问题规模太小,线程管理和调度反而成为影响性能的瓶颈);
  (3)对于计算密集型应用程序,我们应将程序线程数限制为与处理器核心数相同;
  (4)对于IO密集型应用,阻塞时间是影响线程数量的关键因素。可以用如下公式估算程序所需线程数量:线程数 = CPU可用核心数/(1–阻塞系数),其中0≤阻塞系数<1;
  (5)我们应该将问题分解为若干子任务,这样才能提高CPU的利用率并使其每个核都有足够多的活干;
  (6)我们必须避免共享可变状态,并用隔离可变性或共享不可变性取而代之;
img-1-9

参考资料

  1. 《面向模式的软件体系结构 卷2:用于并发和网络化对象的模式》
  2. 《设计模式:可复用面向对象软件的基础》
  3. 《Java并发编程设计原则与模式 第二版》
  4. 《JAVA并发编程实践》
  5. 《分布式Java应用:基础与实践》
  6. 《深入理解Java虚拟机:JVM高级特性与最佳实践》
  7. 《Effective Java中文版(第2版)》
  8. 《Java虚拟机并发编程》
  9. 《Java性能优化权威指南》
  10. 《Java程序性能优化——让你的Java程序更快、更稳定》
  11. 《Erlang编程指南》
  12. 《CLR via C#(第3版) 》
  13. 《C# 5.0 in a Nutshell》
  14. 《Programming Ruby中文版》
  15. 《松本行弘的程序世界》
  16. 《Go语言编程(七牛云存储团队执笔) 》
  17. 《Go并发编程实战》
  18. 《快学Scala》
  19. 《SCALA程序设计-JAVA虚拟机多核编程实战》
  20. 《Scala Cookbook》
文章目录
  1. 1. 概述
  2. 2. 问题分析
  3. 3. 分工原则
    1. 3.1. 确定线程数
    2. 3.2. 确定任务的数量
  4. 4. 共享可变性
  5. 5. 小结
  6. 6. 参考资料