在这个小节中 我们会学习进程互斥的几种软件实现方法

知识总览

那我们会学习单标志法 双标志 先检查 双标志后检查和Peterson算法这四种算法

这个小节的考察频率总体来说还是很高的 经常会在选择题甚至大题当中进行考察

所以这个小节的内容十分重要 那这个小节的学习当中 大家需要注意理解各种算法的思想和原理

当然 这个我一会会用一些比较容易理解的例子来进行解释 另外 我们还需要结合上个小节当中学习到的

实现互斥的四个代码逻辑部分来对每一种算法进行分析

也就是说 进入区是哪一段代码 然后临界区是哪一段 退出区是哪一段

特别我们要关注的是 进入区和退出区都分别做了什么样的一种处理 第三点大家需要关注的是

这些算法他们分别有哪些缺陷 那这个问题大家可以结合上个小节当中学习到的

实现互斥的四个原则来进行分析 也就是 空闲让进 忙则等待

那几个原则那具体的 我们会在讲解当中带大家进行分析 那首先我们来体会一下

如果在一个系统当中没有进程互斥的话 那么会发生什么情况 假设

如果没有注意进程互斥？

系统中有a b 这两个进程正在并发的运行 那么如果刚开始是a进程 上处理机运行

那a进程会执行他相应的代码 并且他会使用打印机这个资源 但是当他使用打印机的这个过程中

如果说a进程的时间片已经用完了 那么在这种情况下 a进程就会被剥夺处理机的使用权

接下来 操作系统会调度b进程 让b进程上处理机运行 注意 此时a进程其实还在使用打印机 只不过使用到一半就被切换到另外的进程了

但此时如果毕竟城上处理机运行的话 他执行了一些代码 之后毕竟城也会开始使用打印机

所以 由于a进程 它使用打印机 使用到一半的时候 b进程也开始使用打印机了

因此 a b这两个进程的内容就会打印在一起 就会混在一起 那这种情况并不是我们想要看到的

所以从这个例子中 我们就可以看到互斥的一个必要性 那 如果a b 这两个进程可以互斥的访问打印机

也就是说 只有当a把打印机使用完了之后 b才可以接着访问打印机

那在这种情况下 就不会出现我们这所说的这种问题了 因此我们接下来要探讨的问题就是

能不能用软件用代码的方式实现 让两个进程互斥的访问某一个临界资源

那首先来看第一种方法叫做单标志法 这个算法的思想是两个进程在访问完临界区之后

单标志法

会把使用临界区的权限转交给另一个进程 那我们会设置一个变量 叫

这个变量表示的是当前允许哪个进程进入临界区 如果turn等于零的话 说明此时是允许零号进程进临界区

如果turn等于一的话 说明此时是允许一号进程进临界区 那么两个进程

对临界区的访问代码就是这个样子 首先 每一个进程会在进入区这个位置判断一下

此时是不是允许自己进入 也就是说把他人的纸和自己的这个编号进行个对比

如果此时他人的值不等于自己的编号的话 那么说明此时临界区只允许另一个进程来访问

那我们来分析一下这个过程 刚开始turn的值是零所以如果刚开始

操作系统是调度了p一进程上处理及运行的话 那么p一进程在进入区 这会检查发现turn的值并不等于一

也就是 well循环的这个条件是满足的 于是p一进程它会被卡在well循环 这

一直不断的轮巡检查 因为turn的值一直是不等于一的 直到p一进程用完了操作系统给他分配的时间片之后

此时 操作系统会发生调度 让p一下处理机 而让p零上处理机运行

因此 当p零上处理机的时候 他在进入区 这进行了一个判断 发现此时turn的值是等于零的

也就是说 y o循环的这个条件得不到满足 因此p零进程可以跳过y o循环直接进入第二步

也就是说 p 零进程 他就可以开始访问这个临界区了 那接下来我们思考一下和刚才打印机的例子相同的情况

假设p 零这个进程此时正在访问临界区 而在他访问临界区的过程当中又发生了处理及调度

然后又切换回了进程p一那 由于此时turn的值依然为零

因此 即使pe进程再次上处理机运行 那pe进程的外物循环条件依然是满足的

turn的值依然不等于一所以p一进程还是会在这不断的轮巡轮巡 轮巡一直在检查这个turn的值

直到p一进程的时间片用完 那此时操作系统会再次调读p零进程 让他是继续上处理机运行

那p零进程就会紧接着继续访问他的这个临界资源 然后访问完了之后就可以往下继续执行

那直到p零进程再退出区这个地方 把turn的纸改为一之后

p一进程才有可能跳过这个进入区的外循环 然后访问临界资源

所以从刚才我们分析的过程当中可以看到 这个算法是可以实现同一时刻最多只允许一个进程访问临界区这个事情的

也就是说他可以实现互斥 那很多同学在学习这个算法的时候很容易一头钻进

这个代码里面 但是这些代码比较容易让人看了头晕 所以我尝试着

能不能利用大家的一些生活经验让大家简化对这个算法的认识过程

那其实我们可以把turn这个变量 把它看作是一个谦让的过程

他背后的逻辑其实表示的就是谦让p零进程再退出区 把turn的直射为一

背后的意思是说 p零进程把临界区的这个使用权签让给了p一进程

同样的p 一进程在退出区把确认的值设为了零

那这个背后的逻辑其实是说p一进程把临界区的这个使用权签让给了p零进程

那我们来尝试跳出代码 看一下生活当中谦让的例子 我们假设老渣和小渣又是这两个们

他们俩想要使用马桶 那马桶这个东西一般来说都是互斥使用的

那么 他们俩制定了一个规则 就是说这个马桶只能让两个人轮流的使用

让小渣使用一次 让老渣使用一次 再让小渣使用一次 再让老渣使用一次 所以小渣每一次要使用马桶之前 他要做的事情是

首先要进行一个检查 检查此次是否轮到让自己用了 如果轮到自己用了 那么他就可以开始访问这个临界资源

开始啦啦啦 那当小扎使用完这个临界资源之后

他就会开始做出一个谦让的动作 就是说 我表示下一次这个临界资源

可以让给老扎用 让接下来他开始做其他的事情 其实这些逻辑和我们这的1234都是11对应的

那老渣同学 他也一样 刚开始他是要检查是否轮到自己使用这个连接资源了

接下来 如果轮到自己了 那么他就可以进入临界区 开始访问临界资源 当他用完这个临界资源之后

他会表示 一个谦让的动作 下次这个东西我让给小扎用 然后他就开始做其他的事情

那接下来我们要考虑一下这个算法 它虽然可以实现各个进程对临界区的一个互斥访问

但是它有一个最知名的缺点就是各个进程它只能轮流的使用临界区

每个进程在退出区这一块都会表示一个谦让的动作 下一次是让对方使用

那如果说对方一直不使用这个资源的话 那么当他想要再次使用这个资源的时候 发现

此时并没有轮到自己 所以虽然这个临界资源此时是空闲的 然而

由于上一次是自己表示了这个谦让的动作 所以此时自己还暂时不能访问这个临界资源

因此他最大的一个问题是 他违反了空闲让尽的原则 那这是单标志法

接下来要学习的是双标志先检查法 这个算法的思想是要设置一个布尔行的数组flag 用来标记各个进程是否想要进入临界区

双标志先检查法

比如flag0=force的时候说明林浩进城 此事并不想进入临界区

而当他等于处的时候 说明此时林浩进城是想要进入临界区的 那这个算法采取的策略是

每一个进程在进入临界区之前都会先检查对方是否想要进入临界区

比如说 此时p一进程先检查fg零的值 也就是说他要确定对方是否想要进入临界区

如果弗莱格0=处 也就是对方想要进入临界区的话 那么p一进程就会一直被卡在这个外循环 这

而如果他发现对方此时并不想进入临界区的话 那么他就会把自己的这个flag一设为处

也就向对方表明我想要进入临界区的一个意愿 所以在这种算法当中 每一个进程在进入区做了这样的两个事情

第一个事情是检查对方是否想要进入临界区 第二个事情 如果此时对方不想进入临界区的话

那么 就表达自己想要进入临界区的意愿 所以其实在进入区把弗莱格设为处

他在背后的含义是说要表达自己想要进入临界区的一个意愿

那我们依然还是用小渣和老渣访问临界资源的这个例子 如果采用的是双标志先检查法的话 那么他在背后的处理逻辑其实这样的

如果小渣此时想要使用马桶 那么他先要检查老渣 也就是对方他是否想要使用

如果对方此时是想使用的 那么他就需要循环等待 而如果此时对方不想使用

这个资源的话 那么他就可以表达自己想要使用这个资源的一个意愿

也就是把自己所对应的flag值设为处 那我们也可以把这个动作理解为是上锁的动作

因为把自己的flag值设为处其实就相当于通知对方这个资源现在被我锁住了

那之后 他就可以开始使用这个零接资源 那当他使用完零接资源之后再退出区 这

又会把自己的flag直至为force 也就是要表达我自己不再使用这个临界区了

所以其实在退出区把自己的fact只设为force这个动作 我们可以把它理解为

解锁就是通知对方这个资源我现在已经不再锁住了 你想用的话你就继续用吧

那对于老渣 他的处理逻辑也是一样的 那看起来这个算法好像是没有问题的

但是如果这两个进程是并发的运行的话 那么情况就有可能不同了 那我们来看一下

因为刚开始弗莱克林和弗莱格伊都为force 也就是说刚开始两个进程他们都不想进入临界区

那如果说这两个进程并发运行的话 假设p一进程 他先上处理及运行

那批进程会对这个y的条件进行判断 他发现flag一等于

于是他会跳出这个 我要循环 然后进入第二句 而他还没有执行第二句的时候 如果此时就发生了一个切换

切换到了p一进程 那由于p零进程还没有执行第二句 因此此时p一进程的第五句判断他会发现fled零的值 此时还是force

因此 这个well循环也会被跳过 于是他就开始进入第六句 那接下来p一进程 他会把flag一的直射为处

然后开始进入临界区 开始访问临界区 那如果说此时又发生了进程切换 又切换回了这个p零进程的话

那批零进程 他会把自己的flag值设备处 同时他也会进入林业区

那可以看到 如果这两个进程他们并发的运行的话 那他们就同时进入了临界区

那大家也可以结合下面这个例子来看一下 如果按1526这样的方式来执行的话

是不是小渣和老渣就同时 开始使用马桶 这是很奇怪的事情 所以双标志先检查法 它存在的主要问题是违反了

忙则等待的原则 虽然临界区此时是处于忙的状态 也就是说 有一个进程正在访问临界区

但是 在并发运行的环境下 依然有可能发生两个进程同时进入临界区的情况

那导致这个问题的原因在于这些进程 他们在进入区干了两个事情

一个是检查 一个是上锁 而检查和上锁这两个处理的动作 他们并不能遗弃合成

也就是说 处理了其中的一个动作之后 有可能发生进程切换 进程调度

因此 这就导致了我们刚才所说的问题 导致他们同时进入临界区

那这是双标志先检查法 那接下来我们要看的是双标志后检查法这个算法

双标志后检查法

和刚才的算法其实思想上大致上是相同的 都是用一个flag数组

来表示此时每一个进程想要进入临界区的一个意愿 但是和双标志先检查法的不同点在于

后检查法当中 他是先进行了上锁的动作 之后才进行检查

而先检查法当中是先检查后上所 那在老渣小渣的这个场景当中 就相当于

当小渣想要使用马桶的时候他会说 我小渣现在想要使用马桶

就是向对方表达这个自己想要使用的意愿 也就是进行了上锁的动作之后 他会开始检查老渣是否想要使用

如果老渣此事不想使用的话 那么自己就可以开始进入临界区 开始访问这个临界资源

当他访问完临界资源之后 再把自己的这个意愿给撤销 也就表示我之后不再使用了

这是一个解锁的动作 那老渣也一样 那同样的 我们还是考虑并发的情况

如果这两个进程并发运行的话 我们按1526来分析一下会发生什么情况

假设刚开始是小诈线进行这个处理 那么他会表达自己想要使用临界资源的意愿

而此时发生的进程调度 那么接下来是老渣开始执行他的这一系列指令

那老渣他也会表达说自己也想用这个临界资源的意愿 那接下来再切换回小渣的时候

他会发现 此时老扎是想要使用这个临界资源的 于是小扎就需要等待二这一步

而同样的 如果再切换回老渣的话 那么他也会发现 此时小渣他也说过自己想要使用

所以他也不敢进入这个临界区 因此他就会卡在六这一步 所以这就导致了小渣和老渣这两个并发的进程

他们都进不了临界区的情况 因此双标至后检查法 他虽然简解决了这个忙泽等待的问题

也就是说 不可能有两个进程同时访问理解区 但是他又产生了新的问题 就是

违背了空闲让镜和有限等待的原则 空闲让镜的意思就是说 此时虽然这个临界区没有任何一个进程在访问

但是 像刚才我们所分析的那种情况一样 在这种情况下 有可能每一个进程都都进不了这个临界区

所以 这是违背了空闲让境 另外 如果两个进程都卡在了外循环这个地方

那么这两个进程 他们就永远不可能往下推进 因此他们就变成了无限的等待这个

临界区 所以这个算法 它违背了有限等待的原则 那这会导致

各个进程长期无法访问这个临界区资源 从而产生饥饿的现象 所以这是双标之后检查法的一个缺点

那最后我们要学习的是Peterson算法 这种算法的思想 它就是结合了双标制法和单标志法的

Peterson 算法

那种核心双标制法是每一个进程会主动的表示自己想要进入临界区的意愿

而单标志法的turn变量 它的本质在于每一个进程都会互相谦让着

让对方来使用这个连接去 也就类似于一个恐龙让离的一个过程 所以这个算法它会设置一个flag数组

这个数组就是用来表示每个进程他是否想要使用临界区这个意愿

是用来表达意愿的 而turn这个变量是来表达谦让这个动作的

而每一个进程 他在进入区当中会做这样的几个事情 第一他把自己所对应的那个flag值设为处

也就是说 表示自己此时想要进入临界区第二个动作 他会把turn的值设为对方的这个编号

p零进程把衬设为一p一进程会把衬设为零那这个负值其实就是一个谦让的动作

也就是说 他表示自己可以优先让对方使用这个临界区的资源

那在回到小渣和老渣的例子当中 小渣在使用马桶之前 他会先表示我小渣想要使用

就是表达自己的意愿 也就是把弗莱克直设为处 第二步 他会把他人的直设为对方的这个标号

那这其实就是表示我愿意优先让老渣先用 这是一个谦让的过程 是一个客气化

第三步 他会检查此时老渣是不是想用 那这个其实就是检查对方的flag值是否为处

如果对方也想用 并且最后是自己表达了这个谦让的动作

那么 这种情况下 我就等待 那这个逻辑就对应了y循环的这个判断 如果此时对方也想进入

并且趁的值等于一也就是说 最后是我自己表达了那个谦让 而对方没有再让回来

那在这种情况下 自己就需要卡在这个外循环着 循环等待那直到小扎 他发现

老渣现在已经不想用这个资源了 或者说当他发现老渣表示了

他愿意优先让小渣使用 也就是这两个条件中任何一个不满足 那他就不再等待

他就会开始使用这个零接资源 那当他访问完零接资源之后 他会把自己的flag纸设为f

也就是表达我自己已经不想再使用这个临界资源了 那老渣的处理逻辑是一模一样的

那对于这个算法的分析 我们依然要考虑到这两个进程并发运行的情况

所以同学们可以暂停来自己推一下 如果我们按照这样的一些顺序来

以此执行的话 那么会不会发生两个进程同时进入临界区 或者两个都进不了临界区这类的事情呢

那我们来一起分析一下最后的这种执行方式 16278我们用小渣和老渣的例子来进行分析

然后大家一会再用代码的角度来进行分析 为什么要用他们俩的例子来分析呢 因为

因为这个比较符合我们正常人类的习惯 可以让大家更能看明白背后的逻辑 但是如果直接使用代码的话 可能这些什么直变来变去就会容易让大家

头晕 所以重要的其实是理解这个代码背后想要表示的那种逻辑

那来看一下 刚开始是小渣先执行他的这一系列动作 他执行第一个动作

他表示说 小渣想要使用这个临界资源表达了意愿 接下来切换到老渣

然后老渣他也说我 老渣也想要使用这个零接资源也表达了自己的意愿 也就是说他们俩此时

都想要使用这个连接资源 那接下来是小渣做了一个动作 他表示

他愿意优先让老渣先用 这是一个谦让的动作 再接下来老渣执行期这个语句

老渣表示他愿意优先让小渣先用 那在执行了1627之后 同学们想一想在这种情况下

接下来应该是谁使用这个资源呢 其实结合我们的生活经验并不难理解

由于七这一句是在二之后执行的 也就是说 老渣的谦让动作在小渣的谦让动作之后

也就说刚开始本来是小渣说了一句客气话 没事让你先用吧 然后老渣又说了一句 不 不 不 还是让你先用 那在这种情况下

其实继续往下执行的话 应该是让小渣得到优先使用马桶的权利的

所以 在执行了1627之后 接下来想要再执行八那么老渣会发现小渣 此时他也想要使用这个临界资源

并且最后是自己表示了这个谦让的动作 那既然最后一句客气话是我自己说的 那我就只能

先等在这个地方了 于是他就会卡在循环的这个位置 直到再切换回小渣 小渣发现这个循环卡不住他 然后他就可以开始访问这个临界区了

所以其实Peterson算法虽然看起来复杂 但是他在进入区做的无非就是这么几个事情

第一就是主动争取 就是表达自己想要进去的意愿 第二在争取的同时又进行了主动的谦让

表示 我愿意让对方先进去 他是一个有礼貌的进程 然后第三个动作是检查对方是否也想要使用

并且最后一次是不是自己说了这个谦让的动作 自己说了这个客气话

那谁在最后说的客气话 谁就会失去行动的优先权 那这点其实我们

在平时当中 体会是很明显的 比如说过年了有个阿姨想要给你发压岁钱 然后阿姨对你说

乖 收下阿姨的心意 然后你说 哎 不了 不了阿姨 你的心意我领了钱我就不要了

然后阿姨跟你说 对阿姨来说 你还是个孩子 你就收下吧 那在这个过程中

先是你说了一句客气话 之后又是阿姨说了一句客气话 那在这个时候 你会说

行吧 行吧 那谢谢阿姨 所以结局就是你有压岁钱了 对吧 因为最后的这一句客气话是阿姨说的

最后的谦让动作是阿姨来表示的 所以阿姨在说了这句话之后 他就失去了行动的优先权

然后这个压岁钱就真的被你领走了 那再来看这样一个场景 你跟阿姨说不乐 不拉伊你的心意 我领了钱我就不用了

阿姨说 你就说下吧 之后你又说了一句 哎 真的不用了 阿姨 我已经成年了

而接下来 阿姨不再说话 那在这种情况下 你是最后一个说了客气话的人 你是最后一个做出谦让动作的人

因此 你在说完这句话之后 你就失去了行动的优先权 那在这个情况下 阿姨有可能就真的不给你压岁钱了

所以其实大家对这个算法的思想应该是能够理解的很透彻的 只不过他用代码的方式表现

他穿了一层马甲 可能大家就又看不出来了 但是他在背后做的事情和我们的这种谦让的工作是一模一样

尽管各个进程是并发运行的 但是他们对turn的值得一个设置 肯定也有一个先后顺序

那最后是谁设置了turn的值 就说明最后是谁做出了这个谦让的动作 那这个进程就会

失去行动的优先权 他就会让对方优先进入这个林业区 那建议大家还是把刚才我们提出的这几个问题并发 运行的时候 他们各自这些变量是怎么变化的 大家

都暂停来推导一下 那理解了算法的思想之后 这个推导的过程相信并不难

那这个地方 我们只抛出结论 Peterson算法 他用软件的方法解决了互斥的问题

可以实现空闲 让境 忙则等待和有限等待这三个原则 那为什么可以满足这三个原则

大家需要通过这儿的推导来自己进行体会 不过这个算法的一个明显的缺点是他并没有遵循让权等待的原则

所谓的让权等待就是说如果此时我这个进程进不了临界区

那么就应该立即释放处理及资源 而不应该继续在cpu上跑 但是这个算法的处理方式是

如果我这个进程此时进不了临界区 那么我会一直被卡在外循环 这

然后其实自己还一直在cpu上执行 不断的来检查这个外循环的条件

是否得到满足 所以虽然这个进程此时进不了临界区 但是他依然会占用cpu资源

因此就没有满足让权等待的这个原则 所以Peterson算法 他相较于之前的那是三种

解决方案来说是最好的 但是依然不够好 那还有没有更好的办法呢 这个我们会在之后的小节当中慢慢的介绍

知识回顾

好的 那么在这个小节中 我们介绍了几种互斥的软件实践方法 对于比较缺乏代码经验的跨考的同学来说

不建议大家直接钻到代码里面 而是要理解每一个代码 它在背后想要表达的那个逻辑

那单标志法的一个精髓在于他用一个趁人的变量来表示谦让这个动作

而双标制法的精髓在于他用一个flag数组来表示自己想要进入临界区的一个意愿

而Peterson算法结合了双标制法和单标志法的一个思想的精髓 每个进程在进入区当中都会先主动的争取 主动的表达自己想要进入临界区的意愿

同时又主动的做出一个谦让的动作 那在很多题目当中 只要是用软件方式实现了呼斥

其实大多都离不了这两种思想 要么就是一个谦让 要么就是表示想要进入的意愿

只不过在题目当中有可能会换一个变量的名字 或者进行一些细微的变化

但是大家只要抓住谦让和表达意愿这两个核心的思想 其实很多问题就

都有思路来分析了 那具体的大家还需要根据课后习题来进行巩固 另外想要说的一点是

双标志先检查法 它的这种思路其实是很好的 就是先检查这个临界区 此事是否有人想使用

如果没人使用的话 那我自己就给他上一个锁 但是导致这个算法问题的

关键在于检查和上所这两个动作并不能遗弃合成 那么如果能让检查和上所都遗弃合成的话

其实这个我算法是没有问题的 那在下个小节当中 我们会学到两种

硬件的实现方法 用硬件的方式来保证这两个动作仪器合成 那么就可以保证这个

算法的正确性了 好的 那么以上就是这个小节的全部内容

推荐一个零声学院免费公开课程，个人觉得老师讲得不错，分享给大家：Linux，Nginx，ZeroMQ，MySQL，Redis，fastdfs，MongoDB，ZK，流媒体，CDN，P2P，K8S，Docker，TCP/IP，协程，DPDK等技术内容，立即学习