并行程序设计分为共享内存和消息驱动（其实就是分布式内存）两种，

共享内存：所有CPU共内存，所有CPU由一个操作系统控制的，例如Windows和Linux/UNIX，目前流行的多核、多CPU机器都是属于这种；

消息驱动：其实就是分布式内存，CPU由不同的操作系统控制，不同的CPU之间通过网络通信。例如网格Grid是通过因特网通信、集群Cluster是通过局域网通信、MPP是通过专有的高速网络通信。

通过上面的对比，聪明的读者估计很快就想到了这两种系统并行程序实现方式的差异：

共享内存：通过操作系统的多进程多线程来完成并行任务，通过进程间通信来完成协作；

消息驱动：通过多台机器来完成并行任务，通过消息来完成协作。(MPP物理上看是一台机器，逻辑上是多台机器)。

当然，由于消息驱动系统中每个处理单元都是一*立的机器，对这*立的机器本身当然也可以通过共享内存来实现并行处理。

对于多进程和多线程来说，最有代表性且最常见的的莫过于Windows和Linux（作为UNIX类操作系统的代表，下同）这两个操作系统了。

真是冤家路窄，Windows和Linux这对冤家在这里又碰面了！！

当然，我这里不是要挑起Windows和Linux谁优谁劣的争论，对于一个真正的技术人来说，Windows和Linux本身并没有优劣之分，只有在不同的使用场景下用谁会更好的问题。之所以将Windows和Linux拿来对比，是因为对比更加容易让人理解，记忆也更加深刻！

下面我们首先从多进程和多线程的实现机制方面来对比Windows和Linux。

多进程多线程实现机制

说起进程和线程，估计大家都会立刻想起那句耳熟能详的解释“进程是资源分配的最小单位，线程是运行的最小单位”！。

理论上来说这是对的，但实际上来说就不一定了，例如Windows有进程和线程的概念，而传统UNIX却只有进程的概念（例如经典的《UNIX环境高级编程》中就没有多线程的概念，但Solaris、AIX等又有另外的实现，此处暂且不表），Linux也有进程和线程的概念，但实现机制和Windows又不一样，真是林子大了什么鸟都有：）

有几个进程、线程相关的概念首先要简单介绍一下：

1.1   概念介绍

1.1.1  进程

资源分配最小单位，有的操作系统还是运行最小单位；

1.1.2   线程

运行最小单位，也是CPU调度的最小单位；

1.1.3   ULT、KLT

用户态线程和内核态线程；主要的区分就是“谁来管理”线程，用户态是用户管理，内核态是内核管理（但肯定要提供一些API，例如创建）。

简单对比两者优劣势：

1）可移植性：因为ULT完全在用户态实现线程，因此也就和具体的内核没有什么关系，可移植性方面ULT略胜一筹；

2）可扩展性：ULT是由用户控制的，因此扩展也就容易；相反，KLT扩展就很不容易，基本上只能受制于具体的操作系统内核；

3）性能：由于ULT的线程是在用户态，对应的内核部分还是一个进程，因此ULT就没有办法利用多处理器的优势，而KLT就可以通过调度将线程分布在多个处理上运行，这样KLT的性能高得多；另外，一个ULT的线程阻塞，所有的线程都阻塞，而KLT一个线程阻塞不会影响其它线程。

4）编程复杂度：ULT的所有管理工作都要由用户来完成，而KLT仅仅需要调用API接口，因此ULT要比KLT复杂的多；

1.1.4   POSIX

为了解决不同操作系统之间移植时接口不兼容而制定的接口标准，详见*解释：http://zh.wikipedia.org/wiki/POSIX。

1.1.5  NPTL

为了解决Linux原有线程实现机制的缺陷而创立的一个开源项目，从2.4开始就有发布版本采用NPTL来实现多线程支持了。详见*解释http://zh.wikipedia.org/wiki/Native_POSIX_Thread_Library。

1.1.6   LWP

Lightweight Process，轻量级进程，看名字有点奇怪，为什么叫轻量级进程呢？为什么又要用轻量级线程呢？

看了前面ULT和KLT的比较，估计大家也发现了一个问题：所谓的ULT，因为不能利用多处理器的优势和线程互相阻塞，其实完全不能堪重任，但对于传统UNIX和Linux这类操作系统，内核设计和实现的时候就没有线程这种对象，那怎么实现多线程呢？

天才们于是想出了LWP这个招数，说白了这就是一个“山寨版的进程”，完全具有了山寨的一切特征：

文件系统是原来的进程的；

文件描述符是原来的进程的；

信号处理是原来的进程的；

地址空间是原来的进程的；

但就是进程ID不是原来的进程的，你说像不像BlackBerry的山寨版BlockBerry？

详情请参考*解释：http://en.wikipedia.org/wiki/Light-weight_process

1.2  详细对比

1.2.1  Windows

在此要向Windows致敬：至少相比Linux来说，Windows在线程上的支持是Linux不能比的（不要跟我提DOS哈）！

Windows的实现机制简单来说就是前面提到的KLT，即Windows在内核级别支持线程。每个Windows进程至少有一个线程，系统调度的时候也是调度线程。

当创建一个进程时，系统会自动创建它的第一个线程，称为主线程。然后，该线程可以创建其他的线程，而这些线程又能创建更多的线程。

Windows已经提供了线程编程系列的API，这里就不详述了。

1.2.2  Linux

Linux不同的版本有不同的实现，2.0~2.4实现的是俗称LinuxThreads的多线程方式，到了2.6，基本上都是NPTL的方式了。下面我们分别介绍。

1.2.2.1 LinuxThreads

注：以下内容主要参考“杨沙洲 (mailto:pubb@163.net?subject=Linux 线程实现机制分析&cc=pubb@163.net)国防科技大学计算机学院”的“Linux 线程实现机制分析”。

这种实现本质上是一种LWP的实现方式，即通过轻量级进程来模拟线程，内核并不知道有线程这个概念，在内核看来，都是进程。

Linux采用的“一对一”的线程模型，即一个LWP对应一个线程。这个模型最大的好处是线程调度由内核完成了，而其他线程操作（同步、取消）等都是核外的线程库函数完成的。

在LinuxThreads中，专门为每一个进程构造了一个管理线程，负责处理线程相关的管理工作。当进程第一次调用pthread_create()创建一个线程的时候就会创建并启动管理线程。然后管理线程再来创建用户请求的线程。也就是说，用户在调用pthread_create后，先是创建了管理线程，再由管理线程创建了用户的线程。

这种通过LWP的方式来模拟线程的实现看起来还是比较巧妙的，但也存在一些比较严重的问题：

1）线程ID和进程ID的问题

按照POSIX的定义，同一进程的所有的线程应该共享同一个进程和父进程ID，而Linux的这种LWP方式显然不能满足这一点。

2）信号处理问题

异步信号是以进程为单位分发的，而Linux的线程本质上每个都是一个进程，且没有进程组的概念，所以某些缺省信号难以做到对所有线程有效，例如SIGSTOP和SIGCONT，就无法将整个进程挂起，而只能将某个线程挂起。

3）线程总数问题

LinuxThreads将每个进程的线程最大数目定义为1024，但实际上这个数值还受到整个系统的总进程数限制，这又是由于线程其实是核心进程。

4)管理线程问题

管理线程容易成为瓶颈，这是这种结构的通病；同时，管理线程又负责用户线程的清理工作，因此，尽管管理线程已经屏蔽了大部分的信号，但一旦管理线程死亡，用户线程就不得不手工清理了，而且用户线程并不知道管理线程的状态，之后的线程创建等请求将无人处理。

5)同步问题

LinuxThreads中的线程同步很大程度上是建立在信号基础上的，这种通过内核复杂的信号处理机制的同步方式，效率一直是个问题。

6）其他POSIX兼容性问题

Linux中很多系统调用，按照语义都是与进程相关的，比如nice、setuid、setrlimit等，在目前的LinuxThreads中，这些调用都仅仅影响调用者线程。

7）实时性问题

线程的引入有一定的实时性考虑，但LinuxThreads暂时不支持，比如调度选项，目前还没有实现。不仅LinuxThreads如此，标准的Linux在实时性上考虑都很少。

1.2.2.2   NPTL的实现

NPTL，Native POSIX Thread Library，天生的POSIX线程库。从命名上也可以看出所谓的NPTL就是针对原来的LinuxThreads的，不然为啥叫“Native”呢：）

本质上来说，NPTL还是一个LWP的实现机制，但相对原有LinuxThreads来说，做了很多的改进。下面我们看一下NPTL如何解决原有LinuxThreads实现机制的缺陷。

1）线程ID和进程ID问题

新的exec函数能够创建和原有进程ID一样ID的新进程，这样所有的线程ID都是一样的；且/Proc目录下只会显示进程的初始线程（初始线程就代表整个进程，类似于Windows的进程中第一个线程s），不会再像以前LinuxThreads机制时每个线程在proc目录下都有记录。

2）信号处理问题

内核实现了POSIX要求的线程信号处理机制，发送给进程的信号将由内核分发给一个合适的线程处理，对于致命和全局的信号（例如Stop，Continue， Pending）,所有的线程都同步处理。

3）线程总数问题

内核经过扩展，能够处理任意数量的线程。PID空间经过扩展后，在IA-32系统上能够最大支持20亿线程。

4）管理线程问题

去掉管理进程，管理进程的任务由扩展后的clone函数完成；增加了exit_group的系统调用，用于退出整个进程；

5）信号同步问题

实现了一个叫做Futex（Fase Userspace Mutex，注意不是Mutex）机制用来完成线程间同步，Futex的主要操作是在用户态完成的，这样解决了依靠内核信号机制进行同步的效率问题。详细请参考http://zh.wikipedia.org/wiki/Futex。

当然，NPTL虽然做了很多改进，但依然不是100% POSIX兼容的，LinuxThreads的第6个和第7个问题在NPTL机制下依然没有解决，但这并不掩盖NPTL带来的巨大改进，下面是性能对比图：

NPTL官方的文档：http://people.redhat.com/drepper/nptl-design.pdf。

1.3    对决？

看了前面的分析，大家可能纳闷了，这哪里是对决哦？全部是讲Linux的实现了。

其实我也郁闷，本来应该更加详细的介绍Windows实现机制的，但由于Linux的不争气，全部用来变成对它的分析了。

进程间通信

多进程和多线程本质上就是将原来一个进程或者线程处理的任务分给了多个进程或者线程，也可以说是将原来一个CPU处理的任务分给了多个CPU处理，类似于随着生产力的发展，原来一个人包打天下的个人英雄主义时代被分工合作的团队取代一样。

既然是一个团队，就必然涉及到分工合作问题，并行程序的设计本质上就是解决“分工”和“合作”的问题。其中“分工”主要是后面讲到“并行程序设计模式”，而“合作”则是本篇重点要讨论的问题。

相信大家做过项目的都知道所谓合作其实就是“通信”和“冲突解决”。常见的“通信”有开会、电话、邮件、甚至QQ等，无非是为了交换信息，而“冲突解决”其实就是为了解决资源不足，大家抢着用的问题。

可能许多菜鸟、大侠以及网上的很多博客都和和我开始一样，将“通信”和“冲突解决”混为一谈了，一说到进程间通信，就会口若悬河的冒出一大堆名词：管道、信号量、消息队列、互斥。。。。。这里面有的是“通信”（管道、消息队列），有的是“冲突解决”（信号量、互斥），并不是一类东东。

下面我们分别从“通信”和“冲突解决”两方面来比较Windows和Linux。

1.1        Windows进程间通信

标准（例如《Windows系统编程》里面提到的）的Windows进程间通信有三个：匿名管道、命名管道（又叫FIFO）、邮槽（MailSlot），实际上常用的还有一个：共享内存。之所以说它不是标准的，我猜测可能是共享内存设计本意不是为了进程间通信用的，而是为了内存映射用的。

1.1.1   匿名管道

顾名思义：匿名管道就是“匿名”的“管道”。为什么这样拆开呢？正所谓名如其人，通过名字我们就可以了解大概这是个什么东东。

匿名：之所以叫做“匿名”，当然是因为没有名字了，但为什么会没有名字呢？没有名字又有什么好处呢？其实很简单了，“匿名”当然是不想让其它人知道了，说白了这个“匿名管道”就是只给父子进程用的，别人不需要也不可能知道名字的。

管道：说道管道，你是否想到了“下水管道”、“煤气管道”等？对了，和这些管道本质上是一样的，就是可以传送东西的，所以叫做管道。要注意匿名管道是“单向流通”（也叫半双工）的。

1.1.2   命名管道

聪明的你看到这个名字肯定就会产生如下两个想法，我们就一一来解答：

1）和匿名管道看起来很像

是的，命名管道就是相对匿名管道来说的。

2）命名管道和匿名管道有什么差别？

1.1.3   邮槽

邮槽和命名管道类似，都是有名字的，也可以跨网络进行通信，既然是这样，为什么Windows还要设计邮槽呢？其实也没有什么玄虚，说简单点就是管道都是“点对点”的（命名管道虽然是一对多，但具体的通信还是1对1进行的），而邮槽是为了提供一种“广播”通信机制（王婆卖瓜一下：微软还不如将邮槽叫做“广播”：-P）。

下面我们看看邮槽和命名管道的对比：

1.1.4   共享内存

就像前面提到的一样，共享内存并不是正统的进程间通信的机制，共享内存其实只不过是Windows“内存映射文件”的一个特殊用法而已。

然而实际*享内存在进程间通信却比较常见，从使用方便性上来说，共享内存其实没有前面介绍的方便（必须结合互斥、事件等一起使用），但为什么应用比较多呢？关键在于共享内存性能很高。

共享内存应该是介于匿名管道和命名管道之间的通信方式，为什么这么说呢？主要有如下几个原因：

1）共享内存和匿名管道相比：共享内存有名称，可用于多个进程通信，这点像命名管道；

2）共享内存和命名管道相比：共享内存只能在一台机器上使用，不能跨网络，这点和匿名管道类似

3）共享内存是双向的，这点又和命名管道类似。

1.2        Linux进程间通信

介绍完了Windows，介绍Linux就相对轻松一些了，虽然Windows和Linux形同水火，打的不可开交，但实际上说白了，它们并不是两个完全不同的东东，在很多的地方都相似，进程间通信也不例外。

Linux的进程间通信主要有管道、命名管道、消息队列、共享内存、信号量，其中信号量Semaphore其实是为了同步用的，因此我这里就放到下一篇关于同步的博文中去分析。另外，很多人将信号signal也作为进程间通信，但我认为信号更像是为了同步而设计的，因此也放到下一篇博文中去分析。

1.2.1   管道

Linux的管道和Windows的管道是一样的，这里就不详细介绍了。

需要注意的是Linux多了一个叫做“流管道”的东东，除了流管道是全双工（也就是双向）外，流管道其它都和管道一样。

1.2.2   命名管道

Linux的命名管道和Windows的命名管道差异就比较大了，主要对比如下：

1.2.3   消息队列

这个是Linux特有的进程通信方式，我感觉它有点像邮槽，都能够实现一对多。不过消息队列和邮槽的方向正好相反：消息队列是一堆进程向一个进程发，邮槽是一个进程向一堆进程发。

消息队列还有一个牛B的特性就是消息队列的消息可以分优先级，进程不一定非要取第一个消息，也可以取指定消息优先级的消息。因此这个特性又可用于多对多通信，即：不同的收方指定不同的优先级。当然实际应用中应该没人会这么用，直接创建多个消息队列是最方便、最简单、效率最高的方法。

1.2.4   共享内存

Linux的共享内存机制和Windows本质上是一样的，即都是利用了内存映射的功能。不过Linux将“内存映射到内存”包装成了“共享内存”，而不像Windows，在使用的时候通过指定不同的参数来区分是“内存映射到文件”还是“共享内存”，所以各位大侠可能在网上有时能够看到有人将“内存映射”和“共享内存”都说是Linux进程间通信的方式，原因就在这里。

1.3        OS间进程通信

前面分别介绍了Windows和Linux进程间通信，看到这里，你肯定会有疑问：什么？还有OS进程间通信？不同OS之间的进程是不可能通信的！

是的，从操作系统层面来说，Windows的进程和Linux的进程当然是不能通信的，但如果从网络层面来说，两台机器总是要通信的吧？不可能Windows只能和Windows通信，Linux只和Linux通信吧？

说到这里估计你已经恍然大悟了：不就是Socket通信么？

是的，就是它，虽然它是用于机器间通信的，但大家想想，机器间通信不就是各个应用程序通信么？各个应用程序不就是对应操作系统中的一个或者多个进程么？

Windows和Linux对决(线程间同步)

1.1        Windows线程同步

1.1.1   关键代码区Critical Section

所谓“关键代码区”，相信大家看名字也能理解个大概了。首先：它很关键，第二：它是代码区。之所以关键，当然目的就是每次只能一个线程能够进入；既然是代码区，那就是只能在一组拥有同样代码的线程中用。

那什么情况下会用到关键代码区呢？当然是要保护多个线程都会用到的东西了，说到这里，想必你已经猜到了：全局变量和静态变量。

1.1.2   互斥Mutex

互斥看起来和关键代码区是一样的，都是每次都是只允许一个线程使用。但互斥和关键代码区相比，具有如下特点：

1.1.3   信号量Semaphore

信号量本质上就是一个计数器，当计数器大于0时就意味着被保护的对象可用。每次申请计数器就减1，释放就加1.

信号量和互斥体相比，一个最明显的差别就在于互斥体每次只能有一个线程进行访问，而信号量可以有多个线程进行访问。

看到这里，大家可能都像我开始一样存在这样的问题：如果将信号量最大值设置为1，那么不就是相当于互斥量了吗？

看起来是一样的，而且在有些系统上也确实是这样的，据说是互斥体底层就是信号量来实现的，或者干脆就没有互斥体（例如传统UNIX），但在有的系统上还是有差别的，差别在于：申请和释放是否要同一个线程完成，Windows就是这种形式。互斥体要求同一线程来申请和释放，而信号量就可以由不同的线程申请和释放（但是我很难想象这样做有什么好处，难倒要给一个线程集中获取信号量，再来通知另外的线程工作？）。

1.1.4   事件Event

事件本质上是一个系统信号，即：发生了某件事情后，发一个信号给其它关心这件事情的线程。

从事件的本质上来看，事件不是为了资源保护的，而是为了线程间通知用的。举个简单的例子：Socket接收完一个消息后，将其放入队列，然后需要通知消息处理线程进行处理。

大家想想，如果没有事件通知会怎么样呢？那接收线程只能设一个定时器或者循环，定时甚至循环去查询队列中是否有消息，这种定时和循环处理是对系统性能的极大浪费，所以，有了事件后，就不用这么浪费了。

1.2        Linux线程同步

介绍完Windows，Linux介绍就很方便了，就像上一篇博文提到的一样，Windows和Linux其实很多地方相似，线程同步也不例外。

1.2.1   关键代码区？？？

不好意思，Linux没有这个东东。

1.2.2   互斥Mutex

Linux和Windows是一样的，这里就不详细介绍了，需要注意的是传统UNIX并没有互斥这个东东，传统UNIX的互斥是通过二元信号量（即最大值为1）来实现的。

1.2.3   信号量Semaphore

需要注意的是Linux中信号量有两种：一种是内核POSIX标准的信号量，一种是用户态的传统UNIX IPC信号量。两者的差别如下：

POSIX信号量和Windows的信号量是一样的。

1.2.4   条件变量Conditions

看到这个名字有点莫名其妙，条件变量和线程同步有什么关系呢？

但其实是Linux（或者是POSIX）的名字取得不好才导致我们很难理解，本质上条件变量就是Windows的事件，作用也是一样的。唉，如果Linux或者POSIX不想和Windows同名，改成叫“通知”也能让我们这些小虾多省点脑力啊：）

1.2.5   信号Signal

类似于“共享内存”也是一种进程间通信的方式一样，我把信号也列进来作为线程同步的一种，因为本质上信号不是为了线程间同步而设计的，但我们可以利用其作为线程同步来使用。

如何使用信号呢？既然信号本身就是一种通知（还记得上面我建议将“条件变量”建议改名为什么吗？），那我们就按照通知来使用了，例如：A做完了某事，发一个信号给B，B收到后开始启动做另外一件事。

请注意：和“条件变量”不同的是，条件变量支持广播机制，而信号只能是点对点，因此实际使用中应该还是“条件变量”方便一些。当然如果是传统UNIX，那就只能利用信号来进行通知了。

===============================================================================

注：看我的博客的朋友可能会发现一个现象，我几乎从来不介绍详细的函数或者API，而基本上都在“归纳、总结、对比”。这是我个人的一个风格或者理解吧，我认为函数或者API用的时候查一下就可以了，而在分析和设计的时候，关键是要知道有哪些东西可以给我们用，而且要知道我们具体究竟应该用哪个，因此在平时就必须多归纳、总结、对比，而不是背住各种函数和API。

多机协作（又叫分布式处理）

嗯，费了九牛二虎之力，终于将Windows和Linux对比完了。你是否准备伸个懒腰，喝杯热咖啡，听点音乐来放松一下呢？

别急，革命尚未成功，同志还需努力，铁还得趁热打。还记得第二篇博文里面总结的两种并行实现技术没有？一个是“多进程多线程”，另一个是“多机协作”，到目前为止我们基本上只把“多进程多线程”分析完毕了，还有另外一个“多机协作”没有分析，本篇我们就探讨一下“多机协作”这种实现机制。

不过事先申明，由于“多机协作”这种实现机制范围太广：小到普通的双机、中到模拟地球运算的大型机或者巨型机、又如Google这样NB的公司发明的分布式文件系统、再到现在热热闹闹的“云计算”、或者大家最常用的BT、电骡等P2P技术都属于这一范畴，且实现太过复杂，不同的系统实现机制也相差很大，限于本人能力，只能“蜻蜓点水”了，如有兴趣研究，推荐《分布式系统概念与设计》这本书，我也没有读过，不过据说还不错。

幸运的是“多机协作”实现机制和“多核编程”并没有什么关系，因此即使蜻蜓点水对大家的多核设计水平影响不大。

废话了半天，让我们转到正题上。虽然前面提到了“多机协作”范围很广，实现机制也各不相同，但既然大家都划到“多机协作”这一类里面，自然有一些基因是相同的。那么就让我们对“多机协作”进行一次基因图谱制作，看看究竟有哪些共同基因。

u       只有一种通信方式：消息。

是的，看到这个不要惊讶，虽然实现形式可以多种多样，但本质上来说，多机协作系统只有一种通信方式：消息。不管是基于TCP/IP的Socket消息，还是基于电信网7号信令的MAP消息，还是内部光纤通信的XX消息，本质上这些都是消息通信。和“多进程多线程”多种多样的方式来比，显得有点单薄，因此也就增大了设计的难度。

u       没有多机同步机制

看到这个是不是更加吃惊？但现实就是如此残酷，多机协作没有一个现成可用的同步机制来实现诸如互斥、事件、信号量等同步功能。

但实际应用中你的应用又不得不用到这些东东，例如Google的分布式文件系统，因此你要自己去实现这些东东，这也增大了设计的难度。

u       没有“老大”

这里的老大不是指黑社会的老大哈，相反它是一个好公仆，这个“老大”负责全局的事物管理。嗯，你可能会说“多进程多线程”里面也没有老大的啊？

多进程多线程之间确实没有天然的老大，谁当老大完全是由我们设计人员决定的，但还有一个我们无法决定的老大：操作系统！操作系统在“多进程多线程”实现机制里面完成了众多我们没有怎么关注但却不得不用到的功能：进程线程创建、调度、隔离、通信、同步等。

在“多机协作”实现机制中，唯一的老大就是我们设计人员！你要决定如何隔离、如何调度、如何通信、如何同步等所有这些事情，因此设计难度又上一层楼！

举个最简单的例子：多进程多线程实现机制中，时间或者时钟都是操作系统来控制和提供；而在多机协作中，光一个时间或者时钟同步就能让你累个半死！！

看完上面的初步分析，我们可以得出一个这样的结论：多机协作只有一个消息通信，然后要基于消息通信来实现同步、通信、管理、调度、分布式处理等所有你所需要的功能！所以“多机协作”要比“多进程多线程”设计复杂得多。

看到这里，你是否泄气了呢？本着“不抛弃，不放弃”的精神，我们还是要勇敢面对，而且幸好现在也有很多多机协作的解决方案了。流行的有三个：微软的COM/DCOM、ORG的CORBA、SUN的Java RMI。这些多机协作（或者叫分布式）方案封装了很多底层的通信、调用、同步等机制，使得我们能够简单的实现多机协作。

详细的方案请各位参考COM、CORBA、RMI的相关文档。