上一篇计算机系统009 - 操作系统之进程中讲述了操作系统设立进程、线程的概念主要是为了便于切换管理，同时也提到，在单处理器结构系统中，进行进程或线程级别的切换可以在承担一定切换消耗后降低平均响应时长。而随着硬件技术的发展，主要是多处理器架构的兴起，操作系统中并行的概念也逐渐成为主流。

既然提到多处理器架构的兴起，也就再多说几句。最开始那段时间，也就是电气CPU的年代，CPU既重又笨。第一次飞跃是随着晶体管硬件技术的革新而来，主频得到了极大提升，随后的第二次飞跃则是由集成电路所推动。发展到了这里，CPU制造商却发现通过提升主频、缓存所能换来的提升效益与成本相比，性价比很低。自然地，有一波人就打起了量的主意。通过将多个CPU核心，甚至多个CPU本身集成入芯片，同时处理多个可分割的计算任务，达到降低平均执行时长的目的。简单的来说，就是通过增加更多的服务窗口，使得排队的时间减少，进而减少整体执行时间。

1. 并行

介绍其他内容之前，先对并行、并发两个概念稍加说明。理解这两个概念时可以类比程序和进程的概念，具体如下：

• 并发Concurrency
  Concurrency是指程序、算法或问题本身可分解为顺序无关或不完全依赖执行顺序单元的属性，从语法来讲，并发虽然是一个名词，但可以看成是表达为拥有某种能力的形容词。也就是说假如一个程序具有并发的属性，那么即使将分解后单元以乱序或局部顺序执行，最终结果也不会受影响，这为单元并列执行提供了基础。
  简而言之，并发是只程序在结构上拥有一种能力，与执行本身无关。

• 并行Parallelism
  如前所述，并行的全称可以视为并列执行，Parallelism指的是多个单元或多个任务正在同时执行，强调的是一种现象。如果说并发是静态的程序能力，那么并行就是这种能力动态发挥作用的现象本身。

插一句题外话，由于目前使用的大部分计算机系统概念都形成于西方，所使用的语言也以英文为主，汉化翻译的过程中，有时候很难找到十分贴切的词汇去映射抽象的概念本体，导致直面概念的中文词汇（如进程、线程、纤程、并行、并发）时很难获取到精确理解。这时候，还是建议先找到概念的英文表示，从英文本身的解释出发，融汇理解。

1.1 并行核心问题

回到并行本身，并行的最大特征是同时执行，那么对应的硬件前提就是切实存在多个CPU核心甚至多个CPU，以此支持线程、进程的调度。前面的章节中我们讲到，进程、线程本身是需要使用地址空间、栈空间、以及其他相关硬件资源的。按照单处理器架构执行时，始终能保证同一时刻，只会有一个进程或线程运行，所以在资源共享这一块不会出现太多问题。但在多处理器多核架构下多个进程、线程同时执行，随时有可能发生两个进程、线程需要使用同一资源（包括CPU时间、存储器、文件以及I/O设备等）的现象。

举个例子，大部分人应该都有包饺子的经历，假如现在有一碗馅料，里面只有一根勺子，那么当只有一个人在包饺子时，他可以随时获取到勺子的使用权，并在不用时将其闲置等待；假如现在还是一根勺子，但有两个人在包饺子，由于大家包饺子的节奏肯定不会绝对相同，那么在获取勺子使用权时就存在如下几种情况：

• 对方使用中，你只能选择等待
• 对方未使用，直接获取，使用期间如对方需使用，同样需等待
• 双方同一时刻伸手获取勺子使用权

前面两种还好，既不会太闲置，也能和谐进行。但第三种情况就尴尬了，到底谁该缩回伸出去的手？虽然无比尴尬，但既然发生了问题，终归还是要解决的。从包饺子的所遇到的问题中，可以发现并行的两大核心问题是同步和通信，同步时为了互斥，通信是为了合作。

1.2 同步Synchronization

同步，英文表示为Synchronization，生活中的解释是协调事件共同操作某一系统，而在计算机领域，这个同步指代两个方面的同步：

• 进程同步
  多个进程在某一特定位置进行连接或握手，以确保达成共识或基于指定次序执行。

• 数据同步
  数据同步是指保持同一数据集多个备份的一致性，或是保证数据完整性。

上述说明的关键点是确保事件的发生基于指定次序，万事总得讲究个先来后到，哪怕我比你早一毫秒碰到了勺子，那也是先来，理应优先响应，获得使用权。你要想获得勺子的使用权，可以先跟我确认，看我状态，看我心情给不给你用。如果我不给，那你就乖乖等着，等我用完了再用。

所以伴随着同步的是潜在互斥的结果，任何时刻，只允许一个人使用某一特定资源，比如内存中某一字节，又比如打印设备等。通常对于互斥的硬件层的支持有两种：

• 中断禁用
  一旦获得使用权后立即禁止中断，直到使用结束后重新允许中断。既然本进程无法被中断，自然就不存在资源冲突的问题。中断禁用的问题是只适用于单处理器结构的系统，多处理器结构中，每个CPU有自己的中断控制，而进程中只能禁止所分配到的CPU的中断，无法真正防止其他CPU中进程获取同一资源而引发冲突。

• 专用机器指令
  将两个动作在一个指令周期内完成来保证操作整体的原子性，实现互斥。如在一个指令周期内完成读-写或读-测试两条指令，指令执行期间会阻塞其他指令的访问，以达成资源级别的互斥。

1.3 通信

前面提到，假如我正在使用勺子，而你希望使用，那就必须等待我使用结束，或是跟我两目对视，会心一笑让中断下来让你先用。操作系统中，进程或线程也需要通过通信来确认资源当前使用情况，有效的信息能够帮助进程及时获取资源使用权。

通常进程（线程）之间会以如下三种状态共存：

• 双方都不知道对方存在
  双方都不知道对方的存在，那就只有操作系统掌握了双方的关系。例如两个进程都同时希望使用打印设备，假设该打印设备任一时刻只能服务于单个进程，那么操作系统就必须保证两者互斥，不去同时操作打印设备。当然，现在的打印设备会在打印执行单元前将打印任务序列化，所以同时提交也能支持，只不过内部依然是依次执行单个打印任务的。

• 双方间接知道对方的存在
  通过共享对象来达成通信，如生产者、消费者，除了生产、消费两个特性外，他们均不知道各自更多的信息。

• 双方直接知道对方的存在
  直接知道意味着知道对方进程的基本信息，如进程ID。有了进程ID，就可以建立两者通信的专用线路。类似而言，假如大家都在某一共享空间如留言板上匿名留言，为了继续通信，也只能在留言板上回复。而如果我知道对方真正ID，那么就可以直接私信进行交流了。

基于以上三种共存状态，进程间为了完成合作，也需要使用不同的通信机制。

2. 通信机制

对于通信机制的理解，应回归到适用的场景本身。

2.1 信号量Semaphore

在通信双方都不知道对方存在的条件下，要想完成通信，那么必须考虑通过操作系统完成同步，这一部分直接由操作系统全局统筹实现。而在双方间接知道对方的情况下，最典型的方法就是信号量。信号量的基本原理是：两个或多个进程可以通过简单的信号进行合作，一个进程可以被迫在某一位置停止，直到它接收到一个特定的信号。通过调整信号结构，理论上任何复杂的合作需求都可以得到满足。

信号量实质上可视为一个具有整数值的变量，该变量支持三个操作：

• 初始化，赋值一个非负整数
• signal()，离开临界区块时使用，增加信号量值，当信号量不为负值时，处于wait()中进程将恢复运行，进入临界区。
• wait()，进入临界区块时使用，减少信号量值，当信号量为负值时，被阻塞；为非负时，可以继续。

其逻辑可以换位到银行窗口服务与客户的关系，服务窗口数量就是信号量。

• 银行初始化提供了N个窗口，等价于信号量值初始化为N

• 客户来到银行大厅，使用wait()申请一个窗口服务，申请后N值减1

  • 如N-1>0，表明申请前N>1，即申请后仍有窗口富余
  • 如N-1=0，表明申请前N=1，即申请到了最后一个服务窗口
  • 如N-1<0，表明申请前N<=0，即原本就没有服务窗口

• 客户使用完服务窗口后，发出signal()信号，发出后N值加1。当N+1后不再为负值，原先被wait()阻塞的进程就能继续运行。即其他等待的客户就可以使用服务窗口了

信号量初始值代表着wait()被阻塞前所支持的进程/线程最大数目，当该值可为任意整数时，称为计数信号量。而如果信号量初始值只能为1，也就是说信号量值只能在0/1间变化，那么该信号量也称为二进制信号量。通常的实现称为Mutex，即互斥量。和广泛分布在整个程序中的计数信号量相比，Mutex通常只用在同一线程中，即signal()/wait()均应由同一线程调用。

2.2 管程(Monitor)

管程提供和信号量相似的功能，而且在使用上更加易于控制。管程由一至多个程序、一个初始化序列以及局部数据组合而成。其主要特征是：

• 只能通过管程提供的内部程序访问数据变量
• 每个进程通过管程提供的程序之一进行访问
• 任一时刻管程中只能执行一个程序，其他程序均被阻塞直到管程重新可用

前两个特征与面向对象封装类似，最后一个特征则是互斥的体现。简而言之，管程就是通过分配有限的访问渠道给进程，并保证任一时刻只能由一个渠道访问数据，达到保护数据的目的。再通俗一点，管程就像是一个有多扇门的房间，房间里面储存了一些物品，任一时刻只要有人进入房间，就将所有门反锁。完成对物品的操作后，再取消反锁，退出房间。

2.3 消息传递

和现实生活中一样，消息传递的目的是为了将某些讯息告知对方，便于对方及时做出反应。进程间传递消息也是为了告知对方发生了什么事件、切换到什么状态等变化。消息要想被双方理解，就要遵循相同的格式。通用的消息格式如下图所示：

除去消息类型，最主要的字段应该是源ID和目标ID，分别代表了消息的发送者和接收者。对于同一主机而言，这可以是相互区别的进程ID即可，对于网络中的不同主机而言，该字段则需添加上网络中进行唯一标示的IP地址。

3. 典型并行问题

要想进一步理解各种通信机制，还是要回归到问题本身。并行过程中之所以会产生问题，关键在于对同一资源的竞争，如果不能协调各进程/线程有序访问该资源，就会使得依赖于资源值的进程因为值错误而导致运行错误。

3.1 生产-消费者问题

生产-消费者问题也称为有限缓冲问题，是一个经典的多线程同步问题。该问题中有如下三个主体：

• 固定大小的共享缓冲区
• 生产者线程，负责重复生成一定数据并存放到缓冲区中
• 消费者线程，负责重复消耗缓冲区中数据

问题关键在于确保生产者不会在缓冲区满时写入数据，消费者也不会在缓冲区中为空时消耗数据。换句话说，缓冲区中可用部分的多少是关键数据。

3.2 读者-写者问题

读者-写者问题发生在多个线程读或写同一共享资源时，通常，任一时刻只允许有一个线程写资源，且如有线程正在写资源，则所有读操作也会被阻塞。如无线程正在写，则多个线程可同时读取该资源。

通用的解决方案是使用读写锁，该锁中可将读与写操作互斥，而在读本身上使用信号量进行计数即可。

4. 总结

本篇概念较多，希望通过多次对比例证能够对问题进行降解。文中提及并行由来、并行过程中潜在典型问题以及相应的解决办法，但到目前为止，仍止步于可能由于对单一资源竞争引发冲突。事实上，再往坏处想，假如涉及到的资源也从单一变成了多个（如哲学家就餐问题），那么多个进程/线程与多个资源间的相互竞争则会引发更大的灾难。而这，也就是不得不单独开篇去阐述“死锁”的缘由。