20.4 死锁检测慕课视频播放-操作系统-MOOC慕课视频教程-柠檬大学

下面我们来讨论死锁检测算法

死锁检测和前边的银行家算法

不一样的地方在于

我不管分配的时候状态

我只是在系统运行不下去

我要去检测

看看系统里的资源分配状态

看是否已经出现死锁

所以死锁检测呢

是首先它允许系统进入死锁状态

然后系统维护资源分配图

当前哪些已经分配出去

哪些正在请求

具有这样一张图

然后周期性的调用死锁检测算法

来看这里是否存在死锁

如果有那我就会

调用死锁恢复机制来进行恢复

那我们首先关心的是如何来检测

刚才我们在银行家算法里头

这个分配是否安全

那我是假装分配出去

然后去看它是否安全

而死锁检测呢实际上你已经分配完了

只是去看它是否安全了

那这时候说

这个检测和前边的银行家算法里的

安全检测有什么区别

那实际上在这里呢

最主要的一个区别就是

它没有最大资源请求量的判断

其它的它们俩是很相似的

首先它有一个向量

我现在系统里还有哪些可用资源

这是个M 维的向量

然后再有一个M乘N的矩阵

是说我每一个进程

已经分配了每一类资源各是多少

这是它的基本数据结构

然后说我们怎么检测呢

我首先是对两个变量进行初始化

一个是work

指的是我现在系统里的空闲资源

也就是它的可用资源

然后是每一个线程的状态

它是否还占用资源

如果说它还占用资源

那它就是false

这就是我们要考虑的

如果它已经不占用资源

那么这个要么是结束的

要么不是我们这里关心的

资源所需要讨论的

然后我们就需要来检查

是否是我现在剩余的这些资源

够某一个线程执行到结束

那所谓的执行到结束它有一个请求

这个请求和当前的

可用资源之间是个啥关系

如果是能找到

我满足某一个线程的当前请求

那这时候说就算是找着了

如果说找了一圈之后没有办法满足

那这时候系统就有可能进入死锁状态了

找到之后我就把它以分配的

相当于我当前这个请求的资源

用剩余的资源是可以满足的分配给它

它完成运行它已经分配资源

又可以回收回来到这个work里头

那这样的话我这个线程就变成完成状态

然后我再回来找

如果说我经过若干轮

我把所有的线程的状态

都变成是完成状态的话

那么这时候呢

我的系统就算是安全的

如果说这里头有一个它是false

还处在等待状态的话

那么这时候它就是产生了死锁

我们看到在这里呢

银行家算法和死锁检测算法

它俩非常相似

但是有一些小的区别

然后它的计算量呢

我在这是对每一个线程要循环一圈

然后我要检查最多会到N的平方轮

然后我每一个资源会进行一次操作

那这时候呢会是M乘N的平方

所以在这里头

如果说你的进程数目

和资源量很大的话

那这个死锁检测的开销是很大的

还有一个就是我多长时间检测一次

把这些开销算到里头去

实际上开销是很大的

那我们在前边说操作系统内部呢

通常情况下不管死锁的事

也就是由于这个原因

下边我们通过一个实际的例子

来看死锁检测

在这个例子当中呢

我有五个线程三种资源

它的资源总数的情况在这

分别是7、2、6

然后这个是它当前已经分配出去的状态

和当前各个进程请求的状态

在这我们实际上就可以看到一种情况

我这里有两个请求是0

实际上我们通常情况下

只是在没有可用资源的时候

我才会来做这种检查

这两个没有请求的这个线程

它肯定是可以执行结束的

我们让它执行结束

这时候看到我的可用资源是变成3 1 3

这时我看

我这个资源是否可以满足剩余的

还需要资源的这些线程的资源需求量

我们从这可以看到它都满足

所以这时候这个状态呢

它是能够正常结束

里头是没有死锁的

这是我们找到了一个安全序列

所以在这示例里头呢

看这个检查还是比较容易的

我们换一个角度

我实际上在这里呢

就把这两个的量给换了一下

这时候第一个仍然是可以结束

然后第三个原来是可以结束

现在变成是还要申请

但这时我们就看到

实际上这时候你没有办法

找到一个可以结束的状态

因为第一个可以回收是B这个资源

而B这个资源呢只有它需要

剩下的都A和C

A和C都没有了那这样的话

我们就都没有办法顺利的完成

所以这时候呢

系统里就出现死锁了

那出现死锁之后我们就会想到

这死锁怎么来处理

那在这之前呢

我们还会再有一个问题

说死锁检测算法我怎么来用

刚才我们说是没有资源了

我会来做这死锁检测

然后我多长时间检测一次

那这时候呢

你不能等它系统里已经是完全搞不动了

你才会来做这种检测

那这时候呢

你往回滚的量也是会很大的

这是你在选择时间和周期的时候

需要考虑的问题

然后再有一个呢

就是如果说里头出现了

多个造成死锁的循环

那这时候你很难分辨出

哪一个是里头的关键

因为我们找出关键的原因是

为了减少我终止的进程的数目

如果你找不着的话

那这时候你就会终止很多进程

这时候呢它的开销也会是很大的

假定说我能找着是否有死锁

然后这时候我要进行进程的中终止

我需要把产生死锁的进程终止掉

我一次只终止一个

因为你一块终止很多个的话

有可能也是没必要的我终止一个

然后看它是否还会再有死锁

那这时候说我到底终止哪一个呢

这是我们在这里

关于终止进程的顺序的考虑

首先第一个我们按优先级

那优先级最低的

然后再一个就是

我看它已经执行了多长时间

和未来它可能需要执行多长时间

有可能未来执行多长时间

你干脆就不知道

已经运行了多长时间

运行时间越长的我们越希望留下它

原因在于它已经占用系统资源

算了很长时间了

还有一种考虑是

它已经占用的资源的情况

实际上我们时间也是一种资源

它已经占用的资源和未来需要的资源

这都是我们在这里

选择终止进程的时候所需要考虑的

还有两种可能的考虑是我在终止的时候

我会终止多少个进程

这个数目越小越好

然后会说我终止了进程是什么样的

是前台的交互进程和后台的批处理

我们通常情况下是愿意

让用户交互的进程能够继续执行下去

这是终止进程的选择

然后我选择了要终止之后

那我怎么来终止呢

由抢夺资源

抢占进程所占用的资源

这是我选择成本最小的

然后我可以回退

回退到以前的某个状态

然后继续启动进程的执行

在这里头呢可能会出现饥饿

我一个进程终止之后我再继续执行

可能还会是同样的进程被终止

这时候呢

就会出现我们这里说的饥饿情况

这是我们关于死锁检测的讨论

操作系统课程列表：

第零讲在线教学环境准备

-0.1 Piazza讨论区

--piazza访问和使用

--html

-0.2 在线实验平台

-0.2在线实验平台

第一讲操作系统概述

-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.2 系统启动流程

-3.3 中断、异常和系统调用比较

--3.3 中断、异常和系统调用比较

-第三讲启动、中断、异常和系统调用--3.3 中断、异常和系统调用比较

-3.4 系统调用

--3.4 系统调用

-第三讲启动、中断、异常和系统调用--3.4 系统调用

-3.5 系统调用示例

--3.5 系统调用示例

-3.6 ucore+系统调用代码

--3.6 ucore+系统调用代码

第四讲实验一 bootloader启动ucore os

-4.1 启动顺序

-4.2 C函数调用的实现

-4.3 GCC内联汇编

-4.4 x86中断处理过程

-4.5 练习一

-4.6 练习二

-4.7 练习三

-4.8 练习四练习五

-4.9 练习六

第五讲物理内存管理: 连续内存分配

-5.1 计算机体系结构和内存层次

-5.2 地址空间和地址生成

-5.3 连续内存分配

-5.4 碎片整理

-5.5 伙伴系统

-第五讲物理内存管理: 连续内存分配--5.6 练习

第六讲物理内存管理: 非连续内存分配

-6.1 非连续内存分配的需求背景

-6.2 段式存储管理

-6.3 页式存储管理

-6.4 页表概述

-6.5 快表和多级页表

-6.6 反置页表

-6.7 段页式存储管理

-第六讲物理内存管理: 非连续内存分配--6.8 练习

第七讲实验二物理内存管理

-7.1 了解x86保护模式中的特权级

--7.1 了解x86保护模式中的特权级

-第七讲实验二物理内存管理--7.1 了解x86保护模式中的特权级

-7.2 了解特权级切换过程

--7.2 了解特权级切换过程

-第七讲实验二物理内存管理--7.2 了解特权级切换过程

-7.3 了解段/页表

--7.3 了解段/页表

-第七讲实验二物理内存管理--7.3 了解段/页表

-7.4 了解UCORE建立段/页表

--7.4 了解ucore建立段/页表

-第七讲实验二物理内存管理--7.4 了解UCORE建立段/页表

-7.5 演示lab2实验环节

--7.5 演示lab2实验环节

第八讲虚拟存储概念

-8.1 虚拟存储的需求背景

-8.2 覆盖和交换

-8.3 局部性原理

-8.4 虚拟存储概念

-8.5 虚拟页式存储

-8.6 缺页异常

第九讲页面置换算法

-9.1 页面置换算法的概念

--9.1 页面置换算法的概念

-9.2 最优算法、先进先出算法和最近最久未使用算法

--9.2 最优算法、先进先出算法和最近最久未使用算法

-第九讲页面置换算法--9.2 最优算法、先进先出算法和最近最久未使用算法

-9.3 时钟置换算法和最不常用算法

--9.3 时钟置换算法和最不常用算法

-第九讲页面置换算法--9.3 时钟置换算法和最不常用算法

-9.4 Belady现象和局部置换算法比较

--9.4 Belady现象和局部置换算法比较

-第九讲页面置换算法--9.4 Belady现象和局部置换算法比较

-9.5 工作集置换算法

--9.5 工作集置换算法

-第九讲页面置换算法--9.5 工作集置换算法

-9.6 缺页率置换算法

--9.6 缺页率置换算法

-第九讲页面置换算法--9.6 缺页率置换算法

-9.7 抖动和负载控制

--9.7 抖动和负载控制

第十讲实验三虚拟内存管理

-10.1 实验目标：虚存管理

--10.1 实验目标：虚存管理

-第十讲实验三虚拟内存管理--10.1 实验目标：虚存管理

-10.2 回顾历史和了解当下

-- 10.2 回顾历史和了解当下

-第十讲实验三虚拟内存管理--10.2 回顾历史和了解当下

-10.3 处理流程、关键数据结构和功能

--10.3 处理流程、关键数据结构和功能

-第十讲实验三虚拟内存管理--10.3 处理流程、关键数据结构和功能

-10.4 页访问异常

--10.4 页访问异常

-第十讲实验三虚拟内存管理--10.4 页访问异常

-10.5 页换入换出机制

--10.5 页换入换出机制

-第十讲实验三虚拟内存管理--10.5 页换入换出机制

第十一讲进程和线程

-11.1 进程的概念

--11.1 进程的概念

-第十一讲进程和线程--11.1 进程的概念

-11.2 进程控制块

--11.2 进程控制块

-第十一讲进程和线程--11.2 进程控制块

-11.3 进程状态

--11.3 进程状态

-第十一讲进程和线程--11.3 进程状态

-11.4 三状态进程模型

--11.4 三状态进程模型

-11.5 挂起进程模型

--11.5 挂起进程模型

-第十一讲进程和线程--11.5 挂起进程模型

-11.6 线程的概念

--11.6 线程的概念

-第十一讲进程和线程--11.6 线程的概念

-11.7 用户线程

--11.7 用户线程

-第十一讲进程和线程--11.7 用户线程

-11.8 内核线程

--11.8 内核线程

-第十一讲进程和线程--11.8 内核线程

第十二讲进程控制

-12.1 进程切换

--12.1 进程切换

-第十二讲进程控制--12.1 进程切换

-12.2 进程创建

--12.2 进程创建

-第十二讲进程控制--12.2 进程创建

-12.3 进程加载

--12.3 进程加载

-第十二讲进程控制--12.3 进程加载

-12.4 进程等待与退出

--12.4 进程等待与退出

-第十二讲进程控制--12.4 进程等待与退出

第十三讲实验四内核线程管理

-13.1 总体介绍

-13.2 关键数据结构

-13.3 执行流程

-13.4 实际操作

第十四讲实验五用户进程管理

-14.1 总体介绍

--14.1 总体介绍

-14.2 进程的内存布局

--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.5 进程复制

-14.6 内存管理的copy-on-write机制

--14.6 内存管理的copy-on-write机制

第十五讲处理机调度

-15.1 处理机调度概念

--15.1 处理机调度概念

-第十五讲处理机调度--15.1 处理机调度概念

-15.2 调度准则

--15.2 调度准则

-15.3 先来先服务、短进程优先和最高响应比优先调度算法

--15.3 先来先服务、短进程优先和最高响应比优先调度算法

-第十五讲处理机调度--15.3 先来先服务、短进程优先和最高响应比优先调度算法

-15.4 时间片轮转、多级反馈队列、公平共享调度算法和ucore调度框架

--15.4 时间片轮转、多级反馈队列、公平共享调度算法和ucore调度框架

-第十五讲处理机调度--15.4 时间片轮转、多级反馈队列、公平共享调度算法和uc

-15.5 实时调度和多处理器调度

--15.5 实时调度和多处理器调度

-第十五讲处理机调度--15.5 实时调度和多处理器调度

-15.6 优先级反置

--15.6 优先级反置

-第十五讲处理机调度--15.6 优先级反置

第十六讲实验六调度器

-16.1 总体介绍和调度过程

-16.2 调度算法支撑框架

-16.3 时间片轮转调度算法

-16.4 Stride调度算法

第十七讲同步互斥

-17.1 背景

--17.1 背景

-17.2 现实生活中的同步问题

--17.2 现实生活中的同步问题

-第十七讲同步互斥--17.2 现实生活中的同步问题

-17.3 临界区和禁用硬件中断同步方法

--17.3 临界区和禁用硬件中断同步方法

-第十七讲同步互斥--17.3 临界区和禁用硬件中断同步方法

-17.4 基于软件的同步方法

--17.4 基于软件的同步方法

-第十七讲同步互斥--17.4 基于软件的同步方法

-17.5 高级抽象的同步方法

--17.5 高级抽象的同步方法

-第十七讲同步互斥--17.5 高级抽象的同步方法

第十八讲信号量与管程

-18.1 信号量

--18.1 信号量

-第十八讲信号量与管程--18.1 信号量

-18.2 信号量使用

--18.2 信号量使用

-第十八讲信号量与管程--18.2 信号量使用

-18.3 管程

--18.3 管程

-第十八讲信号量与管程--18.3 管程

-18.4 哲学家就餐问题

--18.4 哲学家就餐问题

-18.5 读者-写者问题

--18.5 读者-写者问题

第十九讲实验七同步互斥

-19.1 总体介绍

--19.1 总体介绍

-19.2 底层支撑

--19.2 底层支撑

-第十九讲实验七同步互斥--19.2 底层支撑

-19.3 信号量设计实现

--19.3 信号量设计实现

-第十九讲实验七同步互斥--19.3 信号量设计实现

-19.4 管程和条件变量设计实现

--19.4 管程和条件变量设计实现

-第十九讲实验七同步互斥--19.4 管程和条件变量设计实现

-19.5 哲学家就餐问题

--19.5 哲学家就餐问题

第二十讲死锁和进程通信

-20.1 死锁概念

--20.1 死锁概念

-第二十讲死锁和进程通信--20.1 死锁概念

-20.2 死锁处理方法

--20.2 死锁处理方法

-第二十讲死锁和进程通信--20.2 死锁处理方法

-20.3 银行家算法

--20.3 银行家算法

-第二十讲死锁和进程通信--20.3 银行家算法

-20.4 死锁检测

--20.4 死锁检测

-第二十讲死锁和进程通信--20.4 死锁检测

-20.5 进程通信概念

--20.5 进程通信概念

-第二十讲死锁和进程通信--20.5 进程通信概念

-20.6 信号和管道

--20.6 信号和管道

-第二十讲死锁和进程通信--20.6 信号和管道

-20.7 消息队列和共享内存

--20.7 消息队列和共享内存

-第二十讲死锁和进程通信--20.7 消息队列和共享内存

第二十一讲文件系统

-21.1 文件系统和文件

--21.1 文件系统和文件

-第二十一讲文件系统--21.1 文件系统和文件

-21.2 文件描述符

--21.2 文件描述符

-第二十一讲文件系统--21.2 文件描述符

-21.3 目录、文件别名和文件系统种类

--21.3 目录、文件别名和文件系统种类

-第二十一讲文件系统--21.3 目录、文件别名和文件系统种类

-21.4 虚拟文件系统

--21.4 虚拟文件系统

-第二十一讲文件系统--21.4 虚拟文件系统

-21.5 文件缓存和打开文件

--21.5 文件缓存和打开文件

-第二十一讲文件系统--21.5 文件缓存和打开文件

-21.6 文件分配

--21.6 文件分配

-第二十一讲文件系统--21.6 文件分配

-21.7 空闲空间管理和冗余磁盘阵列RAID

--21.7 空闲空间管理和冗余磁盘阵列RAID

-第二十一讲文件系统--21.7 空闲空间管理和冗余磁盘阵列RAID

第二十二讲实验八文件系统

-22.1 总体介绍

--22.1 总体介绍

-第二十二讲实验八文件系统--22.1 总体介绍

-22.2 ucore 文件系统架构

--22.2 ucore 文件系统架构

-第二十二讲实验八文件系统--22.2 ucore 文件系统架构

-22.3 Simple File System分析

--22.3 Simple File System分析

-第二十二讲实验八文件系统--22.3 Simple File System分析

-22.4 Virtual File System分析

--22.4 Virtual File System分析

-第二十二讲实验八文件系统--22.4 Virtual File System分

-22.5 I/O设备接口分析

--22.5 I/O设备接口分析

-第二十二讲实验八文件系统--22.5 I/O设备接口分析

-22.6 执行流程分析

--22.6 执行流程分析

第二十三讲 I/O子系统

-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

--html

20.4 死锁检测在线视频