并发编程..

mezilla

引子
2005年3月，C++大师Herb Sutter在Dr.Dobb’s Journal上发表了一篇名为《免费的午餐已经结束》的文章，一石激起千层浪，该文引起了社区广大程序员的热烈讨论。文章指出：现在的程序员对效率、伸缩性、吞吐量等一系列性能指标相当忽视，很多性能问题都依仗越来越快的CPU来解决。但CPU的速度很快将偏离摩尔定律的轨迹，并达到一定的极限。所以，越来越多的应用程序将不得不直面性能问题。而解决这些问题的办法就是采用并发编程技术。当你读到这里的时候，第一感觉可能就是“不敢苟同”，觉得作者在危言耸听，妖言惑众，过分渲染并发编程的重要性。
其实不然，正如Herb Sutter所说，由于串行处理速度的限制已经把“并发编程”推到了聚光灯下，串行化技术在程序设计中的砥柱地位在未来必将被取代，一个多核与并发编程的时代必将到来。由于当今大多数程序员对并发编程还是一片空白，因此深入了解和学习并发编程已经刻不容缓。甚至，还有人提出了“不懂并发编程的程序员，不是一个合格的程序员”的观点。不管愿意接受与否，“免费的午餐”的确已经结束。
何为并发
大家也许还记得那个懵懂的中学时代吧，手捧课本，端坐教室，听华罗庚大师讲“烧水沏茶”的故事。他将统筹学原理运用到日常生活中，竟然产生事半功倍的效果，给了我们很大的启示。手敲键盘之际，调试程序之余，与同事神侃之时，我们是否应该坐下来静静地思考一下，能否将“烧水沏茶”的道理运用到程序设计与开发的过程中呢？能否在编写程序的时候把类似于劈材、打水、烧水、拿茶叶、泡茶等一系列的程序行为并发执行？答案是：完全可以。这正是“并发编程”的绝妙之处，也是本文将要给大家介绍的内容。
首先，我们来看一看“何为并发”。如果两个事件在同一时间间隔内发生就称之为并发（concurrency）。两个或多个任务在同一时间间隔内执行叫做并发执行。
我们再通过一个现实生活中的例子来阐述并发的机理。现在满大街都是减肥广告，减肥成了众多人乐此不疲的话题。但是正确的减肥方法并不能单纯地依靠节食或药物，一个好的减肥方案往往需要同时考虑“适当的节食”和“一定强度的锻炼”。我们可以把“节食”和“锻炼”看作是并发执行的任务，也就是说改进饮食结构和正规的身体训练必须要在同一时间间隔内发生，这样才可以达到减肥的目的。通过这个例子，我们可以得出这样一个结论：任何一个逻辑控制流和另外的逻辑控制流在某一时间段内相互重叠，这就是并发。并发技术使得应用程序在同一时间段内能够做更多的工作，极大地提高了效率，同时也增强了程序的可伸缩性。
软件并发的基本层次
并发总体上可分为三个层次：软件级的并发、操作系统级的并发和硬件级的并发。一般来讲，硬件级的并发和操作系统级的并发都会支持软件级的并发，由于操作系统级并发和硬件级的并发不是我们普通程序员所能支配的，所以我们着重关注软件级的并发。
并行和分布式编程是达到软件级并发的两种基本途径。它们是两种不同的，但有时又相互交叉的编程方法。并行编程技术是将程序分配给单个或多个处理器运行，这些处理器通常在某一个物理或虚拟的计算机内；而分布式编程技术是将程序分配给两个或多个处理器运行，这些处理器可能在也可能不在同一个计算机中。在纯粹的并行程序中，并发执行的部分往往都是同一个程序中的某些部分，而在分布式程序中，这些并发执行的部分通常往往被实现成分离的程序。这两者之间的区别及程序的典型结构如图1和图2所示：


图1 并行程序的典型系统结构

图2分布式程序的典型系统结构

一般而言，软件级的并发可分为如下几个层次：
1.         指令级的并发
当一条单指令中的多个部分被同时执行时，便产生了指令级的并发。这种并发执行对象的划分粒度是最小的，以指令或指令中的某一部分为单位。下面我们来看一个简单的指令级并发实例，如图3所示。


例如代码中的(a+b)和(c-d)部分，就能够同时执行。这种并发通常由编译器指令所支持，而不受程序员的直接控制。关于指令级的并发，可以参看《Intel C++9.0 迈向多核CPU时代的终极优化利器》（2005年第7期《程序员》）一文中的“编译器自动并行化”部分。
2.         例程（函数/程序）级的并发
如果应用程序中的某一逻辑可以分解成若干互不相干的函数，那么就可以将这些函数分配给不同的进程或线程，让这些函数并发执行来提高工作效率。这种并发执行对象的划分粒度较小，以函数为单位，次之于指令级并发。在实际的程序开发过程中，这种级别的并发是最常见的一种。笔者曾经参与过一个项目，所负责的部分里有一个模块要求将各种图像格式转换成JPG格式，同时获取相关图像数据（长、宽、高、角版/切版、DPI值等），并写入数据库中。这个模块最终就是用函数级的并发技术完成的。设置一个函数完成图像转换，另一个函数完成图像数据的获取，同时写入数据库。将这两个函数分别分配给不同的线程来执行，并在一个合适的点进行同步，如果任何一个函数失败，那么都将删除另外一个已经生成的记录。
3.         对象级的并发
这种并发执行对象的划分粒度较大，通常以对象为单位。当然，这些对象要满足一定的条件，不违背流程执行的先后顺序。如果满足以上条件，我们就可以把每个对象分配给不同的进程或线程，根据一些中间件标准，比如CORBA、ICE等，每个对象甚至可以被分配给同一网络上的不同计算机或不同网络上的不同的计算机上执行，这样就实现了对象级的并发执行。
4.         应用级的并发
这一级别的并发，相信大家并不陌生。现代操作系统都能同时并行运行数个应用程序，比如，笔者在键盘上敲下上面这些文字的同时，耳朵上还带着耳机，欣赏着美妙的音乐，这不就是典型的应用级的并发吗？这种级别的并发性可以看作是一种将单个内核用来运行多个应用程序的策略。
构建并发程序的几种机制
从上文可以看出，并发性不仅仅局限于内核，它也可以在应用程序中扮演重要角色。如例程级的并发，基于例程级并发的应用程序称为并发程序（concurrent program）。例程级的并发在很多方面都有其优势，如在多处理器上并行计算、访问慢速设备、人机交互和为多个网络客户端提供服务等等。
现代操作系统提供了三种基本的构造并发程序的机制，以下所讲述的原理不仅仅局限于windows操作系统。
1.         进程
这种并发性是指通过将程序分解成多个进程来完成，即每个逻辑控制流都是一个进程，由内核负责调度和维护。因为进程有独立的虚拟地址空间，想要和其他进程进行通信，则需要使用某种显式的进程间通讯（IPC）机制，这是基于进程设计方法的一个缺点。基于进程设计的另外一个缺点就是往往速度比较慢，因为进程控制和IPC的开销都很高。
2.         I/O多路复用
在这种形式的并发编程中，应用程序在一个进程的上下文中显式地调度它们自己的逻辑流。逻辑流被模型化为状态机，作为数据到达文件描述符的结果，主程序显式地从一个状态转换到另一个状态。因为程序是一个单独的进程，所以所有的流都共享同一地址空间。
对Unix /Linux熟悉的读者对这一机制并不陌生。在Linux下提供了select/poll/epoll等各种方法，在BSD一类系统中，还提供了Kqueue方法。
I/O多路复用技术可以用作并发事件驱动程序的基础。在事件驱动中，流是作为某种事件的结果前进的。服务器使用I/O多路复用，借助select之类的函数，检测事件的发生。很明显，采用这类方法设计程序，将使程序变得很复杂。
3.         线程
除了将程序分解成多个进程来执行外，还可以分解成多个线程来执行。线程是运行在一个单一进程上下文中的逻辑流，由内核负责调度。一个线程就是运行在一个进程上下文中的一个逻辑流。如典型的windows完成端口IOCP，就是利用线程池来提供服务。
并发程序设计的难点
在软件开发和设计过程中，串行化编程的思想已经根深蒂固，以至于很多程序员都发觉难以适应，仍然固守着串行编程的习惯。然而在并行编程世界中所有的一切都已经发生了变化。在并行编程世界中，程序可以被分解成多个任务，并且每个任务都可以在相同的时间点执行，每个任务又可以被分配给多个线程来执行。程序执行的顺序和位置通常是不可预知的，多个任务能够在任意处理器上同时开始执行，但是不确定首先完成哪个任务，按照什么次序来完成这些任务，以及由什么处理器来执行这些任务。除了多个任务能够并行执行外，单个任务也可能具有能同时执行的部分和子任务。此时就不得不对并行执行的任务加以协调，让这些任务之间进行彼此通信，以便在它们所完成的作业之间实现同步。
编写并发程序，主要存在着以下三大基本的挑战：
1.         确认问题领域的环境中存在的固有并行性；
2.         将软件适当地分解成两个或多个任务，这些任务可以在同一时刻执行，即这些任务可以被并发执行；
3.         协调上述过程中所分配的任务，使软件正确而高效地运行，从而达到预期的目的。
用一句话概括这三点就是：发现并确认、分解、通信和同步。
无论使用哪种并发机制，都会存在着如下几种障碍：对共享数据的并发访问，目前提出的解决方案是通过对信号量的P/V原语操作来进行同步，当然也存在着其他同步技术，比如JAVA的多线程就是用一种叫做JAVA监控器的机制来进行同步。
并发同时也引入了一些其他问题，比如：被调用的函数必须具有一种称为线程安全的属性。一个函数被称为线程安全的，当且仅当该函数被多个并发线程反复地调用时，它会一直产生正确的结果。有一类重要的线程安全函数，叫做可重入函数，其特点就是：当这类函数被多个线程调用时，不会引用任何共享数据。可重入性函数是线程安全函数的一个真子集，他们之间的关系如下图所示：


                图4 可重入函数、线程安全和线程不安全函数之间的集合关系

竞争和死锁也是并发编程中出现的一类典型问题。当程序员错误的假设逻辑流该如何调度时，就会发生竞争，若调度产生错误，就有可能发生一个流等待一个永远不会发生的事件或流，就会产生死锁。
总结
本文只起一个抛砖引玉的作用，并发编程博大精深，非一两篇文章所能阐述透彻。由于现行的大多数编程语言都没有支持并行性的关键字（是否所有的语言都不支持，笔者不敢枉下结论），所以需要我们自己在实际的编程过程中摸索前进。但也不需要我们白手起家，业界提供了不少支持并发编程的标准和库，例如比较流行的有MPICH/PVM/MICO等。最普遍的并行和分布式编程环境是集群、MPP和SMP计算机。笔者希望和所有的并发编程爱好者结交朋友，可以通过
normalnotebook@126.com
联系。并在此非常感谢我MM为我修改这篇文章，功劳属于你。
参考文献
[1] Cameron Hughes ,Tracey Hughes.Parallel and Distributed Programming Using C++
[2] Herb Sutter.The Free Lunch Is Over: A Fundamental Turn Toward Concurrency in Software
[3] Randal E.Bryant,David O’Hallaron.深入理解计算机系统






本文来自ChinaUnix博客，如果查看原文请点：http://blog.chinaunix.net/u/20996/showart_255921.html