20.3 银行家算法慕课视频播放-操作系统-MOOC慕课视频教程-柠檬大学

下面我们来讨论银行家算法

银行家算法是一种死锁避免的方法

它指的是说

我们以银行贷款分配的策略为基础

通过判断系统是否处于安全状态

来确定我这一次的资源分配是否同意

这里借用的银行贷款分配策略是这样的

客户在申请贷款的时候

那你必须告诉银行

你最大的资金申请量是多少

并且保证在你的项目执行完毕之后

能及时归还贷款

对于我们操作系统里的

银行家算法也是有类似的要求的

从银行这个角度来说

它只要保证用户贷款的数量

不超过银行的最大值

那么这银行就应该尽可能的

满足客户的需求

也就是说银行手里头没钱不行

有钱不把它借给客户

实际上它的利用效率也是很低的

那这个比喻呢

我们可以这样来进行对应

银行家对应着我们这是操作系统

银行家要来判断

我借出去这笔钱行是不行

安全不安全

操作系统需要来判断

我这个资源分配出去是否安全

那银行家借的是资金

这是它的资源

对于我们操作系统来说

我的CPU内存

这是我的资源

银行家应对的是客户

而操作系统应对的

是申请资源的线程或者是进程

具体怎么做呢

首先它要对系统的状态

有一系列的记录

你比如说在我们这里头

假定系统里的线程数目是N

然后资源的种类是M

这时候呢它们有一个矩阵

M乘N的矩阵

表示每一个线程

它需要申请的每一类资源的总数

那有了这个数字之后呢

这里的一行

那肯定是小于我系统里

所拥有的所有资源的总量

这是一个最基本的限制

第二个是说我系统里的剩余资源

这地方是一个长度为M的向量

也就相当于系统里有M总资源

每一种资源当前还剩多少

再有一个是分配矩阵

这里描述是已经分配给

每一个线程的各类资源的数目

以便能够知道它和总量之间

到底是个什么样的关系

已经分配出去

不能大于每个进程

在起头的时候声称的总量

再有一个就是还有一个未来需要的量

这也是一个M乘N的矩阵

每一个线程它还需要M类的资源里的

每一种各需要多少那从这

这几个向量和矩阵之间

有这样一个关系

最大的和未来需求的

和已经分配的它们构成一个等式

未来需要的等于最大的

减去你已经分配的

这是银行家算法在运行过程当中

需要维护的信息

也就是说它需要知道

我现在总共有多少资源

哪些已经分配出去了

哪些还是空闲的

这是它必须掌握的否则的话

它没有办法判断到底是否处于安全

然后在这里就有一个安全的判断算法

这里头呢它的做法是说

我们把现在可用的资源复制一下

作为我当前进行判断的一个工作场所

然后就看在这个状态下

是不是我可以满足

当前已经分配过资源的这些线程

它的总的需求

如果能满足

表示我当前这种状态下

可以把所有已经分配出去的资源

最后在用户用完之后能够回收回来

如果不是这样的话

它就是不安全的那在这呢

每一个线程有一个状态

false表示当前还没有运行完

如何来判断当前是否安全呢

它就是在所有这些线程里头去查找

我未来需要的资源的总量

是否小于我当前有的这些资源总量

并且当前这个线程是没有执行完的

如果能找到这种情况

那实际上就说明我当前的可用资源

是可以满足某一个线程的

未来的所有需要的

那这时候呢

我能把它的资源给回收回来

如果你找了一圈之后没有找到

那这时候呢

就相当于是不安全了

如果找到那这时候呢

我就会把资源放回到可用资源里

就是放回到work里

同时把它的状态改为true

也就是说这个线程结束了

然后我再回到这来继续找

到最后所有的都满足

或者说有一个不满足

但是我找不着剩余的资源

可以满足某一个线程未来的需要

那这是最后一步

是否所有的线程

都已经变成完成状态

如果不是它就是不安全的

如果是那这时候它就是安全的

这是银行家算法里头最核心的部分

基本的思路就是我当前的剩余资源

可以满足某一个线程的未来需要

并且这种迭代循环到最后

能够满足所有的线程的需要

也就相当于我找到了一个安全序列

有了这个基本的判断之后

我们的银行家算法说起来就简单了

每一次请求的时候

我来判断这个请求是否安全

首先第一个判断

这个请求的资源量

和最大的需求量比较

它是不是比它小

需要的资源量和你当前申请的资源量

如果说你现在就已经超了

那肯定这就已经报错了

那我就拒绝分配给你相应的资源

如果满足我需求的量

还没有到我声称的最大量

那这时候呢

就进入第二步判断

看我现在可用的资源是不是够你用的

如果不够用线程必须等待

如果说够用

再来判断我现在这个是不是安全

怎么来判断呢

假定你把当前的用户申请允许了

把资源分配给它了

然后看我是不是能找到一个安全序列

假定你已经把用户的请求分配完毕了

这三个矩阵或者是向量

它的状态发生变化

然后我们调用前边的

安全状态判断算法

来对它进行判断

判断完的结果有两个

一个是安全的

一个是不安全的

如果安全的那我同意分配

并且把资源分配给相应用户

如果不安全那这时候

我前边就已经拒绝

或者说到这我也再拒绝

这是银行家算法

那这个算法到底怎么来用呢

我们下边通过一个例子来说明

最主要的部分就是

判断这个状态是否安全

假定给一个初始状态

这是我系统里的总的资源数目

R1、R2、R3

分别是9、3、6

它的资源总数

这是四个线程

它们所声称的资源需求总量

每一个的总量都小于我这个

比如最大是9

R1没有大于9的

如果说这时候就有一个

那你直接告诉它这事是不行的

这是我已经分配出去

到当前这个状态的

这两个矩阵相减就是未来它需要的

这时候我也可以告诉你我当前剩余的

那这个状态是否安全呢

我们需要判断的就是未来需要的量

和我当前所剩余的这些资源比较而言

是不是我可以找到一个序列

最后把所有的资源全部收回

我们对照了一下

第一次你可以找谁

1、2、3、4

最后一个资源只有这一个

T2是我正好所有的都满足的

因为它只要R3

我这里R3有 OK

这事行了

假定我把T2的需求满足分配

给它一个R3资源这时候呢

我就可以把这里

它用到的资源就都给收回来了

那么这时候我这就变成6、2、3

我分配完之后的状态是这样的

原来这两个的状态就都清零了

我这的状态变成6、2、3

然后这时候说我是安全的吗

实际上我们看下去

我这的剩余资源可以满足

剩下的三个线程任何一个

当前执行都是可以的

那这样的话

我又可以把它们的都给回收回来

再来这样的话

我们就看到最后剩一个

这肯定满足

所以我们说这个状态是安全的

那我们再换一个例子来看

在这地方同样是当前资源总数

各个线程需要的资源总量

以及与我已经分配出去的状态

和未来各个线程需要的资源量

和我当前的状态

用户再想分配一个变成这种状态

T1请求R1和R3各一个资源

变成现在这种状态了

那这种状态是安全的吗

我们说如果你敢这么分配

分配完了之后

剩余的资源就已经没有办法满足

这四个线程当中的任意一个

未来的需要了

这个可以满足剩下的R2

都是不满足的了

两个就不行

然后R3的话

那这两个不行

所以最后你就没有办法找到一个

当前资源够某一个线程未来所有的需要

所以这个状态是不安全的

如果说T1请求R1和R3资源数个数为一的话

那么这个请求呢

你是不能同意的

同意了你这个系统就是不安全的了

操作系统课程列表：

第零讲在线教学环境准备

-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.3 银行家算法在线视频