银行家算法

什么是银行家算法：

银行家算法是一种最有代表性的避免死锁的算法。在避免死锁方法中允许进程动态地申请资源，但系统在进行资源分配之前，应先计算此次分配资源的安全性，若分配不会导致系统进入不安全状态，则分配，否则等待。为实现银行家算法，系统必须设置若干数据结构。

要解释银行家算法，必须先解释 *** 作系统安全状态和不安全状态。

安全序列是指一个进程序列{P1，…，Pn}是安全的，如果对于每一个进程Pi(1≤i≤n），它以后尚需要的资源量不超过系统当前剩余资源量与所有进程Pj (j < i )当前占有资源量之和。

安全状态

如果存在一个由系统中所有进程构成的安全序列P1，…，Pn，则系统处于安全状态。安全状态一定是没有死锁发生。

不安全状态

不存在一个安全序列。不安全状态不一定导致死锁。

原理：

我们可以把 *** 作系统看作是银行家， *** 作系统管理的资源相当于银行家管理的资金，进程向 *** 作系统请求分配资源相当于用户向银行家贷款。

为保证资金的安全,银行家规定:

(1) 当一个顾客对资金的最大需求量不超过银行家现有的资金时就可接纳该顾客;

(2) 顾客可以分歧贷款,但贷款的总数不能超过最大需求量;

(3) 当银行家现有的资金不能满足顾客尚需的贷款数额时,对顾客的贷款可推迟支付,但总能使顾客在有限的时间里得到贷款;

(4) 当顾客得到所需的全部资金后,一定能在有限的时间里归还所有的资金

*** 作系统按照银行家制定的规则为进程分配资源，当进程首次申请资源时，要测试该进程对资源的最大需求量，如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源，否则就推迟分配。当进程在执行中继续申请资源时，先测试该进程已占用的资源数与本次申请的资源数之和是否超过了该进程对资源的最大需求量。若超过则拒绝分配资源，若没有超过则再测试系统现存的资源能否满足该进程尚需的最大资源量，若能满足则按当前的申请量分配资源，否则也要推迟分配。

程序举例：

已知进程{P0,P1,P2,P3,P4}，有三类系统资源A、B、C的数量分别为10、5、7，在T0时刻的资源

（1）若进程P1请求资源，发出请求向量Request1（1，0，2），编写程序用银行家算法判断系统能否将资源分配给它；

（2）若进程P2提出请求Request(0，1，0)，用银行家算法程序验证系统能否将资源分配给它。

程序代码：

P1进程提出的请求，可以分配。

P2进程不能分配，因为请求的B类资源超过了它的最大值。

#include<stdioh>

#include<stdlibh>

#include<stringh>

#define MAXSIZE 50

void main()

{

unsigned int Available[MAXSIZE]; //可利用资源向量

unsigned int Max[MAXSIZE][MAXSIZE]; //最大需求矩阵

unsigned int Allocation[MAXSIZE][MAXSIZE]; //已分配矩阵

unsigned int Need[MAXSIZE][MAXSIZE]; //需求矩阵

unsigned int Request[MAXSIZE]; //请求向量

unsigned int Work[MAXSIZE]; //工作向量

bool Finish[MAXSIZE]; //是否有足够资源分配给进程,使之运行完成

unsigned int SafeSequence[MAXSIZE]; //安全序列

int i,j;

int p; //请求资源的进程的下标

int temp = 0; //安全序列下标

int total = 0;

int N;

int M;

printf("请输入进程数N=");

scanf("%d",&N);

printf("请输入资源种类数M=");

scanf("%d",&M);

//用户输入数据,初始化Available数组

printf("初始化可用资源数组:\n");

for(i=0; i<M; i++)

{

printf("\t%c类资源:",65+i);

scanf("%d",&Available[i]);

}

//用户输入数据,初始化Max数组

printf("初始化最大需求数组:\n");

for(i=0; i<N; i++)

{

printf("\tP%d进程最大需要\n",i);

for(j=0; j<M; j++)

{

printf("\t\t%c类资源:",65+j);

scanf("%d",&Max[i][j]);

}

}

//用户输入数据,初始化Allocation数组

printf("初始化已分配资源数组:\n");

for(i=0; i<N; i++)

{

printf("\tP%d进程已分配\n",i);

for(j=0; j<M; j++)

{

printf("\t\t%c类资源:",65+j);

scanf("%d",&Allocation[i][j]);

}

}

//初始化Need数组

for(i=0; i<N; i++)

for(j=0; j<M; j++)

{

Need[i][j] = Max[i][j] - Allocation[i][j];

}

//进程发出资源请求后检查

do

{

printf("资源请求:\n");

printf("\t输入请求资源的进程下标:");

scanf("%d",&p);

printf("\t进程P%d请求\n",p);

//初始化请求向量

for(i=0; i<M; i++)

{

printf("\t\t%c类资源:",65+i);

scanf("%d",&Request[i]);

}

for(i=0; i<M; i++) //检查Request <= Need

if(Request[i] > Need[p][i])

{

printf("\t请求的%c类资源数超过它所宣布的最大值!\n",65+i);

break;

}

if(i == M) //通过上层检查,继续检查Request <= Available

{

for(i=0; i<M; i++)

if(Request[i] > Available[i])

{

printf("\t尚无足够%c类资源,P%d须等待!\n",65+i,p);

break;

}

}

if(i == M) //尝试分配

{

for(i=0; i<M; i++)

{

Available[i] -= Request[i];

Allocation[p][i] += Request[i];

Need[p][i] -= Request[i];

}

}

}while(i<M);

//初始化Work,Finish向量

for(i=0; i<M; i++)

{

Work[i] = Available[i];

}

for(i=0; i<N; i++)

{

Finish[i] = false;

}

//安全性算法

do

{

total = temp;

for(i=0; i<N; i++)

{

if(Finish[i] == false)

{

for(j=0; j<M; j++)

if(Need[i][j] > Work[j])

{

break;

}

if(j == M) //各类资源都满足Need <= Work

{

for(j=0; j<M; j++)

{

Work[j] += Allocation[i][j]; //释放资源

}

Finish[i] = true;

SafeSequence[temp++] = i; //加入安全序列

}

}

}

}while(total != temp); //所有进程检查一遍之后，如果安全序列有变化，则进行下一轮

//否则说明所有的Finish都为true,或者因没有安全序列退出循环

if(temp == N)

{

printf("安全序列:");

for(temp=0; temp<N; temp++)

{

printf("P%d ",SafeSequence[temp]);

}

}

else

{

printf("系统处于不安全状态!不能分配!\n");

}

getchar();

getchar();

}

这个程序还行，输入有点麻烦，我自己编写的是用文件输入系统描述信息的，但是缺少说明，怕你搞不明白。希望对你有所帮助！

一、单项选择题（在每小题的四个备选答案中，选出

一个正确的答案，并将其代码填入题干后的括号

内。每小题1分，共10分）

1 某一时刻、某一资源的信号量s=0，它表示 （）

A该时刻该类资源的可用数目为1

B该时刻该类资源的可用数目为－1

C该时刻等待该类资源的进程数目为1

D该时刻等待该类资源的进程数目为0

2 进程间的间接通信方式是指 （）

A源进程将消息发送给管道B源进程将消息发送给缓冲区

C源进程将消息发送给信箱D源进程将消息直接发送给目标进程

3 设置快表的目的在于 （）

A提高地址查找的命中率 B提高地址变换速度

C淘汰不用的页 D增加页表的容量

4 绝对路径和相对路径比较 （）

A绝对路径便于使用 B相对路径便于使用

C绝对路径比相对路径短 D相对路径字符比较长

5 并发是指两个或多个事件 （）

A在同一时刻发生 B在同一时间区段内发生

C两个进程相互交互 D在时间上相互无关

6 进程的组成有三部分：程序、PCB和 （）

A数据字段 B数据记录C数据集合 DSDT

7 若给定一个逻辑地址空间中的地址为A，页面大小为L，则页内地址D为 （）

AA/L BA mod L CINT[A/L] DA－L

8 按用途文件可分为用户文件、库文件和 （）

A只读文件 B只写文件C系统文件 D索引文件

9硬件在中断过程中参与的一项工作是 （）

A交换PSW B修改信号量C保留现场 D恢复现场

10分页式存储管理系统中，地址的构成为 （）

A页号 B页内地址

C页号和页内地址 D页号

二、多项选择题 （在每小题的五个备选答案中，选出二

至五个正确答案，并将其代码填在题干后的括号

内；错选、多选不得分。每小题2分，共18分）

1 存储器管理的功能包括 （）

A内存分配 B内存保护 C地址映射

D内存扩充 E磁盘空闲区管理

2 PCB的主要特征体现在 （）

A记录进程运行状态B标志进程的存在

C其中包含进程控制信息 D其中包含进程调度信息

E由程序和数据块组成

3 线程与进程比较而言，下面论述成立的有 （）

A一个线程通常由多个进程组成

B一个进程通常由多个线程组成

C相对而言，线程运行需要更多的资源

D线程比进程运行需更少的资源

E线程运行的系统开销更小

4 文件控制块FCB中包含的信息通常有三类，它们分别是 （）

A基本信息 B删除信息 C存取控制信息

D使用信息 E创建信息

5文件的分级安全管理一般可分成 （）

A系统级 B用户级 C目录级

D文件级 E字段级

6 第一级容错技术包括 （）A双份目录 B双份文件分配表 C热修复重定向

D写后读校验 E磁盘双工

7 按信息交换单位分类，I/O设备可分成 （）

A低速 B中速 C字符设备

D块设备 E高速

8 中断的过程通常包括 （）

A中断请求 B中断响应 C中断设置

D中断处理 E中断返回

9 按存取控制属性文件可以分为 （）

A只读 B系统文件 C用户文件

D只写 E只执行

三、判断改错题（认为对的，在题后的括号内打“√”，

认为错的打“×”，并加以改正。每小题2分，判

断、改错各1分，判断错误全题无分。共20分）

1 分页式管理中地址变换机构的任务在于将物理地址变换成逻辑地址。

（）

2由于有了 *** 作系统，同一时刻瞬间可以有多个程序被执行。 （）

3 索引分配支持直接访问。 （）

4阻塞态是进程等待CPU调度时所处的状态。 （）

5对于临界资源，进程间应当互斥访问。 （）

6与分布式 *** 作系统比较，网络 *** 作系统是集中式的。 （）

7在时间片轮转调度算法中，如时间片过小，就会引起因频繁调度而导致

的调度开销太大，系统运行性能低下。 （）

8银行家算法是用来预防死锁的。 （）

9为了使连入网络的计算机之间能正确地传送信息，制定了一组通信规则

或约定，这种规则或约定称为网络 *** 作系统。 （）

10动态重定位指地址变换在装入时不进行，而在程序执行时，边执行，边

转换。 （）

四、简答题（每小题5分，共30分）

1在创建一个进程时，所要完成的工作有哪些

2在高级通信机制中，进程有哪几种通信方式

3 用文字描述银行家算法的基本思想

4 分段保护的方法通常有哪些

5 设备驱动程序的主要功能有哪些

6 举例说明树型目录结构的组成。

五、设计题（每小题11分，共22分）

1 动态分区管理中，画出最坏适应算法的分配流程。（所谓最坏适应算法是指在当前所有空闲块中，找出的空闲块分配给申请者作业）

2 假定系统为某进程分配了三个物理块，现有以下的页面引用串：

7，0，1，2，0，3，0，1，2，3，0，3，2，1，2，0，1，7，0，1

利用LRU算法描述页面在内存块中的置换过程。

*** 作系统试题参考答案及评分标准

一。单项选择题（每小题 1分，共10分）

1-5： D C B B B6-10：C B C A C

二。多项选择题（错选、多选不得分。每小题2分，共18分）

1ABCD2ABCD3BDE4ACD

5ABCD6ABCD7CD8ABDE9ADE

三。判断改错题（每小题2分，判断、改错各1分，判断错误全题无分。共20分）

1×改正为：分页式管理中地址变换机构的任务在于将逻辑地址变换成物理地址。

2×改正为： *** 作系统实现进程的并发运行是从宏观角度，在单CPU系统中，每一时刻瞬间不可能执行多个程序。

3√

4×改正为：阻塞态是进程等待某一事件时所处的状态。

5√ 6√ 7√

8×改正为：银行家算法是用来避免死锁的。

9×改正为：为了使连入网络的计算机之间能正确地传送信息，制定了一组通信规则或约定，这种规则或约定称为协议。

10√

四、简答题（每小题5分，共30分）

1⑴申请空白PCB为新进程分配的数字标识符，并从PCB集合中索取一空白PCB；

⑵为新进程分配资源。包括必要的内存，进程需要的其它资源；

⑶初始化进程控制块。包括初始化标识符信息，处理机状态信息，处理机控制信息等；

⑷将新进程插入就绪队列。

2高级通信机制可分为三大类：

⑴共享存储器系统。相互通信的进程之间共享某些数据结构或共享存储区；

⑵消息传递系统。进程之间的数据交换以消息为单位，进行直接的或间接的通信；

⑶管道通信。管道体现为一个文件，发送信息的进程以字符流形式将数据送入管道，接收进程可以从管道中读取数据。

3银行家算法的基本思想是：将系统中的所有资源比做银行家的资金，每进行一次资源的分配，银行家都要从当前的资源分配情况出发，计算这种分配方案的安全性，如果是安全的，则进行分配，否则选择其它可能的分配方案。这样，每次分配都计算安全性，从而可以避免死锁的发生。

4分段保护的方法通常有：

⑴越界检查。在段表寄存器中存放有段表长度信息，在进行存储访问时，将逻辑地址空间的段号与段表长度进行比较，如段号等于或大于段表长度，将发出越界中断信号；

⑵存取控制检查。段表中设置存取控制字段，用于规定对该字段的访问方式；

⑶环保护机构。环按高低编号，数据按不同的级别分布在各个环中，访问时，进

程按自己所处的环级别对处在不同级别环中的资源进按环规则行访问。

5设备驱动程序的主要功能如下：

⑴将接收到的抽象要求转换为具体要求；

⑵检查用户I/O请求的合法性，了解I/O设备的状态、传递有关参数、设置设备的工作方式；

⑶发出I/O命令，启动分配到的I/O设备，完成指定的I/O *** 作；

⑷及时响应由控制器或通道发来的中断请求，并根据中断类型调用相应的中断处理程序；

⑸对于设置有通道的计算机系统，驱动程序还应能够根据用户的I/O请求，自动地生成通道程序。

6树型目录结构由多个结点构成树型结构，主目录作为根结点，称为根目录。数据文件作为树叶，其它所有目录均作为枝结点。由根结点到树叶的符号序列称为路径。

举例如下：

五、设计题（每小题11分，共22分）

1设用户请求的分区大小为usize，表中每个空闲分区的大小为msize若size=msize-usize（size表示切割后剩余分区的大小），addr表示对应size大小的分区起始地址。流程图如下所示。

这个 你要明确两个概念

Need 需求资源

Request 请求资源

需求是指最大要多少资源 请求是一次需要多少资源

我举个例子 某程序最大需要3个寄存器 做加法运算

开始只要两个 存加数a和被加数b 而且a和b不能被改变

但是这个计算 无比复杂 需要一个小时

计算完了 才需要第三个存结果c

那么他的need是3 第一次request是2 第二次request是1

为什么第一次request不直接是3呢

他要第三个寄存器 一个小时不用浪费啊 留给别人用啊

希望你懂了

import javautil;

class ThreadTest {

static int type = 4, num = 10; //定义资源数目和线程数目

static int[] resource = new int[type]; //系统资源总数

//static int[] copyResource = new int[type]; //副本

static Random rand = new Random();

static Bank[] bank = new Bank[num]; //线程组

Bank temp = new Bank();

public void init() {

//初始化组中每个线程，随机填充系统资源总数

for(int i = 0; i < type; i++)

resource[i] = randnextInt(10) + 80;

Systemoutprint("Resource:");

for(int i = 0; i < type; i++)

Systemoutprint(" " + resource[i]);

Systemoutprintln("");

for(int i = 0; i < banklength; i++)

bank[i] = new Bank("#" + i);

}

public ThreadTest4() {

init();

}

class Bank extends Thread {

//银行家算法避免死锁

public int[]

max = new int[type], //总共需求量

need = new int[type], //尚需资源量

allocation = new int[type]; //已分配量

private int[]

request = new int[type], //申请资源量

copyResource = new int[type]; //资源副本

private boolean isFinish = false; //线程是否完成

int[][] table = new int[banklength][type4]; //二维资源分配表

private void init() {

// 随机填充总共、尚需、已分配量

synchronized(resource) {

for(int i = 0; i < type; i++) {

max[i] = randnextInt(5) + 10;

need[i] = randnextInt(10);

allocation[i] = max[i] - need[i];

resource[i] -= allocation[i]; //从系统资源中减去已分配的

}

printer();

for(int i = 0; i < type; i++) {

if(resource[i] < 0) {

//若出现已分配量超出系统资源总数的错误则退出

Systemoutprintln("The summation of Threads' allocations is out of range!");

Systemexit(1);

}

}

}

}

public Bank(String s) {

setName(s);

init();

start();

}

public Bank() {

//none

}

public void run() {

try {

sleep(randnextInt(2000));

}

catch(InterruptedException e) {

throw new RuntimeException(e);

}

while(true) {

//程序没有完成时一直不断申请资源

if(askFor() == false) {

try {

sleep(1000);

}

catch(InterruptedException e) {

throw new RuntimeException(e);

}

}

else

tryRequest();

if(noNeed() == true)

break;

}

//休眠一段时间模拟程序运行

try {

sleep(1000);

}

catch(InterruptedException e) {

throw new RuntimeException(e);

}

Systemoutprintln(getName() + " finish!");

synchronized(resource) {

//运行结束释放占有资源

for(int i = 0; i < type; i++) {

resource[i] += allocation[i];

need[i] = allocation[i] = max[i] = 0;

}

}

}

private void printer() {

//打印当前资源信息

Systemoutprint(getName() + " Max:");

for(int i = 0; i < type; i++)

Systemoutprint(" " + max[i]);

Systemoutprint(" Allocation:");

for(int i = 0; i < type; i++)

Systemoutprint(" " + allocation[i]);

Systemoutprint(" Need:");

for(int i = 0; i < type; i++)

Systemoutprint(" " + need[i]);

Systemoutprint(" Available:");

for(int i = 0; i < type; i++)

Systemoutprint(" " + resource[i]);

Systemoutprintln("");

}

private boolean askFor() {

//随机产生申请资源量并检测是否超标

boolean canAsk = false;

for(int i = 0; i < type; i++) {

request[i] = randnextInt(20);

//防止申请量超过所需量

if(request[i] > need[i])

request[i] = need[i];

}

for(int i = 0; i < type; i++) //防止随机申请资源全为0

if(request[i] > 0)

canAsk = true;

synchronized(resource) {

//锁住可供资源检查是否超标

for(int i = 0; i < type; i++) {

if(request[i] > resource[i])

//如果申请资源超过可供资源则等待一段时间后重新申请

return false;

}

}

return canAsk;

}

private void tryRequest() {

//创建副本尝试分配请求

synchronized(resource) {

for(int i = 0; i < type; i++)

//依然要防止请求量超出范围

if(request[i] > resource[i])

return;

for(int i = 0; i < type; i++) {

//复制资源量并减去需求量到一个副本上

copyResource[i] = resource[i];

copyResource[i] -= request[i];

}

Systemoutprint(getName() + " ask for:");

for(int i = 0; i < type; i++)

Systemoutprint(" " + request[i]);

Systemoutprintln("");

if(checkSafe() == true) {

//如果检查安全则将副本值赋给资源量并修改占有量和需求量

for(int i = 0; i < type; i++) {

resource[i] = copyResource[i];

allocation[i] += request[i];

need[i] -= request[i];

}

Systemoutprintln(getName() + " request succeed!");

}

else

Systemoutprintln(getName() + " request fail!");

}

}

private boolean checkSafe() {

//银行家算法检查安全性

synchronized(bank) {

//将线程资源信息放入二维资源分配表检查安全性，0~type可用资源／type~type2所需资源／type2~type3占有资源／type3~-1可用+占用资源

for(int i = 0; i < banklength; i++) {

for(int j = type; j < type2; j++) {

table[i][j] = bank[i]need[j%type];

}

for(int j = type2; j < type3; j++) {

table[i][j] = bank[i]allocation[j%type];

}

}

//冒泡排序按需求资源从小到大排

for(int i = 0; i < banklength; i++) {

for(int j = i; j < banklength-1; j++) {

sort(j, 4);

}

}

//进行此时刻的安全性检查

for(int i = 0; i < type; i++) {

table[0][i] = copyResource[i];

table[0][i+type3] = table[0][i] + table[0][i+type2];

if(table[0][i+type3] < table[1][i+type])

return false;

}

for(int j = 1; j < banklength-1; j++) {

for(int k = 0; k < type; k++) {

table[j][k] = table[j-1][k+type3];

table[j][k+type3] = table[j][k] + table[j][k+type2];

if(table[j][k+type3] < table[j+1][k+type])

return false;

}

}

}

return true;

}

private void sort(int j, int k) {

//递归冒泡排序

int tempNum;

if(table[j][k] > table[j+1][k]) {

for(int i = type; i < type2; i++) {

tempNum = table[j][i];

table[j][i] = table[j+1][i];

table[j+1][i] = tempNum;

}

/temp = bank[j];

bank[j] = bank[j+1];

bank[j+1] = temp;/

}

else if(table[j][k] == table[j+1][k] && k < type2) //此资源量相同时递归下一个资源量排序并且防止超出范围

sort(j, k+1);

}

private boolean noNeed() {

//是否还需要资源

boolean finish = true;

for(int i = 0; i < type; i++) {

if(need[i] != 0) {

finish = false;

break;

}

}

return finish;

}

}

public static void main(String[] args) {

ThreadTest t = new ThreadTest();

//后台线程，设定程序运行多长时间后自动结束

new Timeout(30000, "---Stop!!!---");

}

}

状态A是安全的，状态B是不安全的。

首先，从状态A来说，目前可分配资源数是1，而用户3正好差一个资源，所以分配给用户3，用户3执行完毕，就可以释放6个资源，这样，其他三个用户也都可以完成了。

而状态B呢，可分配资源数只有2个，无论给哪个用户都不能满足用户的需求，这样就出现了循环等待，也就出现死锁了。除非有剥夺机制，才能不发生死锁。

以上就是关于银行家算法全部的内容，包括:银行家算法、2003年10月甘肃省高等教育自学ks *** 作系统试卷、 *** 作系统 银行家算法等相关内容解答，如果想了解更多相关内容，可以关注我们，你们的支持是我们更新的动力！