当前课程知识点：操作系统(RISC-V) > 第十五讲 死锁和并发错误检测 > 15.4 死锁检测 > 15.4 死锁检测
下面我们来讨论死锁检测算法
死锁检测和前边的银行家算法
不一样的地方在于
我不管分配的时候状态
我只是在系统运行不下去
我要去检测
看看系统里的资源分配状态
看是否已经出现死锁
所以死锁检测呢
是首先它允许系统进入死锁状态
然后系统维护资源分配图
当前哪些已经分配出去
哪些正在请求
具有这样一张图
然后周期性的调用死锁检测算法
来看这里是否存在死锁
如果有 那我就会
调用死锁恢复机制来进行恢复
那我们首先关心的是如何来检测
刚才我们在银行家算法里头
这个分配是否安全
那我是假装分配出去
然后去看它是否安全
而死锁检测呢实际上你已经分配完了
只是去看它是否安全了
那这时候说
这个检测和前边的银行家算法里的
安全检测有什么区别
那实际上在这里呢
最主要的一个区别就是
它没有最大资源请求量的判断
其它的它们俩是很相似的
首先它有一个向量
我现在系统里还有哪些可用资源
这是个M 维的向量
然后再有一个M乘N的矩阵
是说我每一个进程
已经分配了每一类资源各是多少
这是它的基本数据结构
然后说我们怎么检测呢
我首先是对两个变量进行初始化
一个是work
指的是我现在系统里的空闲资源
也就是它的可用资源
然后是每一个线程的状态
它是否还占用资源
如果说它还占用资源
那它就是false
这就是我们要考虑的
如果它已经不占用资源
那么这个要么是结束的
要么不是我们这里关心的
资源所需要讨论的
然后我们就需要来检查
是否是我现在剩余的这些资源
够某一个线程执行到结束
那所谓的执行到结束它有一个请求
这个请求和当前的
可用资源之间是个啥关系
如果是能找到
我满足某一个线程的当前请求
那这时候说 就算是找着了
如果说找了一圈之后没有办法满足
那这时候系统就有可能进入死锁状态了
找到之后我就把它以分配的
相当于我当前这个请求的资源
用剩余的资源是可以满足的分配给它
它完成运行它已经分配资源
又可以回收回来到这个work里头
那这样的话我这个线程就变成完成状态
然后我再回来找
如果说我经过若干轮
我把所有的线程的状态
都变成是完成状态的话
那么这时候呢
我的系统就算是安全的
如果说这里头有一个它是false
还处在等待状态的话
那么这时候它就是产生了死锁
我们看到在这里呢
银行家算法和死锁检测算法
它俩非常相似
但是有一些小的区别
然后它的计算量呢
我在这是对每一个线程要循环一圈
然后我要检查最多会到N的平方轮
然后我每一个资源会进行一次操作
那这时候呢 会是M乘N的平方
所以在这里头
如果说你的进程数目
和资源量很大的话
那这个死锁检测的开销是很大的
还有一个就是我多长时间检测一次
把这些开销算到里头去
实际上开销是很大的
那我们在前边说操作系统内部呢
通常情况下不管死锁的事
也就是由于这个原因
下边我们通过一个实际的例子
来看死锁检测
在这个例子当中呢
我有五个线程 三种资源
它的资源总数的情况在这
分别是7、2、6
然后这个是它当前已经分配出去的状态
和当前各个进程请求的状态
在这我们实际上就可以看到一种情况
我这里有两个请求是0
实际上我们通常情况下
只是在没有可用资源的时候
我才会来做这种检查
这两个没有请求的这个线程
它肯定是可以执行结束的
我们让它执行结束
这时候看到我的可用资源是变成3 1 3
这时我看
我这个资源是否可以满足剩余的
还需要资源的这些线程的资源需求量
我们从这可以看到 它都满足
所以这时候这个状态呢
它是能够正常结束
里头是没有死锁的
这是我们找到了一个安全序列
所以在这示例里头呢
看这个检查还是比较容易的
我们换一个角度
我实际上在这里呢
就把这两个的量给换了一下
这时候第一个仍然是可以结束
然后第三个原来是可以结束
现在变成是还要申请
但这时我们就看到
实际上这时候你没有办法
找到一个可以结束的状态
因为第一个可以回收是B这个资源
而B这个资源呢 只有它需要
剩下的都A和C
A和C都没有了 那这样的话
我们就都没有办法顺利的完成
所以这时候呢
系统里就出现死锁了
那出现死锁之后我们就会想到
这死锁怎么来处理
那在这之前呢
我们还会再有一个问题
说死锁检测算法我怎么来用
刚才我们说是没有资源了
我会来做这死锁检测
然后我多长时间检测一次
那这时候呢
你不能等它系统里已经是完全搞不动了
你才会来做这种检测
那这时候呢
你往回滚的量也是会很大的
这是你在选择时间和周期的时候
需要考虑的问题
然后再有一个呢
就是如果说里头出现了
多个造成死锁的循环
那这时候你很难分辨出
哪一个是里头的关键
因为我们找出关键的原因是
为了减少我终止的进程的数目
如果你找不着的话
那这时候你就会终止很多进程
这时候呢 它的开销也会是很大的
假定说我能找着是否有死锁
然后这时候我要进行进程的中终止
我需要把产生死锁的进程终止掉
我一次只终止一个
因为你一块终止很多个的话
有可能也是没必要的 我终止一个
然后看它是否还会再有死锁
那这时候说我到底终止哪一个呢
这是我们在这里
关于终止进程的顺序的考虑
首先第一个我们按优先级
那优先级最低的
然后再一个就是
我看它已经执行了多长时间
和未来它可能需要执行多长时间
有可能未来执行多长时间
你干脆就不知道
已经运行了多长时间
运行时间越长的我们越希望留下它
原因在于它已经占用系统资源
算了很长时间了
还有一种考虑是
它已经占用的资源的情况
实际上我们时间也是一种资源
它已经占用的资源和未来需要的资源
这都是我们在这里
选择终止进程的时候所需要考虑的
还有两种可能的考虑是我在终止的时候
我会终止多少个进程
这个数目越小越好
然后会说我终止了进程是什么样的
是前台的交互进程和后台的批处理
我们通常情况下是愿意
让用户交互的进程能够继续执行下去
这是终止进程的选择
然后我选择了要终止之后
那我怎么来终止呢
由抢夺资源
抢占进程所占用的资源
这是我选择成本最小的
然后我可以回退
回退到以前的某个状态
然后继续启动进程的执行
在这里头呢 可能会出现饥饿
我一个进程终止之后 我再继续执行
可能还会是同样的进程被终止
这时候呢
就会出现我们这里说的饥饿情况
这是我们关于死锁检测的讨论
-1.1 课程概述
--课程概述
-1.2 教学安排
--视频
-1.3 什么是操作系统
--Video
-1.4 为什么学习操作系统，如何学习操作系统
--Video
-1.5 操作系统实例
--视频
-1.6 操作系统的演变
--视频
-1.7 操作系统结构
--视频
-1.8 OS实验概述
--视频
-2.1 从OS角度看计算机系统
-2.2 从OS角度看RISC-V
-2.3 Rust语言与系统编程
-2.4 RISC-V CPU启动
-2.5 RISC-V CPU启动进一步分析
-3.1 基本概念与原理
-3.2 硬件架构支持
-3.3 中断处理机制
-3.4 系统调用
--3.4 系统调用
-4.1 计算机体系结构和内存层次
-4.2 地址空间和地址生成
-4.3 连续内存分配
-4.4 碎片整理
--4.4 碎片整理
-4.5 伙伴系统
--4.5 伙伴系统
-4.6 SLAB分配器
-5.1 非连续内存分配的需求背景
-5.2 段式存储管理
-- 5.2 段式存储管理
-5.3 页式存储管理
-5.4 页表概述
--5.4 页表概述
-5.5 快表和多级页表
-5.6 RISC-V页映射机制
-5.7 使能RISC-V页表
-6.1 虚拟存储的需求背景
-6.2 覆盖和交换
-6.3 局部性原理
-6.4 虚拟存储概念
-6.5 虚拟页式存储
-6.6 缺页异常
--6.6 缺页异常
-6.7 RISC-V缺页异常
-7.1 页面置换算法的概念
-7.2 最优算法、先进先出算法和最近最久未使用算法
-7.3 时钟置换算法和最不常用算法
-7.4 Belady现象和局部置换算法比较
-7.5 页表自映射
-8.1 工作集置换算法
-8.2 缺页率置换算法
-8.3 抖动和负载控制
-8.4 面向缓存的页替换算法
-9.1 进程的概念
-9.2 进程控制块
-9.3 进程状态
--9.3 进程状态
-9.4 三状态进程模型
-9.5 挂起进程模型
-9.6 线程的概念
-9.7 用户线程
--9.7 用户线程
-9.8 内核线程
--9.8 内核线程
-9.9 进程地址空间与熔断 (meltdown) 漏洞
-10.1 进程切换
-10.2 进程创建
-10.3 进程加载
-10.4 进程等待与退出
-10.5 rCore进程和线程控制
-11.1 处理机调度概念
-11.2 调度准则
-11.3 先来先服务、短进程优先和最高响应比优先调度算法
--11.3 先来先服务、短进程优先和最高响应比优先调度算法
-11.4 时间片轮转、多级反馈队列、公平共享调度算法和ucore调度框架
--11.4 时间片轮转、多级反馈队列、公平共享调度算法和ucore调度框架
-11.5 实时调度
-11.6 优先级反置
-11.7 rCore调度框架
-12.1 对称多处理与多核架构
-12.2 多处理器调度概述
-12.3 O(1)调度
-12.4 CFS调度
-12.5 BFS调度算法
-13.1 背景
--13.1 背景
-13.2 现实生活中的同步问题
-13.3 临界区和禁用硬件中断同步方法
-13.4 基于软件的同步方法
-13.5 高级抽象的同步方法
-14.1 信号量
--14.1 信号量
-14.2 信号量使用
-14.3 管程
--14.3 管程
-14.4 哲学家就餐问题
-14.5 读者-写者问题
-14.6 Rust语言中的同步机制
-15.1 死锁概念
-15.2 死锁处理方法
-15.3 银行家算法
-15.4 死锁检测
-15.5 并发错误检测
-16.1 进程通信概念
-16.2 信号和管道
-16.3 Linux信号机制
-16.4 消息队列和共享内存
-16.5 D-Bus机制
-16.6 Binder机制
-17.1 文件系统和文件
-17.2 文件描述符
-17.3 目录、文件别名和文件系统种类
-17.4 虚拟文件系统
-17.5 文件缓存和打开文件
-17.6 文件分配
-17.7 空闲空间管理和冗余磁盘阵列RAID
-18.1 FAT文件系统
-18.2.1 EXT4文件系统-历史
-18.2.2 EXT4文件系统-支持大容量存储
-18.2.3 EXT4文件系统-支持恢复异常
-18.3 ZFS文件系统
-19.1 I/O特点
-19.2 I/O结构
-19.3 I/O数据传输
-19.4 磁盘调度
-19.5 Linux I/O子系统
-20.1 Linux内核错误分析
-20.2.1 用rust写操作系统-系统编程语言rust
--20.2.1 用rust写操作系统-系统编程语言rust
-20.2.2 用rust写操作系统-rust与操作系统开发
--20.2.2 用rust写操作系统-rust与操作系统开发
-21.1 Background
-21.2 Futures in Rust
-21.3 Generators and async/await
--21.3 Generators and async/await
-21.4 Self-Referential Structs & Pin
--21.4 Self-Referential Structs & Pin
-21.5 Waker and Reactor
-22.1 Overview
-22.2.1 How VMM works - CPU
-22.2.2 How VMM works - memory & I/O