ineed

(完整word版)操作系统实验报告—银行家算法模拟

第1页

银行家算法模拟

【开发语言及实现平台或实验环境】

C++/C＃

MicrosoftVisualStudio6。0/MicrosoftVisualStudio。NET2003

【实验目的】

(1）进一步理解利用银行家算法避免死锁的问题；

（2）在了解和掌握银行家算法。

（3）理解和掌握安全序列、安全性算法

【实验内容】

（1）编写安全性算法；

(2）编写银行家算法，并编制银行家算法通用程序，将调试结果显示在计算机屏幕上，再检测和

笔算的一致性。

【实验原理】

一、安全状态

指系统能按照某种顺序如〈P1,P2,…,Pn>(称为序列为安全序列），为每个进

程分配所需的资源，直至最大需求,使得每个进程都能顺利完成。

二、银行家算法

假设在进程并发执行时进程i提出请求j类资源k个后，表示为Requesti[j]=k。系统按下

述步骤进行安全检查：

（1）如果Requesti≤Needi则继续以下检查，否则显示需求申请超出最大需求值的错误。

（2）如果Requesti≤Available则继续以下检查，否则显示系统无足够资源，Pi阻塞等待。

（3）系统试探着把资源分配给进程Pi，并修改下面数据结构中的数值：

(完整word版)操作系统实验报告—银行家算法模拟

第2页

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等待.

三、安全性算法

(1）设置两个向量：①工作向量Work：它表示系统可提供给进程继续运行所需的各类资源数

目，它含有m个元素,在执行安全算法开始时，Work∶=Available;②Finish:它表示系统是否

有足够的资源分配给进程，使之运行完成。开始时先做Finish［i]∶=fal;当有足够资源分配

给进程时，再令Finish［i］∶=true.

(2）从进程集合中找到一个能满足下述条件的进程：①Finish［i]=fal；②Need［i，j］

≤Work［j］；若找到，执行步骤（3),否则，执行步骤（4）。

（3）当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行：

➢Work［j］∶=Work［i］+Allocation［i，j］;

➢Finish［i］∶=true；

➢gotostep2;

（4）如果所有进程的Finish［i］=true都满足，则表示系统处于安全状态；否则，系统处于

不安全状态。

【实验步骤】

（1)参考图1-1所示流程图编写安全性算法.

N

初始化Work和Finish

开始

(完整word版)操作系统实验报告—银行家算法模拟

第3页

（2）编写统一的输出格式。

每次提出申请之后输出申请成功与否的结果。如果成功还需要输出变化前后的各种数据，

并且输出安全序列。

（3)参考图1—2所示流程图编写银行家算法。

N

Y

N

Y

Requesti[j]>Need[i][j]

出错返回：

return(error)

Requesti[j]>Available[j]

出错返回：(进程阻

塞)

return(error)

Available[j]=Available[j]–Requesti[j]

Allocation[i][j]=Allocation[i][j]+Requesti[j]

Need[i][j]=Need[i][j]–Requesti[j]

假定分配：

输入初始参数（资

源分配及请求情

开始

(完整word版)操作系统实验报告—银行家算法模拟

第4页

（4)编写主函数来循环调用银行家算法。

【实验思考】

（1)在编程中遇到了哪些问题？你是如何解决的？

答：编程的过程中，在实现安全性算法和银行家算法的问题上遇到了困难，比如进程使用字

母表示，如何识别进程和进程与程序联系在一起的问题，一直阻碍着我,后来结合将所学知识我

通过for循环语句将输入的字母先进行判断再与整型数据对应,然后再将进程与程序联系在一起,

从而解决了问题。

（2)在安全性算法中，为什么不用变量Available，而又定义一个临时变量work？

答：定义一个临时变量work是为了防止在不安全的情况下破坏数据原值，这样就能使程序更

加安全。

(完整word版)操作系统实验报告—银行家算法模拟

第5页

【源代码】

＃include〈iostream.h>

＃include〈string。h〉

＃defineM3//资源的种类数

＃defineN5//进程的个数

voidoutput(intiMax[N］［M］,intiAllocation［N][M］，intiNeed［N］[M］，intiAvailable

［M],charcName［N]）;//统一的输出格式

boolsafety(intiAllocation[N］[M］，intiNeed[N]［M],intiAvailable［M],charcName[N］）;

boolbanker（intiAllocation[N]［M］,intiNeed[N]［M］，intiAvailable［M］，charcName

［N］)；

voidmain()

｛

inti,j;

//当前可用每类资源的资源数

intiAvailable[M］=｛3,3，2｝;

//系统中N个进程中的每一个进程对M类资源的最大需求

intiMax［N］［M］=｛{7，5，3｝，{3，2，2｝，｛9，0，2｝，｛2,2，2},{4,3，3｝};

//iNeed［N]［M］每一个进程尚需的各类资源数

//iAllocation［N］［M］为系统中每一类资源当前已分配给每一进程的资源数

intiNeed[N]［M],iAllocation[N][M］=｛{0,1,1｝,｛2，0，0｝，｛3,0，2},{2，1,1},{0,0，

2｝｝;

//进程名

(完整word版)操作系统实验报告—银行家算法模拟

第6页

charcName［N］=｛'a’,’b'，’c'，’d',’e'｝;

boolbExitFlag=true;//退出标记

charch；//接收选择是否继续提出申请时传进来的值

boolbSafe；//存放安全与否的标志

//计算iNeed[N][M］的值

for(i=0；i〈N；i++）

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

iNeed[i]［j］=iMax[i］［j]—iAllocation［i]［j];

//输出初始值

output（iMax,iAllocation，iNeed,iAvailable,cName）；

//判断当前状态是否安全

bSafe=safety（iAllocation，iNeed,iAvailable，cName);

//是否继续提出申请

while（bExitFlag)

{

cout<<”n"<<"继续提出申请?ny为是；n为否。n";

cin〉>ch；

switch（ch）

｛

ca'y’：

//cout<<"调用银行家算法”；

bSafe=banker(iAllocation，iNeed，iAvailable,cName)；

(完整word版)操作系统实验报告—银行家算法模拟

第7页

if（bSafe）//安全，则输出变化后的数据

output（iMax,iAllocation，iNeed，iAvailable,cName）;

break;

ca’n'：

cout〈〈"退出。n”;

bExitFlag=fal；

break;

default：

cout<〈”输入有误，请重新输入：n";

｝

}

}

//输出

voidoutput（intiMax［N]［M]，intiAllocation［N]［M]，intiNeed［N][M]，intiAvailable

［M］,charcName［N]）

｛

inti，j；

cout<〈”ntMaxtAllocationtNeedtAvailable”<

cout<〈”tABCtABCtABCtABC"〈

for(i=0；i

{

cout<

(完整word版)操作系统实验报告—银行家算法模拟

第8页

for（j=0；j

cout<〈iMax[i]［j］<<””；

cout〈<”t";

for(j=0;j

cout〈

cout<<”t”；

for(j=0；j

cout〈〈iNeed[i］[j］<<””;

cout<〈"t”;

cout<〈"";

//Available只需要输出一次

if(i==0)

for（j=0;j〈M；j++)

cout<〈iAvailable［j］〈<"”；

cout<〈endl;

｝

｝

//安全性算法，进行安全性检查；安全返回true，并且输出安全序列,不安全返回fal，并输出

不安全的提示；

boolsafety（intiAllocation[N］[M],intiNeed［N][M］,intiAvailable[M],charcName[N］)

｛

inti，j，flag，x=0；

(完整word版)操作系统实验报告—银行家算法模拟

第9页

charName[N］；

intWork［M]；

boolFinish[N］;

for（j=0；j〈M；j++)

Work[j]=iAvailable［j]；

for（i=0；i〈N;i++）

Finish［i］=fal;

while（true）

｛

flag=0；

for（i=0；i

{

if(Finish［i]==fal＆＆Work［0］>=iNeed［i］[0]&＆Work［1］>=iNeed

［i］[1]＆&Work[2］〉=iNeed［i]［2])

{

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

{

Work［j］+=iAllocation［i］［j]；

｝

Finish[i]=true；

flag++；

Name［x++］=cName［i]；

(完整word版)操作系统实验报告—银行家算法模拟

第10页

}

｝

for（i=0；i

{

if（Finish［i］==fal）

{

i=i;

break；

｝

}

if（i==5）

{

cout〈〈”n";

cout〈<"安全序列为："；

for(x=0；x〈N；x++)

cout〈〈Name[x]<<”"；

cout〈<"n";

returntrue；

｝

if(flag==0）

｛

cout<<”无安全序列"；

(完整word版)操作系统实验报告—银行家算法模拟

第11页

returnfal;

}

｝

returntrue;

}

//安全返回true，不安全返回fal

boolbanker(intiAllocation［N][M],intiNeed［N]［M］,intiAvailable[M］，charcName

［N］）

｛

intiMax[N］[M］={{7，5,3｝,｛3,2，2}，{9，0,2},{2，2，2}，｛4，3，3}｝;

inti,j,Request[M],check[M];

boolf=true；

charx；

while(f)

{

cout〈<"请输入进程名：";

cin>>x;

for（i=0；i〈N；i++）

if(cName［i]==x)

{

i=i；

break;

(完整word版)操作系统实验报告—银行家算法模拟

第12页

}

if（i==5）

cout〈<”n您输入的进程名有误!请重新输入”；

el

f=fal;

}

cout〈〈”请输入各资源数量:";

for（j=0;j

cin>〉Request[j];

for（j=0；j

{

check[j]=Request［j］+iAllocation［i］［j］;

｝

for(j=0;j〈M;j++）

{

if（（iMax［i]［j］—check［j］）<0）

｛

cout<<"n资源申请超过最大需求量!！!n”；

returnfal;

｝

｝

for（j=0;j

(完整word版)操作系统实验报告—银行家算法模拟

第13页

｛

if(（iAvailable［j］-Request[j］)<0)

｛

cout<〈”n不能满足进程!！!n”；

returnfal;

}

｝

for（j=0;j

｛

iAvailable[j］—=Request[j]；

iAllocation［i]［j］+=Request[j］;

iNeed[i]［j］-=Request［j］;

｝

safety（iAllocation，iNeed，iAvailable,cName）;

returntrue；

｝

【实验结果与分析】

(完整word版)操作系统实验报告—银行家算法模拟

第14页

(完整word版)操作系统实验报告—银行家算法模拟

第15页

【实验思考及总结】

操作系统的基本特征是并发与共享.系统允许多个进程并发执行，并且共享系统的软、硬件

资源。为了最大限度的利用计算机系统的资源，操作系统应采用动态分配的策略，但是这样就

容易因资源不足，分配不当而引起“死锁”。而我本次课程设计就是得用银行家算法来避免“死

锁”。银行家算法就是一个分配资源的过程,使分配的序列不会产生死锁。此算法的中心思想是：

按该法分配资源时，每次分配后总存在着一个进程，如果让它单独运行下去，必然可以获得它

所需要的全部资源，也就是说，它能结束,而它结束后可以归还这类资源以满足其他申请者的需

要。

通过这次实验,我体会到银行家算法的重要性,银行家算法是避免死锁的主要方法,其思路在

很多方面都非常值得我来学习借鉴。