操作系统课程设计报告 银行家算法+磁盘调度

1、北 华 航 天 工 业 学 院操作系统课程设计报告课设报告题目： 银行家算法 磁盘调度算法 作者所在系部： 计算机科学与工程系 作者所在专业： 计算机科学与技术 作者所在班级： 作 者 姓 名 ： 指导教师姓名： 赵辉 完 成 时 间 ： 2011/12/19 北华航天工业学院教务处制摘 要计算机系统由硬件和软件两部分组成。操作系统是配置在计算机硬件上的第一次软件，是对硬件系统的首次扩充，在计算机系统中占据了特别重要的地位。操作系统已成为现代计算机系统、多处理机系统、计算机网络、多媒体系统以及嵌入式系统中都必须配置的、最重要的系统软件。本文利用Mircosoft Visual C+6.0编写程

2、序，实现了（1）模拟银行家算法和安全算法来避免死锁（2）模拟磁盘调度算法其中银行家算法实现了：（1）程序可以输入3种资源的数目，5个进程对3种资源的最大需求量、已分配量和需求量；（2）能够判断某一时刻系统是否处于安全状态，如果处于安全状态能够给出安全序列；（3）当某进程提出资源申请时，能够判断是否能把资源分配给申请进程。磁盘调度算法实现了：（1）能够输入程序要访问的磁道序列和磁头当前所在的磁道数。（2）可以选择某磁盘调度算法（先来先服务算法、最短寻道时间优先算法、扫描算法和循环扫描算法）。（3）能够显示磁盘调度顺序和平均寻道长度。关键词：操作系统 模拟 银行家算法 磁盘调度算法目 录第一章 绪

3、论11.1 课程设计的背景和意义11.1.1 课程设计的理论研究基础11.1.2 课程设计的意义21.2 课程设计环境2第二章 需求分析32.1 功能要求32.1.1 银行家算法32.1.2 磁盘调度算法32.2 问题的解决方案3第三章 系统设计43.1 数据设计43.1.1 数据结构设计43.1.2 数据之间的关系43.1.3 函数设计4第四章 系统实现64.1 数据结构实现64.2 函数实现64.3 主函数实现174.4 系统界面194.4.1 银行家方法的运行界面194.4.2磁盘调度算法的运行界面21第五章 系统测试225.1 模块测试225.1.1银行家算法225.1.2 磁盘调度算

4、法245.2 课程设计过程中遇到的问题26总 结27致 谢28参考文献29第一章 绪论随着计算机技术发展，计算机已经应用的各个领域，促进了各行各业的发展。与此同时，人们对计算机的要求也越来越高，其中就包括对计算机操作系统的要求。人们希望操作系统更加合理配置计算机硬件系统的有限资源，更方便操作计算机硬件系统。本文利用Mircosoft Visual C+6.0编写程序，实现了（1）模拟银行家算法和安全算法来避免死锁（2）模拟磁盘调度算法通过模拟，反映了操作系统如何合理有效的管理和分配资源。1.1 课程设计的背景和意义1.1.1 课程设计的理论研究基础在多道程序系统中，虽可以借助于多个进程的并发执

5、行来改善系统的资源利用率，提高系统的吞吐量，但可能发生一种危险多个进程在运行过程中因争夺资源而造成僵持，当进程处于这种僵持状态时，若无外力作用，他们都将无法继续向前推进，即死锁。而银行家算法是最具代表性的避免死锁的算法。银行家算法和安全检查算法：（1）程序可以输入3种资源的数目，5个进程对3种资源的最大需求量、已分配量和需求量；（2）能够判断某一时刻系统是否处于安全状态，如果处于安全状态能够给出安全序列；（3）当某进程提出资源申请时，能够判断是否能把资源分配给申请进程。磁盘是可供多个进程共享的设备，当有多个进程都要求访问磁盘时，应采取一种最佳调度算法，以使各进程对磁盘的平均访问时间最小。由于在

6、访问磁盘的时间中，主要是寻道时间，因此，磁盘调度的目标是使磁盘的平均寻道时间最少。磁盘调度算法：（1）能够输入程序要访问的磁道序列和磁头当前所在的磁道数。（2）可以选择某磁盘调度算法（先来先服务算法、最短寻道时间优先算法、扫描算法和循环扫描算法）。（3）能够显示磁盘调度顺序和平均寻道长度。1.1.2 课程设计的意义通过课程设计，可以更深入理解操作系统中的部分经典算法，了解操作系统的工作原理。1.2 课程设计环境编程环境介绍运行环境：Windows XP3或Windows 7工具软件：Mircosoft Visual C+6.0硬件环境：处理器1.5GHz以上，内存1GB，显卡256M第二章 需

7、求分析2.1 功能要求2.1.1 银行家算法（1）程序可以输入3种资源的数目，5个进程对3种资源的最大需求量、已分配量和需求量；（2）能够判断某一时刻系统是否处于安全状态，如果处于安全状态能够给出安全序列；（3）当某进程提出资源申请时，能够判断是否能把资源分配给申请进程。2.1.2 磁盘调度算法（1）能够输入程序要访问的磁道序列和磁头当前所在的磁道数。（2）可以选择某磁盘调度算法（先来先服务算法、最短寻道时间优先算法、扫描算法和循环扫描算法）。（3）能够显示磁盘调度顺序和平均寻道长度。2.2 问题的解决方案（1）模拟银行家算法和安全算法来避免死锁（2）模拟磁盘调度算法第三章 系统设计3.1 数

8、据设计3.1.1 数据结构设计1. 银行家算法的数据结构设计（1）可用资源向量Availablem，Availablej=k表示系统中现有Rj类资源K个。（2）最大需求矩阵Maxnm，Maxij=K表示进程i需要Rj类资源的最大数目为K个。（3）分配矩阵Allocationnm，Allocationij=K表示进程i当前已分配得到Rj类资源的数目为K个。（4）需求矩阵Neednm，Needij=K表示进程i还需要Rj类资源K个。其满足Needij= Maxij-Allocationij。 （5）Requestnm,Requestij=K 表示进程Pi需要K个Rj类型的资源。2. 磁盘调度算法的

9、数据结构设计（1）cidaom,存放存入请求访问的磁道号。3.1.2 数据之间的关系需求矩阵Neednm，Needij= Maxij-Allocationij。3.1.3 函数设计1. 银行家算法函数设计void Input(); /用于输入的函数void Output(); /用于打印输出表格的函数void Alloc();/试分配给进程iint Safecheck();/安全检测函数void Redata(int i); /恢复原来的资源分配状态Alloc函数，当Pi发出资源请求后，系统按下述步骤进行检查：（1）如果Requestij=Needij,便转向步骤（2）；否则认为出错，因为它所

10、需要的资源数已经超过它所宣布的最大值。（2）如果Requestij= Availablej，便转向步骤（3）；否则表示尚无足够资源，Pi须等待。（3）系统试探着把资源分配给进程Pi，并修改下面的数据结构中的数值：Availablej= Availablej-Requestij；Allocationnm= Allocationnm+ Requestij；Needij= Needij- Requestij；（4）系统执行安全性算法，检查此次资源分配后系统是否处于安全状态。若安全，才分配，否则本次试探作废，恢复原来的资源分配状态。Safecheck函数（1）设置两个向量 工作向量Workm,表示系统

11、可提供给进程继续运行所需的各类资源数目，在执行安全算法之前，Work=Available；完成向量Finishm,表示系统是否有足够的资源分配给进程，使之运新完成。开始时Finish=-1即不能。分配完Finish=1（2）从进程集合中找到一个能满足下述条件的进程：Finishi=-1；Needi=Workj 若找到，执行（3），否则，执行（4）（3）当进程Pi获得资源后，可顺利执行，直至完成，并释放分配给它的资源，继续（2）；（4）如果所有进程的Finishi=1都满足，表示系统处于安全状态，否则系统处于不安全状态。2.磁盘调度算法函数设计int *bubble(int cidao,int

12、m) /使用冒泡法按从小到大顺序排列void FCFS(int cidao,int m) /先来先服务void SSTF(int cidao,int m) /最短寻道时间优先void SCAN(int cidao,int m) /扫描算法void CSCAN(int cidao,int m) /循环扫描算法第四章 系统实现4.1 数据结构实现银行家算法数据结构：int Available3; /Available三类资源(A,B,C)的可利用量int Sum3=10,5,7; /Sum为各类资源总数 int Request3; /Request三类资源(A,B,C)申请资源量int Max53

13、=7,5,3,3,2,2,9,0,2,2,2,2,4,3,3; /三类资源(A,B,C)的最大需求量int Allocation53=0,1,0,2,0,0,3,0,2,2,1,1,0,0,2; / 三类资源(A,B,C)已分配量int Need53; / 三类资源(A,B,C)进程需求量4.2 函数实现银行家算法函数实现void Alloc() /分配给进程iint i,j;int flag;char yes;docouti;if(i4|i0) cout进程号不正确，请重输:4|i0);cout请求量(3种资源):;for(j=0;jRequestj;flag=0; /初始化为0，即未请求或

14、请求未成功for(j=0;j3;j+)if(Requestj=Needij) /实际需求量未超过理论需求量if(Requestj=Availablej) /资源足够flag=1; /表示请求符合条件，可以分配elsecout资源不足，请等待!endl;return;elsecout资源超过最大需求量endl;flag=0;return;if(flag=1) /对于符合条件可以分配的进程请求for(j=0;j3;j+)/把资源分配给该进程Availablej=Availablej-Requestj;Allocationij=Allocationij+Requestj;Needij=Needij-

15、Requestj;if(Safecheck()=1) /执行安全检查，此次资源分配后系统处于安全状态coutyes;yes=toupper(yes);if(yes=Y)cout分配成功endl;elseRedata(i); /恢复原来的资源分配状态elsecout分配不安全endl;Redata(i); /恢复原来的资源分配状态int Safecheck()/安全性检查int i=0,j=0,k=0,flag1,flag2,count=0;/flag用于描述每次int queueMAX;int work3; /系统可提供给进程继续运行所需的各类资源数目int finish5; / -1表示未被

16、执行，1表示已被执行for(j=0;j3;j+)workj=Availablej; /在执行安全算法开始时，Work=Availablefor(i=0;i5;i+) finishi=-1; /初始化，均未被执行doflag1=0; /do while循环运行标识for(i=0;i5;i+)if(finishi=-1) /进程未执行，向下进行for(j=0;j3;j+) /三种资源都满足才可分配，flag2=1；否则flag2=0if(Needij=workj)flag2=1;/满足分配条件elseflag2=0;/表示资源不够break;if(flag2=1) /满足分配条件（三种资源都可以分

17、配）flag1=1;/表示有可以分配资源的进程，分配完后重新从头查找for(j=0;j3;j+)workj=workj+Allocationij;/运行完后回收资源finishi=1; /表示该进程已经执行完毕queuecount=i; /将进程号存入数组queue中count+;break;while(flag1);if(count=5)cout分配安全,找到一个安全序列：endl;for(i=0;icount;i+)coutqueuei;coutendl;cout | work | Need |Allocation|work+Allocation|finish|endl;cout | A

18、B C | A B C | A B C | A B C | |endl;for(i=0;i3;i+)worki=Availablei;for(i=0;i5;i+)k=queuei;coutpk |;for(j=0;j3;j+)cout workj ;cout | ;for(j=0;j3;j+)cout Needkj;cout | ;for(j=0;j3;j+) cout Allocationkj ;cout| ;for(j=0;j3;j+)workj=workj+Allocationkj;cout workj ; cout | ;cout finishk ; cout | ;coutendl;

19、return 1;elsecout分配不安全, 本次资源申请不成功!endl;return 0;void Redata(int i) /恢复分配for(int j=0;j3;j+)Availablej = Availablej + Requestj;Allocationij = Allocationij - Requestj;Needij = Needij + Requestj;cout数据已恢复初始状态.endl;磁盘调度算法：void FCFS(int cidao,int m) /先来先服务 磁道号数组，个数为m int now;/当前磁道号 int sum=0; /总寻道长度 int j

20、,i; float ave; /平均寻道长度cout磁盘请求序列为：; for( i=0;im;i+) /按先来先服务的策略输出磁盘请求序列 coutcidaoi ; coutendl; coutnow ; sum+= abs(cidao0-now); /求绝对值cout磁盘扫描序列为：; for( i=0;im;i+) /输出磁盘扫描序列 coutcidaoi ; for(i=0,j=1;jm;i+,j+) /求平均寻道长度 sum+=abs(cidaoj-cidaoi); ave=(float)(sum)/(float)(m); coutendl; cout平均寻道长度：aveendl;v

21、oid SSTF(int cidao,int m) /最短寻道时间优先 磁道号数组，个数为m int k=1; int now,l,r; int i,j,sum=0; float ave; cidao=bubble(cidao,m); /调用冒泡排序算法排序 从小到大 coutnow; if(cidaom-1=now) /若当前磁道号大于请求序列中最大者，则直接由外向内依次给予各请求服务 cout=0;i-) coutcidaoi=now) /若当前磁道号小于请求序列中最小者，则直接由内向外依次给予各请求服务 cout磁盘扫描序列为：; for(i=0;im;i+) coutcidaoicid

22、ao0&nowcidaom-1) /若当前磁道号大于请求序列中最小者且小于最大者 cout磁盘扫描序列为：; while(cidaok=0)&(rm) /当前磁道在请求序列范围内 /选择与当前磁道最近的请求给予服务 if(now-cidaol)=(cidaor-now) /从当前磁道向前移动 coutcidaol ; sum+=now-cidaol; now=cidaol; l=l-1; else /从当前磁道向后移动 coutcidaor ; sum+=cidaor-now; now=cidaor; r=r+1; if(l=-1) /磁头移动到序列的最小号，返回外侧扫描仍未扫描的磁道 for

23、(j=r;jm;j+) coutcidaoj=0;j-) coutcidaoj ; sum+=cidaom-1-cidao0; ave=(float)(sum)/(float)(m); coutendl; cout平均寻道长度： aveendl;void SCAN(int cidao,int m) /扫描算法 先要给出当前磁道号和移动臂的移动方向 int k=1; int now,l,r,d; /d为磁头移动臂移动方向选择 int i,j,sum=0; float ave; cidao=bubble(cidao,m); /调用冒泡排序算法排序 从小到大 coutnow; if(cidaom-1

24、=now) /若当前磁道号大于请求序列中最大者，则直接由外向内依次给予各请求服务,此情况同最短寻道优先 cout=0;i-) coutcidaoi=now) /若当前磁道号小于请求序列中最小者，则直接由内向外依次给予各请求服务,此情况同最短寻道优先 cout磁盘扫描序列为：; for(i=0;im;i+) coutcidaoicidao0&nowcidaom-1) /若当前磁道号大于请求序列中最小者且小于最大者 while(cidaoknow) /确定当前磁道在已排的序列中的位置 k+; l=k-1; r=k; cout ，0表示向内d; if(d=0) /选择移动臂方向向内，则先向内扫描 c

25、out=0;j-) coutcidaoj ; /输出向内扫描的序列 for(j=r;jm;j+) /磁头移动到最小号，则改变方向向外扫描未扫描的磁道 coutcidaoj ; /输出向外扫描的序列 sum=now-2*cidao0+cidaom-1; else /选择移动臂方向向外，则先向外扫描 cout磁盘扫描序列为：; for(j=r;jm;j+) coutcidaoj=0;j-) /磁头移动到最大号，则改变方向向内扫描未扫描的磁道 coutcidaoj ; sum=-now-cidao0+2*cidaom-1; ave=(float)(sum)/(float)(m); coutendl;

26、 cout平均寻道长度： aveendl;void CSCAN(int cidao,int m) /循环扫描算法 int k=1; int now,l,r; int i,j,sum=0; float ave; cidao=bubble(cidao,m); /调用冒泡排序算法排序 coutnow; /对输入数据进行有效性判断 if(cidaom-1=now) /若当前磁道号大于请求序列中最大者，则直接将移动臂移动到最小号磁道依次向外给予各请求服务 cout磁盘扫描序列为：; for(i=0;im;i+) coutcidaoi=now) /若当前磁道号小于请求序列中最小者，则直接由内向外依次给予各

27、请求服务,此情况同最短寻道优先 cout磁盘扫描序列为：; for(i=0;im;i+) coutcidaoicidao0&nowcidaom-1) /若当前磁道号大于请求序列中最小者且小于最大者 cout磁盘扫描序列为：; while(cidaoknow) /确定当前磁道在已排的序列中的位置 k+; l=k-1; r=k; for(j=r;jm;j+) coutcidaoj ; /输出从当前磁道向外扫描的序列 for(j=0;jr;j+) /当扫描完最大号磁道，磁头直接移动到最小号磁道，再向外扫描未扫描的磁道 coutcidaoj ; sum=2*cidaom-1+cidaol-now-2*

28、cidao0; ave=(float)(sum)/(float)(m); coutendl; cout平均寻道长度： aveendl;4.3 主函数实现1.银行家算法主函数：void main()int choice;docoutendl;cout欢迎银行家算法系统(资源数:3,进程:5)!endlendl;cout*银行家算法*endl;cout 1:输入数据 endl;cout 2:显示矩阵 endl;cout 3:分配资源 endl;cout 0:退出系统 endl;cout*endl;coutchoice;choice=toupper(choice);switch(choice)cas

29、e 1:Input();break; /调用输入函数case 2:Output();break; /调用输出函数case 3:Alloc();break; /调用预分配函数case 0:cout退出成功endl;break;default: cout输入无效，请重输:;break;while(choice!=0);2.磁盘调度算法：void main() int a; int cidaomaxsize; int i=0,count; cout *欢迎进入磁盘调度算法程序* endl; cout请输入程序要访问的磁道序列（以-1结束输入）：endl; coutcidaoi; i+; while(

30、cidaoi-1!=-1); cout输入结束！endl; count=i-1; cout你输入的磁道序列为：; for(i=0;icount;i+) coutcidaoi ; /输出磁道序列 coutendl; int choice; while(choice) coutendl; cout*endl; cout* 系统菜单 *endl; cout*endl; cout* 1. 先来先服务 *endl; cout* *endl; cout* 2. 最短寻道时间优先 *endl; cout* *endl; cout* 3. 扫描调度 *endl; cout* *endl; cout* 4. 循环扫描 *endl; cout* *endl; cout* 0. 退出 *endl; cout* *endl; cout*endl; coutchoice; switch(choice) case 1:FCFS(cidao,count);break;/使用FCFS算法 case 2:SSTF(cidao,count); break;/使用SSTF算法 case 3:SCAN(cidao,count);break;/使用SCAN算法 case 4:CSCAN(cidao,count);break;/使用CSCAN算法 ca