【《现代操作系统 第4版》】4、进程间的通信之互斥

买面包问题

假设有两个人A、B要采购面包，首先查看冰箱中是否有面包，如果没有则离开家去超市购买面包，买来后把面包放到冰箱。
假设A、B的日程如下图所示。显然这会导致面包超买，如何保证最多只有一个人去买面包呢br>

如上图所示，进程A完成两次判断准备去执行买面包的操作时，由于发生上下文切换，切换到了B，对B来说，此时也是无面包无标签的状态，B也准备去执行买面包的操作。之后，又通过2次切换，从而导致面包出现了超买。

方案二

先留便签，后检查面包和便签

这个方案会由于上下文切换存在不会有人去买面包的情况：

这个方案可能导致没有人去买面包。

显然这个方案是可行的。但是它仍然存在如下的几个问题：

• 比较复杂，很难验证它的有效性
• 每个进程的代码都略有不同，如果进程过多的话处理起来过于复杂
• 当A在等待时，它不能做其他事，浪费CPU

方案五

结合上面的各种方案分析可知。就是由于存在上下文切换从而导致各种便签方案中的操作存在乱序，使得结果不可预知。那如果可以保证 “没有面包就去买面包” 这个操作始终只有一个进程来执行，就不会出现面包超买的问题。就像方案一一样，通过加锁即可实现始终只有一个人买面包。

进程间通信（Inter Process Communication，IPC）

对独立的进程来说，由于它不和其他进程通信和依赖，所以它是确定的、可重现的。
对于需要进行交互的进程来说，常常面临如下三个问题：

• 一个进程如何把信息传递给另一个进程
• 如何确保两个或更多的进程在关键活动中不会出现交叉
  • 买面包中如何确保只有一个进程去买面包
  • 简单的说就是如何使进程互斥执行
• 如何确定程序正确的执行
  • 比如进程A产生数据，进程B打印A产生的数据，如何保证进程A和进程B的顺序
  • 简单的说就是如何使进程同步工作

由于在不同地址空间进行通信的线程属于不同进程间的通信，所以除了第一个问题外，同步和互斥在多线程之间也存在，解决方式同进程

竞争(态)条件（race condition）

竞争(态)条件：当两个或多个进程读写某些共享资源时，最后的结果取决于对资源的访问顺序

买面包的例子中A和B之间就存在竞态条件，谁去买面包，取决于他们对便签或锁的访问顺序。
存在竞态条件的程序较难调试，而多核增长所带来的并行使得竞态条件越来越普遍。

互斥（mutual exclusion）

要避免产生竞态条件，就需要阻止多个进程同时读写共享资源，即需要一种机制来确保当一个进程在使用一个共享资源时，其他进程不能做同样的操作。这种机制就叫做互斥机制。

比如买面包例子中的方案一是通过对冰箱加锁从而实现了互斥。

临界区（critical setion）

对共享资源进行访问的程序片段称为临界区。如方案五中的加锁和释放锁之间的那段代码段，就是临界区。
使两个进程(或线程)不同时处于临界区中，就能够避免竞态条件。

使用临界区的互斥效果如下：

在上面代码中，变量 turn，初始值为 0 ，用于记录轮到哪个进程进入临界区，并检查或更新共享内存。
开始时，进程 0 检查 turn，发现其值为 0 ，于是进入临界区。进程 1 也发现其值为 0 ，所以在一个等待循环中不停的测试 turn，看其值何时变为 1。连续检查一个变量直到某个值出现为止，这种方法称为 。由于这种方式浪费 CPU 时间，所以这种方式通常应该要避免。只有在有理由认为等待时间是非常短的情况下，才能够使用忙等待。用于忙等待的锁，称为 。

这种方案类似买面包的方案四，确实能很好的解决问题。但是它有时会不满足的临界区规则。

假设进程 0 离开临界区时，它将 turn 的值设置为 1，以便允许进程 1 进入其临界区。随后进程 1 完成操作后很快便离开了临界区。此时两个进程都处于临界区之外，turn 的值又被设置为 0 。但是，如果进程 0 之后并不想立即进入临界区。比如 后存在一段逻辑，这就会导致这时进程1不能进入临界区，它必须等进程0再次进入临界区后才能继续进行。

这说明，如果一个进程比另一个进程的执行速度慢很多时，位于临界区外的进程可能会阻塞其他进程。显然这并不是一个好的方案。

Peterson算法

一开始，没有任何进程处于临界区中。

假设进程 0 和进程 1 顺序进入临界区：
进程 0 调用 。它通过设置数组元素和将 turn 置为 0 来表示它希望进入临界区。由于进程 1 并不想进入临界区，即 ，所以 很快便返回。如果进程 1 现在调用，进程 1 将在此处挂起直到 变为 FALSE，而这种情况只有在进程 0 调用 退出临界区时才会发生。

假设进程 0 和进程 1同时调用 。它们都将自己的进程存入 turn，此时，只有最后保存进去的进程号才有效，前一个进程的进程号会由于重写而丢失。假如进程 1 是最后存入的，则 turn 为 1 。当两个进程都运行到 的时候，进程 0 将不会循环并进入临界区，而进程 1 将会无限循环且不会进入临界区，直到进程 0 退出为止。

类似的算法还有Dekkers算法、Eisenberg-McGuire算法、Bakery算法等

总结

基于软件的解决方法，存在如下特点：

• 实现复杂
• 需要忙等待，浪费CPU时间

原子操作指令

基于软件的解决方法实现起来比较复杂，为了降低复杂度。硬件提供了一些同步原语，来辅助进入或退出临界区。比如中断禁用，原子操作指令等。 而操作系统通过硬件原语构造了锁、信号量等更高级的编程抽象来简化进程间的通信。

锁

锁是一个抽象的数据结构，它表示一个二进制状态（锁定/解锁），具有两个方法：

• Lock::Acquire() : 锁被释放前一直等待，然后得到锁
• Lock::Release()：释放锁，唤醒任何等待的进程

在买面包中的方案五中就是一种锁机制，显然，从编码上使用锁来实现临界区要比软件的实现方案简单的多。

现代CPU体系结构都提供一些特殊的原子操作指令来实现锁机制。比如TSL指令、XCHG指令。

TSL指令

TSL指令，即测试并加锁（test and set lock）指令，它对于如下操作：

• 从内存单元中读取值
• 测试该值是否为1（然后返回真或假）
• 内存单元值设置为1

注意，这虽然是3个操作，但是这些操作已经被封装成了一条机器指令，这3个操作不会被中断，也不会因上下文切换而分解为多个步骤。它们是一个整体，要么全部完成，要么全部失败。这种特性就是原子性。

执行 TSL 指令的 CPU 将会锁住内存总线，用来禁止其他 CPU 在这个指令结束之前访问内存。

为了使用 TSL 指令，要使用一个共享变量 lock 来协调对共享内存的访问。当 lock 为 0 时，任何进程都可以使用 TSL 指令将其设置为 1，并读写共享内存。当操作结束时，进程使用 指令将 lock 的值重新设置为 0 。

进程在进入临界区之前会先调用 ，判断是否进行循环，如果 lock 为 1 则进行忙等待，如果 lock 为 0 则进入临界区。在进程从临界区返回时它调用 ，这会把 lock 设置为 0 。

与基于临界区问题的所有解法一样，进程必须在正确的时间调用 enter_region 和 leave_region ，解法才能奏效。

使用 TSL 指令实现自旋锁

XCHG指令

XCHG （exchange）指令原子性的交换了两个内存中的值，本质上与 TSL 一样。Intel x86 CPU 在底层同步中使用 XCHG 指令。

优化忙等待

使用 TSL 指令如何避免忙等待呢鉴之前的进程管理，当一个进程等待某个事件时，可以将其挂到等待队列中让其等待，从而使其让出CPU的执行权，给其他进程使用。同理，在获取锁时，如果失败则将该进程加入等待队列中。进程退出临界区时，除了将LOCK置为1，同时还会去唤醒等待队列中的进程再次进行TSL指令来争夺锁。

如果临界区的执行时间很短，选择忙等待，因为它无需进行上下文切换
如果临界区的执行时间较长，远大于上下文切换的开销，则可以选择基于上下文切换的这种非忙等待方式。

原子操作指令锁的特征

• 优点
  • 适用于单处理器或者共享主存的多处理器中任意数量的进程同步
  • 简单并且容易证明
  • 支持多临界区
• 缺点
  • 忙等待浪费了 CPU 时间
  • 可能导致饥饿（忙等待的进程长时间得不到执行）
  • 死锁（比如优先级反转问题）

假设有2个进程 H 和 L，H 的优先级高于 L。而进程调度的规则是不论何时只要 H 进程处于就绪态 H 就开始运行。如果在某一时刻，L 处于临界区中，此时 H 变为就绪态，准备运行。现在 H 要开始忙等待，但由于当 H 就绪时 L 就不会被调度，导致 L 永远无法离开临界， 而这从而又导致了 H 一直处于忙等待，这种情况就是优先级反转问题。

来源：贫道法号说不得