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

1、操作系统课程设计报告课题： 银行家算法 专业计算机科学与技术学生姓名班级b计算机072学号0710604216指导教师信息工程学院一、实验要求和实验目的实验目的：本课程设计是学生学习完操作系统原理课程后，进行的一次全面的综合训练，通过课程设计，让学生更好地掌握操作系统的原理及实现方法，加深对操作系统基础理论和重要算法的理解，加强学生的动手能力。实验要求：从课程设计的目的出发，通过设计工作的各个环节，达到以下教学要求：两人一组，每组从所给题目中任选一个（如自拟题目，需经指导教师同意），每个学生必须独立完成课程设计，不能相互抄袭，同组者文档不能相同；设计完成后，将所完成的工作交由指导教师检查；要求

2、写出一份详细的设计报告。二、设计内容：课题一、编制银行家算法通用程序，并检测所给状态的系统安全性。1）银行家算法中的数据结构：可利用资源向量available。这是一个含有m个 元素的数组，其中的每一个元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源的数目，其数值随该类资源的分配和回收而动态地改变。availablej=k，则表示系统中现有rj 类资源k个。最大需求矩阵max。这是一个n*m的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果maxi，j=k，则表示进程i需要rj类资源的最大数目为k。1. 分配矩阵allocation。这也是一个n*m的

3、矩阵，它定义了系统中每一类资料当前已分配给没一进程的资源数。如果allocationi，j=k，则表示进程i当前已分得rj类资源的数目为k。需求矩阵need。这也是一个n*m的矩阵，用以表示每一个进程尚需的各类资源数。如果needi,j=k，则表示进程i还需要rj类资源k个，方能完成其任务。上述三个矩阵存在如下关系： needi,j= maxi，j- allocationi，j2）银行家算法设requesti 是进程pi的请求向量，如果requesti，j=k,表示进程pi需要k个rj类型的资源。当pi发出资源请求后，系统按下述步骤进行检查：如果requesti，j= needi,j，便转向步

4、骤2；否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。三、设计思路设计思路a、 设计进程对各在资源最大申请表示及初值确定。b、 设定系统提供资源初始状态。c、 设定每次某个进程对各类资源的申请表示。d、 编制程序，依据银行家算法，决定其申请是否得到满足。四、详细设计1、初始化：由用户输入数据，分别对可利用资源向量矩阵available、最大需求矩阵max、分配矩阵allocation、需求矩阵need赋值。2、银行家算法：在避免死锁的方法中，所施加的限制条件较弱，有可能获得令人满意的系统性能。在该方法中把系统的状态分为安全状态和不安全状态，只要能使系统始终都处于安全状态，便可以避免发

5、生死锁。银行家算法的基本思想是分配资源之前,判断系统是否是安全的;若是,才分配。它是最具有代表性的避免死锁的算法。设进程cusneed提出请求request i，则银行家算法按如下规则进行判断。(1)如果request cusneed i= needcusneedi，则转(2)；否则，出错。(2)如果request cusneed i= availablecusneedi，则转(3)；否则，出错。银行家算法的数据结构假设有m个进程n类资源，则有如下数据结构:#define w 10#define r 20int m ; /总进程数int n ; /资源种类 int all_resourcew;

6、 /各种资源的数目总和int maxwr; /m个进程对n类资源最大资源需求量int availabler; /系统可用资源数int allocationwr; /m个进程已经得到n类资源的资源量int needwr; /m个进程还需要n类资源的资源量int requestr; /请求资源个数 3.安全性检测算法 1)先定义两个变量,用来表示推算过程的数据. fn=an,表示推算过程中,系统中剩余资源量的变化. jn=false表示推算过程中各进程是否假设已完成 系统试探分配资源，修改相关数据：availablei-=requestcusneedi;allocationcusneedi+=re

7、questcusneedi;、needcusneedi-=requestcusneedi;4、安全性检查算法1)设置两个工作向量work=available;finish2)从进程集合中找到一个满足下述条件的进程，finish=false;need=work;如找到，执行(3)；否则，执行(4)3)设进程获得资源，可顺利执行，直至完成，从而释放资源。work+=allocation;finish=true;goto 24)如所有的进程finish= true，则表示安全；否则系统不安全。 安全状态: 在某时刻系统中所有进程可以排列一个安全序列:p1,p2,pn,刚称此时,系统是安全的. 所谓安

8、全序列p1,p2,pn是指对于p2,都有它所需要剩余资源数量不大于系统掌握的剩余的空间资源与所有pi(ji)所占的资源之和. 不安全状态可能产生死锁.目前状态 最大需求 尚需 p1 3 9 6 p2 5 10 5 p3 2 42 在每一次进程中申请的资源,判定一下,若实际分配的话,之后系统是否安全. 银行家算法的数据结构. 五、代码清单#include #include #include #include #include #include const int max_p=20; const int maxa=10; /定义a类资源的数量 const int maxb=5; const int

9、 maxc=7; typedef struct node int a; int b; int c; int remain_a; int remain_b; int remain_c; bank; typedef struct node1 char name20; int a; int b; int c; int need_a; int need_b; int need_c; process; bank banker; process processesmax_p; int quantity; /初始化函数 void initial() int i; banker.a=maxa; banker.

10、b=maxb; banker.c=maxc; banker.remain_a=maxa; banker.remain_b=maxb; banker.remain_c=maxc; for(i=0;imax_p;i+) strcpy(,); processesi.a=0; processesi.b=0; processesi.c=0; processesi.need_a=0; processesi.need_b=0; processesi.need_c=0; /新加作业 void add() char name20; int flag=0; int t; int ne

11、ed_a,need_b,need_c; int i; coutendl; cout新加作业endl; coutname; for(i=0;iquantity;i+) if(!strcmp(,name) flag=1; break; if(flag) cout错误,作业已存在endl; else coutneed_a; coutneed_b; coutneed_c; t=1; coutneed_abanker.remain_a) cout错误,所需a类资源大于银行家所剩a类资源banker.remain_b) cout错误,所需b类资源大于银行家所剩b类资源bank

12、er.remain_c) cout错误,所需c类资源大于银行家所剩c类资源endl; t=0; if(t) strcpy(,name); processesquantity.need_a=need_a; processesquantity.need_b=need_b; processesquantity.need_c=need_c; quantity+; cout新加作业成功endl; else cout新加作业失败endl; /为作业申请资源 void bid() char name20; int i,p; int a,b,c; int flag;

13、 coutendl为作业申请资源endl; coutname; p=-1; for(i=0;iquantity;i+) if(!strcmp(,name) p=i; break; if(p!=-1) couta; coutb; coutc; flag=1; if(abanker.remain_a)|(aprocessesp.need_a-processesp.a) cout错误,所申请a类资源大于银行家所剩a类资源或该进程还需数量banker.remain_b)|(bprocessesp.need_b-processesp.b) cout错误,所申请b类资源大于银

14、行家所剩b类资源或该进程还需数量banker.remain_c)|(cprocessesp.need_c-processesp.c) cout错误,所申请c类资源大于银行家所剩c类资源或该进程还需数量endl; flag=0; if(flag) banker.remain_a-=a; banker.remain_b-=b; banker.remain_c-=c; processesp.a+=a; processesp.b+=b; processesp.c+=c; cout为作业申请资源成功endl; else cout为作业申请资源失败endl; else cout该作业不存在endl; /撤

15、消作业 void finished() char name20; int i,p; coutendl撤消作业endl; coutname; p=-1; for(i=0;iquantity;i+) if(!strcmp(,name) p=i; break; if(p!=-1) banker.remain_a+=processesp.a; banker.remain_b+=processesp.b; banker.remain_c+=processesp.c; for(i=p;iquantity-1;i+) processesi=processesi+1; strcp

16、y(,); processesquantity-1.a=0; processesquantity-1.b=0; processesquantity-1.c=0; processesquantity-1.need_a=0; processesquantity-1.need_b=0; processesquantity-1.need_c=0; quantity-; cout撤消作业成功endl; else cout撤消作业失败endl; /查看资源情况 void view() int i; coutendl查看资源情况endl; cout银行家所剩资

17、源(剩余资源/总共资源)endl; couta类:banker.remain_a/banker.a; cout b类:banker.remain_b/banker.b; cout c类:banker.remain_c/banker.c; coutendlendl作业占用情况(已占用资源/所需资源)endl0) for(i=0;iquantity;i+) cout作业名:endl; couta类:processesi.a/processesi.need_a; cout b类:processesi.b/processesi.need_b; cout c类:proces

18、sesi.c/processesi.need_c; coutendl; else cout当前没有作业endl; /显示版权信息函数 void version() coutendlendl; cout 银行家算法 endl; coutendlendl; void main() int chioce; int flag=1; initial(); version(); while(flag) cout1.新加作业 2.为作业申请资源 3.撤消作业endl; cout4.查看资源情况 0.退出系统endl; coutchioce; switch(chioce) case 1: add(); break; case 2: bid(); break; case 3: finished(); break; case 4: view(); break; case 0: flag=0; break; default: cout选择错误endlendl; 六、使用说明运行环境c-free4.0，新建任务。将编制好的代码输入此运行环境中。按f5：出现如上图所示窗口。按照提示，新建一个作业：