13.2 现实生活中的同步问题在线视频

下面我们通过一个

生活当中的例子

来说明同步的问题

和相应的解决办法

在计算机里头和生活当中呢

实际上有些问题

我们是可以来进行类比的

这种类比的办法呢

可以我们利用生活当中的常识

来帮助我们理解

操作系统当中的同步问题

当然你在做这件事情时候

也需要想到

计算机和人之间的一些区别

比如说我们在进行协调的时候

我们人的一些假设前提

和计算机是不一样的

所以这时候呢

他们的处理也会不一样

好 我们先看一个例子

这是一个家庭采购的例子

说一家里头

我们冰箱里头

放有各种各样的食品

好 那这时候问

如果说冰箱里东西吃完了

那这时候怎么办

那家里的成员会说

我去看冰箱里有没有面包

如果没有

那我就离开家去商店去买

那到达商店之后

买完再回来把它放进冰箱里头

这件事情就算行了

我想我们很多家庭里呢

都是这样安排的

但是在实际生活当中

我们也可能会出现这种情况

第二个人进来之后

由于时间错开一点

头一个人在去商店的路上

第二个人呢开始看冰箱

这时候他们俩没打照面

当然你说我们俩

去同一个商店买的路上会碰到

那这事没有了

但是每家基本上

都会碰到过这种情况

我买重的时候

好 那这样的话这种情况

我们怎么解决

那你说我在家里通常情况下

很少量的几次重复

我们是可以接受的

但是对于计算机来说

这件事情是不好办的

我们怎么能够把

这件事情的协调做得

很成功和高效

那这时候呢

就有这样几个条件

一呢是冰箱里头没有面包之后

我必须有人去买

就说有人看到冰箱里没有了

那他就会去买

第二个呢是说

我最多只能一个人去买

因为如果说多个人一块去买的话

这时就会买重

那怎么解决这个问题呢

那说 这是一种很极端的做法

说我在冰箱上加一锁并且有一钥匙

那买之前呢我把冰箱锁上

然后我回来放进去之后

我再把它打开

好这样一来的话

第二个人来看冰箱已经锁上了

那这时候呢他就不会再去买

那这时候说

这种解决办法好像

在我们生活当中不会这样做

那比如说这里这种情况

你把冰箱锁上仅仅是为了面包

实际上冰箱里还有别的东西

那别人想取别的食品的时候

那它也取不出来了

所以这种做法呢

对于我们来说是不恰当的

那我们需要在这里呢

来讲解决办法

我们怎么来做呢

首先想到的一个办法呢

是在冰箱上贴一便签

然后用这个便签呢

表示有人去买面包去了

其他的人看到这个便签之后

他就不会再去买了

这一种做法

我们把它比较具体地描述出来

就是采购之前

我留下一张便签

完成采购之后我把便签去掉

那别人看到便签的时候呢

他就不去买了

这是我们的自然语言描述

然后我们把它变成伪代码的形式

就是这样的

先检查是否有面包

然后检查是否有别人留下的便签

然后如果没有的话我就留下便签

然后去买面包

然后把便签去掉

整个过程结束

那这时的问题是说

如果用计算机来执行

这段代码它有效吗

那我们在这里呢说它会有麻烦

仍然是偶尔会出现买多了情况

那什么情况下会出现买多呢

说 检查面包和检查便签之后

在你贴便签之前

如果有其他的人来

检查面包和便签的话

那这时候它也是没有的

好 这时候呢

就会出现两个人一块去买

那你说在生活当中

我检查便签有没有和

往上贴便签这件事情

两个是挨着的

如果另外一个人来检查的话

我们会看到

但是把它放到

计算机程序里来运行的时候呢

你两个进程交替执行

检查和后面的设置

它俩是没办法做到这一点的

所以在这儿呢

这在生活当中

这种做法就是有效的

而在计算机里呢

这种做法就是会有麻烦的

好 我们下面具体来看一下这个麻烦

首先是两个进程A和B

第一个呢做检查

检查是否有面包

检查是否有人贴便签

然后这时候呢做了进程切换

切换到另一个进程B

它检查有没有面包

检查有没有便签

这两个进程的检查结果

都是没有面包没有便签

好 那这时候它们会做什么

那都会去采购

好 这时候又切回到A

它就留下一个便签然后去买面包

好 然后这边呢

也留下一个便签也去买面包

这时候我们看到有啥麻烦了

这两个都会买重复的面包

那你说在这里头你这么切换

这两者之间这个间距

是我们在生活当中碰不到的

或者说很少碰到的

好 那在这儿呢他就会出现

所以这个地方有问题

因为它会有间歇性的麻烦

而这种错误呢

它并不是在所有情况下

每次运行都会有

它会很难调试

并且这时候你需要知道

我在什么地方

可能会出现调度

所以这种方案呢是我们不理想的

那这时候我们怎么办呢

第二种做法说

我把便签挪到前面去贴

我先贴上便签然后再来检查

这时候是不是就没问题了

好 那我们把这件事情也转换成代码

贴便签一前一后

中间做检查

没有之后去买面包

这种做法行得通吗

好 我们也来看具体的一种可能性

贴便签 切换 再贴便签

这时候大家就已经会

察觉到一个问题

两个都贴便签之后

那么不管你怎么切换

它都会检查有没有面包

没有 或者是有

好有没有便签

他会检查有便签

好 那他就不会去买面包了

好 这边呢也是一样的

检查有便签

他也不会去买面包了

好 那等到你最后一个回来

这时候会出现什么情况

我们这两个买面包的动作

没有任何一个进程执行

他们都出来了

这时候我冰箱里也没有面包

好 这时候我们就找到了

一种情况它会失败

那这时候呢会出现什么情况

谁也不会去买面包

那这样就没面包了

好 说你把这个便签

挪到前边来也不行

刚才我们说放到后面不行了

挪到前面也不行

那这时候是啥呢

说你检查便签的时候

没有区分到底是谁留下的便签

甚至于这种情况

只有你自己在执行的时候

他也没法买回面包来

好 那说 我们在这里怎么办呢

我们把便签做得更准确一些

A留的便签和B留的便签

我是不一样的

好 那这时候呢

就转到我们的第三种方案

第三种方案呢

是在便签上加上标记

以区别这个便签到底是谁留下的

这样的话我只检查对方的便签

那这时候呢

我们给出相应的代码

那我们仍然是在

检查之前留便签 两边

留便签呢便签上有标记

那从这里我们写伪码上来说呢

这两边的代码已经不一样了

但实际上如果说你加上相应的数组

并且用数组下标

作为你这个进程标识的话

那这个地方的代码呢

仍然可以写成是一样的

好 在这种情况下

留下便签检查是否有对方的便签

如果没有检查是否有面包

如果没有面包那我去买面包

两边都是这样

好 那这时候说

这个做法能行得通吗

好 我们看一个实际的情况

在这里呢大家

第一个进程先留下便签

然后第二个进程留下便签

我们看这种极端的情况

它会是什么样的结果

切回去这边再来

执行这个代码的时候

因为他已经有了对方的便签

那这时候他不会去检查是否有面包

然后直接出来了

好 那这时候说

到这边的时候呢

他检查是否有对方的便签

那有 那他也不会检查是否有面包

好 那这样一来的话

实际上两边都没有去检查

是否有面包就直接出来了

好 那这时候说会出现啥情况

实际上大家都留下便签

并且我这便签上

也能区分出是谁留的

但是这时候呢

由于我留便签的时候是说你要去买

双方都认为对方去买

好 这时候麻烦就出来了

这时候谁也没买

好 那这时候怎么办呢

那我们说我们再来做一个调整

我在这里头呢

这边A和B我们代码做了一些修改

然后说你在这里头呢

其中一个进程

在检查到对方有便签之后

那我就重复的检查

一直到对方没有便签了

而另一个进程呢

仍然跟前面的做法是一样的

跟我们前面方案3

好 那这个办法能行吗

那我们来解释一下看看

他到底在什么情况下是行得通的

比如说我们仍然是刚才那种情况

前一个进程留下便签

第二个进程留下便签

然后两边进行检查

那在前面程序里呢

后边这个检查有对方的便签

它就直接走掉了

那这个时候呢由于两边不一样

我头一个在检查的时候

他检查对方留有便签

这时候我不是走掉

而是在这儿一直等待

一直等到B把便签撤掉

那我会在这儿

好 等到B把便签撤掉的时候呢

我们刚才说如果说这个B

留下便签的时候在它的前面

那这时候呢他会看到A留有便签

所以他直接走掉了

那这时候呢他检查一下

然后看有A的便签

那他就直接走掉了

好 他没有去买面包

而这时候呢A呢

由于一直等到B离开 好

检查完了之后说那这时候离开了

B没有去买

那这时候他再去看是否有面包

没面包他去买

那这样的话在这种情况下

他是能够回来的

好 那这时候我们看到

这两个进程呢

它的代码是不一样了

这时候我也没办法换方式

让它俩写成完全一样

那这时候问

我们刚才那种情况

它能够避免掉了

它还会再有别的问题吗

好 实际上在这里头呢

我们需要把它所有可能

这种切换的组合都想一遍

想清楚每一种情况

它都能通过的话

枚举完 那这件事情呢

它就能通过了

那这时候实际上我们在做

同步互斥问题的时候

很多时候是需要很仔细去想

像这种分的情况

你比如说在这里头

我们会关键想哪条呢

一个是什么时间留便签

你比如说一边留便签

另一边没有参与这件事情

那这时候说我检查是否留下便签

是否检查对放有没有便签

对方不存在

好 那这时候呢

他就直接检查有没有面包

他自己就会去买

所以你只有一个进程

A运行的时候没有问题

能正常买回面包来

好 只有一个B呢也能行

好 那实际上我们重点需要关心的是

这两个他们之间检查的时候

留便签的时候有交互

一种是说B在A之前

那B在A之前的话

那他在这儿留便签的时候呢

这个B有可能留下便签之后

他检查没有A的便签

好 或者说刚好检查有

好 刚好检查B没有便签的时候

A没有留下便签的时候

那这时候呢他会去买面包

买面包的话

A再来检查在中间

在这个之后某个时间

他会检查B如果这时候

正在买的过程当中他会等到这儿

等完结束之后呢

后面再来检查的时候

那这边已经有面包了

他不会去买

所以这种情况也是行的

好 那这时候说我这个B在A之后

并且是在你检查完之后

你比如我检查这个B没有留下便签

我就怎么去看有没有面包

如果这时候B在这儿留下自己便签

情况会是什么样

大家可以仔细去想想

那我们说通过

各种各样的情况组合到一起

那这件事情是没有问题的

那这时候问

这个做法怎么样

好像枚举的情况很多

我们想起来很不容易

所以这件事情呢

它是有效的 但是很复杂

你很难去验证它的有效性

这时候说 我们这样做之后

它的麻烦是两头代码不一样

略微有一点不一样的时候

它结果就会差很远

好 那如果说我有更多的进程

这事怎么干

哦 一想这个问题好像更复杂

还有一个问题是

A他必须在中间要反复的去查

这时候呢他不能干别的

就好比说我们要去打电话找一个人

我打完电话之后不在

那我再去一次

在我们这里呢称之为叫忙等待

那这种呢他是要占用CPU的

好 这也是他的问题

那这时候说

我们是不是有更有效的办法

好 那我们在这儿呢

我们给出一种假定

假定我能用原子操作实现一个锁

那我们这事就好做了

什么原子操作实现的锁呢

这个锁呢有这样一个功能

首先我申请的时候

在锁被释放之前

我一直处于等待状态

一直到他获得锁

如果有两个进程

同时在等待这个锁

那么这时候呢他只会有一个获得

另一个呢还继续等待

如果说我们能做到这一点

那这时候呢

并且把它实现成一个原子操作

在这中间呢不会被暂停

释放呢就是解锁

并且唤醒处于等待状态当中的进程

有了这两条实现之后

我们给出一个代码

这时候呢是基于原子锁的解决方案

刚开始申请

然后在这里判断是否有面包

去买面包

然后到最后的时候呢

释放这个锁 解锁

好 那这时候呢被我们标准化成

这部分代码叫临界区

前面这一段呢叫进入临界区

后面叫退出临界区

相应的这两段代码保护下

中间在这个临界区里头执行呢

就只有一个进程

好 基于这样的办法呢

我们这件事情呢就能做的很好

好 我们看到在这个例子当中

两个进程为了

协调他们之间的操作

那中间的关系是很复杂的

那如果说我们系统里有更多的资源

这件事情会变成啥样呢

好 我们在这儿呢做一个归纳

进程之间的交互关系

他们对对方的感知能到什么程度

我们在这儿呢分了三种情况

一种呢是完全不感知

一种呢是两者通过

一个第三方来协调

你比如说都要占用共享的资源

然后再有一种情况是

两者需要直接进行通讯

那这三种情况对应着

他们之间交互关系呢是这样的

没有关系的时候

他是相互独立的

相互不影响

如果说我有共享的第三方

这里我们需要通过

共享这个资源来进行协调

如果说两者有直接通讯

那么这时候需要

通过通讯来进行协调

好 那在这种情况下

他们之间的相互影响呢

第一个情况独立的

对这方没有影响

第二个呢是说他的结果

依赖于共享资源的状态

有可能一个进程占用了资源

另一个进程要想

使用这个资源的时候

他就没办法使用了

要么等到这个资源可以用

要么这件事情他以失败告终

而第三个呢双方通讯的时候

这个结果就依赖于

双方的通讯的结果

好 那这时候呢通讯结果的不同呢

他结果也是不一样

好 在这个过程当中

我们的进程之间呢

会出现这样三种关系

互斥 死锁和饥饿

分别是指什么意思呢

互斥是指一个进程占用了资源

其它的进程就不能使用这个资源了

那必须等待使用资源的进程释放

那在这个过程当中呢

资源的使用是互斥的

第二个死锁

死锁呢是多个进程

各自都占有了一部分资源

那这时候呢形成循环等待

那各自占用一部分资源

这种情况是允许存在的

好 那等到某一个能够得到

他所需要的所有资源

好 那他执行结束之后释放资源

好 这样的话这个

部分等待其他的就能有资源

到最后大家都用完了

那这件事情出来

如果构成一个循环等待

就好比说我们在一个十字路口

四辆车叉成一个井字

好 那这时候呢所有的他就等的

就谁也不让的话

那这件事情就堵死了

这种情况呢

是我们这里说到的死锁

还有一种情况呢是饥饿

饥饿是指一些进程轮流占用资源

而导致一个进程呢一直得不到资源

比如说像我们前面说到的调度

有一个进程占用CPU来执行

但是它的优先级低

而比它优先级高的进程呢

又一直在运行

那这样的话

它就属于饥饿的状态

好 那我们说在实际的操作系统里头

由于我们有资源共享

我们就会出现

互斥 死锁和饥饿这些情况

但是如果说我们想避免这种情况

那我们资源利用效率呢又不够高

好 所以我们在操作系统里头

就要提供一组同步互斥的机制

来在保证资源的使用率的前提下

避免这些同步所带来的问题

下面呢我们会具体来

介绍它的各种各样的解决办法