进程同步机制（软件同步，硬件同步，信 量，管程）

进程同步机制

• • 一、进程同步的几个重要概念
  • 二、软件同步机制
  • • 2.1 双标志位法
  • 三、硬件同步机制
  • • 3.1 关中断
    • 3.2 测试并建立（Test-and-Set，TS）指令
    • 3.3 对换指令
  • 四、信 量机制
  • • 4.1 整型信 量
    • 4.2 记录型信 量
    • 4.3 AND型信 量
    • 4.4 信 量集
  • 五、管程机制

进程的同步机制包含软件同步机制、硬件同步机制、信 量机制等，也就是这些机制，可以保证程序并发执行时的可再现性，在介绍之前，我们先来看下几个概念：

一、进程同步的几个重要概念

进程同步机制的主要任务，是对多个相关的进程在执行次序上进行协调，使并发执行的诸多进程之间能够按照一定的规则共享系统资源，并能很好的相互合作，从而使程序之间的执行具有可再现性。

• 1. 进程间的两种制约关系：

  • 间接相互制约（互斥）：因为进程在并发执行的时候共享临界资源而形成的相互制约的关系，需要对临界资源互斥地访问；
  • 直接制约关系（同步）：多个进程之间为完成同一任务而相互合作而形成的制约关系。

• 2. 临界资源：
  指同一时刻只允许一个进程可以该问的资源称之为临界资源，诸进程之间采取互斥方式，实现对临界资源的共享。

• 3. 临界区
  进程中访问临界资源的那段代码。
  每个进程在进入临界区之前，应先对欲访问的临界资源的“大门”状态进行检测，如果“大门”敞开，进程便可进入临界区，并将临界区的“大门”关上；否则就表示有进程在临界区内，当前进程无法进入临界区。

• 4. 指令
  指令就是机器语言的一个语句，它是一组有意义的二进制代码，因为是机器语言的一条指令，所以指令就可以等价于是原子性的，只有在执行完一条指令后才会去响应中断。

• 5. 原语
  由若干条指令组成的，用户完成一定功能的一个过程。原语操作的一个特点就是“原子操作”，
  因此原语在执行的过程中不允许被中断。原子操作在系统态下执行，常驻内存。

• 同步机制应遵循的规则

  • 1. 空闲让进：当临界区的“大门”敞开时，应当允许一个请求的进入临界区的进程立即进入临界区。
  • 2. 忙则等待：当临界区的“大门”关闭时，因而其他试图进入临界区的进程必须等待，以保证对临界资源的互斥访问。
  • 3. 有限等待：对要求进入临界区的进程，应保证有限的时间能进入自已的临界区，以免陷入“死等” 状态。
  • 4. 让权等待：当进程不能进入自已的临界区时，应立即释放处理机，以免进程陷入“忙等”状态。

忙等 和 死等 都是没能进入临界区，它们的区别如下：

• 死等： 对行死等的进程来说，这个进程可能是处于阻塞状态，等着别的进程将其唤醒（signal 原语），但是如果唤醒原语一直无法执行，对于阻塞的进程来说，就是一直处于死等的状态，是无法获得处理机的。
• 忙等：忙等状态比较容易理解，处于忙等状态的进程是一直占有处理机去不断的判断临界区是否可以进入，在此期间，进程一直在运行，这就是忙等状态。有一点需要注意的是，忙等是非常可怕的，因为处于忙等的进程会一直霸占处理机的，相当于陷入死循环了。 忙等的状态在单CPU 系统中是无法被打破的，只能系统重启解决。

不管是“忙等”还是“死等”，都是对OS 有害的，都应该努力避免。

二、软件同步机制

其实说到使用软件来实现同步机制，大家想到最多的应该就是 Java 多线程，Java 通过锁，synchronized，信 量等机制实现了线程的同步，但是线程间是共享父进程中的所有资源的。
但是当线程之间，如果需要共享系统资源时，进程之间很难直接通过软件来进行交流，对系统资源的互斥共享就很麻烦，需要借助硬件资源来完成同步，需要在内存中单独使用一块区域来保存进程是否在临界区内的标志。

2.1 双标志位法

先来看一段代码：

代码逻辑很清晰，就是进程p1 或 p2 想进入临界区之前，先去判断对方是否在临界区内，如果在的话，就一直循环等待，束则就进入临界区，然后挂锁。
第一眼看起来没啥问题，但是如果进程在执行期间，比如p1 中的while 判断完比后，进入，在inside1 = true 之前发生了中断，p1 进入了临界区，但锁没来得及挂上；因此如果此时 进程p2 运行时，也可以进入临界区，这种情况下两个进程同时进入了临界区，进程的执行就会出现错误。

虽然前面的是小概率事件，但也是可能存在的。

针对这个问题，你可能会想，我在判断之前挂上锁呢，我们把代码的须序调整一下：

这样的话，进程 p1 和 p2 在并发执行的时候就没有问题了。
我们来看这样一种情况，p1 先执行，挂锁成功，假设在成功之后，p1 发生了中断，进程p2 开始执行，此时p2 同样也可以挂锁，但是在判断是否可以进入临界区时，无法成功，会一直循环中断判断，当p1 恢复再次执行时，尴尬的事情发生了，p1 也无法进入临界区了，因为 p2 同样把锁给锁上了。

双标志位法先检查可能会让两个进程同时进入临界区，双标志位法后检查可能会让两个进程都无法进入临界区，形成死锁问题。

三、硬件同步机制

前面我们在软件同步机制里，都是在落锁和判断之间发生中断，乃至导致无法实现互斥进入临界区，
那么我们是不是可以在这个期间不允许发生中断呢/p>

这就需要用到硬件了。

3.1 关中断

这个方法简单有效，进程在落锁和判断之间不是有可能发生中断么，那我们在测试之前关闭中断（OS 内核不响应中断信 ），到测试并上锁后在打开中断。
这样可以保证两个操作之间的连续性，保证临界资源的互斥访问。

3.2 测试并建立（Test-and-Set，TS）指令

我们使用关中断来解决落锁与判断之间不允许响应中断，但是我们如果把这两个执行变成一条指令呢br> 这样是不是就可以保证中断不会在落锁和判断之间被响应/p>

我们可以借助一条硬件指令 — “测试并建立” 指令TS（Test-and-Set）来实现临界资源的互斥访问。

TS 指令一般描述如下：

我们可以把TS 指令看成上面的TS 函数的执行过程，其执行过程是一可分割的，即是一条原语。
当 lock 值为 false 时，表示临界资源空闲，当lock 的值为true 时，表示该资源正在被使用。

使用TS 指令管理临界区时，需要为每个临界资源设置一个布尔变量lock。 当有进程需要进入临界区时，需要先用TS 指令尝试临界区对应的那把锁。
如果返回true，临界区空闲，可以进入，并落锁 ，阻止别的进程再进入临界区；
如果返回fase，则必须要循环请求，直到TS 返回的值变为 true。

3.3 对换指令

该指令也称为 swap 指令，用于交换两个字的内容，其处理过程描述如下：

swap 指令 和 TS 指令 类似，也需要为每个临界资源设置一个布尔变量lock，不同的进程中使用一个局部变量key 字段去替换出lock中的值 ，通过key 的值就可以判断出临界资源是否空闲。

有一点需要注意的，因为原语是将多个指令合并成一个指令，在原语的执行过程中也是不响应中断的，使之成为原子操作，
这个期间，等于是屏蔽中断，也就等价于我们讲的第一种硬件方式—– 关中断，
因此原语操作的指令长序应该是短小精悍的，这样才能保证系统的效率。

四、信 量机制

信 量机制是1965年迪杰斯特拉（Edsger Wybe Dijkstra）提出的一种卓有成效的进程同步工具。
信 量机制在长期的应用中得到了很大的发展，从整型信 量经记录型信 量，进而发展为“信 量集”机制，在目前来讲，信 量。

需要着重说明的一点是：
信 量除了初始化外，仅能被通过两个标准的原子操作和来访问，这两个操作也被称为P、V操作，这几个操作都是原语操作。

4.1 整型信 量

整型信 量是最开始由迪杰斯特拉定义的，整型信 量也很简单，里面只有一个表示资源的数量的整形量，
一般使用S符 来表示，整型信 量下的wait和signal操作可描述如下：

因为wait和signal操作是原子的，因此他们在执行的过程中是不可被中断的。
也就是说当一个进程在修改某个信 量时，没有其他的进程可以同时对该信 量进行修改。

需要注意的是，整型信 量的wait操作，只要是信 量S

还有就是，把信 量的初值置为1，表示只允许一个进程访问临界资源，此时的信 量就可以转换为互斥信 量，用于完成进程的互斥（对所有的信 量机制都是一样）。

4.2 记录型信 量

?为了解决整型信 量存在的忙等问题，应当采取让权等待原则。
但是又会出现一个新的问题，如果多个进程并发请求访问临界资源，除了第一个抢到了信 量外，其余的进程都应该释放处理机，但是这些等待的进程要如何保存呢/p>

为此，除了wait操作需要遵循让权等待原则，还需在信 量中增加一个进程的链表指针list，用与链接上面描述的多个等待访问临界资源的进程。
也因为记录了等待的进程，这种信 量集之被称为记录型信 量。

记录型信 量具体的描述以及对应的wait和signal操作如下所示：

? 在记录型型 量中，S->value的初值表示系统中某类资源的数目；对它每次wait操作，意味进程请求一个单位的该类资源，使得系统中可分配的该类资源数减少一个，因此描述为S->value–；
当S.valuelist中。

我们再来分析下signal操作，首先释放一个单位资源（S->value++），然后判断是否有进程在等待申请信 量，如果有的话，就应该调用wakeup原语从等待队列（list所链接的进程队列）中唤醒一个进程。

通过上面的描述，我们来说一下在记录型型 量中，value值所代表的意义：

1. value>0，此时表示系统中还剩余的该类资源的数量；
2. value=0，此时恰好处于一个平衡状态，系统中的资源分配完了，同样也没有进程在等待资源，即list队列中是没有等待进程的；
3. value，此时，value的绝对值表示有多少个进程在等待申请信 量，也即是list队列的长度。并且P、V操作必须成对的出现，有一个P操作就必定有一个与之配对的V操作（当为互斥操作时，它们同处于同一进程当为同步操作时，则不在同一进程中出现）。

4.3 AND型信 量

AND信 量正如其名，其基本思想是：
将进程在整个运行过程中需要所有资源，一次性的全部分配给进程，待进程使用完后再一起释放。

AND 信 量可以满足某些进程需要申请多个资源后才可以执行任务的场景，并且AND 信 量可以解决死锁问题，
比始哲学家进餐问题中，一次给哲学家分配左右两支筷子，那么就不会有哲学家会因为吃不到而饿死了。

AND 信 量使用的还是记录型信 量的数据结构，下面是 Swait 操作和 Ssignal 操作：