操作系统课程设计银行家算法

《操作系统－-课程设计报告》

银行家算法

姓名:

学号：

专业:

指导老师:

目录

一、设计目的 ............................................................................... 错误!未定义书签。

二、设计要求?错误!未定义书签。

三、设计内容和步骤 ................................................................... 错误!未定义书签。

四、算法描述?错误!未定义书签。

五、实验结果?错误!未定义书签。

六、实验心得 ............................................................................... 错误!未定义书签。

一、设计目的

银行家算法是避免死锁的一种重要方法,本实验要求用高级语言编写和调试一个简单的银行家算法程序。加深了解有关资源申请、避免死锁等概念，并体会和了解死锁和避免死锁的具体实施方法。

二、设计要求

在了解和掌握银行家算法的基础上,能熟练的处理课本例题中所给状态的安全性问题,能编制银行家算法通用程序,将调试结果显示在计算机屏幕上。

具体程序的功能要求:

1．设定进程对各类资源最大申请表示及初值确定。

2.设定系统提供资源初始状况(已分配资源、可用资源)。

３．设定每次某个进程对各类资源的申请表示。

4．编制程序，依据银行家算法，决定其申请是否得到满足。

三、设计内容和步骤

设计内容

银行家算法的思路：先对用户提出的请求进行合法性检查，即检查请求的是不大于需要的,是否不大于可利用的。若请求合法，则进行试分配。最后对试分配后的状态调用安全性检查算法进行安全性检查。若安全,则分配,否则,不分配，恢复原来状态,拒绝申请。

设计步骤

1、为实现银行家算法，系统中需要设置若干数据结构,用来表示系统中各进程的资源分配及需求情况。

假定系统中有M个进程，N类资源。进程数和资源数由程序中直接定义 #defｉnｅＭ 5 ／／总进程数

#defiｎe Ｎ 3 /／总资源数

银行家算法中使用的数据结构如下:

(1)可利用资源Available。这是一个含有m个元素的数组，其中的每一

个元素代表一类资源的空闲资源数目,其初值是系统中所配置的该类资源的数目，其数值随该类资源的分配和回收而动态的改变。如果Avaｉlable[j]=ｋ，表示系统中Ｒj类资源有k个。

（2）最大需求矩阵Max。这是一个n＊ｍ的矩阵，它定义了系统中每一个进程对各类资源的最大需求数目。如果Max[i,ｊ]=ｋ，表示进程Ｐi对Ｒj类资源的最大需求数为k个。

(3）分配矩阵Ａllocaｔｉｏn。这是一个ｎ＊m的矩阵，它定义了系统中当前已分配给每一个进程的各类资源。如果Alｌoｃatｉon[i,j］＝k，表示进程Pi当前已分到 Rｊ类资源有k个。

（４）需求矩阵Ｎeed。这是一个n＊m的矩阵,它定义了系统中每一个进程还需要的各类资源的数目。如果Nｅed ［ｉ,j]=ｋ，表示进程Pｉ需要Rｊ类资源有k个，才能完成任务。

ｉｎt Max[５］[3]={｛7,5,3｝,｛3,2,2},{9,0,2},{2,２,2｝,{4,３，3}}；//每个进程对每类资源的最大需求

ｉnt Ａllｏcation[5][3]=｛{0，１，0｝,｛2，0,０},{3,0,2},{2,1，１},｛0,0,２}｝;//系统已分配资源

ｉnt Avａliable［3]=｛3,３,2}; //系统可利用资源

inｔ Neeｄ［５][3]={{７,4,3},{1,2,２｝,｛６，0,0},｛0,1,1},｛４,3,1｝};／/还需要资源

int Reqｕesｔ［3]；

2、实现过程

主函数

voiｄmａin（）//主函数

{ ｉnt ｃhｏｉcｅ;

?showｄaｔa();

?safeAlｇoriｔhm(）;

ｄo

?{ prｉntf（＂\n输入接下来你要进行的操作１：分配资源 2:显示资源否则按任意键退出");

? scanf("%ｄ",&choice);

? sｗitch(cｈｏiｃｅ）

｛casｅ１：ｂankｅrAlgｏrithｍ(); bｒeａk;

?? case 2： sｈowｄaｔａ(）；break；

deｆaulｔ: break;

?}

}whiｌe（（choice==１)||（ｃhｏｉcｅ=＝２));

}

其中用到的函数操作有三个

?ｓhowdaｔa（)；//显示资源矩阵

?sａｆeAlgｏrithｍ(）;/／安全性检测算法

bａｎkeｒAlgorithm(）;//利用银行家算法对申请资源对进行判定

3、安全性检查

程序中安全性算法的描述如下：

（1) 设置如下两个工作向量：

Work:表示系统可提供给进程继续运行的各类资源的空闲资源数目,它含有ｍ个元素,执行安全性算法开始时,Work＝Ａvａilaｂlｅ。

Fｉnish：表示系统是否有足够的资源分配给进程,使之运行完成。开始时，Fｉｎiｓｈ[i]＝ｆalse；当有足够的资源分配给进程Ｐi时,令Fiｎisｈ[i]=true。

(2）从进程集合中找到一个能满足下列条件的进程:

Fｉｎｉsh［i]==ｆalsｅ;

Neｅd ｉ<＝ Wｏrk；,

如果找到了就执行步骤（３），否则执行步骤（4）。

（3) 当进程Pｉ获得资源后,可执行直到完成，并释放出分配给它的资源，故应执行

Work = Woｒｋ＋Allｏcaｔiｏn;

Fｉｎish［i]=fａlse;

然后转向第(2)步骤。

(4) 若所有进程中的Fｉｎｉsｈ[i]都是trｕｅ,则表示系统处于安全状

态；否则，系统处于不安全状态。

此过程由一个安全性检测函数实现:saｆeAlgoｒitｈm(）;/／安全性检测算法

4、对进程申请资源的处理

当某一进程提出资源申请时，系统须做出判断,能否将所申请资源分配给该进程。设ｒｅquｅst为进程i的请求向量，如果reqｕｅst[j]=K,表示进程i需要K个j资源。当系统发出请求后,系统按下述步骤开始检查：?（１) 如果ｒｅqueｓt［ｊ]<=need[ｉ][j],转向步骤２；否则报告出错，申请的资源大于它需要的最大值。

(2）如果requｅsｔ[j］<=avａilａble[j］,转向步骤3；否则报告出错，尚无足够的资源。?（３）系统试探着把资源分配给ｐ[i］,并修改下列数据结构中的值：

avaｉlａble［j]=availaｂｌe［j]-ｒeｑｕesｔ[j］

allｏcatiｏn[i][j］=ａllocaｔｉon[i][j]+ｒｅquest[j］

need［i]［ｊ］=need[i]［ｊ]-request[j]

（4)系统进行安全性算法，检查此次分配后，系统是否还处于安全状态,若安全,把资源分配给进程i；否则,恢复原来的资源分配状态，让进程ｉ等待。?整个过程由银行家算法实现:bａnkeｒAlgoｒitｈｍ()//利用银行家算法对申请资源对进行判定

四、算法描述

＃incluｄｅ＜striｎg.h>

#inｃlｕｄe<ｓｔdio.ｈ＞

＃ｄeｆine M ５//定义进程数

＃definｅ N ３ //定义资源数s

＃defｉne False 0

#defiｎｅ True 1

int Mａx[5]［3]={{7,５,３}，｛3,2,2}，{９,０,2｝，{2,2,2},{４,3,3}}；//每个进程对每类资源的最大需求

iｎt Alｌocatｉｏｎ［5]［3]={{0,１,0}，{２,0,０},{３,０,２},{2,1,1},{0，0,2}};/／系统已分配资源

int Avaliａbｌe[3]={３,３，2}; ／/系统可利用资源

ｉnt Neeｄ［5][3]＝｛｛7,４,3},｛１，2,2},{6,0,０},{０,1,１}，{4,３，1｝};//还需要资源

iｎｔ Requeｓｔ［3];

void showdata()//显示资源矩阵

｛

iｎｔ i,j;

printf（＂系统目前可利用的资源数量:＼n Ａ，B,Ｃ\n");

prｉｎtf("reｓouｃe: ＂);

for (j＝0;j

priｎtf("%d,",Avaliａble［j］);/／输出分配资源

printf("＼ｎ");

ｐrintf("各进程的资源需求:\ｎ＂);

fｏｒ(ｉ=0;ｉ＜M；i＋＋）

{

? prinｔｆ(＂pr%d: ",i);

ｆｏr (j=0;ｊ<Ｎ;j++）

{

? printf（"%ｄ，",Max[i][j]）;//输出最大需求资源数

? }

?ｐｒintf("\n"）;

}

ｐrintf(＂各进程得到资源:\n＂）;

for (i=０；i

{

ｐrintf("pr%d： ",i）;

fｏr（j＝0；j

?priｎｔf（"%d,＂,Allocaｔion［i］[ｊ]);//输出已分配资源数? prｉｎtf（"\ｎ")；

｝

prｉntf(＂各进程还需求资源:＼ｎ")；

for (ｉ＝０;i<Ｍ;i++）

{

pｒintf("pr%d: ",i）;

? for（ｊ=0；j<Ｎ;j++)

??prｉntｆ("%d,",Need[i］[j］);//输出还需要资源数

?ｐrintf（＂\n"）;

｝

｝

voｉd releａｓe(iｎt i)//判断是否安全,若不安全则释放第ｊ类资源{

?ｉnｔ j;

for （ｊ=0；ｊ

{

Avaliable［j]=Avaliabｌe[j］+Rｅquest[j];

Aｌlocatｉon[ｉ］[j]＝Allｏcａtiｏn[ｉ]［j]-Requeｓt[j]；

Neｅd[i][j］＝Neｅd[i]［j]+Rｅquesｔ[j];

}

｝

ｖoiｄ diｓtribuｔe(int i）／／若符合条件则对第j类资源进行分配{

ｉｎt j;

ｆｏｒ（j=０;j＜M;j＋+)

{

Avａｌiａble[j]＝Avaｌiabｌe[j］-Reｑuesｔ[j]；

Ａllocaｔioｎ[i][ｊ]=Alｌocatｉｏn[ｉ]［j]+Requｅst［ｊ]；

Nｅeｄ[i][j］=Need[i][j］－Ｒｅqueｓt[j］;

}

｝

vｏid saｆeAｌgｏｒithm()//安全性算法

{

inｔ Wｏrk[3],Finｉsh[M]＝｛0},ｒesｕｌｔ[Ｍ],ｒun;

?/* ｗｏrｋ：表示系统可提供给进程继续运行的所需的各类资源数目

? finisｈ：表示系统是否有足够的资源分配给进程

?ｒｅｓｕlｔ用来存放依次执行成功的线程*／

int i，j，ｋ=０，m，demand；

?fｏr(ｉ=0;i＜3；i+＋）

{

? Work[ｉ]=Avaliaｂｌe[i］; ／／开始的时候wｏrk=avaｉlaｂle

}

foｒ(i=0;i＜M;ｉ+＋）

? {

??dｅｍand=0;

?for（j=0;j

｛

?if （Finisｈ［i]==Falｓe&&Need[ｉ]［j]<=Ｗork［j］) ?{ demand＋＋;

?iｆ(dｅmand=＝３）//只有ABＣ三类资源都满足才把相应的线程记入数组reｓuｌt中

???｛?foｒ(m=０；m

???Woｒk[m]=Worｋ［m]+Allｏcatiｏn［i][m];//重新分配第i类线程的当前可利用资源

?Fiｎiｓh[i］＝Ｔrｕe;

? result[k］=i；

??ｉ=-1;

???? k+＋;

??}?

｝

? elsｅ

? if(Fｉniｓh[ｉ]==Ｆalse)

? {

?iｆ（i=＝M-1)

??? {?pｒiｎｔf("系统不安全\n");//如果不成功,输出系统不安全? rｕｎ=Faｌse; ?}

?? breaｋ;

??｝

?}

? }

priｎtf（＂系统资源分配成功!＂)；//如果安全，输出成功

prinｔｆ（"分配的序列:\ｎ");

ｆｏr（i＝0;ｉ

?{

prｉntf(＂pr％d "，resｕlt[ｉ]）；

? }

｝

vｏid bａｎkerAlgoriｔhm(）//利用银行家算法对申请资源对进行判定{

?int i,j，ＯK=1,ｒun=True;

?ｐrintf(＂\n请输入第一个要求分配的资源进程号从(0 to ４）:");

ｓｃanｆ（＂%ｄ",&i）;//输入须申请的资源号

printf("请输入进程 %d 申请的资源:\n"，i);

?for(j=0；j<３;j＋+)

?{