本篇文章给大家谈谈银行家算法,以及银行家算法破坏了死锁的什么条件对应的知识点,希望对各位有所帮助,不要忘了收藏本站喔。
本文目录一览:
- 1、银行家算法是什么?
- 2、浅析银行家算法
- 3、什么是银行家算法
- 4、“银行家算法”是怎样的一个算法?
- 5、银行家算法
- 6、网络操作系统中的银行家算法是什么?
银行家算法是什么?
银行家算法=-- -
1. 安全状态: 在某时刻系统中所有进程可以排列一个安全序列:{P1,P2,`````Pn},刚称此时,系统是安全的.
所谓安全序列{P1,P2,`````Pn}是指对于P2,都有它所需要剩余资源数量不大于系统掌握的剩余的空间资源与所有Pi(ji)所占的资源之和.
2.不安全状态可能产生死锁.
目前状态 最大需求 尚需
P1 3 9 6
P2 5 10 5
P3 2 4 2
在每一次进程中申请的资源,判定一下,若实际分配的话,之后系统是否安全.
3.银行家算法的思路:
1),进程一开始向系统提出最大需求量.
2),进程每次提出新的需求(分期贷款)都统计是否超出它事先提出的最大需求量.
3),若正常,则判断该进程所需剩余剩余量(包括本次申请)是否超出系统所掌握的
剩余资源量,若不超出,则分配,否则等待.
4.银行家算法的数据结构.
1),系统剩余资源量A[n],其中A[n]表示第I类资源剩余量.
2),各进程最大需求量,B[m][n],其中B[j][i]表示进程j对i
类资源最大需求.
3),已分配资源量C[m][n],其中C[j][i]表示系统j程已得到的第i资源的数量.
4),剩余需求量.D[m][n],其中D[j][i]对第i资源尚需的数目.
5.银行家算法流程:当某时刻,某进程时,提出新的资源申请,系统作以下操作:
1),判定E[n]是否大于D[j][n],若大于,表示出错.
2),判定E[n]是否大于系统剩余量A[n],若大于,则该进程等待.
3),若以上两步没有问题,尝试分配,即各变量作调整.
4),按照安全性推测算法,判断,分配过后,系统是否安全,若安全,则实际分配,否则,撤消分配,让进程等待.
6."安全性检测"算法
1),先定义两个变量,用来表示推算过程的数据.
F[n]=A[n],表示推算过程中,系统中剩余资源量的变化.
J[n]=False表示推算过程中各进程是否假设"已完成"
2),流程:
在"剩余"的进程中(在推算)过程中,一些进程假设已完成,查找D[j][n]=F[n]的进程,找到后令J[j]=True
(假设该进程完成),F[n]+D[j][n](该进程所占资源释放),如此循环执行.
若最后,所有的F[n]=True(在推算过程中,所有进程均可以完成),则表示(分配过后)系统是安全的,否则系统是不安全的.
参考资料:
浅析银行家算法
作为避免死锁的一种算法,银行家算法可以说是最为出名的了。这个名字的来源是因为该算法起初是为银行系统设计的,以确保银行在发放现金贷款时,不会发生不能满足所有客户需要的情况。在操作系统中也可以用它来实现避免死锁。
首先我们要了解银行家算法的本质也即避免死锁的原理。避免死锁作为一种事先预防死锁的策略,原理是在为各个进程分配资源的过程中不允许系统进去不安全状态,以此来避免死锁的发生。所谓安全状态,是指系统能按某种进程推进顺序为每个进程分配其所需资源,直至满足每个进程对资源的最大需求,使每个进程都可以顺利地完成。此时称该进程推进序列为安全序列,如果无法找到这样一个安全序列,则称系统处于不安全状态。
银行家算法中的数据结构。为了实现银行家算法,在系统中必须设置这样四个数据结构,分别用来描述系统中可利用的资源,所有进程对资源的最大需求,系统中的资源分配以及所有进程还需要多少资源的情况。
(1)可利用资源向量Available。这是一个含有m个元表的数组,其中的每一个元素代表一类可利用的资源数目。其数值随该类资源的分配和回收而动态地改变。如果 Available=K,则表示系统中现有Rj类资源K个。
(2)最大需求矩阵Max。这是一个nxm的矩阵,它定义了系统中n个进程中的每个进程对m类资源的最大需求。如果Max[i,j]=K,则表示进程i需要Rj类资源的最大数目为K。
(3)分配矩阵 Allocation。这也是一个nxm的矩阵,它定义了系统中每一类资源当前已分配给每一进程的资源数。如果Allocation[i,j]=K,表示进程i当前已分得Rj类资源的数目为K。
(4)需求矩阵Need。这也是一个nxm的矩阵,用以表示每一个进程尚需的各类资源数。如果Need[i,j]=K,则表示进程i还需要Rj类资源K个才能完成。
当一个进程发出请求资源的请求后,如果它所请求的资源大于目前系统可利用资源则不予分配。如果小于可利用资源,则系统试探着把资源分配给该进程,并修改分配之后的资源数值。接着系统执行安全算法,检查此次资源分配后系统是否处于安全状态。若安全,才正式将资源分配给该进程,以完成本次分配。否则,将本次的试探分配作废,恢复原来的资源分配状态,让该进程等待。
什么是银行家算法
银行家算法是最有代表性的避免死锁算法,是Dijkstra提出的银行家算法。这是由于该算法能用于银行系统现金贷款的发放而得名。
银行家可以把一定数量的资金供多个用户周转使用,为保证资金的安全,银行家规定:
(1)当一个用户对资金的最大需求量不超过很行家现有的资金时可接纳该用户.
(2)用户可以分期贷款,但贷款的总数不能超过最大需求量;
(3)当银行家现有的资金不能满足用户的尚需总数时,对用户的贷款可推迟支付,但总能使用户在有限的时间里得到贷款;
(4)当用户得到所需的全部资金后,一定能在有限的时间里归还所有资金
银行家算法是通过动态地检测系统中资源分配情况和进程对资源的需求情况来决定如何分配资源的,在能确保系统处于安全状态时才能把资源分配给申请者,从而避免系统发生死锁。
要记住的一些变量的名称
1 Available(可利用资源总数)
某类可利用的资源数目,其初值是系统中所配置的该类全部可用资源数目。
2 Max:某个进程对某类资源的最大需求数
3 Allocation: 某类资源已分配给某进程的资源数。
4 Need:某个进程还需要的各类资源数。
Need= Max-Allocation
系统把进程请求的资源(Request)分配给它以后要修改的变量
Available:=Available-Request;
Allocation:=Allocation+Request;
Need:= Need- Request;
“银行家算法”是怎样的一个算法?
银行家算法问题是研究一个银行家如何将其总数一定的现金安全地借给若干个顾客,使这些顾客既能满足对资金的要求,又能完成其交易,也使银行家可以收回自己的全部现金不致于破产。银行家要求每个顾客必须在开始前说明它所需借款总额和顾客当前的借款总数不能超过开始时声明的所需最大借款总额数。假如银行家能使他当前的全部顾客在有限的时间内完成他们的交易,那么当前的状态是安全的,反之状态是不安全的。
银行家算法
什么是银行家算法:
银行家算法是一种最有代表性的避免死锁的算法。在避免死锁方法中允许进程动态地申请资源,但系统在进行资源分配之前,应先计算此次分配资源的安全性,若分配不会导致系统进入不安全状态,则分配,否则等待。为实现银行家算法,系统必须设置若干数据结构。
要解释银行家算法,必须先解释操作系统安全状态和不安全状态。
安全序列是指一个进程序列{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类资源超过了它的最大值。
#includestdio.h
#includestdlib.h
#includestring.h
#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; iM; i++)
{
printf("\t%c类资源:",65+i);
scanf("%d",Available[i]);
}
//用户输入数据,初始化Max数组
printf("初始化最大需求数组:\n");
for(i=0; iN; i++)
{
printf("\tP%d进程最大需要\n",i);
for(j=0; jM; j++)
{
printf("\t\t%c类资源:",65+j);
scanf("%d",Max[i][j]);
}
}
//用户输入数据,初始化Allocation数组
printf("初始化已分配资源数组:\n");
for(i=0; iN; i++)
{
printf("\tP%d进程已分配\n",i);
for(j=0; jM; j++)
{
printf("\t\t%c类资源:",65+j);
scanf("%d",Allocation[i][j]);
}
}
//初始化Need数组
for(i=0; iN; i++)
for(j=0; jM; 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; iM; i++)
{
printf("\t\t%c类资源:",65+i);
scanf("%d",Request[i]);
}
for(i=0; iM; i++) //检查Request = Need ?
if(Request[i] Need[p][i])
{
printf("\t请求的%c类资源数超过它所宣布的最大值!\n",65+i);
break;
}
if(i == M) //通过上层检查,继续检查Request = Available ?
{
for(i=0; iM; i++)
if(Request[i] Available[i])
{
printf("\t尚无足够%c类资源,P%d须等待!\n",65+i,p);
break;
}
}
if(i == M) //尝试分配
{
for(i=0; iM; i++)
{
Available[i] -= Request[i];
Allocation[p][i] += Request[i];
Need[p][i] -= Request[i];
}
}
}while(iM);
//初始化Work,Finish向量
for(i=0; iM; i++)
{
Work[i] = Available[i];
}
for(i=0; iN; i++)
{
Finish[i] = false;
}
//安全性算法
do
{
total = temp;
for(i=0; iN; i++)
{
if(Finish[i] == false)
{
for(j=0; jM; j++)
if(Need[i][j] Work[j])
{
break;
}
if(j == M) //各类资源都满足Need = Work
{
for(j=0; jM; j++)
{
Work[j] += Allocation[i][j]; //释放资源
}
Finish[i] = true;
SafeSequence[temp++] = i; //加入安全序列
}
}
}
}while(total != temp); //所有进程检查一遍之后,如果安全序列有变化,则进行下一轮
//否则说明所有的Finish都为true,或者因没有安全序列退出循环
if(temp == N)
{
printf("安全序列:");
for(temp=0; tempN; temp++)
{
printf("P%d ",SafeSequence[temp]);
}
}
else
{
printf("系统处于不安全状态!不能分配!\n");
}
getchar();
getchar();
}
这个程序还行,输入有点麻烦,我自己编写的是用文件输入系统描述信息的,但是缺少说明,怕你搞不明白。希望对你有所帮助!
网络操作系统中的银行家算法是什么?
利用银行家算法避免死锁
. 银行家算法
设Requesti是进程Pi的请求向量,如果Requesti[j]=K,表示进程Pi需要K个Rj类型的资源。当Pi发出资源请求后,系统按下述步骤进行检查:�
(1) 如果Requesti[j]≤Need[i,j],便转向步骤2;否则认为出错,因为它所需要的资源数已超过它所宣布的最大值。
(2) 如果Requesti[j]≤Available[j],便转向步骤(3);否则, 表示尚无足够资源,Pi须等待。
(3) 系统试探着把资源分配给进程Pi,并修改下面数据结构中的数值:�
Available[j]∶=Available[j]-Requesti[j];�
Allocation[i,j]∶=Allocation[i,j]+Requesti[j];�
Need[i,j]∶=Need[i,j]-Requesti[j];�
(4) 系统执行安全性算法,检查此次资源分配后,系统是否处于安全状态。若安全,才正式将资源分配给进程Pi,以完成本次分配;否则, 将本次的试探分配作废,恢复原来的资源分配状态,让进程Pi等待。
(3) 系统试探着把资源分配给进程Pi,并修改下面数据结构中的数值:�
Available[j]∶=Available[j]-Requesti[j];�
Allocation[i,j]∶=Allocation[i,j]+Requesti[j];�
Need[i,j]∶=Need[i,j]-Requesti[j];�
(4) 系统执行安全性算法,检查此次资源分配后,系统是否处于安全状态。若安全,才正式将资源分配给进程Pi,以完成本次分配;否则, 将本次的试探分配作废,恢复原来的资源分配状态,让进程Pi等待。
(3) 系统试探着把资源分配给进程Pi,并修改下面数据结构中的数值:�
Available[j]∶=Available[j]-Requesti[j];�
Allocation[i,j]∶=Allocation[i,j]+Requesti[j];�
Need[i,j]∶=Need[i,j]-Requesti[j];�
(4) 系统执行安全性算法,检查此次资源分配后,系统是否处于安全状态。若安全,才正式将资源分配给进程Pi,以完成本次分配;否则, 将本次的试探分配作废,恢复原来的资源分配状态,让进程Pi等待。
发表评论