232_进程互斥的软件实现方法
# 2.3_2_进程互斥的软件实现方法
各位同学大家好。在上个小节中，我们介绍了进城互斥和进程同步的相关概念，从这个小节开始，我们会介绍进程互持和进程同步的一些具体的实现方法
这个小节我们先介绍进程互斥的几种软件实现方法，包括单标志法、双标志先检查法，双标志后检查法，还有 Peterson 算法。在学习小节的过程当中，大家需要注意理解各个算法的思想原理，并且结合上一小节学习的实现互斥的 4 个逻辑部分，也就是什么进入区、临界区、退出区剩余区知识点，还要结合实现互斥要遵循的 4 个原则，来对各个算法进行具体的分析。
# 单标志法
那么我们先来看一下第一个算法叫单标志法，这个算法的思想是在每个进程访问完临界区之后，会把使用临界区访问临界区的权限转交给另外一个进程，也就是说每一个进程它是否能进入临界区，这个事情其实是另一个进程说了算说了算的，两个进程会交替的使用临界区。
那么我们具体用代码来看一下，在系统当中会设置一个叫做 turn 的变量，这个变量是用来表示当前允许访问临界区的进程号，那么在这个例子当中，我们默认它 turn 的初始值为 0，也就是表示刚开始是可以由 0 号进程 p0 进入临界区进行访问
那么 p0 和 p1 两个进程对临界区访问的代码分别是这个样子
我们来结合代码具体分析一下。首先 turn 的值初始值是 0，所以也就意味着刚开始只允许 p0 进程进入临界区。而如果刚开始是 p1 进程上处理机运行的话，那么当 p1 运行到这一句，也就是进入区的检查的语句的时候，那么他会发现 turn 这个值此时是 0 不等于 1，也就是说此时并不允许一号进程进入临界区，所以由于此时 while 这个循环的循环条件是满足的，turn 等于 0 不等于 1，所以 p1 进程它会一直被卡在 5 这条语句这会一直进行循环检查，一直到 p1 进程的时间片，给它分配的时间片用完了，然后发生调度之后 p0 进程上处理机运行。
P0 进程执行的第一句也就是进入区的语句，由于此时 turn 是等于 0 的，所以 p0 进程的 while 循环的条件并不满足，所以他在检查之后会跳过这个循环，然后顺利的进入二，也就是顺利的进入临界区，开始访问临界区。如果说他在访问临界区的过程当中，又一次发生了进程调度，进程切换，切换回了 p1 进程的话，那么由于此时 turn 这个值依然还保持 0，不变还没有被修改，所以 p1 这个进程还是会继续被卡在 5 这个语句，这会一直循环检查，然后一直到它的时间片用完，然后又切换回 p0，p0 又得以继续往下执行。一直到 p0 把临界区访问结束之后，他会在退出区这儿，把 turn 这个值也就是允许进入临界区的进程号，把它修改为一，把访问临界区的权限让给谦让给 p1 进程，
然后 p1 进程再上处理机执行，它就可以跳过循环，然后 p1 进程也可以顺利的访问临界区，一直到 p1 访问完临界区，临界在退出区的时候，又把访问临界区的权限访交还给 p0 进程，又把 turn 变为 0。
所以可以看到刚才的分析过程中，我们会发现这个算法单标志法它其实是可以实现所谓的互斥的，也就是说同一时刻最多只会有一个进程在访问临界区，但是同时这个算法也有它很明显的一个缺点，就是刚才我们的分析也表明了，对临界区的访问其实一定是按照 p0，p1，p0，p1 这样交替的轮流来访问的，所以这个特性带来的问题是，如果刚开始可以访问临界区的进程是 p0 进程，那么如果 p0 进程一直不访问临界区的话，那么 turn 这个值一直会保持零不变。这样的话即使 P1 此时想进入临界区，由于 turn 的值一直保持为 0，所以 p1 一直会被卡在这个循环这。
因此即使此时临界区是空闲的，暂时没有任何一个进程进入，并且此时有一个进程，p1 明确的表示自己想要进入临界区，但是由于这个算法的限制，它只要 p0 没有先访问的话，那么 p1 也没有权利进入。所以这个算法的主要问题就是违背了所谓的空闲让进原则，当临界区空闲的时候，未必只要有进程申请就可以让它进入临界区，所以这是单标志法的一个局限性。
# 双标志先检查法
那么之后人们又提出了一个叫做双标志先检查法的一种算法，这个算法的思想是会设置一个 bool 的一个数组，这个数组我们在这就命名为 flag，然后这个数组是用来表示各个元素，当前是否想进入临界区。如果说这个数组当中的某一个元素，它的值是 true，那么就表示和这个元素对应的进程号对应的进程，它此时是想要进入临界区的，那么在刚开始的时候，我们会把这个数组中的各个元素全部设为 false，也就是说刚开始 0 号暂时不想进入临界区，一号也暂时不想进入临界区。那么之后在每一个进程想要进入临界区之前，会把自己对应的那一个标志位把它改成 true，也就是用这种方式来告诉别的进程，现在我想进入临界区。
如果说此时系统当中只有两个进程，那么这两个进程的代码就分别是这样子，当然也有可能是有多个进程，那么多个进程互斥访问的代码其实也大同小异，无非就是把这个数组还要再拓展一下，具体的大家有兴趣可以自己去推敲。
那么我们来分析一下 p1 进程的代码，在刚开始 p1 首先检查 p0 进程是否想要进入临界区，因为他是否想要进入临界区的意愿，它是记录在 flag[0]布尔型的变量里的，如果说此时 p0 想要进入临界区，也就是这个值为 true，那么 p1 进程在执行 5 这个语句的时候，它就会一直被卡在这，然后一直不断的循环执行 5 这个语句，一直到 flag[0]被设为 false，也就是 p0 进程明确的表示自己暂时不会使用临界区的时候，它才可以跳出这个循环继续往下执行。
那么当 p1 进程确定了其他的进程暂时不想进入临界区之后，他就会把自己是否想要进入临界区标志位设置为 true，向其他进程表明，此时 p1 进程是想要进入临界区的，之后就可以开始正常的访问临界区。一直访问完临界区之后，再把自己的标志设为 false，又告诉其他进程，此时我已经用完临界区已经暂时不需要用了，那么这是这个算法的思想
咱们这么分析一看看起来还挺合理的，不过问题在于这两个进程他们是并发执行的，而并发执行会存在一个可怕的问题，叫做异步性。所以如果说这两个进程在执行的过程当中发生了切换，那么刚开始是 p0 上处理机运行，它先运行了一这个语句，因为刚开始这两个进程进入临界区的意愿都是 false，所以刚开始执行 1 这一句，他会发现此时 p1 进程暂时不想进入临界区，那么他就把这个他就可以正常的跳出这个循环，接下来会继续执行二这个语句，
但是在执行二这个语句之前，又恰好发生了进程切换。 那么 p1 上处理及执行 5 这条语句，此时他也发现 0 号进程 p0 此时他也暂时不想进入临界区，所以这个循环也可以跳过，于是 p1 进程也可以顺利的往下执行。那么接下来又切换回了，p0 进程由于这个循环已经跳出了，那么接下来就应该执行的是二，而 p1 进程之后再切换回 p1 进程的话，也要执行的就是 6 这条语句，所以可以发现如果用这种方式来执行的话，p0 进程的 flag 标志会设为 true，p1 的 flag 也会设为 true，并且他们两个是有可能同时进入临界区的，那么这样的话就违反了互斥访问的一个最核心的问题，因为已经有了两个进程，同时对临界区进行访问了，所以双标志先检查法的主要问题就是违背了盲则等待的原则。当一个进程在访问临界区的时候，另一个进程也有可能同时在访问临界区。那么这个造成这个问题的原因是什么？原因就在于在这个算法当中，其实进入区做了两件事情，
第一件事是检查，检查别的进程是否想进入临界区。
第二件事情是上锁，告诉别的进程，此时我想进入临界区。
如果说这两个操作他们是一个不可中断，一气呵成的那种原子操作的话，那么这个算法其实是没有问题的，但是问题就在于它在进入区的这两个操作的中间，也就是检查之后还要上锁之前，中间有可能会发生进程切换，从而就导致了这种违背盲则等待的原则这样的一个问题，所以这是双标志先检查法。
# 双标志后检查法
那么为了解决两个进程不能互斥的问题，人们又提出了另外一种叫做双标志后检查法，这种方式是前一种方式的一个改版，前一个算法的问题是先检查后上锁，所以如果一个进程检查了，还没上锁之前，又切换到了另一个进程，另一个进程又开始检查，那么就会发现两个进程检查都通过这样的情况，所以就导致了两边同时上锁，并且两边同时访问临界区的问题。
那么基于考虑人们又想到了是否能先上锁，然后再检查，也就是说先把这个坑给占上，然后之后再检查是否还有别的进程需要使用临界区，所以双标志后检查法其实和之前算法是很类似的，只不过是把上锁放在了前面，然后把检查放在了后面。
所以和刚才一样，如果对于 p1 进程来说，他会先把自己的标志为标记为 true，也就是告诉其他的进程，此时我想要进入临界区，然后把这个坑占了之后，他才会开始检查其他的进程是否会想要使用临界区，如果其他进程不想使用临界区的话，那么循环就可以跳过，它就可以顺利的访问临界区。
但是这个算法的缺陷也很明显，咱们还是用刚才那种进入区的这两个操作，不能一气呵成的那种方式来进行分析。如果说两个进程并发执行，那么按照 1526 这样的执行顺序就会发现，刚开始 p0 把 flag0 设为了处，然后 5 然后切换为 p1 进程，他要把 flag 一也设为主之后又切换回 p0，那么他会发现此时 p1 进程的 Flag 是 true，所以这个循环会一直循环检查下去之后，又切换回 p1，那么 p1 也发现 p0 这个 flag 也为 true，它也会一直循环下去，所以这就导致了 p0 和 p1 两个进程都没有办法进入临界区。
所以双标志后检查法它虽然解决了互斥，解决了忙则等待的问题，但是它同时又违背了空闲让进，还有有限等待的原则。两个进程如果发现发生刚才咱们描述的这种情况的话，这两个进程都会长期一直没有办法往下推进，从而导致临界资源没有办法分配给任何一个进程，然后这两个进程都会产生饥饿的现象，所以这又是双标志后检查法存在的一个问题
大家有没有发现在我们分析这些算法的问题的时候，主要的问题一般是会发生在两个进程或者多个进程并发执行的时候，而并发执行的异步性才是导致这些问题的原因。
所以咱们在考试的过程当中，不一定会给我们考察这些原模原样的这几种算法，但是大家需要学会的一点是我们需要自己学会分析，哪一个部分是所谓的进入区，然后在进入区做了哪些事情。如果说在进入区做了两三件不同的事情，那么这些事情交替着，用异步的方式，不同的顺序来交替的执行，有没有可能引发问题？大家在遇到具体的题目的时候，还需要用刚才咱们说的这种方法多进行锻炼
# Peterson 算法
刚才介绍的这三种方法多多少少都存在一些问题，接下来我们会介绍一种更厉害的算法，Peterson 算法，这个算法是 1981 年有一个叫做 Peterson 的人来提出的一种算法，他的想法是在双标志后检查法当中，两个进程都会想着想要进入临界区，但是谁也不让谁，最后就导致了刚才咱们说的那种谁都无法进入临界区的问题。
他的想法是如果说双方都真的想用临界区的话，那么可以让进程尝试着孔融让梨，主动的让给对方先使用临界区这样的机会。
那么 Peterson 算法的具体的实现是这个样子，首先还是和刚才的双标志检查法一样，会设置一个数组，用来表示各个进程想要进入临界区的意愿。如果说为 false 的话暂时不想进入，如果说为 true 的话，那么想要进入临界区
另外还会像单标志法那样设置一个 turn 这样的变量，这个变量就是用来记录孔融让梨的过程，到底是优先让哪个进程进入临界区，我们还是用 p1 进程的代码来进行分析。
刚开始 p1 会在 flag 这个数组当中标记，表示自己此时是想进入临界区的，之后他又会做一个主动让对方先进入临界区，这样一个谦让的过程，把 turn 改为 0，也就是说他此时愿意优先让 p0 进程进入临界区，之后会进行一个 while 循环检查。如果说他发现此时 p0 进程他想进入临界区，并且最后自己也确实已经表示了，我愿意让 p0 优先进入临界区，如果这两个条件同时满足的话，那么 p1 进程就会一直被卡在这个循环这儿，一直要等待等待 p0 进程出临界区，把 flag0 设为 false，它才可以开正常的访问。
所以在这个算法当中，其实进入区当中做了三件事情，一个是表示自己想要进入的意愿，第二个事情是表示自己可以优先让对方进入临界区。第三个事情才是真正的来进行检查。
那么和双标志检查法问题一样，如果说在并发的过程当中，两个进入区的这些操作互相穿插着，按照各种不同的顺序来执行的话，会不会发生什么问题呢？
我们来看几个例子，如果我们按 123678 这样的顺序来执行的话，大家具体分析一下不难，因为它其实类似于串行的那种情况，它肯定可以由 p0 优先的先进入临界区。
那么第二种情况，如果先按照 1623 这样的顺序
- 首先 p0 会表示自己越想要进入临界区，然后 p1 也表示自己想要进入临界区，这就是发生了双标志后检查法当中两个都争着进入临界区的情况。但是不同的是如果此时又切换回 p0 进程的话，那么 p0 进程它会表示自己愿意优先把进入临界区的权利让给 p1 进程，也就是把 turn 这个值设为 1，那么 p0 接着往下执行，他会发现此时 p1 进程它的 flag 也是 true，并且刚才自己已经说了愿意让给 p1，那么 p0 进程就暂时不好意思进入临界区，所以它会一直被卡在这个循环，这没办法往下推进，直到 p0 的时间片用完
- 然后又会切换回 p1 进程， P1 进程已经执行了 6 这一句，接下来会执行 7 这一句，也就会把 turn 设为 0，也就是 p1 会主动的说，我愿意把临界区的访问权让给 p0 进程。由于最后谦让这个动作是 p1 进程做出来的，所以它在之后进入循环的时候会发现， p0 其实也想进入临界区，并且自己最后说了一句，我想要让给 p0 先进入临界区这样的一句话，所以说他检查循环的条件也满足，他会一直循环等待么 p1 进程就一直会运行到它的时间片用完，然后再被切换回 p0 进程。
- 此时由于 p1 进程在后面又说了一次，他愿意谦让，也就是把 turn 这个值从 1 覆盖为了 0，p0 进程在进行 while 检查的时候就会发现 turn 是等于 0 的，那么 while 循环的条件就不满足，于是 p0 就可以跳出循环，然后顺利的访问临界区，一直到自己访问完临界区，在退出区的时候又把自己的意愿设置为 false，然后再切换回 p1，p1 又可以继续往下执行。
- 其他还有一些就是两边交替执行的情况，大家也可以自己用排列组合的方式再具体来分析一下，到底会发生什么，这种方式也是理解 Peterson 算法最好的一种方式，自己在稿纸上手动模拟一下各种情况是怎么进行的。
其实 Peterson 算法的这种三步走的这种思想，在我们的生活当中也经常会使用到，比如说有两个人，一个叫湘湘，一个叫臭臭，他们想要使用马桶临界资源，但临界资源同一时刻只能由一个人访问，所以它需要互斥的来使用它。那么用 Peterson 算法的这种思想的话，如果按照 123 这样的顺序来执行， p0 进程先执行的话，那么就相当于湘湘这个人他会先说自己想要马桶，并且会明确的表示，如果有需要的话，可以让臭臭先用。
但是他在执行三这个语句的时候发现，虽然自己已经表示了可以让臭臭先用，但是由于此时臭臭这个人暂时不需要使用马桶，所以香香可以访问临界资源马桶，所以它就可以上去运行。
那么第二种情况，如果我们按 16278 这样的顺序来执行的话，就类似于刚开始湘湘这个人说自己想用马桶，然后臭臭也说自己也想用马桶，之后湘湘表示可以让臭臭先用，但再之后臭臭又说了一句，可以让湘湘先用，所以就是两个人互相谦让的过程。
但是由于最后的谦让动作是臭臭这个人说的，所以如果他继续往下执行，开始检查的时候就会发现对方也想要使用资源，但是最后是自己说了可以先让给对方用，所以最后那句客气话，其实是这边说的，因此他就不好意思先使用临界资源，他会一直循环等待，一直到让他先使用临界资源，所以有没有发现这个例子和我们 Peterson 算法简直是一模一样的思想
比起之前的那几种算法来说，那么这个算法就成功的解决了互斥的问题，并且遵循了空闲让进，忙则等待，有限等待这些原则，但是这个算法并没有提供一些什么阻塞排队这样的机制，所以他并没有遵循让权等待的原则。也就是说即使 p0 进程暂时不能进入临界区，但是它依然会占用 CPU，让 CPU 一直运行循环，然后进入一个忙等的状态。所以 Peterson 算法其实比起之前的三种软件解决方案来说是最好的，但是依然不够好，还有可以改进的空间，咱们在之后介绍别的的解决方案的时候再继续介绍。
# 小结
所以这个小节当中我们介绍了这样 4 个算法，其中比较难理解的是 Peterson 算法，在考试当中除了这些算法之外，还有可能会考察一些别的咱们没有见过的算法。但是对于所有的这些问题的分析，其实都可以用刚才咱们聊到的方法就是说我们先区分出哪一个是进入区，在进入区做了哪些事情，然后我们再把进入区当中的这几个操作，让他们在两个进程并发的环境下，分别用不同的顺序来依次推进，然后用这种方式来验证进入区的进入区当中的这些操作，在并发环境下有没有可能导致新的问题，那么这就是互斥的软件算法的一种大体的解决思路
