实验二银行家算法实验报告

1、操作系统原理实验报告实验二 银行家算法实验专业：计算机科学与技术学号：030840204姓名：简郸实验日期：2010-5-22一、实验目的通过银行家算法理解操作系统安全状态和不安全状态。二、实验要求根据课本第204页在T0时刻系统分配的资源，用银行家算法判断系统是否处于安全序列，它的安全序列怎样。三、实验方法内容1. 算法设计思路我们可以把操作系统看作是银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求分配资源相当于用户向银行家贷款。操作系统按照银行家制定的规则为进程分配资源，当进程首次申请资源时，要测试该进程对资源的最大需求量，如果系统现存的资源可以满足它的最大需求量则按当

2、前的申请量分配资源，否则就推迟分配。当进程在执行中继续申请资源时，先测试该进程已占用的资源数与本次申请的资源数之和是否超过了该进程对资源的最大需求量。若超过则拒绝分配资源，若没有超过则再测试系统现存的资源能否满足该进程尚需的最大资源量，若能满足则按当前的申请量分配资源，否则也要推迟分配。2. 算法流程图3. 主要的常量变量n：系统中进程的总数 m：资源类总数 Available: ARRAY1.m of integer; Max: ARRAY1.n,1.m of integer; Allocation: ARRAY1.n,1.m of integer; Need: ARRAY1.n,1.m o

3、f integer; Request: ARRAY1.n,1.m of integer; 符号说明： Available 可用剩余资源 Max 最大需求 Allocation 已分配资源 Need 需求资源 Request 请求资源4. 主要模块当进程pi提出资源申请时，系统执行下列 步骤：(“=”为赋值符号，“=”为等号) step（1）若Request<=Need, goto step（2）；否则错误返回 step（2）若Request<=Available, goto step（3）；否则进程等待 step（3）假设系统分配了资源，则有： Available=Availabl

4、e-Request; Allocation=Allocation+Request; Need=Need-Request 若系统新状态是安全的，则分配完成 若系统新状态是不安全的，则恢复原状态，进程等待 为进行安全性检查，定义数据结构： Work:ARRAY1.m of integer; Finish:ARRAY1.n of Boolean; 安全性检查的步骤： step (1): Work=Available; Finish=false; step (2) 寻找满足条件的i： a.Finish=false; b.Need<=Work; 如果不存在，goto step(4) step(3)

5、 Work=Work+Allocation; Finish=true; goto step(2) step (4) 若对所有i,Finish=true,则系统处于安全状态，否则处于不安全状态 /* 银行家算法，操作系统概念(OS concepts Six Edition) reedit by Johnny hagen，SCAU，run at vc6.0 */四、实验代码#include "malloc.h" #include "stdio.h" #include "stdlib.h" #define alloclen sizeof(s

6、truct allocation) #define maxlen sizeof(struct max) #define avalen sizeof(struct available) #define needlen sizeof(struct need) #define finilen sizeof(struct finish) #define pathlen sizeof(struct path) struct allocation int value; struct allocation *next; ; struct max int value; struct max *next; ;

7、struct available /*可用资源数*/ int value; struct available *next; ; struct need /*需求资源数*/ int value; struct need *next; ; struct path int value; struct path *next; ; struct finish int stat; struct finish *next; ; int main() int row,colum,status=0,i,j,t,temp,processtest; struct allocation *allochead,*all

8、oc1,*alloc2,*alloctemp; struct max *maxhead,*maxium1,*maxium2,*maxtemp; struct available *avahead,*available1,*available2,*workhead,*work1,*work2,*worktemp,*worktemp1; struct need *needhead,*need1,*need2,*needtemp; struct finish *finihead,*finish1,*finish2,*finishtemp; struct path *pathhead,*path1,*

9、path2; printf("n请输入系统资源的种类数:"); scanf("%d",&colum); printf("请输入现时内存中的进程数:"); scanf("%d",&row); printf("请输入已分配资源矩阵:n"); for(i=0;i<row;i+) for (j=0;j<colum;j+) printf("请输入已分配给进程 p%d 的 %c 种系统资源:",i,'A'+j); if(status=0) al

10、lochead=alloc1=alloc2=(struct allocation*)malloc(alloclen); alloc1->next=alloc2->next=NULL; scanf("%d",&allochead->value); status+; else alloc2=(struct allocation *)malloc(alloclen); scanf("%d,%d",&alloc2->value); if(status=1) allochead->next=alloc2; status

11、+; alloc1->next=alloc2; alloc1=alloc2; alloc2->next=NULL; status=0; printf("请输入最大需求矩阵:n"); for(i=0;i<row;i+) for (j=0;j<colum;j+) printf("请输入进程 p%d 种类 %c 系统资源最大需求:",i,'A'+j); if(status=0) maxhead=maxium1=maxium2=(struct max*)malloc(maxlen); maxium1->next=ma

12、xium2->next=NULL; scanf("%d",&maxium1->value); status+; else maxium2=(struct max *)malloc(maxlen); scanf("%d,%d",&maxium2->value); if(status=1) maxhead->next=maxium2; status+; maxium1->next=maxium2; maxium1=maxium2; maxium2->next=NULL; status=0; printf(&

13、quot;请输入现时系统剩余的资源矩阵:n"); for (j=0;j<colum;j+) printf("种类 %c 的系统资源剩余:",'A'+j); if(status=0) avahead=available1=available2=(struct available*)malloc(avalen); workhead=work1=work2=(struct available*)malloc(avalen); available1->next=available2->next=NULL; work1->next=w

14、ork2->next=NULL; scanf("%d",&available1->value); work1->value=available1->value; status+; else available2=(struct available*)malloc(avalen); work2=(struct available*)malloc(avalen); scanf("%d,%d",&available2->value); work2->value=available2->value; if

15、(status=1) avahead->next=available2; workhead->next=work2; status+; available1->next=available2; available1=available2; work1->next=work2; work1=work2; available2->next=NULL; work2->next=NULL; status=0; alloctemp=allochead; maxtemp=maxhead; for(i=0;i<row;i+) for (j=0;j<colum;

16、j+) if(status=0) needhead=need1=need2=(struct need*)malloc(needlen); need1->next=need2->next=NULL; need1->value=maxtemp->value-alloctemp->value; status+; else need2=(struct need *)malloc(needlen); need2->value=(maxtemp->value)-(alloctemp->value); if(status=1) needhead->nex

17、t=need2; status+; need1->next=need2; need1=need2; maxtemp=maxtemp->next; alloctemp=alloctemp->next; need2->next=NULL; status=0; for(i=0;i<row;i+) if(status=0) finihead=finish1=finish2=(struct finish*)malloc(finilen); finish1->next=finish2->next=NULL; finish1->stat=0; status+;

18、 else finish2=(struct finish*)malloc(finilen); finish2->stat=0; if(status=1) finihead->next=finish2; status+; finish1->next=finish2; finish1=finish2; finish2->next=NULL; /*Initialization compleated*/ status=0; processtest=0; for(temp=0;temp<row;temp+) alloctemp=allochead; needtemp=nee

19、dhead; finishtemp=finihead; worktemp=workhead; for(i=0;i<row;i+) worktemp1=worktemp; if(finishtemp->stat=0) for(j=0;j<colum;j+,needtemp=needtemp->next,worktemp=worktemp->next) if(needtemp->value<=worktemp->value) processtest+; if(processtest=colum) for(j=0;j<colum;j+) work

20、temp1->value+=alloctemp->value; worktemp1=worktemp1->next; alloctemp=alloctemp->next; if(status=0) pathhead=path1=path2=(struct path*)malloc(pathlen); path1->next=path2->next=NULL; path1->value=i; status+; else path2=(struct path*)malloc(pathlen); path2->value=i; if(status=1) pathhead->next=path2; status+; path1->next=path2; path1=path2; finishtemp->stat=1; else for(t=0;t<colum;t+)