操作系统课程设计进程_银行家_页面调度

1、设计题目操作系统课程设计学生姓名李飞吾学号 20106637 专业班级信息计10-2班指导教师 2012年 12 月 22 日设计题目共3题如下描述成绩课程设计主要内容首先感谢老师和同学的指导1、设计目的：操作系统原理课程设计是信息计算科学专业实践性环节之一，是对学习完操 作系统原理 课程后进行的一次较全面的综合训练。 其目的在于加深对操作系统 的理论、 方法和基础知识的理解， 掌握操作系统结构、 实现机理和各种典型算法， 系统地了解操作系统的设计和实现思路，培养学系统设计能力， 并了解操作 系

2、统的发展动向和趋势。对以后工作或者进一步研究都有促进作用。2、设计题目：进程调度算法银行家算法-页面调度算法3、设计总结：a、知识总结有效性一直是操作系统所追求的目标之一。操作系统的有效性包含以下两个方面：1、提高资源利用率；2、提高系统吞吐率。引入进程管理，处理机调度，存储器管理，设备管理，文件管理等等机制，都是为了实现该特性的。而实现各种机制却有着不同算法，算法的优劣就显得尤为重要了。b、实践感悟由于时间仓促，此次课程设计并未投入大量时间，依然存在许多不足。但是通过对算法的进一步理解，加以程序实现，让我对本专业的学习兴趣更加浓厚了。课程设计时，遇到了一些问题，通过与老师及同学的交流，和网上

3、查阅资料，学到了更多的知识。在此对老师和同学表示感谢。指导老师评语建议：从学生的工作态度、工作量、设计(论文的)创造性、学术性、使用性及书面表达能力等方面给出评价。签名： 20 年月日目录一、 算法设计概述1、设计背景-12、运行环境-1二、进程调度算法1、进程并发执行-12、算法原理及设计-23、代码设计-3三、银行家算法1、进程死锁状态-132、算法原理及设计-133、代码设计-16四、页面调度算法1、页式虚拟存储-202、算法原理及设计-203、代码设计-21五、课程设计总结 1、知识总结-26 2、实践感悟-26一、 算法设计概述1、设计背景操作系统是管理计算机硬件资源，控制其他程序运

4、行并为用户提供交互操作界面的系统软件的集合。操作系统是计算机系统的关键组成部分，负责管理与配置内存、决定系统资源供需的优先次序、控制输入与输出设备、操作网络与管理文件系统等基本任务。操作系统作为系统与用户之间的接口，极大方便了用户使用操作系统，同时也推动了计算机科学的发展。操作系统原理课程设计是信息计算科学专业实践性环节之一，是对学习完操 作系统原理 课程后进行的一次较全面的综合训练。 其目的在于加深对操作系统 的理论、 方法和基础知识的理解， 掌握操作系统结构、 实现机理和各种典型算法， 系统地了解操作系统的设计

5、和实现思路，培养学系统设计能力， 并了解操作 系统的发展动向和趋势。对以后工作或者进一步研究都有促进作用。2、设计环境开发环境：Visual C+ 6.0运行环境：Windows 7/ XP二、 进程调度算法1、进程的并发执行并发性是操作系统的重要特征在多道程序环境下，并发性是指在一段时间内宏观上有多个程序在同时运行，但在单处理机系统中，每一时刻却只能有一道程序执行，故在微观上这些程序只能是分时地交替运行。倘若在计算机系统有多个处理机，则这些可以并发执行的程序便可以被分配到多个处理机上，实现执行，即利用每个处理机来处理一个可以并发执行的程序，这样，多个程序便可同时执行。程序

6、是静态实体，进程是动态的，通过对进程调度实现，实现程序运行。调度的实质是系统按照某种特定的分配策略来分配资源。进程调度的目的是分配CPU资源。由于进程调度程序执行的频率很高，因此调度算法的好坏将直接影响到操作系统的性能。本实验的目的是模拟实现几种常见的进程调度算法，通过对几组进程分别使用不同的调度算法，计算进程的平均周转时间和平均带权周转时间，比较各种算法的性能优劣。2、算法原理及设计（1）进程调度算法进程调度算法包括先来先服务调度算法、优先数调度算法、时间片论转算法和分级调度算法等4种。本实验包括3种算法，有兴趣的读者可以在完成这些算法的基础上实现第四种算法。下面对前3种算法作一一简单介绍。

7、<1> 先来先服务（FCFS）调度算法本算法在进行调度时，总是选择一个最先进入进程就绪队列的进程，把处理器分配给它，使之开始运行。该进程一直运行到完成或发生阻塞事件时，才放弃处理器。<2> 优先数调度算法对每个进程确定一个优先数，进程调度总是让具有最高优先数的进程先使用处理器。如果就绪队列中出现优先数相同的进程，则对这些有相同优先数的进程采用先来先服务算法进行调度。对于占用处理器的进程，系统可以使用“抢占式”或“非抢占式”的策略。“非抢占式”指进程一旦占用处理器，除非自己愿意，否则操作系统不能将处理器强行夺走，即使该进程的优先数已经小于就绪队列中的某个进程。“抢占式”则

8、相反，一旦就绪队列中的某个进程优先数大于正在执行的进程，立刻进行进程切换。进程的优先数可以发生变化。本实验的基本要求是实现固定优先数的调度算法，读者可以在这个基础上添加动态优先数功能。<3> 时间片轮转调度算法在需要保证响应时间的场合通常采用时间片轮转算法来分配处理器。本算法将所有的就绪进程按先来先服务的原则排成一个队列，每次调度时把CPU分配给队首进程，令其执行一个时间片。时间片用完，调度程序自动停止该进程的执行，将它放到进程就绪队列的末尾，等待下一次执行，然后将CPU分配给就绪队列中新的队首进程，也让它执行一个时间片。重复这个过程，直到所有的进程执行完毕。（2）衡量算法性能的参

9、数下面引入两个衡量调度算法性能的参数。平均周转时间：平均带权周转时间：其中：n为进程数目Ti为第i个进程的周转时间，即进程从开始运行到结束的时间Tsi为第i个进程要求执行的时间，即需要在CPU上的执行时间。3、代码设计（1）建立进程控制块进程控制块至少应该包括：进程名称进程需要执行时间进入就绪队列时间进程执行结束时间进程控制块代码typedef struct node char sNum4; /进程编号int ArriveTime;/进程到达时间int RunTime; /进程要求执行的时间int Privilege; /进程的优先数int Finished; /标志进程是否执行完成int T

10、ime; /进程等待时间的借助变量int WaitTime; /进程的等待时间int TurnoverTime; /进程的周转时间float WeighTurnTime; /进程带权周转时间pcb; 进程号到达时间要求执行时间00411352210335469572169357112381242913110147112051223313242214253115261（2）就绪进程序列如上右表所示3、代码设计#include<stdio.h> #include<string.h> #include<iostream.h> const int timeslice

11、=5; /定义时间片的长度const int MAXPCB=100; /定义最大进程数/定义进程结构体typedef struct node char sNum4; /进程编号int ArriveTime; /进程到达时间int RunTime; /进程要求执行的时间int Privilege; /进程的优先数int Finished; /标志进程是否执行完成int Time; /求进程的等待时间的借助变量int WaitTime; /进程的等待时间int TurnoverTime; /进程的周转时间float WeighTurnTime; /进程的带权周转时间pcb; pcb pcbsMAX

12、PCB; int PCBNum; /进程数 /PCB初始化函数void initPCB() int i; for(i=0;i<MAXPCB;i+) strcpy(pcbsi.sNum,""); pcbsi.ArriveTime=0; pcbsi.RunTime=0; pcbsi.Privilege=0; pcbsi.Finished=0;pcbsi.Time=0; pcbsi.WaitTime=0; pcbsi.TurnoverTime=0; pcbsi.WeighTurnTime=0; /for(i=0;i<MAXPCB;i+)PCBNum=0; /void

13、initPCB() /读进程流文件数据函数int readData() FILE *fp; char sFile20; int i; cout<<"请输入进程流文件名（注意：包括后缀名）: " cin>>sFile; if(fp=fopen(sFile,"r")=NULL) cout<<"错误,文件打不开,请检查文件名"<<endl; else while(!feof(fp) fscanf(fp,"%s %d %d %d",pcbsPCBNum.sNum,&p

14、cbsPCBNum.ArriveTime,&pcbsPCBNum.RunTime,&pcbsPCBNum.Privilege); PCBNum+; /while(!feof(fp)/输出所读入的数据cout<<endl<<"输出所读入的数据："<<endl<<endl; cout<<"进程编号进程到达时间要求执行时间优先数"<<endl; for(i=0;i<PCBNum-1;i+) cout<<" "<<pcbsi.

15、sNum<<" "<<pcbsi.ArriveTime<<" "<<pcbsi.RunTime<<" "<<pcbsi.Privilege<<endl; return(1); /if(fp=fopen(sFile,"r")=NULL)return(0); / int readData()/重置PCB数据,以供另一个算法使用void reInitPCB() int i; for(i=0;i<MAXPCB;i+) pcbsi.Fi

16、nished=0; pcbsi.Time=0;pcbsi.WaitTime=0;pcbsi.TurnoverTime=0;pcbsi.WeighTurnTime=0; /void reInitPCB()/先来先服务调度算法void FCFS() int i; int Total1; float Total2;reInitPCB();/重置PCB数据,以供另一个算法使用/输出先来先服务调度算法执行流cout<<endl<<"-"<<endl; cout<<"先来先服务调度算法执行流:"<<endl

17、; cout<<"进程编号到达时间等待时间运行时间周转时间带权周转时间"<<endl; pcbs0.TurnoverTime=pcbs0.RunTime+pcbs0.ArriveTime; pcbs0.WeighTurnTime=(float)pcbs0.TurnoverTime/pcbs0.RunTime;for(i=0;i<PCBNum-1;i+) cout<<" "<<pcbsi.sNum<<" "<<pcbsi.ArriveTime<<&

18、quot; "<<pcbsi.WaitTime <<" "<<pcbsi.RunTime<<" "<<pcbsi.TurnoverTime<<" "<<pcbsi.WeighTurnTime<<endl; pcbsi+1.Time=pcbsi.Time+pcbsi.RunTime;pcbsi+1.WaitTime=pcbsi+1.Time-pcbsi+1.ArriveTime; pcbsi+1.TurnoverTime=pcbsi

19、+1.WaitTime+pcbsi+1.RunTime; pcbsi+1.WeighTurnTime=(float) pcbsi+1.TurnoverTime/pcbsi+1.RunTime; Total1 = 0;Total2 = 0.0;for(i=0;i<PCBNum-1;i+)Total1+=pcbsi.TurnoverTime; Total2+=(float) pcbsi.TurnoverTime/pcbsi.RunTime; cout<<" 总周转时间:"<<Total1<<" 平均周转时间:"<

20、;<Total1/PCBNum<<endl<<" 总带权周转时间:"<<Total2<<" 平均带权周转时间:"<<Total2/(PCBNum-1)<<endl; cout<<endl<<"-"<<endl; /void FCFS()/优先数调度算法void privilege() int i,j,CurMin; int Time=0; int Total1;float Total2;int QueueMAXPCB; i

21、nt CurPriority=1000; reInitPCB();/重置PCB数据,以供另一个算法使用for(i=0;i<PCBNum-1;i+) /按优先数递增排序PCB CurPriority=1000; for(j=0;j<PCBNum-1;j+)if(pcbsj.Finished=0)&&(pcbsj.Privilege<CurPriority) CurMin=j; CurPriority=pcbsj.Privilege; /for(j=0;j<PCBNum;j+)Queuei=CurMin; pcbsCurMin.Finished=1; pcb

22、sCurMin.TurnoverTime=pcbsCurMin.RunTime+Time;pcbsCurMin.WeighTurnTime=(float)pcbsCurMin.TurnoverTime/pcbsCurMin.RunTime;Time+=pcbsCurMin.RunTime; /for(i=0;i<PCBNum;i+) /输出优先数调度执行流cout<<endl<<"-"<<endl; cout<<"优先数调度执行流:"<<endl; cout<<"进程

23、编号优先数运行时间周转时间带权周转时间"<<endl; for(i=0;i<PCBNum-1;i+) cout<<" "<<pcbsQueuei.sNum<<" "<<pcbsQueuei.Privilege<<" "<<pcbsQueuei.RunTime<<" "<<pcbsQueuei.TurnoverTime<<" "<<pcbsQueuei

24、.WeighTurnTime<<endl; Total1=0; Total2=0.0; for(i=0;i<PCBNum-1;i+)Total1+=pcbsi.TurnoverTime; Total2+=(float) pcbsi.TurnoverTime/pcbsi.RunTime; cout<<"总周转时间:"<<Total1<<" 平均周转时间:"<<Total1/PCBNum<<endl<<" 总带权周转时间:"<<Total

25、2<<" 平均带权周转时间:"<<Total2/(PCBNum-1)<<endl; cout<<endl<<"-"<<endl; /void privilege()/时间片轮转调度算法void timer() int i,Num,Flag=1; int Round=0; /轮转周期数int Total=0; /总时间片数reInitPCB(); /重置PCB数据,以供另一个算法使用cout<<endl<<"-"<<endl; c

26、out<<"时间片轮转调度执行流（时间片的长度为5秒）:"<<endl; while(Flag=1)Flag=0; Num=0; for(i=0;i<PCBNum-1;i+)/统计末执行完的进程数Numif(pcbsi.Finished=0) Num+; /if(pcbsi.Finished=0) /for(i=0;i<PCBNum;i+)if(Num>0)Round+;cout<<endl<<""<<Round<<"轮："for(i=0;i&l

27、t;PCBNum-1;i+) if(pcbsi.Finished=0) Flag=1;cout<<pcbsi.sNum<<" "Total+; if(pcbsi.RunTime<=timeslice*(Round) pcbsi.Finished=1; /if(pcbsi.RunTime<=block_time*(Round+1)/if(pcbsi.Finished=0) /for(i=0;i<PCBNum;i+) /if(Num>0) /while(Flag=1)cout<<endl<<"轮转

28、周期数:"<<Round<<"总时间片数:"<<Total<<endl;cout<<endl<<"-"<<endl; /void timer() void SPF() /短进程优先调度算法 reInitPCB();cout<<endl<<"-"<<endl; cout<<"短进程优先调度算法执行流:"<<endl; cout<<"进程编号到达

29、时间等待时间运行时间周转时间带权周转时间"<<endl; int i,j;for(i=1;i<PCBNum-1;i+)for(j=0;j<PCBNum-i-1;j+) if(pcbsj.RunTime>pcbsj+1.RunTime) pcb temp; strcpy(temp.sNum,pcbsj+1.sNum); temp.ArriveTime=pcbsj+1.ArriveTime; temp.RunTime=pcbsj+1.RunTime; temp.Privilege=pcbsj+1.Privilege; strcpy(pcbsj+1.sNum,

30、pcbsj.sNum); pcbsj+1.ArriveTime=pcbsj.ArriveTime; pcbsj+1.RunTime=pcbsj.RunTime; pcbsj+1.Privilege=pcbsj.Privilege; strcpy(pcbsj+1.sNum,temp.sNum); pcbsj.ArriveTime=temp.ArriveTime; pcbsj.RunTime=temp.RunTime; pcbsj.Privilege=temp.Privilege; pcbs0.Finished=1; pcbs0.WaitTime=0; pcbs0.TurnoverTime=pcb

31、s0.RunTime+pcbs0.ArriveTime; pcbs0.WeighTurnTime=(float)(pcbs0.TurnoverTime)/(pcbs0.RunTime); int Total1= pcbs0.WaitTime; float Total2= 0.0; cout<<" "<<pcbs0.sNum<<" "<<pcbs0.ArriveTime<<" "<<pcbs0.WaitTime <<" "<&l

32、t;pcbs0.RunTime<<" "<<pcbsi.TurnoverTime<<" "<<pcbsi.WeighTurnTime<<endl;for(i=1;i<PCBNum-1;i+) pcbsi.Time+=pcbsi-1.Time+pcbsi-1.RunTime; pcbsi.WaitTime=pcbsi.Time-pcbsi.ArriveTime; pcbsi.TurnoverTime=pcbsi.WaitTime+pcbsi.RunTime; Total1+=pcbsi.Tu

33、rnoverTime; Total2+=pcbsi.TurnoverTime/pcbsi.RunTime; pcbsi.Finished=1;cout<<" "<<pcbsi.sNum<<" "<<pcbsi.ArriveTime<<" "<<pcbsi.WaitTime <<" "<<pcbsi.RunTime<<" "<<pcbsi.TurnoverTime<<

34、" "<<pcbsi.WeighTurnTime<<endl;cout<<"总周转时间:"<<Total1<<" 平均周转时间:"<<Total1/(PCBNum-1)<<"总带权周转时间:"<<Total2<<" 平均带权周转时间:"<<Total2/(PCBNum-1)<<endl; cout<<endl<<"-"&l

35、t;<endl; /void SPF() void interface()/显示界面信息 cout<<endl<<endl; cout<<" "<<endl;cout<<" "<<endl; cout<<" "<<endl; cout<<" "<<endl; cout<<" "<<endl;cout<<" "<

36、<endl; cout<<"欢迎进入进程调度模拟系统 "<<endl;cout<<" "<<endl; cout<<" "<<endl; cout<<" "<<endl; cout<<" "<<endl;cout<<" "<<endl; cout<<"实验一：进程调度算法 "<<end

37、l; cout<<" "<<endl; cout<<" "<<endl; cout<<" "<<endl;cout<<" "<<endl;cout<<endl<<endl; /void interface()/主函数void main() int Input; bool bGoOn;char sGoOn1; interface(); /显示界面信息initPCB(); /PCB初始化函数bGoOn

38、= true;strcpy(sGoOn," ");if(readData()=1) /标志读进程流文件数据函数执行是否正确while (bGoOn)cout<<endl<<"请选择进程调度功能，输入（1 or 2 or 3 or 4）"<<endl<<endl;cout<<"1 先来先服务（FCFS）算法"<<endl<<"2 优先数（privilege）调度算法"<<endl<<"3 时间片轮转（

39、HRN）调度算法"<<endl<<"4 短进程优先（SPF）调度算法"<<endl;cin>>Input;switch(Input)case 1:FCFS(); /先来先服务算法break;case 2:privilege();/优先数调度算法break;case 3:timer();/时间片轮转调度算法break;case 4:SPF(); /短进程优先调度算法break;default:printf("n输入的算法编号错误!n");break;/switch(Input)bGoOn= fals

40、e;strcpy(sGoOn," ");cout<<endl;cout<<"要继续进行进程调度算法模拟吗?(Y/N)"cin>>sGoOn;bGoOn=(sGoOn0='y'|sGoOn0='Y');/while bGoOn /if(readData()=1)/void main()e、运行截图三、 银行家算法1、进程死锁状态在多道程序系统中，虽然可借助于多个进程的并发执行来改善系统的资源利用率，提高系统的吞吐量，但可能发生一种危险死锁。所谓死锁（Deadlock），是指多个进程在运行过

41、程中因争夺资源而造成的一种僵局（DeadlyEmbrace）,当进程处于这种僵持状态时，若无外力作用，他们都将无法向前推进。具有代表性的避免死锁的算法，是Djikstra的银行家算法，这是由于该算法能用于系统现金贷款的发放而得名的。2、算法原理及设计（1）银行家算法思想：对用户提出的请求进行合法性检查，即检查请求的是不大于需要的，是否不大于可利用的。若请求合法，则进行试分配。最后对试分配后的状态调用安全性检查算法进行安全性检查。若安全，则分配，否则，不分配，恢复原来状态，拒绝申请。（2）银行家算法数据结构：可利用资源向量int Availablej j为资源的种类最大需求矩阵int Maxij

42、 i为进程的数量分配矩阵int Allocationij需求矩阵int needij= Maxij- Allocationij申请各类资源数量int Request ij i进程申请j资源的数量工作向量int Workx int Finishy（3）银行家算法进程i发出请求申请k个j资源，Request ij=k a、检查申请量是否不大于需求量：Request ij<=needi,j,若条件不符重新输入，不允许申请大于需求量。b、检查申请量是否小于系统中的可利用资源数量：Request ij<=availablei,j，若条件不符就申请失败，阻塞该进程，用goto语句跳转到重新申请

43、资源。c、若以上两个条件都满足，则系统试探着将资源分配给申请的进程，并修改下面数据结构中的数值：Availablei,j= Availablei,j- Request ij；Allocationij= Allocationij+ Request ij；needij= needij- Request ij；d、试分配后，执行安全性检查，调用safe()函数检查此次资源分配后系统是否处于安全状态。若安全，才正式将资源分配给进程；否则本次试探分配作废，恢复原来的资源分配状态，让该进程等待。e、用dowhile 循环语句实现输入字符y/n判断是否继续进行资源申请。（4）安全性检查算法a、设置两个向量：

44、工作向量Work，它表示系统可提供给进程继续运行所需的各类资源数目，在执行安全性算法开始时，Work= Available。Finish，它表示系统是否有足够的资源分配给进程，使之运行完成。开始时先做Finishi=0；当有足够的资源分配给进程时，再令Finishi=1。b、在进程中查找符合以下条件的进程：条件1：Finishi=0；条件2：needij<=Workj若找到，则执行步骤(3)否则，执行步骤(4)c、当进程获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行：Workj= Workj+ Allocationij；Finishi=1；goto step 2；d、

45、如果所有的Finishi=1都满足，则表示系统处于安全状态，否则，处于不安全状态。初始化函数chushihua()开始（5）操作系统银行家算法流程图：输入各进程当前已分配的资源数输入各进程对各类资源的最大需求输出提示：输入有误，请重新输入初始化函数chushihua()结束，银行家函数Bank()提出请求REQUESTiError;REQUESTi<=NEEDi输出提示：你的请求被拒！REQUESTi<=AVAILABLEiError;Safe();AVAILABLEi-=REQUESTi；ALLOCATIONi-=REQUESTi;NEEDi+=REQUESTi；输出提示：同意分

46、配请求是否进行再次分配退出程序，银行家算法Bank()结束;Work=AVAILABLE;FINISH=false；安全性算法Safe()开始输出提示：系统是不安全的NEEDi<=Work&&FINISHi=false;Work+=ALLOCATIONi;FINISHi=ture;安全算法safe()结束安全，输出安全序列Return ture；3、代码设计#include <iostream.h>#include <vector> #include <iomanip>#include <stdlib.h>using nam

47、espace std; #define TRUE 1 /定义 TRUE =1#define FALSE 0 /定义 FLASE=0void bank(vector<int>,vector<vector<int> >,vector<vector<int> >,int ,int ); /声明bank（应行家算法）int safe(vector<int> Available,vector<vector<int> > Need,vector<vector<int> > Allocat

48、ion,int n,int m);/声明safe（）安全性算法void init();/*主函数main()*/void main()init();int safe(vector<int> Available,vector<vector<int> > Need,vector<vector<int> > Allocation,int n,int m);/*初始化函数init()*/void init()int m; /m资源类数int n; /进程数system("color 0B");cout<<end

49、l<<endl; cout<<" "<<endl;cout<<" "<<endl; cout<<" "<<endl; cout<<" "<<endl; cout<<" "<<endl;cout<<" "<<endl; cout<<"欢迎进入银行家算法调度系统 "<<endl;co

50、ut<<" "<<endl; cout<<" "<<endl; cout<<" "<<endl; cout<<" "<<endl;cout<<" "<<endl; cout<<"实验二：银行家算法 "<<endl; cout<<"作者：学习 "<<endl; cout<<&quo

51、t; 2012.12.16 "<<endl; cout<<" "<<endl; cout<<" "<<endl; cout<<" "<<endl; cout<<" "<<endl;cout<<" "<<endl;cout<<endl<<endl; cout<<"输入资源类数"<<endl;

52、cin>>m;vector<int> Available(m); /动态申请数组Available可用资源向量cout<<"输入各类资源总数:"<<endl;/*/ /* 下面的被刚掉的为在DOS下输入资源向量*/ /*未被刚掉的是从Available.txt文件中读入数据*/*/*/for (int i=0;i<m;i+)cout<<"输入R"<<i<<"类资源总数:"cin>>Availablei;/*/FILE *fp;fp=fopen("Available.txt","r+");cout<<"从Available.txt文件中读入数据，并输出"<<endl;for(int i=0;i<m;i+)fscanf(fp,"%d",&Availab