各位同学 大家好
今天我们来介绍死锁和进程通讯
死锁呢 是进程之间
由于共享资源所导致的一种
无限期等待的情况
那在这里头呢
我们会讨论死锁的基本概念
处理死锁的方法都有哪些
我们会具体介绍银行家算法
和死锁检测算法
这两个具体的算法
另外一个部分呢
是进程间通讯
也就是说两个进程之间
它们有一些什么样的通讯手段
那在这里呢
我们会介绍四种 信号和管道
消息队列和共享内存
那首先呢 我们来介绍死锁
死锁是由于竞争资源或通讯关系
两个或更多个线程
在执行的过程当中出现的一种
永远相互等待其他进程
才能引发的事件的状态
那这时候呢 我们先通过一个
具体的例子来看一下
这就是单向通行桥梁
那在这里头呢 这个桥梁呢
我们可以认为它是一种共享的资源
桥梁上只能单向通行
那这时候呢 不同方向的车
会共享这个单向通行的桥梁
那桥梁的每一部分呢
是一个资源
如果这个桥梁整个是一个资源
它也不会出现问题
那要占用就整个占用
实际上我们在这里
是由于部分占用所导致的问题
在这里呢 桥梁在使用的时候
可能出现死锁
比如说在这里头
对向行驶的两个车辆
在桥梁上正相遇了
好 那这时候谁也没有办法继续前行
都等待对方
而这种等待呢 是没有结果的
这种情况下呢 在我们通常做法呢
是一个方向的车辆倒退
好 那这样另一个方向呢能通行
这实际上就是我们在这里头
给到的一种死锁的解决办法
就是资源的抢占
与此同时呢
即使不出现这种情况
也会出现饥饿的情况
一个方向的车持续的运行
而另一个方向的车呢
就没有办法通过这个桥梁了
这是实际生活当中的一个例子
我们在操作系统里头
对于资源共享的情况
也会有一个跟它很类似的情况
那在具体讨论如何解决的办法之前
我们需要比较深入的来分析一下
死锁它出现的相关背景情况
你比如说我们资源的使用过程
出现死锁的条件等等
首先呢 我们来看
进程访问资源它的流程
在系统里头呢
我们存在各种类型的资源
比如说像我们这里说到的
CPU的执行时间 内存 I/O设备
每一类资源呢
可能会有多个实例
你比如说像你的CPU
可能有多个CPU
对于这些资源呢
我们在访问的时候
通常是什么样的流程呢
那进程访问资源的流程是这样的
说这个资源为系统所占用
进程在使用的时候
首先我需要申请
申请系统当中空闲的资源
然后申请到了之后呢
这个资源的状态
就由空闲变成被进程占用了
然后进程占用资源使用
这有一个持续的时间段
等它用完了之后 它会释放资源
释放资源之后呢
这时候资源的状态呢
就由占用变成了空闲
这是一个资源的使用的流程
那在这个流程当中呢
我们可以看到
资源和进程之间的相互关系了
然后为了更进一步的讨论
我如何来解决死锁的问题
那我们有必要对资源的特征
进行一个分析
在这里头呢
我们就把资源分成了两类
一类叫可重用资源
对于这些可重用资源呢
它的这些资源是不可以删除的
任何一个时刻呢
只能有一个进程使用
一个进程使用释放之后
另外的进程就可以重用了
比如说像CPU
你占用一个时间段 再使用
好 过一会儿之后
你用完了 你释放
另外一个线程就可以来使用CPU的资源
大家交替使用
这就是我们前面所说到的
调度所要解决的问题了
那对于这种资源呢
它有些什么样的实例呢
那我们这里头处理器 I/O通道
存储 I/O设备 那这些都是
这是硬件资源
也有一些软件资源
你比如说文件 数据库等等这些
都是我们这里的资源
这些资源呢 是不可以被删除的
那至少是在这里头
文件我们是可以删除的
但实际上这是对应于
进程在访问这些资源的过程
当中的一种情况
还有就是在这里
它可能会出现死锁
那出现死锁的原因是说
一个进程我会占用一部分资源
并且请求另外一部分资源
如果说你是一个整体的话
这种情况也没有了
这是可重用资源
还有一类叫消费资源
这一类消费资源
它有一个创建和销毁的过程
比如说这里头我们看到的一些实例
中断 中断又出现和处理例程
信号 消息 这些都是有一个进程产生
另一个进程使用 这样一个过程
那在这里头呢 它可能出现死锁
比如说我们在这里时常见到的
通讯双方相互等待对方的消息
这是时常出现的一种情况
那这时候相互等下去
就出现无限期的等待了
好 我们在这里头呢
对资源有了一个描述
对进程访问资源的过程有了一个描述
好 那这时候我们如何来描述
进程和资源之间的关系呢
这是我们这里的资源分配图
它描述资源和进程之间的
分配和占用关系
这是一个有向图
那这个有向图里都有些什么内容呢
首先第一个它有两类顶点
一类是我们系统当中的进程
每一进程用一个圆圈来表示
然后另一类顶点呢 是资源
每一类资源对应着一个顶点
资源里头的实例的数目
在这里用小圆点来表示
好 那这是我们顶点的情况
然后这些顶点之间的关系有两种
资源请求边
一个进程指向一类资源
表示这个进程要请求
这类资源当中的一个实例
还有一类呢
是资源分配边
这表示一个资源实例
已经分配给了某一个进程 在这
用这个资源分配图我们就可以表示出
进程和资源之间的申请和占用关系
这是一个实际的例子
我们从这张图里可以看到
有四种资源 有三个进程
它们之间有请求关系
也有占用关系
在这个图里头呢
我们想知道 会不会出现死锁呢
我们看下去之后 比如说这里头
进程P3占用资源R3
它用完了之后它释放
那这时候呢
P2就可以得到运行
运行结束之后 那所有这些
请求的编就都会得以分配
所有进程都能执行完
那这种情况呢
它是不会出现死锁了
再看下一个图
这和刚才的图就多了一条边
这时候呢 我们就看到
在这里 出现了一个循环等待
P2请求R3
R3已经分配给了P3
P3又请求R2
R2已经分配给了P2
这时候就有一个循环等待
并且这个循环等待呢
它没有结束的时候
好 那这时候呢
我们知道它会出现死锁
对于这种简单的情况呢
我们直接从这图上就可以很清楚的看出来
但实际上我们遇到的麻烦是
在系统当中有几百个进程
有几十种 或者更多的资源
这时候你再来做判断
那就会有时间开销和比较困难
这是一个资源分配图
那里头也有一个循环
但它会出现死锁吗
细分析下去之后
跟我们刚才情况一样的
它不会出现死锁
但是它要循环
好 那这时候我们说
不能仅仅依靠循环来判断是否出现死锁
具体说起来我们会怎么来做呢
那这就是我们这里的
出现死锁的必要条件
必须满足我们这里说到的四个条件
同时满足才会出现死锁
第一个条件呢 是互斥
我们必须有某种资源
任何一个时刻 只有一个进程使用
如果说你的资源是可以共享
不需要互斥的
那不会出现这种情况
第二个是持有并等待
也就是说我一个进程
如果说它本身不占有任何资源
那就不会有别人等它
它不会请求别的资源的话
那它也就不会等别人
好 那这样的话就是
必须你持有至少一种资源
并且正在等待获取其他进程占有的资源
这时候才构成我们这里的第二个条件
持有并等待
然后第三个条件呢 是说非抢占
那这类指的是
资源只有在进程使用后自愿放弃
我不可以强行剥夺
比如说就像我们刚才说的
单向通行的桥梁
两个都走到中间相互等待了
那这时候司机通常情况下
都希望对方主动放弃
那实际上在这里头呢
通常情况下 这个是不容易满足的
好 这是第三个条件
第四个条件呢 是循环等待
我在这些资源的请求和占有关系中
我必须存在一个循环等待
也就是说存在一个等待进程的集合
0等1 1等2
N减1等N
一直到N等0
这样构成一个循环
如果没有这个循环的话
也不会出现死锁
有了这几个关于死锁的讨论
那我们在这张图里呢
去判断它是否有死锁
那就看刚才说的那四个条件
是否都成立
那这时候我们刚才那两个例子
一个是有死锁的
一个是没有死锁的
好 有了这些讨论之后
我们下边就可以来具体地讨论
我们对付死锁到底都有一些
什么样的处理方法