最近在研究操作系统，也多找了些资料研究了一番，感觉对于进程互斥算法的理解更透彻了，就把这些进程互斥的软件实现方法分享给大家，希望大家一样可以理解彻悟！
开始前我们先复习一下进程互斥存在的原因和什么是进程互斥，所谓进程互斥，先要了解到进程的并发，并发就会共享计算机资源，共享资源又分为了互斥共享与同时共享，互斥共享就是我们这篇文章研究的内容。
文章目录：
一：进程互斥引入
1.1 互斥访问临界资源逻辑分步：
1.2 互斥访问临界资源原则：
二：进程互斥软件实现方法
2.1 单标志法
互斥过程：
2.2 双标志先检查法
互斥过程：
2.3 双标志后检查法
互斥过程：
2.4 peterson 算法
互斥过程：
一：进程互斥引入
我们先引入一个概念： “ 临界资源 ”，我们往往把一个时间段内只允许一个进程使用的资源叫做临界资源，手机上的话筒，摄像头，打印机……等等都属于临界资源，还有部分变量和缓冲区等也属于临界资源，对临界资源的访问必须是互斥进行的。有了这个概念，我们就可以把对临界资源的访问分为以下的四个部分：
1.1 互斥访问临界资源逻辑分步：
互斥访问逻辑上分为了四个步骤，分别为进入区，临界区，退出区和剩余区四部分
- 进入区：检查是否可进入临界区，可进入则 ”上锁 ”
- 临界区：访问临界资源的代码
- 退出区：解除访问临界资源，即 ” 解锁 ”
- 剩余区：其他操作
1.2 互斥访问临界资源原则：
- 空闲让进：临界区空闲时允许请求进入临界区的一个进程进入临界区
- 忙则等待：有进程进入临界区时，其他想要进入临界区的进程需要等待
- 有限等待：需要访问临界区的进程应在一定时间段内进入临界区，防止其饥饿
- 让权等待：当确定一个进程不能进入临界区，应立即释放处理机，防止盲等
二：进程互斥软件实现方法
进程互斥有软件实现方法也有硬件实现方法，这篇文章是其软件实现方法，下面是其实现方法的四个分类：
2.1 单标志法
单标志法算法思想：每个进程访问完临界区后会把临界区使用权给另一个进程，每个进程能不能进入临界区完全由另一个进程决定
下面有两个进程分别为 p1 和 p2：（turn代表的意思是 当前允许进入临界区的进程号）
p1 进程：（代码前的编号代表第几行，下面均称为代码1，代码2 ……）
p2 进程：
互斥过程：
- 若 turn 初始值为 2，即一开始允许进入临界区的进程号为 2，如果 p1 进程先上处理机，则其代码1 满足条件，则一直执行代码1，直到进程1的时间片耗尽，调度切换 p2 上处理机。
- 此时 代码5 不成立，则跳过执行后面代码（while语句后面有分号，是单独的语句）执行代码8 时turn变为了 1，在 p2 时间片耗尽后又调度 p1上处理机。
- 此时 代码1 不成立，跳过执行后面代码，turn 又变为 2
- 循环往复
结论：
我们可以发现对于临界区的互斥访问一定是按照 p1–p2–p1–p2–p1 这样轮流访问的，但是如果一旦某个进程允许进入了临界区但是始终不访问，这时候虽然临界区是空闲的，但是另一个进程也会一直不被允许访问，违反了原则 ” 空闲让进 ”
2.2 双标志先检查法
双标志先检查法算法思想：设置了一个 bool 型的数组名为 flag[]，数组中元素表示各个进程是否进入临界区，flag[1]=” ture ” 则代表进程p1此刻进入临界区，每个进程进入前都要先检查当前有没有别的进程想进入（while 检查），如果没有，则给自身 flag 设为 ture，然后进行访问临界区
下面有两个进程分别为 p1 和 p2：
公共条件：
p1 进程：（代码前的编号代表第几行，下面均称为代码1，代码2 ……）
p2 进程：
互斥过程：
- 如果p1 p2 并行一个一个执行，不会有问题，但是如果按照代码 1–5–2–6–3–7 等等并发执行，会出现以下情况
- p1进程执行 代码1 判断进程p2想进入临界区 不成立，会跳过执行下面代码，然后接下来按要求的代码执行顺序并发执行 代码5，同理也不成立也会跳过执行下面的代码
- 轮到执行代码2，此时 flag[1]=true，其会进入临界区，然后轮到执行 代码6，此时 flag[2]=true，p2其也会进入临界区，二者均进入了临界区，同时访问了
结论：
进入临界区的检查和上锁不是一起处理的，检查后，上锁前有可能发生进程切换，导致同时进入临界区，违反了原则 ” 忙则等待 “
2.3 双标志后检查法
双标志后检查法算法思想：改变自双标志先检查法，那个方法先检查后上锁，那不妨这个方法先上锁后检查试试
下面有两个进程分别为 p1 和 p2：
公共条件：
p1 进程：（代码前的编号代表第几行，下面均称为代码1，代码2 ……）
p2 进程：
互斥过程：
- 还是仍然按照代码 1–5–2–6–3–7 等等并发执行，会出现以下情况
- p1进程执行 代码1 可以进入临界区，调度p2进入处理机执行 代码5，也可以进入临界区，然后再按照要求顺序执行代码2和代码7，会发现二者均没办法继续执行，会一直执行 while，最终导致进程饥饿
结论：
解决了双标签先检查法的不能遵循忙则等待问题，但是不遵守原则 ” 空闲让进 ” 和 ” 有限等待 ”，会导致进程饥饿现象
2.4 peterson 算法
peterson 算法思想：双标签后检查法中，两个进程都是愣头青，都想进入临界区，最后谁也进不去，peterson 算法就利用了 互相谦让 的思想，主动地让对方先进入临界区
下面有两个进程分别为 p1 和 p2：
公共条件：（此处 turn=1 意思就是优先让 p1 进程进入临界区）
p1 进程：（代码前的编号代表第几行，下面均称为代码1，代码2 ……）
p2 进程：
互斥过程：
第一种情况：按照 代码123–789 的顺序执行
- 先执行 代码123，p1想进入临界区，并且表明自己可以优先让 p2 进入，然后代码3 成立，反复执行 while 不跳转下一条语句，时间片耗尽后换p2执行
- 接下来执行 代码789，p2想进入临界区，并且表明自己可以优先让 p1 进入，然后代码9 成立，反复执行 while 不跳转下一条语句，时间片耗尽后换p1执行
- 由于执行代码8时 的 turn 变为了1，则时间片再轮到 p1执行时，代码3 则不再成立，会跳转下面的语句，这时候执行到 代码5 后 flag[1] 会变为 false
- 等 p1 时间片再耗尽，此时 flag[1] 会变为 false，代码9 也不再成立，跳转执行下面的语句
第二种情况：按照 代码1– 7–23–89 的顺序执行
- 先执行代码1，p1 自己想进入临界区，在调度到进程 p2 分配处理机，执行代码7，p2 也想进入临界区
- 再调度执行 p1 分配处理机，执行代码2-3，p1 进程可以优先让 p2进程 使用临界区，代码3 不成立，执行while
- 接下来 p1 时间片耗尽再调度 p2，接下来的步骤就和第一种一样了。
结论：
解决了其他方法的不遵守原则问题，但是违反了原则 ” 让权等待 ”，因为如果一个进程不能进入临界区，其也会执行 while，一直在占用CPU执行循环，会发生忙等现象
文章知识点与官方知识档案匹配，可进一步学习相关知识算法技能树首页概览34273 人正在系统学习中
来源：卡卡西最近怎么样
声明：本站部分文章及图片转载于互联网，内容版权归原作者所有，如本站任何资料有侵权请您尽早请联系jinwei@zod.com.cn进行处理,非常感谢！