软件与并发巨变 不得不面对的革命
http://portal.acm.org/citation.cfm?id=1095421&dl=acm&coll=&CFID=15151515&CFTOKEN=6184618
作者: 罗小平编译, 出处:程序员, 责任编辑: 叶江,
在过去30年里，并发虽然一直被鼓吹为“下一件大事”或“未来之路”，但软件界不为所动。现在，并行终于出现在我们面前了：新一代计算机全面支持并发，这将引发软件开发方式的巨变。
深远影响
在过去30年里，并发虽然一直被鼓吹为“下一件大事”或“未来之路”，但软件界不为所动。现在，并行终于出现在我们面前了：新一代计算机全面支持并发，这将引发软件开发方式的巨变。
本文主要讨论并发对软件——包括编程语言和程序员——的深远影响。
Olukotun和Hammond所描述的硬件发展，代表着计算机计算方式的重大变化。过去30年里，半导体工业的发展及其在处理器上的应用， 推动了已有顺序式软件运行速度的稳步提升。但体系结构上的多核处理器变化仅对并发应用有益，因此几乎对绝大多数现存软件没有价值。在不久的将来，已有的桌 面应用不可能比现在跑得更快。实际上，它们的运行速度会稍慢，因为为了降低高密度多核处理器的电能消耗，新的芯片内核被简化并运行在更低的时钟速度。
这将对软件至少是主流软件的开发带来深远影响。计算机的能力无疑越来越强，但程序不再可能从硬件性能提升大餐中免费获益，除非它们实现了并发。
即便抛开多核变化的强制要求不谈，我们也有理由实现并发，尤其是将工作从同步转到异步，可以提高响应速度，就像目前的应用里必须让工作远离GUI线程，以便计算在后台进行时，屏幕能得到重绘。
但实现并发是有难度的。不仅目前的语言和工具仍未为将应用转化为并行程序做好充分准备，而且在主流应用中也很难找到并行，尤其糟糕的是——并发要求程序员以人类难以适应的方式思维。
不过，多核在未来不可回避，我们必须找到与之相适应的软件开发方式。接下来，我们将深入探讨并发的难度所在，以及一些未来可能的应对方向。
软件新纪元
今天的并发编程语言和工具几乎与结构化编程时代初期的顺序化编程同时起步。信号量和协程是实现并发的基本手段，锁与线程建立在更高层次，可以结 构化构造并发程序。而我们需要的是以面向对象为基础的并发——建立在更高层次的抽象有助于构建并发程序，就像面向对象抽象有益于构建大型组件化程序一样。
几个因素决定了并发变革对我们冲击可能比面向对象大。首先，并发是获得更高性能的必需手段。像C之类的语言，无视面向对象，但仍能在很多开发领 域发挥作用。如果并发变成了应用性能提升的华山一条路，那么商业和系统语言的存在价值就只能建立在支持并发编程的基础上。因此现存的如C之类的语言，就必 须支持超越pthreads之流简单模式以外的并发特性，不能支持并发编程的语言将逐步走向消亡，而仅仅能在现代硬件不重要的场合占得一席之地。
并发比面向对象冲击更大的第二个原因是，尽管顺序化编程已经很难，但并发编程更难。例如，在分析顺序化程序时，环境相关性分析是考量环境影响行为的基础技术。并发程序则还需要进行同步分析，而同时做环境相关性和同步分析已经被证明不可企及
最后，人类在遭受并发的突然袭击后，发现并发程序比顺序化代码难以把握得多。即使最细心的程序员，也很可能考虑不到简单半有序作业集里的交叉问题。
客户端和服务端应用的差别对客户端应用来说，并发是一个挑战。但是在很多服务端程序里，并发则是一个“已经解决的问题”，我们可以例行公事般地构造并发应用，结果它就能 很好工作，尽管进一步改进程序以确保其更具扩展性，仍需艰巨努力。这些程序通常都包含大量并行，因为它们同时处理的是大量的彼此无关的请求。比如Web服 务器和网站，运行的是同样代码的副本，处理绝大多数时候彼此无关的数据。
而且，它们的执行环境被隔离，通过高度支持并发存取结构化数据的数据库之类的抽象数据访问方式实现状态共享。因此，代码通过数据库实现数据共享，就能得到“安宁从容的感觉”——就好像运行在一个整洁、单线程的世界一样。
而客户端应用的世界里，则没有那么规则和结构化。通常，客户端程序为单用户执行相关的小型运算，由此出发，我们发现可以通过将运算分割为多个更 有效率的小片断来实现并发。也就是说让用户界面和程序运算小片断可能以多种方式交互和共享数据。但这类程序难以并发执行，因为其代码是非均态的，结构密 织、交互复杂，而且操作的是基于指针的数据结构。
并行
·编程模型(Programming Models)
现在，你能用多种方式实现并行，但每种方式仅仅适用于特定类型程序。大多数时候，没有细致入微的设计与分析，很难事先知道哪种模型适合给定问题。如果无法清楚确定给出的问题能套用哪种模型，往往就必须将多个模型杂合起来灵活运用。
这些并行编程模型可以从以下两个方面明确加以区分：并行作业的粒度，和任务间的耦合程度。这两个方面的不同，造就了迥异的编程模型。我们接下来依次讨论。
并行作业，小到单个指令，比如加法和乘法运算，大到需花费数小时甚至数天的程序。显然，并行体系中小作业的累计耗费是巨大的，因此，像并行指令 运算等一般要求用硬件实现。与多处理器结构相比，多核处理器减少了通讯和同步消耗，因此减少了小片代码的累计成本。同样，一般来说，粒度划分越小，就越要 注意拆分任务、以及为它们提供彼此间通讯和同步的成本。
另一方面是作业在通讯和同步时的耦合程度。不要有这样的幻想：作业完全独立执 行，最后产生完全不同的输出。在这种情况下，各作业有序执行，不会 引发同步和通讯问题，很容易实现无数据竞争可能的编程。这样的情况是罕见的，绝大多数程序的并发作业都要共享数据。因此作业更为变化多端，保证其正确和高 效的复杂性也大为增加。最简单的情况是每个任务执行完全一样的代码。这种类型的共享常常是规则的，通过对单个任务的分析就能理解。更具挑战性的是不规则并 行，这个时候，各作业的情况互不相同，共享模式更难于理解。
·无依赖并行(Independent parallelism)
可能最简单、只具有基本行为的模型是无依赖并行(有时候也叫密集并行(EP，Embarrassingly Parallel))，一个或者多个作业独立运行，处理分离的数据。
小粒度数据并行依赖于并发执行的作业的独立性。它们应该无输入输出数据的共享、无交叉执行，比如：
double A[100][100];
…
A = A * 2;
求得100×100数组每个元素与2的乘积，然后保存到原元素位置。100000次的乘法运算都独立运行，彼此没有交叉。它可能是比大多数计算机的实际需要更理想化的并行模型，粒度很小，因此实际应用中通常会将矩阵分成n×m个块，然后在这些块的基础上执行并行计算。
而在粒度轴的另一端，很多应用，比如搜索引擎，共享仅仅一个巨型只读数据库，因此要求并行查询没有交叉。同样，大规模仿真系统要求很多并行程序同时访问包含输入参数的大型空间，这是一个让人颇感棘手的并行应用。
·规则并行(Regular parallelism)
比无依赖并行略为复杂的是计算工作彼此依赖时，将同样的操作应用到一个数据集上。如果在两个操作间需要通讯或同步，则操作间存在依赖。
我们考虑以下用四个相邻元素的平均值替换数组中每个元素的运算模型：
A[i, j] = (A[i-1, j] + A[i, j-1] + A[i+1, j] + A[i, j+1]) / 4;
这类运算要求细致协调，确保在用平均值替换前，已经准备好数组中相邻数据。如果不考虑空间消耗，可以将计算得到的平均值写入一个新数组。一般， 其他更结构化的计算策略，比如用Diagonal Wavefront算法访问数组，会得到同样的结果，而且有更好的缓存寻址和更低的内存消耗收益。
规则并行程序可能需要同步控制，或者精心排练的执行策略，以确保得到正确的结果，但不像普通并行，它可以通过分析隐藏在操作后面的代码以确定怎样实现并行，并知道如何共享数据。
再次移到粒度轴的另一端，譬如Web站点上的运算工作，除了访问相同数据库，存在典型的独立性。因此除了数据库事务，所有的运算都并行进行，不需要大量协调工作。
·无结构并行(Unstructured parallelism)
大多数情况下，最没有规律的并行形式是并行运算彼此不同，因此它们的数据访问无可预测，需要通过显式同步加以协调。这是使用多线程和显式同步编 写的程序里最常见的并行形式，其中的线程在程序里扮演着互不相同的角色。一般，对于这种并行形式，除了知道两个线程访问数据发生冲突时需要显式同步，我们 在其他方面很难说出个头头道道;另外，这类程序具有不确定性。
锁
·状态共享存在的问题;锁的局限性
无结构并行面临的又一个挑战来源于无结构状态共享。客户端应用通常通过共享内存的办法来解决对象图(Graphs of Objects)中交互行为无可预测的问题。
假设两个任务希望访问同一个对象，其中一个可以修改对象的状态，如果我们不加控制，那么就会产生数据竞争。竞争的后果很糟糕，并发任务可能读写到不一致或已损毁的数据。
有大量同步策略可以解决数据竞争问题，其中最简单的就是锁。每一个需要访问共享数据片的任务在访问数据前必须申请得到锁，然后执行计算;最后要 释放锁，以便其他任务可以对这些数据执行别的操作。不幸的是，尽管锁在一定程度上能避免数据竞争，但它也给现代软件开发带来了严重问题。
最主要的问题是，锁不具有可组合性。你不能保证由两部分以锁为基础、能正确运行的代码合并得到的程序依然正确。而现代软件开发的基础恰恰是将小程序库合并为更大程序的组装能力;因此，我们无法做到不考察组件的具体实现，就能在它们基础上组装大软件，这是个大问题。
造成组装失败的祸首是死锁。考虑最简单的情况，当两个任务以相反顺序申请两个锁时，死锁就出现了：任务T1获得了锁L1，任务T2获得了锁 L2，然后，T1申请获得锁L2，同时T2申请获得L1。此时，两个任务将永久阻塞。而被以相反顺序请求两个锁的情况在任何时候都可能发生，所以获得一个 锁后，只有让调用进入你无法控制代码的内部，才可能找到解决死锁问题的办法。
但是，那些可扩展的框架却没有考虑这个问题。即使目前最 根正苗红的商业应用框架也是这么干的，包括.NET框架、Java标准库等。之所以没出 什么大问题，是因为开发人员仍然没有编写要求频繁锁定的大量并发的程序。很多复杂模型希望解决死锁问题——比如实现退避/重送(backoff-and- retry)协议——但这些模型都需要程序员经受严格训练，并且一些解决办法还可能引入其他问题(比如活锁(或空转，livelock))。
通 过确保所有锁申请都只能在安全顺序基础上得到满足的死锁预防技术，也无能为力。例如锁调整与锁分级策略，要求所有同级锁按照预定顺序一次满足，此 后只能申请获得更高级别的单一锁，以此的确可以避免锁冲突。这类技术虽然在实践中还未普及，不过在单一团队维护的模块和框架内已经发挥了作用。但是，它们 要求对全部代码的完全控制。这就严重限制了这些技术在可扩展框架、插件系统和其他需要将多方编写的代码整合环境里的应用。
一个更基 本问题是，锁的实现依赖于程序员对协定的严格遵循。锁与它所保护的数据间关系相当隐讳，只能通过程序员的纪律性得到维系。程序员必须总 能清楚记得访问共享数据前，要在正确地点放置恰当的锁。有时，程序里的锁管理协定的确存在，但它们几乎从来没有精确到可供工具实现检验。
锁还有其他一些更加微妙的问题。锁定是一个全局属性，很难被本地化到单个过程、类或者框架。所有访问共享数据片的代码都必须知道且服从锁约定，无论是谁编写这些代码，代码用在什么地方。
即便将同步本地化，也并非任何时候都能正常工作。拿一个常见解决方案，如Java中的synchronized方法来说。对象的每个方法都能从 对象得到一个锁，所以没有任何两个线程可以同时直接访问对象的状态。而对象状态仅能通过对象的方法访问，程序员又记得给方法增加了 synchronized声明，如此一来，看似达到了我们的目的。
而实际上，synchronized方法至少有三个主要的问题。首 先，它们不适合于其方法会调用别的对象(比如Java的Vector和. NET的SyncHashTable)的虚函数的类型，因为获得一个锁后调用进入第三方代码，就可能引发死锁。其次，synchronized方法可能导 致频繁锁定，因为它们要求在所有的对象实例上获得和释放锁，即便很多对象从不存在线程交互。第三，synchronized方法的锁粒度过小，当程序在单 或多个对象上调用多个方法时，无法保证操作的原子性。我们以如下简单的银行事务为例：
account1.Credit(amount); account2.Debit(amount)
逐对象(Per-object)锁定可以保护每个调用，但不能阻止其他线程看到两个账户在多次调用之间的不一致信息。这种类型的操作，原子性与单个调用的边界不吻合，因此需要额外的、显式同步。
·锁的替代者
考虑到内容完整性，我得提一下锁的两个主要备选方案。一个是无锁编程(Lock-Free Programming)。通过对处理器内存模式的深入认识，建立可共享但无显式锁定的数据结构是可能的。无锁编程难度很大且非常脆弱，因此新的无锁数据 结构实现方案，仍在不断修改之中。
第二个替代物是事务内存(Transactional Memory)，它将数据库中事务模式的核心思想移植到编程语言里来。程序员将自己的程序编写为一个个具有确定原子性的块，它们可以分离执行，因此只有在 每个原子行为执行前和执行后，并发操作才能访问共享数据。尽管很多人看好事务内存的前途，但它目前仍处于研究之中。
对语言的要求·我们需要何种编程语言
我们需要更高层次的语言抽象，要让目前的命令式语言进化式扩展，这样，现存的应用才能快速实现并发执行。无论是初始开发阶段，还是维护阶段，编程模型都必须让并发易于理解和实现。
·显式、隐式和自动并行
显式编程模型提供的抽象要求程序员能明确定位并发出现的位置。其主要优点是，它允许程序员充分利用各自在应用领域的知识，充分挖掘应用的并发潜能。不足在于面对共享数据时，要求程序员高度熟练，以实现新的更高层次的编程抽象模型。
隐式编程模型将并发隐藏在库和API包内部，因此在库以并行方式执行工作时，程序员得以持续保有全局视野。这种方式可以让初级程序员安全使用并 发。主要弱点是难以获得并发的全部性能收益。另外，也很难设计出在任何场合都不暴露并发的接口——比如，当程序将操作应用在相同数据的多个实例时。
另一个正被广泛研究的方法是自动并行，编译器试图自动找到并行部分，通常应用于Forthan之类老式语言编写的程序里。听起来很吸引人哦，但 这种办法在实践中不大行得通。必须有对程序的精确分析，才能弄清程序的潜在行为。而对Forthan之类简单语言做这类分析就颇具挑战性了，面对像C这样 的以指针为基础操作数据的语言，更是难上加难。再说，顺序式程序通常使用的是顺序式算法，能实现并发的部分非常有限。
·命令式和函数式语言
流行商用编程语言(如Pascal、C、C++、Java和C#)都是命令式语言，在这些语言里，程序员分步指定对变量和数据结构的变化。小粒度控制构造(如循环)、低层次数据操作和共享易变对象实例等因此，使以这些语言编写的程序难以分析并实现自动并行。
我们通常相信函数式语言，如Scheme、ML和Haskell等，能够铲除这类障碍，因为它们就为并发而生。以这些语言写成的程序，操作没有并发危险、不需改变的对象实例。此外，它们没有副作用，执行顺序上的限制很少。
但实际中，函数式语言并不一定有益于并发。函数式程序中的并行主要执行于过程调用层次，这对于传统并行处理器来说，粒度过小。而且，大多数函数式语言允许操作可变对象时存在部分副作用，因此应用了这些特性的代码，也难以实现自动并行。
这些语言为了增加表达能力和提高效率又引入了可变状态。在纯粹的函数式语言里，复合数据结构，如数组、树等，是通过原结构副本外加待修改数据实 现更新的。这种方法从语义上讲颇有魅力，但性能糟糕(线性算法很容易升级为二阶算法)。此外，函数式更新对严格的顺序式运算无能为力，此时，每个操作都会 等待至上一个操作完成对程序状态的更新才能执行。
函数式语言对于并发的真正贡献是这些语言中广泛采用的高层次编程方式，在这种方式 下，像Map和Map-Reduce等操作会将计算应用于复合 数据结构的所有元素。这种高层次的操作方式是并发的坚实基础。这种编程风格，幸运的是，这种编程方式没有被固化于函数式语言，对命令式语言有重要借鉴意 义。
例如，Google的Jeffrey Dean和Sanjay Ghemawat描述过Google如何使用Map-Reduce实现大规模分布式计算。命令式语言可以开动脑筋将这些特性纳为己用，并从中获益。这一点 重要，毕竟，我们的工业不能从头再来。为了保护全世界对现存软件的巨大投资，特别需要尽快增加对并发的支持，同时保护软件开发人员拥有的命令式语言专业知 识和经验。
抽象优化
目前的大多数语言都在线程和锁层次实现了显式编程。这种抽象层次过低且难以系统化。这种架构不足以成为构建抽象的坚实基础，它纵容多线程程序随意阻塞和重入(reentrancy)，以致带来很多问题。
更高层次抽象允许程序员用自然方式表述任务，此时，运行时系统能将这些任务有计划调度，使之适配于计算机硬件。这将使应用在新的硬件上获得更好性能。另外，在常规开发中，程序员将得闲将精力放在任务内部的顺序执行流程上来。
有关更高层次抽象的两个基本例子是异步调用和future。无阻塞函数和方法产生的是异步调用。调用者可继续执行，从概念上说，也就是消息被发 送到任务或者fork进程去独立执行操作。期货(future)是一种从异步调用返回操作结果的机制，但目前仅是一个有价值的概念，还未具体实现。
更高层次抽象的又一个例子是主动对象(Active Object)，它运行在自有的线程里，因此创建1000个这样的对象，就相当于创建了1000个执行线程。主动对象仅有一个方法在给定时间执行，它扮演 监视器的角色，但不要求传统意义上的锁定。相反，来源于主动对象外部的方法调用是通过此对象汇集、编队和派发异步消息实现的。从专业化的Actor语言到 传统C代码的STA(Single-Threaded Apartment)式COM套件等，主动对象有很多种设计实现。
其他更高层次抽象也是需要的，比如描述和检测异步消息交换的协议。所有这些方法应该被整合起来构建一个统一的编程模型，从而满足各主要粒度层次的典型应用的并发要求。
对工具的要求
·我们需要何种工具
因为并行编程的固有难度和我们对它的不熟悉，必然需要更好的编程工具系统地帮助我们查漏补缺、调试程序、寻找性能瓶颈和测试程序。没有这些工具，并发将成为提高开发和测试人员生产率的障碍，导致并发软件成本更高，而质量更低劣。
并发会带来不同于顺序式代码的新型程序错误。数据竞争(同步不足或死锁造成)和活锁(不适当同步造成)缺陷难以发现和理解，因为其行为通常具有 不确定性且难以重现。传统调试方法，比如启动前设置断点再重新运行程序，对于执行路径和行为每次都可能发生变化的并发程序来说，无能为力。
在并发世界里，系统级的缺陷检测工具具有重大价值。这些工具利用静态程序分析法系统地探测程序所有可能的执行行为，因此它们能够捕捉到不能重现 的错误。尽管类似技术，比如模型检测，已经在天生支持并发的硬件的缺陷探测中获得重大成功，但在软件中非常困难。大多数情况下，软件的状态空间比硬件大得 多，因此这些系统探测虚拟状态的技术还有很多工作要做。无论是硬件还是软件，模块化和抽象都是提高分析可行性的关键。在硬件模型测试中，如果你能将ALU (arithmetic logic unit)拆分为一个个寄存器做独立分析，那么你的任务就变得很容易实现了。
这就引出了软件更难以分析的第二个原因：将软件切分为众多片段，做独立分析，然后合并结果去看它们如何一起工作要难得多。共享状态、不确定接口和格式不明的交互将使软件分析任务的挑战性大大增加。
目前，并发软件的缺陷检测工具是个热门研究领域。其中，微软研究院的KISS(Keep it Strictly Sequential)是项有前途的技术，它将多线程程序转化为包括了原始的不超过两个切换环境的线程的所有可能行为的顺序式程序。转换后的程序可以被大 量现存的顺序式工具分析，因此这些工具得以完成有限模型的并发缺陷检测工作。
即便我们取得了上述一些成绩，程序员仍然需要优秀的调试 工具帮助他们理解并行程序里的复杂和难以重现的交互行为。有两项常规技术可以收集这方面 信息。一是更好的日志跟踪工具，可以记录哪一个消息被送到了哪个进程或线程，进程和线程又访问了哪个对象，因此开发者可以回溯并部分理解程序的执行行为。 开发者也希望获得追踪跨线程因果关系(比如哪个消息传递到了主动对象，何时执行，导致哪一个别的消息传递到了其他主动对象)、回放、重排队列里的消息、步 进包含回调的异步调用模式，以及其他能力，借以检测代码的并发执行行为。第二个办法是重放执行，它能让程序员备份程序的执行历史，然后可重新执行一些代 码。重放调试的想法由来已久，但它的高成本和复杂性导致了被抛弃的下场。最近，虚拟机监视器(VMM，Virtual Machine Monitor)已经逐渐呈现出取代这两项技术的趋势，未来的并发世界里，这项技术很可能成为必需品。
并发世界也需要性能调试和调节 方面的新工具。并发引入了新的性能瓶颈，比如锁竞争(Lock Contention)、缓存一致性(Cache Coherence)管理和锁护送效应(Lock Convoys)等，这些问题依靠简单工具是难以察觉的。对计算机底层和程序并发结构更为敏感的新工具，将帮助我们更好的发现这些问题。
测试领域，也必须发生变化。并发程序，因其不确定性行为，更难于测试。用以跟踪语句和分支是否得到执行的简单代码覆盖测试方法，需要被扩展以支 持对其他并行执行代码的评估，否则测试将提供不符实际的反应程序执行完整度的优化结果图。另外，简单压力测试也需要通过更多地使用类似模块检测技术以探测 系统状态空间的系统级技术加以扩充。比如，Verisoft使用这些技术在寻找电话交换软件错误方面已经取得相当成功。现在，很多并发应用通过加大测试时 的压力大小来建立应用不太可能遭受严重竞争的信心。未来，这将愈加显得不够，软件开发者将必须以严格的确定性测试代替基于压力测试的想当然，来证明他们产 品的质量。
并行是关键
并发解决方案将是软件史上的一次重大变革。其难点不在于多核硬件的构建，二是让主流应用从持续爆炸式增长的CPU性能中获益的编程方式。
软件工业必须重归现存应用在新硬件上更快运行的跑道。为此，我们必须开始学习编写包含至少数十最好数百可分离任务(当然不是说同时处于活动状态)的并发应用。
并发也开启了新的可能，那就是让软件功能更多、能力更强。这就要求我们积极发挥想象力，找到挖掘并利用新处理器指数级增长的潜能的办法。
为了促成软件目标的早日实现，程序语言设计师、系统构建者和编程工具创造者需要开始努力思考并行，找到比目前成为并行程序构建基础的低层次线程 工具和显式同步更好的技术。我们需要更高层次的并行构建实现，借此更清楚表述开发人员的意图，以使程序的并行架构更加明晰，更容易理解，更能被工具验证。
