银行家算法步骤

操作系统 银行家算法

1. 简介

1.1 定义：银行家算法是一种用于避免死锁的资源分配策略，通过判断当前状态是否安全来决定是否为进程提供所需资源。

1.2 目的：保证系统能够按照合理顺序进行并发执行，并防止出现死锁情况。

2. 死锁概述

在多道程序环境下，当两个或更多进程因竞争有限数量的资源而无限等待时就会产生死锁。常见原因包括互斥、占有和不可剥夺性以及循环等待条件。

3. 资源管理模型

操作系统中使用了三类数据结构：

- 可利用向量(Avlable)：表示每种类型可被分配给各个进程实例数目；

- 最大需求矩阵(Maximum)：记录每个进程对某类资源最大需要量； - 分配矩阵(Allocation) ：描述已经成功地将某些单位从总体汇集转移到具体过渡态；

4. 进展与请求检查流程（Safety Algorithm）

当一个新任务到达后，在满足以下所有条件之前不能接受它:

a）如果存在这样一个i使得Request[i] > Need[i]，则拒绝请求；

b）如果存在这样一个i使得Request[i] > Avlable，则不接受该进程的资源申请。

5. 安全状态检查流程（Safety Algorithm）

当新任务到达后，在满足以下所有条件之前不能接受它:

a) 如果有某个j, 且Work[j]

b) 若对于每个 p∈ T 都有Allocation[p]+ Work >=

Need_p ，

将p从T移到Finish，并释放其占用的全部资源。

6. 算法实现步骤 1）初始化：定义Avlable、Max和Allocation矩阵以及Need数组；

2）判断是否安全：使用银行家算法进行系统当前状态下是否会发生死锁的判断；

3）处理用户请求：

- 检查用户请求所需资源量与可利用向量(Avlable)比较，

操作系统实验⼆：银⾏家算法

实验⼆ 银⾏家算法

⼀、实验⽬的

1、了解什么是操作系统安全状态和不安全状态；

2、了解如何避免系统死锁；

3、理解银⾏家算法是⼀种最有代表性的避免死锁的算法，掌握其实现原理及实现过程。

⼆、实验内容

根据银⾏家算法的基本思想，编写和调试⼀个实现动态资源分配的模拟程序，并能够有效避免死锁的发⽣。

三、实验原理

进程申请资源时，系统通过⼀定的算法判断本次申请是否不可能产⽣死锁（处于安全状态）。若可能产⽣死锁（处于不安全状态），则暂不进⾏本次资源分配，以避免死锁。算法有著名的银⾏家算法。1、什么是系统的安全状态和不安全状态？

所谓安全状态，是指如果系统中存在某种进程序列＜P1，P2，…，Pn＞，系统按该序列为每个进程分配其所需要的资源，直⾄最⼤需求，则最终能使每个进程都可顺利完成，称该进程序列＜P1，P2，…，Pn，＞为安全序列。

如果不存在这样的安全序列，则称系统处于不安全状态。2、银⾏家算法

把操作系统看作是银⾏家，操作系统管理的资源相当于银⾏家管理的资⾦，进程向操作系统请求分配资源相当于⽤户向银⾏家贷款。

为保证资⾦的安全，银⾏家规定: (1) 当⼀个顾客对资⾦的最⼤需求量不超过银⾏家现有的资⾦时就可接纳该顾客;

(2) 顾客可以分期贷款，但贷款的总数不能超过最⼤需求量;

(3) 当银⾏家现有的资⾦不能满⾜顾客尚需的贷款数额时,对顾客的贷款可推迟⽀付,但总能使顾客在有限的时间⾥得到贷款;

(4) 当顾客得到所需的全部资⾦后,⼀定能在有限的时间⾥归还所有的资⾦。

操作系统按照银⾏家制定的规则设计的银⾏家算法为：

（1）进程⾸次申请资源的分配：如果系统现存资源可以满⾜该进程的最⼤需求量，则按当前的申请量分配资源，否则推迟分配。

（2）进程在执⾏中继续申请资源的分配：若该进程已占⽤的资源与本次申请的资源之和不超过对资源的最⼤需求量，且现存资源能满⾜该进程尚需的最⼤资源量，则按当前申请量分配资源，否则推迟分配。

。

-可编辑修改-

操作系统银行家算法

课后作业

。

-可编辑修改- 一、实验目的

加深对多实例资源分配系统中死锁避免方法——银行家算法的理解，掌握

Windows 环境下银行家算法的实现方法。强调对于资源的管理、申请、比较来避免出现死锁的情况，保证系统的正常运行。

二、实验内容

1.在 Windows 操作系统上，利用DEVC++编写应用程序实现银行家算法。

2.创建 n 个线程来申请或释放资源，只有保证系统安全，才会批准资源申请。

三、实验步骤

（一）设计思路：

银行家算法可分为个主要的功能模块，其描述如下：

1.初始化

由用户输入数据，分别对运行的进程数、总的资源种类数、总资源数、各进程所需要的最大资源数量（Max），已分配的资源数量赋值。

2.安全性检查算法

(1)设置两个工作向量Work=AVAILABLE;FINISH=false;

(2)从进程集合中找到一个满足下述条件的进程，

FINISH==false;

NEED<=Work; 。

-可编辑修改- 如找到，执行(3)；否则，执行(4)

(3)设进程获得资源，可顺利执行，直至完成，从而释放资源。

Work+=ALLOCATION;

Finish=true;

(4).如所有的进程Finish= true，则表示安全；否则系统不安全。

3. 银行家算法

在避免死锁的方法中，所施加的限制条件较弱，有可能获得令人满意的系统性能。在该方法中把系统的状态分为安全状态和不安全状态，只要能使系统始终都处于安全状态，便可以避免发生死锁。

银行家算法的基本思想是分配资源之前,判断系统是否是安全的;若是,才分配。它是最具有代表性的避免死锁的算法。

设进程j提出请求REQUEST [i]，则银行家算法按如下规则进行判断。

(1).如果REQUEST [j] [i]<= NEED[j][i]，则转(2)；否则，出错。

(2).如果REQUEST [j] [i]<= AVAILABLE[j][i]，则转(3)；否则，出错。

(一) 实验目的

设计编写银行家算法，判断系统进程请求资源是否安全。

(二) 设计思想

主要运用递归的思想，当能找到一个能满足条件的进程时就进入下一层，并不在检查该进程，否则就返回上一层重新寻找，直到找到一个安全序列并输出该序列；若不能找到，则显示“不安全，无法分配”并结束系统。找到安全序列后提示输入所要分配给进程的资源数，判断是否能找到安全序列，找到则输出，否则就提示重新输入。

(三) 主要数据结构及变量说明

资源数据类型member：typedef struct{int a；int b；int c}，记录每项资源的数量；数据类型group：typedef struct{ member max; member

allacation; member need; member work;}，记录每个进程的相关属性；数据类型available：显示系统可利用资源的数目；数据类型max：每个进程对资源的最大需求；数据类型allacation：每个进程已分配的资源；数据类型work：系统可提供给进程继续运行的资源数目；e[]数列：存放判断进程是否已分配的指针。k存放系统是否进行的判断。

(四) 流程图

开始

初始化数据

输入max和allacation

needresource（）

k==0

k==0

输入分配资源操作

结束 是 是 否

否 main（）

开始

初始化

judge()

k==0

printgroup（）

结束 输出错误 是

否 shuchu（） 开始

y>9

判断条件

修改参数

y==9

k=1

q->e[x]=0 for(x=0;x<5;x++结束 judge(p,q,y+1) judge(）函数 (五) 运行结果

(六) 附录（代码）：

#include

#include

#include

#include

int k;

typedef struct

{

int e[5],f[5];