当前课程知识点：操作系统 > 第二十讲 死锁和进程通信 > 20.1 死锁概念 > 20.1 死锁概念
各位同学 大家好
今天我们来介绍死锁和进程通讯
死锁呢 是进程之间
由于共享资源所导致的一种
无限期等待的情况
那在这里头呢
我们会讨论死锁的基本概念
处理死锁的方法都有哪些
我们会具体介绍银行家算法
和死锁检测算法
这两个具体的算法
另外一个部分呢
是进程间通讯
也就是说两个进程之间
它们有一些什么样的通讯手段
那在这里呢
我们会介绍四种 信号和管道
消息队列和共享内存
那首先呢 我们来介绍死锁
死锁是由于竞争资源或通讯关系
两个或更多个线程
在执行的过程当中出现的一种
永远相互等待其他进程
才能引发的事件的状态
那这时候呢 我们先通过一个
具体的例子来看一下
这就是单向通行桥梁
那在这里头呢 这个桥梁呢
我们可以认为它是一种共享的资源
桥梁上只能单向通行
那这时候呢 不同方向的车
会共享这个单向通行的桥梁
那桥梁的每一部分呢
是一个资源
如果这个桥梁整个是一个资源
它也不会出现问题
那要占用就整个占用
实际上我们在这里
是由于部分占用所导致的问题
在这里呢 桥梁在使用的时候
可能出现死锁
比如说在这里头
对向行驶的两个车辆
在桥梁上正相遇了
好 那这时候谁也没有办法继续前行
都等待对方
而这种等待呢 是没有结果的
这种情况下呢 在我们通常做法呢
是一个方向的车辆倒退
好 那这样另一个方向呢能通行
这实际上就是我们在这里头
给到的一种死锁的解决办法
就是资源的抢占
与此同时呢
即使不出现这种情况
也会出现饥饿的情况
一个方向的车持续的运行
而另一个方向的车呢
就没有办法通过这个桥梁了
这是实际生活当中的一个例子
我们在操作系统里头
对于资源共享的情况
也会有一个跟它很类似的情况
那在具体讨论如何解决的办法之前
我们需要比较深入的来分析一下
死锁它出现的相关背景情况
你比如说我们资源的使用过程
出现死锁的条件等等
首先呢 我们来看
进程访问资源它的流程
在系统里头呢
我们存在各种类型的资源
比如说像我们这里说到的
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
这样构成一个循环
如果没有这个循环的话
也不会出现死锁
有了这几个关于死锁的讨论
那我们在这张图里呢
去判断它是否有死锁
那就看刚才说的那四个条件
是否都成立
那这时候我们刚才那两个例子
一个是有死锁的
一个是没有死锁的
好 有了这些讨论之后
我们下边就可以来具体地讨论
我们对付死锁到底都有一些
什么样的处理方法
-0.1 Piazza讨论区
--html
-0.2 在线实验平台
--实验平台使用帮助
--平台使用帮助
-0.2在线实验平台
--Raw HTML
-1.1 课程概述
--视频
-第一讲 操作系统概述--练习
-1.2 教学安排
--视频
-1.3 什么是操作系统
--Video
-1.4 为什么学习操作系统，如何学习操作系统
--Video
-1.5 操作系统实例
--视频
-1.6 操作系统的演变
--视频
-1.7 操作系统结构
--视频
-2.1 前言和国内外现状
-2.2 OS实验目标
-2.3 8个OS实验概述
-2.4 实验环境搭建
-2.5 x86-32硬件介绍
-2.6 ucore部分编程技巧
-2.7 演示实验操作过程
--Q6
--Q7
--Q10
-3.1 BIOS
--3.1 BIOS
-3.2 系统启动流程
-3.3 中断、异常和系统调用比较
-第三讲 启动、中断、异常和系统调用--3.3 中断、异常和系统调用比较
-3.4 系统调用
--3.4 系统调用
-第三讲 启动、中断、异常和系统调用--3.4 系统调用
-3.5 系统调用示例
-3.6 ucore+系统调用代码
-4.1 启动顺序
--4.1 启动顺序
-4.2 C函数调用的实现
-4.3 GCC内联汇编
-4.4 x86中断处理过程
-4.5 练习一
--4.5 练习一
-4.6 练习二
--4.6 练习二
-4.7 练习三
--4.7 练习三
-4.8 练习四 练习五
-4.9 练习六
--4.9 练习六
-5.1 计算机体系结构和内存层次
-5.2 地址空间和地址生成
-5.3 连续内存分配
-5.4 碎片整理
--5.4 碎片整理
-5.5 伙伴系统
--5.5 伙伴系统
-第五讲 物理内存管理: 连续内存分配--5.6 练习
-6.1 非连续内存分配的需求背景
-6.2 段式存储管理
-- 6.2 段式存储管理
-6.3 页式存储管理
-6.4 页表概述
--6.4 页表概述
-6.5 快表和多级页表
-6.6 反置页表
--6.6 反置页表
-6.7 段页式存储管理
-第六讲 物理内存管理: 非连续内存分配--6.8 练习
-7.1 了解x86保护模式中的特权级
-第七讲 实验二 物理内存管理--7.1 了解x86保护模式中的特权级
-7.2 了解特权级切换过程
-第七讲 实验二 物理内存管理--7.2 了解特权级切换过程
-7.3 了解段/页表
-第七讲 实验二 物理内存管理--7.3 了解段/页表
-7.4 了解UCORE建立段/页表
-第七讲 实验二 物理内存管理--7.4 了解UCORE建立段/页表
-7.5 演示lab2实验环节
-8.1 虚拟存储的需求背景
-8.2 覆盖和交换
-8.3 局部性原理
-8.4 虚拟存储概念
-8.5 虚拟页式存储
-8.6 缺页异常
--8.6 缺页异常
-9.1 页面置换算法的概念
-9.2 最优算法、先进先出算法和最近最久未使用算法
-第九讲 页面置换算法--9.2 最优算法、先进先出算法和最近最久未使用算法
-9.3 时钟置换算法和最不常用算法
-第九讲 页面置换算法--9.3 时钟置换算法和最不常用算法
-9.4 Belady现象和局部置换算法比较
-第九讲 页面置换算法--9.4 Belady现象和局部置换算法比较
-9.5 工作集置换算法
-第九讲 页面置换算法--9.5 工作集置换算法
-9.6 缺页率置换算法
-第九讲 页面置换算法--9.6 缺页率置换算法
-9.7 抖动和负载控制
-10.1 实验目标：虚存管理
-第十讲 实验三 虚拟内存管理--10.1 实验目标：虚存管理
-10.2 回顾历史和了解当下
-第十讲 实验三 虚拟内存管理--10.2 回顾历史和了解当下
-10.3 处理流程、关键数据结构和功能
-第十讲 实验三 虚拟内存管理--10.3 处理流程、关键数据结构和功能
-10.4 页访问异常
-第十讲 实验三 虚拟内存管理--10.4 页访问异常
-10.5 页换入换出机制
-第十讲 实验三 虚拟内存管理--10.5 页换入换出机制
-11.1 进程的概念
-第十一讲 进程和线程--11.1 进程的概念
-11.2 进程控制块
-第十一讲 进程和线程--11.2 进程控制块
-11.3 进程状态
-第十一讲 进程和线程--11.3 进程状态
-11.4 三状态进程模型
-11.5 挂起进程模型
-第十一讲 进程和线程--11.5 挂起进程模型
-11.6 线程的概念
-第十一讲 进程和线程--11.6 线程的概念
-11.7 用户线程
-第十一讲 进程和线程--11.7 用户线程
-11.8 内核线程
-第十一讲 进程和线程--11.8 内核线程
-12.1 进程切换
-第十二讲 进程控制--12.1 进程切换
-12.2 进程创建
-第十二讲 进程控制--12.2 进程创建
-12.3 进程加载
-第十二讲 进程控制--12.3 进程加载
-12.4 进程等待与退出
-第十二讲 进程控制--12.4 进程等待与退出
-13.1 总体介绍
-13.2 关键数据结构
-13.3 执行流程
-13.4 实际操作
-14.1 总体介绍
-14.2 进程的内存布局
-14.3 执行ELF格式的二进制代码-do_execve的实现
--14.3 执行ELF格式的二进制代码-do_execve的实现
-14.4 执行ELF格式的二进制代码-load_icode的实现
--14.4 执行ELF格式的二进制代码-load_icode的实现
-14.5 进程复制
-14.6 内存管理的copy-on-write机制
-15.1 处理机调度概念
-第十五讲 处理机调度--15.1 处理机调度概念
-15.2 调度准则
-15.3 先来先服务、短进程优先和最高响应比优先调度算法
--15.3 先来先服务、短进程优先和最高响应比优先调度算法
-第十五讲 处理机调度--15.3 先来先服务、短进程优先和最高响应比优先调度算法
-15.4 时间片轮转、多级反馈队列、公平共享调度算法和ucore调度框架
--15.4 时间片轮转、多级反馈队列、公平共享调度算法和ucore调度框架
-第十五讲 处理机调度--15.4 时间片轮转、多级反馈队列、公平共享调度算法和uc
-15.5 实时调度和多处理器调度
-第十五讲 处理机调度--15.5 实时调度和多处理器调度
-15.6 优先级反置
-第十五讲 处理机调度--15.6 优先级反置
-16.1 总体介绍和调度过程
-16.2 调度算法支撑框架
-16.3 时间片轮转调度算法
-16.4 Stride调度算法
-17.1 背景
--17.1 背景
-17.2 现实生活中的同步问题
-第十七讲 同步互斥--17.2 现实生活中的同步问题
-17.3 临界区和禁用硬件中断同步方法
-第十七讲 同步互斥--17.3 临界区和禁用硬件中断同步方法
-17.4 基于软件的同步方法
-第十七讲 同步互斥--17.4 基于软件的同步方法
-17.5 高级抽象的同步方法
-第十七讲 同步互斥--17.5 高级抽象的同步方法
-18.1 信号量
--18.1 信号量
-第十八讲 信号量与管程--18.1 信号量
-18.2 信号量使用
-第十八讲 信号量与管程--18.2 信号量使用
-18.3 管程
--18.3 管程
-第十八讲 信号量与管程--18.3 管程
-18.4 哲学家就餐问题
-18.5 读者-写者问题
-19.1 总体介绍
-19.2 底层支撑
-第十九讲 实验七 同步互斥--19.2 底层支撑
-19.3 信号量设计实现
-第十九讲 实验七 同步互斥--19.3 信号量设计实现
-19.4 管程和条件变量设计实现
-第十九讲 实验七 同步互斥--19.4 管程和条件变量设计实现
-19.5 哲学家就餐问题
-20.1 死锁概念
-第二十讲 死锁和进程通信--20.1 死锁概念
-20.2 死锁处理方法
-第二十讲 死锁和进程通信--20.2 死锁处理方法
-20.3 银行家算法
-第二十讲 死锁和进程通信--20.3 银行家算法
-20.4 死锁检测
-第二十讲 死锁和进程通信--20.4 死锁检测
-20.5 进程通信概念
-第二十讲 死锁和进程通信--20.5 进程通信概念
-20.6 信号和管道
-第二十讲 死锁和进程通信--20.6 信号和管道
-20.7 消息队列和共享内存
-第二十讲 死锁和进程通信--20.7 消息队列和共享内存
-21.1 文件系统和文件
-第二十一讲 文件系统--21.1 文件系统和文件
-21.2 文件描述符
-第二十一讲 文件系统--21.2 文件描述符
-21.3 目录、文件别名和文件系统种类
-第二十一讲 文件系统--21.3 目录、文件别名和文件系统种类
-21.4 虚拟文件系统
-第二十一讲 文件系统--21.4 虚拟文件系统
-21.5 文件缓存和打开文件
-第二十一讲 文件系统--21.5 文件缓存和打开文件
-21.6 文件分配
-第二十一讲 文件系统--21.6 文件分配
-21.7 空闲空间管理和冗余磁盘阵列RAID
-第二十一讲 文件系统--21.7 空闲空间管理和冗余磁盘阵列RAID
-22.1 总体介绍
-第二十二讲 实验八 文件系统--22.1 总体介绍
-22.2 ucore 文件系统架构
-第二十二讲 实验八 文件系统--22.2 ucore 文件系统架构
-22.3 Simple File System分析
-第二十二讲 实验八 文件系统--22.3 Simple File System分析
-22.4 Virtual File System分析
-第二十二讲 实验八 文件系统--22.4 Virtual File System分
-22.5 I/O设备接口分析
-第二十二讲 实验八 文件系统--22.5 I/O设备接口分析
-22.6 执行流程分析
-23.1 I/O特点
--视频
-第二十三讲 I/O子系统--23.1 I/O特点
-23.2 I/O结构
--816C80A0F5E3B8809C33DC5901307461
-第二十三讲 I/O子系统--23.2 I/O结构
-23.3 I/O数据传输
--C58221E14388B9DB9C33DC5901307461
-第二十三讲 I/O子系统--23.3 I/O数据传输
-23.4 磁盘调度
--567A3F1FCBFB3F4C9C33DC5901307461
-第二十三讲 I/O子系统--23.4 磁盘调度
-23.5 磁盘缓存
--C327536B80D25CE79C33DC5901307461
-第二十三讲 I/O子系统--23.5 磁盘缓存
-html
--html
