前言

本文的主要内容是进程同步、进程互斥以及信号量机制等基础知识的介绍，包括进程同步和进程互斥的基本内容、进程互斥的软件和硬件实现方法以及信号量机制的简要介绍，重点理解信号量机制这部分的内容。

一、进程同步和进程互斥

同步也称直接制约关系，它是指为完成某种任务而建立的两个或多个进程，因为需要在某些位置上协调这些进程的工作次序而产生的制约关系，进程间的直接制约关系就源于它们之间的相互合作。
前面已经提到过两种资源共享方式，即互斥共享方式和同时共享方式。把一个时间段内只允许一个进程使用的资源称为临界资源，许多物理设备诸如摄像头和打印机等都属于临界资源，还有一些变量、数据、内存缓冲区等也是临界资源。对临界资源的访问必须互斥的进行。
互斥也称间接制约关系，进程互斥指的是当一个进程访问某临界资源时，另一个想要访问该临界资源的进程必须等待，只有当前访问临界资源的进程访问结束并释放该资源之后，另一个进程才能去访问临界资源。
对临界资源的互斥访问可以在逻辑上分为四个部分：
①进入区：负责检查是否可以进入临界区，若可以进入，则应设置正在访问临界资源的标志，这个标志类似于上锁，以阻止其他进程同时进入临界区。
②临界区：访问临界资源的代码段。
③退出区：负责解除正在访问临界资源的标志，这个标志类似于解锁。
④剩余区：做一些其他的处理。
进入区和退出区是负责实现互斥的代码段，临界区也称为临界段。
进程互斥应遵循的四个原则：
①空闲让进。临界区空闲时，可以允许一个请求进入临界区的进程立即进入临界区。
②忙则等待。当已有进程进入临界区时，其他试图进入临界区的进程必须等待。
③有限等待。对请求访问的进程，应该保证能在有限时间内进入临界区，即保证其不会饥饿。
④让权等待。当进程不能进入临界区时，应立即释放处理机，防止进程忙等待。
对进程同步和进程互斥这部分内容简单的总结一下，如下图所示。

二、进程互斥的实现方式

1、软件实现

进程互斥的软件实现方式有单标志法、双标志先检查法、双标志后检查法和 Peterson 算法，注意理解各个算法的思想和原理。

①单标志法

算法思想：两个进程在访问完临界区后会把使用临界区的权限转交给另一个进程，也就是说，每个进程进入临界区的权限只能被另一个进程赋予。
单标志法的代码实现过程如下图所示。

可以看到，这个算法是可以实现同一时刻最多只允许一个进程访问临界区的。通过代码可以分析，对临界区的访问是按照 p0—>p1—>p0—>p1 …这样轮流访问的，但是这种方式存在的问题是，如果此时允许进入临界区的进程是 p0 ，而 p0 一直不访问临界区，那么虽然此时临界区有空闲，但是并不允许 p1 访问。因此，单标志法违背了空闲让进的原则。

②双标志先检查法

算法思想：设置一个布尔型数组，数组中各个元素用来标记各进程想进入临界区的意愿，每个进程在进入临界区之前需要先检查当前有没有别的进程想进入临界区，如果没有，则把自身对应的标志设为 true，之后开始访问临界区。
双标志先检查法的代码实现过程如下图所示。

若按照1-5-2-6 … 这样的顺序执行，进程 p0 和进程 p1 将会同时访问临界区。因为进程 p0 和进程 p1 会并发执行，即进入区的“检查”和“上锁”这两个处理不是一气呵成的，在“检查”后“上锁”前可能发生进程的切换。因此，双标志先检查法违背了忙则等待的原则。

③双标志后检查法

算法思想：针对双标志先检查法的改进，采用先“上锁”后“检查”的方法来避免两个进程同时进入临界区的问题。
双标志后检查法的代码实现过程如下图所示。

若按照1-5-2-6 … 这样的顺序执行，进程 p0 和进程 p1 将都无法进入临界区，因为标志位都置为了true，所以会一直卡在while循环这里，两个进程谁也无法进入临界区。因此，双标志后检查法违背了空闲让进和有限等待的原则，还会因各进程长期无法访问临界资源而产生饥饿现象。

④Peterson 算法

算法思想：双标志后检查法中两个进程都争着进入临界区，但是互不相让，最后两个都无法进入临界区，Gary L. Peterson 提出了一种方法，如果双方都争着想进入临界区，那可以让进程尝试“孔融让梨”，主动地让对方先使用临界区。
Peterson 算法的代码实现过程如下图所示。

这样即使按照1-6-2-7-3-8 … 这样的顺序，也就是两个进程都有想进入临界区的意愿，也都想让对方先进入，但是这样不会陷入循环中谁也进入不了临界区，因为在一个进程时间片用完切换到另一个进程时，会发现 turn 值发生了变化，因此循环结束，该进程成功访问到临界区资源。
Peterson 算法用软件方法解决了进程互斥问题，遵循了空闲让进、忙则等待、有限等待三个原则，但是依然未遵循让权等待的原则(进程暂时无法进入临界区，但依然会占用CPU运行while循环进入忙等状态)。该算法相较于前三种软件实现方法来说是最好的，但仍然不够好。
对进程互斥的软件实现方式这部分内容简单的总结一下，如下图所示。

2、硬件实现

进程互斥的硬件实现方式有中断屏蔽方法、TestAndSet 指令(TS/TSL指令)和 Swap 指令(XCHG指令)，注意理解各个算法的原理和优缺点。

①中断屏蔽方法

中断屏蔽方法是利用开中断指令和关中断指令实现的，其与原语的实现思想相同，即在某进程开始访问临界区到结束访问为止都不允许被中断，因此就不会发生进程切换，也不可能发生两个进程同时访问临界区的情况。
中断屏蔽方法的优点：简单且高效。
中断屏蔽方法的缺点：不适用于多处理机(因为可能发生两个处理机上的两个进程同时访问临界资源的情况)；只适用于操作系统内核进程，不适用于用户进程。

②TestAndSet 指令(TS/TSL指令)

TestAndSet 指令简称 TS 指令，TestAndSet 指令有时也写为TestAndSetLock 指令，因此也简称 TSL 指令。
TS 指令是用硬件实现的，执行的过程不允许被中断，只能一气呵成，下图是用 C 语言描述的逻辑。

分析上述代码，若刚开始 lock 是 false，则返回的 old 值为 false，while 循环条件不满足，直接跳过循环，进入临界区。若刚开始 lock 是 true，则返回的 old 值为 true，while 循环条件满足，会一直循环，直到当前访问临界区的进程在退出区进行解锁。
TestAndSet 指令相比于软件实现方法把“上锁”和“检查”操作用硬件的方式变成了一气呵成的原子操作。
TestAndSet 指令优点：实现简单，无需像软件实现方法那样严格检查是否会有逻辑漏洞；适用于多处理机环境。
TestAndSet 指令缺点：不满足让权等待原则，暂时无法进入临界区的进程会占用 CPU 并循环执行，从而导致忙等。

③Swap 指令(XCHG指令)

Swap 指令在有的地方叫做 Exchange 指令，简称 XCHG 指令。Swap 指令和 TestAndSet 指令在实现上有很多相似的地方。
Swap 指令是用硬件实现的，执行的过程不允许中断，只能一气呵成，下图是用 C 语言描述的逻辑。

Swap 指令的优缺点和 TestAndSet 指令的优缺点相同。
对进程互斥的硬件实现方式这部分内容简单的总结一下，如下图所示。

三、信号量机制

1965年，荷兰学者 Dijkstra (迪杰斯特拉)提出了一种卓有成效的实现进程互斥和进程同步的方法——信号量机制。
用户进程可以通过使用操作系统提供的一对原语来对信号量进行操作，信号量其实就是一个变量，它可以是一个整数，也可以是更复杂的记录型变量，我们可以用一个信号量来表示系统中某种资源的数量，比如系统中有一台打印机，就可以设置一个初值为1的信号量。
一对原语指的是 wait(S) 原语和 signal(S) 原语，可以把原语理解为我们自己写的函数，函数名分别是 wait 和 signal，括号里的信号量 S 就是函数调用时传入的一个参数。wait 和 signal 原语常简称为 P、V 操作(来自荷兰语 proberen 和 verhogen)，常将 wait(S) 和 signal(S) 写作 P(S) 和 V(S)。
P、V 操作必须成对出现，缺少 P 操作就不能保证临界资源的互斥访问，缺少 V 操作会导致资源永不被释放，等待进程永不被唤醒。

1、整型信号量

用一个整数型的变量作为信号量来表示系统中某种资源的数量。
整型信号量与普通整数变量的区别是其对信号量的操作只有初始化、P 操作和 V 操作三种。
下图是用 C 语言描述的整型信号量的逻辑。

该方法仍然不满足让权等待的原则，会产生忙等，因此又提出了记录型信号量的方法。

2、记录型信号量

记录型信号量用记录型数据结构表示信号量。
下图是用 C 语言描述的记录型信号量的逻辑。

上面代码的解释如下：
其中 S.value 的初始值表示系统中某种资源的数目。
对信号量 S 的一次 P 操作意味着进程请求一个单位的该类资源，因此需要执行 S.value–，表示该类资源数目减1，当 S.value < 0 时表示该类资源已经分配完毕，因此进程应调用 block 原语进行自我阻塞，也就是当前运行的进程从运行态转换为阻塞态，主动放弃处理机，并插入到该类资源的等待队列 S.L 中。可以看出来，该机制遵循了让权等待的原则，不会出现忙等现象。
对信号量 S 的一次 V 操作意味着进程释放一个单位的该类资源，因此需要执行 S.value++，表示该类资源数目加1，若加1后仍是 S.value <= 0，表示依然有进程在等待该类资源，因此调用 wakeup 原语唤醒等待队列中的第一个进程，被唤醒的进程从阻塞态转换为就绪态。
下图是用记录型信号量举的例子。

对整型信号量和记录型信号量这部分内容简单的总结一下，如下图所示。

3、信号量机制实现进程同步

信号量机制实现进程同步时，首先要分析哪些地方需要实现同步关系，然后设置同步信号量 S，将其初值设置为0，然后保证在前操作之后执行 V(S)，在后操作之前执行 P(S)。
下图是用信号量机制实现进程同步的一个例子，其中进程2中的代码4需要在进程1中的代码2执行完之后再执行。

简单总结上面的例子，如果代码段的先后操作和预期一致，则正常执行，后操作不会阻塞；若代码段的先后操作和预期不符，则后操作会执行 block 原语主动请求阻塞，等先操作执行完后，信号量 S 变为0，V 操作中再执行 wakeup 唤醒原语唤醒后操作，这样顺序就按照我们的预想执行了。

4、信号量机制实现前驱关系

前驱关系其实就是多个进程同步问题。
下图是信号量机制实现前驱关系的例子。

保证在每一对前驱关系中的前操作之后执行 V 操作，在后操作之前执行 P 操作即可。
对进程互斥、同步和前驱关系这部分内容简单的总结一下，如下图所示。

总结

以上就是操作系统——进程同步、进程互斥及其实现方式、信号量机制的所有内容了，本文中介绍到的 P、V 操作是重点，进程同步和进程互斥过程中什么时候使用 P 操作，什么时候使用 V 操作是需要好好理解并掌握的内容。
参考视频：
进程同步、进程互斥
进程互斥的软件实现方式
进程互斥的硬件实现方式
信号量机制
用信号量机制实现进程互斥、同步、前驱关系