银行家算法Word格式.doc
- 文档编号:868027
- 上传时间:2023-04-29
- 格式:DOC
- 页数:26
- 大小:420KB
银行家算法Word格式.doc
《银行家算法Word格式.doc》由会员分享,可在线阅读,更多相关《银行家算法Word格式.doc(26页珍藏版)》请在冰点文库上搜索。
附录………………………………………………………………(11)
摘要
在多道操作系统中,可以利用多个进程并发执行来改善系统资源利用率,提高系统的吞吐量,但也可能发生人们不想看到的危险——死锁。
为了解决这个问题,人们引入了多种机制处理死锁问题。
本文主要介绍了操作系统如何运用银行家算法和安全性算法避免死锁的产生。
同时运用Java编程语言模拟计算机内部资源分配的过程。
让读者对银行家算法有更深刻的认识。
关键字:
死锁银行家算法安全性算法资源分配
1.需求分析.
1.1银行家算法的提出
本次课程设计主要解决的问题是死锁的避免。
死锁:
是指多个进程因竞争资源而造成的一种僵局,若无外力作用,这些进程将永远不能再向前推进。
避免死锁是在不破坏死锁产生的四个必要条件,在资源的动态分配中,防止进程进入可能发生死锁的不安全状态。
根据此原理,Dijkstra于1965年提出了一个经典的避免死锁的算法----银行家算法(banker’salgorithm)。
银行家算法是一种最有代表性的避免死锁的算法。
在避免死锁方法中允许进程动态地申请资源,但系统在进行资源分配之前,应先计算此次分配资源的安全性,若分配不会导致系统进入不安全状态,则分配,否则等待。
为实现银行家算法,系统必须设置若干数据结构。
所以通过编写一个模拟动态资源分配的银行家算法程序,进一步深入理解死锁、产生死锁的必要条件、安全状态等重要概念,并掌握避免死锁的具体实施方法.
1.2银行家算法设计思.想
我们可以把操作系统看作是银行家,操作系统管理的资源相当于银行家管理的资金,进程向操作系统请求分配资源相当于用户向银行家贷款。
为保证资金的安全,银行家规定:
(1)当一个顾客对资金的最大需求量不超过银行家现有的资金时就可接纳该顾客;
(2)顾客可以分歧贷款,但贷款的总数不能超过最大需求量;
(3)当银行家现有的资金不能满足顾客尚需的贷款数额时,对顾客的贷款可推迟支付,但总能使顾客在有限的时间里得到贷款;
(4)当顾客得到所需的全部资金后,一定能在有限的时间里归还所有的资金. 操作系统按照银行家制定的规则为进程分配资源,当进程首次申请资源时,要测试该进程对资源的最大需求量,如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源,否则就推迟分配。
当进程在执行中继续申请资源时,先测试该进程已占用的资源数与本次申请的资源数之和是否超过了该进程对资源的最大需求量。
若超过则拒绝分配资源,若没有超过则再测试系统现存的资源能否满足该进程尚需的最大资源量,若能满足则按当前的申请量分配资源,否则也要推迟分配。
安全状态:
所谓安全状态,是指系统能按某种进程顺序(P1,P2,…,Pn)(称〈P1,P2,…,Pn〉序列为安全序列),来为每个进程Pi分配其所需资源,直至满足每个进程对资源的最大需求,使每个进程都可顺利地完成。
如果系统无法找到这样一个安全序列,则称系统处于不安全状态。
不安全状态:
不存在一个安全序列,不安全状态一定导致死锁。
1.3银行家算法设计分析
1,银行家算法中的数据结构
1)可利用资源向量Available:
这是一个含有m个元素的数组,其中的每一个元素代表一类可利用的资源数目,其初始值是系统中所配置的该类全部可用资源的数目,其数值随该类资源的分配和回收而动态地改变。
如果Available[j]=K,则表示系统中现有Rj类资源K个。
2)最大需求矩阵Max:
这是一个n×
m的矩阵,它定义了系统中n个进程中的每一个进程对m类资源的最大需求。
如果Max[i,j]=K,则表示进程i需要Rj类资源的最大数目为K。
3)分配矩阵Allocation:
这也是一个n×
m的矩阵,它定义了系统中每一类资源当前已分配给每一进程的资源数。
如果Allocation[i,j]=K,则表示进程i当前已分得Rj类资源的数目为K。
4)需求矩阵Need:
m的矩阵,用以表示每一个进程尚需的各类资源数。
如果Need[i,j]=K,则表示进程i还需要Rj类资源K个,方能完成其任务。
显然:
Need[i,j]=Max[i,j]-Allocation[i,j]
2,银行家算法
设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,安全性算法
1.设置两个向量:
①向量Work:
它表示当前状态下,系统可提供给进程继续运行所需的各类资源数目,在执行安全算法开始时,其初值Work=Available;
②Finish:
它表示系统是否有足够的资源分配给该进程,使之运行完成。
初始令Finish[i]=false;
当有足够资源分配给进程时再令Finish[i]=true。
2.从进程集合中找到一个能满足下述条件的进程:
①Finish[i]=false;
②Need[i,j]≤Work[j]若找到,执行步骤3,否则,执行步骤4
3.当进程Pi获得资源后,可顺利执行,直至完成,并释放出分配给它的资源,故应执行上述步骤:
Work[j]=Work[j]+Allocation[i,j];
Finish[i]=true;
Gotostep2;
4.若所有进程的Finish[i]=true都满足,则表示系统处于安全状态。
否则,系统处于不安全状态。
2、概要设计
2.1主要的常量变量.
structyinhang
{
charname[10];
//定义进程名
intAllocation[20];
//定义分配
intMax[20];
//定义最大需求
intNeed[20];
//定义需求
intRequest[20];
//定义请求向量
intWork[20];
//定义工作向量
intflags;
//标志位
};
intAvailable[20];
2.2主要模块(函数)
voidmain();
2.3算法中用到的数据结构的说明
1.可利用资源向量available[],它是一个含有number个元素的数组,其中的每一个元素代表一类可利用的资源的数目,其初始值是系统中所配置的该类全部可用资源数目。
其数值随该类资源的分配和回收而动态地改变。
如果p[i].available[j]=k,标是系统中现有Rj类资源k个。
2.最大需求数组,这是一个具有n个进程的数组,它定义了系统中n个进程中的每一个进程对number类资源的最大需求。
如果a[i].max[j]=k,表示进程i需要Rj类资源的最大数目为k。
3.分配数组allocation[],这是一个具有n个进程的数组,它定义了系统中的每类资源当前一分配到每一个进程的资源数。
如果p[i].allocation[j]=k,表示进程i当前已经分到Rj类资源的数目为k。
allocationi表示进程i的分配向量,有数组allocation的第i行构成。
4.需求数组need,这是一个具有n个进程的结构体数组,用以表示每个进程还需要的各类资源的数目。
如果a[i].need[j]=k,表示进程i还需要Rj类资源k个,才能完成其任务,p[i].need表示进程i的需求向量,由矩阵need的第i行构成。
上述三个矩阵间存在关系:
p[i].need[j]=p[i].max[j]-p[i].allocation[j];
2.4银行家算法
1、Request是进程Pi的请求向量。
Request=k表示进程Pi请求分配Rj类资源k个。
当P[i]发出资源请求后,系统按下述步骤进行检查:
1).如果Request≤need,则转向步骤2;
否则,认为出错,因为它所请求的资源数已超过它当前的最大需求量。
2).如果Request≤available,则转向步骤3;
否则,表示系统中尚无足够的资源满足Pi的申请,Pi必须等待。
3).系统试探性地把资源分配给进程Pi,并修改下面数据结构中的数值:
p[i].available-=Request
p[i].allocation+=Request
p[i].need-=Request
4).系统执行安全性算法,检查此次资源分配后,系统是否处于安全状态。
如果安全才正式将资源分配给进程P[i],以完成本次分配;
否则,将试探分配作废,恢复原来的资源分配状态,让进程P[i]等待。
2、安全性算法
1)设置两个向量:
①工作向量work:
它表示系统可提供给进程继续运行所需的各类资源数目,它含有m个元素,在执行安全算法开始时work=available;
②flag:
它表示系统是否有足够的资源分配给进程,使之运行完成。
开始时先做flag=0;
当有足够资源分配给进程时,再令flag=1。
2)从进程集合中找到一个能满足下述条件的进程:
p[i].need[j]≤Work[j];
若找到,执行步骤3),否则,执行步骤4)。
3)当进程P[i]获得资源后,可顺利执行,直至完成,并释放出分配给它的资源,故应执行
p[i].work[j]+=p[i];
allocation[j];
p[i].flag=1;
gotostep2;
4)如果所有进程的p[i].flag=1都满足,则表示系统处于安全状态;
2.5流程图
系统流程图
银行家:
安全性:
安全性算法开始
work=available
p[i].flag=0
p[i].need[j]≤Work[j]?
所有进程flag=1?
系统安全并输出安全系列
p[i].flag=1;
系统不安全状态
安全性算法结束
N
Y
系统申请资源
4.调试与测试
5、实验总结
通过本次银行家算法实验,加深了我对银行家算法的了解,掌握了如何利用银行家算法避免死锁。
实验中遇到点问题,通过查阅资料。
通过这次的实践,使我的理论知识更加的牢固,使自己在学习以后的知识及编程语言更加具有信心了。
操作系统是计算机系统中必不可少的系统软件。
它是计算机系统中的各种资源的管理者和各种活动的组织者、指挥者。
在银行家算法这个系统之中,所采用的数据结构应是最基本的部分。
银行家算法的数据结构我们采用了一维数组与二维数组来存储,比如最大需求量Max[][]、已分配资源数Allocation[][]、仍需求资源数Need[][]、以及系统可利用的资源数、申请各类资源等数组。
数据结构虽然重要但却只是基础,而最主要的用以实现系统功能的应该有两个部分,一是用银行家算法来判断,二是用安全性算法来检测系统的安全性。
银行家算法是为了使系统保持安全状态。
我们可以把操作系统看作是银行家,操作系统管理相当与银行家管理的资金,进程向操作系统请求分配资源相当于用户向银行家贷款。
操作系统按照银行家制定的规则为进程分配资源,当进程首次申请资源时,要测试该进程对资源的最大需求量,如果系统现存的资源可以满足它的最大需求量则按当前的申请分配资源,否则就推迟分配。
若超过则拒绝分配资源,若没有超过则再测试系统现存的资源能否满足该进程尚需的最大资源量,若能满足则按当前的申请量分配资源,否则推配。
通过你上面的例子,我们看到银行家算法确实能保证系统时时刻刻都能处于安全状态,但它要不断检测每个进程对各类资源的占用和申请情况,需要花费较多的时间。
这次的实验,让我深有体会。
总之,银行家算法是避免死锁的主要方法,其思路在很多方面都非常值得我们来学习借鉴
参考文献
[1]孙钟秀等编著.操作系统教程[M].北京:
高等教育出版社,2004
[2]汤子瀛哲凤屏汤小丹编著计算机操作系统西安电子科技大学出版社
[3]严蔚敏,吴伟民.数据结构.北京:
清华大学出版社,2006.
[4]《C++程序设计与应用开发》,清华大学出版社
源程序:
#include<
iostream.h>
iomanip.h>
stdlib.h>
string.h>
math.h>
intn,m;
charb='
A'
;
voidmain()
/*进程的各个数据的初始化输入*/
structyinhangp[1000];
structyinhangtemp;
intnumss;
intflag=0,yy;
charnames[10];
cout<
<
"
请输入进程的个数:
endl;
cin>
>
n;
请输入进程的资源个数:
m;
请输入进程:
inti,j;
for(i=0;
i<
i++)
{
cout<
进程名:
"
cin>
p[i].name;
Max:
for(j=0;
j<
j++)
{
cin>
p[i].Max[j];
}
Allocation:
p[i].Allocation[j];
}
p[i].flags=0;
}
intsoucre[20];
输入各类资源的数目:
for(j=0;
b=(char)('
+j);
cout<
输入第"
b<
资源的数目:
cin>
soucre[j];
for(j=0;
for(j=0;
Available[j]=soucre[j];
}
{
for(j=0;
Available[j]-=p[i].Allocation[j];
/*绘制输出表*/
setiosflags(ios:
:
left)
<
setw(15)<
进程名"
Max"
Allocation"
Need"
Available"
b='
setw(5)<
b;
cout<
/*数据输出*/
for(j=0;
{
p[i].Need[j]=p[i].Max[j]-p[i].Allocation[j];
cout<
}
cout<
p[i].Need[j];
if(i==0)
cout<
Available[j];
//安全性
flag=1;
if(i==0)
for(j=0;
{
if(p[i].Need[j]>
Available[j])
flag=0;
break;
}
if(flag==0)
temp=p[i];
if(j==n-1)
{
p[j]=temp;
p[j].flags=0;
continue;
}
p[j]=p[j+1];
cin>
numss;
if(numss!
=0)
i--;
else
else
p[i].Work[j]=Available[j];
p[i].flags=1;
else
if(p
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 银行家 算法