操作系统原理 —— 什么是进程互斥？以及进程互斥的实现方式（十四）

什么是进程互斥？

在操作系统中，有两种资源共享方式，一种是互斥共享方式，一种是同时共享方式。

互斥共享方式就是指在系统中的某些资源，虽然可以提供给多个进程使用，但一个时间段内只允许一个进程访问该资源。

这里就会有一个互斥的概念，一个时间段只允许一个进程访问，这就是进程互斥，

还有一个概念就是，我们把一个时间段内只允许一个进程使用的资源称之为临界资源，比如说摄像头、打印机都属于临界资源。

对于临界资源的访问，必须互斥的进行。进程互斥简单的来说：指当一个进程访问某些临界资源时，另一个想要访问该临界资源的进程必须等待。当前访问临界资源的进程访问结束，释放该资源之后，另一个进程才能去访问临界资源。

那既然有了这个互斥的概念，那各个进程又是如何保证对临界资源互斥访问呢？在操作系统中，如果想要访问临界资源，有这么几个步骤：

1、 entry section; 进入区，负责检查是否可以进入临界区，如果可以进入，则设置正在访问临界资源的标志(可以理解为上锁），以阻止其他进程同时进入临界区。

2、critical section; 临界区，访问临界区资源的那段代码

3、exit section; 退出区，负责解除正在访问临界资源的标志，可以理解为解锁。

4、remainder section; 剩余区，做其他处理。

有了以上这几个动作之后，为了实现对临界资源的互斥访问，同时保证系统整体性能，还需要遵循以下原则：

1、空闲让进：临界资源空闲时，可以允许一个请求进入临界区的进程立即进入临界区。

2、忙则等待：当已有进程进入临界区时，其实试图进入临界区的进程必须等待。

3、有限等待：对请求访问的进程，应保证能在有限时间内进入临界区，保证不会饥饿。

4、让权等待：当进程不能进入临界区时，应立即释放 CPU 执行权，防止进程忙等待。

进程互斥软件的实现方式

单标志算法

算法思想：两个进程在访问完临界区后，会把使用临界区的权限转交给另一个进程，也就是说每个进程进入临界区的权限，只能被另一个进程赋予。

举个例子：

先设置一个单标志，定一个变量，int turn = 0; 这个变量表示一个标志，标志哪个进程可以进入临界区。

我们一起来看下两个进程的代码：

P0 进程：

// 先判断自己是否能进入临界区
while(turn != 0) // 进入区，如果不等于0，那么这个循环会一直阻塞在这里
critical section; // 进入临界区
turn = 1； // 退出区，这个时候需要把进入临界区的权限，转交给另一个进程
remainder section // 剩余区，做一些额外的事情

P1 进程：

// 先判断自己是否能进入临界区
while(turn != 1) // 进入区，如果不等于0，那么这个循环会一直阻塞在这里
critical section; // 进入临界区
turn = 0； // 退出区，这个时候需要把进入临界区的权限，转交给另一个进程
remainder section // 剩余区，做一些额外的事情

这两段代码，简单的模拟了一下，两个进程互斥的情况，首先 turn 的初始值为 0，假设 P1 进程先执行，那么会一直卡在 while 循环那，一直等到 P1 的时间片用完了，发生调度，切换到 P0 进程开始执行。在这个时候 P0 可以进入临界区，并且执行完对应的代码之后，P0 会把临界区的权限，转交给另外一个进程，也是就是对应代码: turn = 1 ，当 P1 重新被 CPU 执行的时候，就可以进入临界区了。

因此，该算法可以实现：同一时刻最多只允许一个进程访问临界区。

但是大家思考一下，，这个算法有一个很明显的缺点，假设现在 P1 进程它执行完了，并且 P1 又把执行权转交给了 P0，但是 P0 它现在不需要使用临界资源，就会出现一种情况，临界资源是空闲的状态，P1 进程想要用，但是没权限，P0 又一直掌握了执行权，又不给 P1，所以违反了空闲让进原则。

双标志先检查算法

算法思想：设置一个布尔类型数组 flag[]，数组中各个元素用来标记各进程想要进入临界区的意愿。比如 flag[0] = true 表示 P0 进程想要进入临界区，每个进程在进入临界区之前先检查当前有没有别的进程想要进入临界区，如果没有，则把自己对应的标志改为 true，之后开始临界区。

我们还是看看代码吧，有一个 boolean flag[2]，初始值都是 false。

P0 进程：

while(flag[1]) // 进入区，先判断其他线程有没有想要使用临界资源的想法，如果有等待
flag[0] = true; // 进入区，如果没有，那么就把自己的对应的表示改为 true
critical section; // 进入临界区
flag[0] = false； // 退出区，使用完之后，把自己的标记成不需要使用了临界资源了
remainder section // 剩余区，做一些额外的事情

P1 进程：

while(flag[0]) // 进入区，先判断其他线程有没有想要使用临界资源的想法，如果有等待
flag[1] = true; // 进入区，如果没有，那么就把自己的对应的表示改为 true
critical section; // 进入临界区
flag[1] = false； // 退出区，使用完之后，把自己的标记成不需要使用了临界资源了
remainder section // 剩余区，做一些额外的事情

这种设计，就避免了刚刚单标志算法空闲让进的问题，但是大家仔细看看代码，在上面的代码中进入区有两行代码，这两个处理并没有保证原子性，在并发的情况下，就有可能 P0 进程 while 循环进去了还没来得及修改自己的标志，P1 进程也开始执行了，由于 P0 还没来及的修改自己的标志，所以 P1 的 while 循环也进去了，这样就会导致，两个进程都获得了临界资源，就违反了 忙则等待 的原则，因为两个进程都进入了临界区了。

双标志后检查算法

算法思想：该算法是基于双标志先检查算法的改进，只是在进入区两个操作调整了一下顺序，代码如下：
P0 进程：

flag[0] = true; // 进入区，先把自己的对应的表示改为 true
while(flag[1]) // 进入区，再判断其他线程有没有想要使用临界资源的想法，如果有等待
critical section; // 进入临界区
flag[0] = false； // 退出区，使用完之后，把自己的标记成不需要使用了临界资源了
remainder section // 剩余区，做一些额外的事情

P1 进程：

flag[1] = true; // 进入区，先把自己的对应的表示改为 true
while(flag[0])// 进入区，再判断其他线程有没有想要使用临界资源的想法，如果有等待
critical section; // 进入临界区
flag[1] = false； // 退出区，使用完之后，把自己的标记成不需要使用了临界资源了
remainder section // 剩余区，做一些额外的事情

这种算法存在很大的问题，还是在并发的场景下，P0进程把自己的标志修改为 true，此时 P1 同样也把自己的标志修改为 true，那么P0、P1 两个的 while 循环都会卡住，两个进程全部都不能进去临界区，并且临界资源是空闲的状态。

违反了空闲让进和有限等待的原则，各个进程都长期无法反问临界资源而产生饥饿现象。

皮特森 Peterson 算法

算法思想：结合双标志、单标志的思想，如果双方都争着进入临界区，那可以让进程尝试相互谦让的做法，具体还是看代码把：

有一个布尔数组 boolean flag[2]，初始值都是 false，还有一个标志 int turn = 0，表示优先让哪个进程进入临界区。

P0 进程：

flag[0] = true; // 进入区，先修改自己的对应的标志，表示自己想要进入临界区
turn = 1; // 进入区，可以优先让对方进入临界区
while(flag[1] && turn == 1)  // 如果对方想进，并且判断自己也可以优先对方先进入，那自己就进入等待
critical section; // 进入临界区
flag[0] = false； // 退出区，使用完之后，把自己的标记成不需要使用了临界资源了
remainder section // 剩余区，做一些额外的事情

P1 进程：

flag[1] = true; // 进入区，先修改自己的对应的标志，表示自己想要进入临界区
turn = 0; // 进入区，可以优先让对方进入临界区
while(flag[0] && turn == 0)  // 如果对方想进，并且判断自己也可以优先对方先进入，那自己就进入等待
critical section; // 进入临界区
flag[1] = false； // 退出区，使用完之后，把自己的标记成不需要使用了临界资源了
remainder section // 剩余区，做一些额外的事情

这个算法解决了前三种算法的缺点，遵循了空闲让进、忙着等待、有限等待三个原则，但是依然没有遵守让权等待的原则，如果自己获取不到进入临界区的权限，那么应该释放 CPU 的资源，而不是一直占有者。

好了，说完软件层面解决进程互斥的办法，在硬件上也有对应的解决办法，我们一起往下看：