[计算机软件及应用]操作系统课设进程调度算法银行家算法.doc

《[计算机软件及应用]操作系统课设进程调度算法银行家算法.doc》由会员分享，可在线阅读，更多相关《[计算机软件及应用]操作系统课设进程调度算法银行家算法.doc（34页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 北 华 航 天 工 业 学 院?操作系统?课程设计报告课设报告题目： 作者所在系部： 计算机科学与工程 作者所在专业： 计算机科学与技术 作者所在班级： 作 者 姓 名 ： 指导教师姓名： 完 成 时 间 ： 2011-12-13 北华航天工业学院教务处制摘 要通过一学期的对操作系统的学习，对操作系统有了一定的知识储藏，为了稳固知识，加深印象，也为了更加深入的了解与钻研操作系统，为以后的学习研究提供帮助，做操作系统课设，分别为进程调度算法、银行家算法。通过进程调度算法课设，解决了进程调度的几个根本算法：先来先效劳算法、短进程优先算法、高响应比算法。通过银行家算法课设，更加深刻的理解了银行家算

2、法，平安算法防止死锁的原理。两个课设为两个知识点，都为操作系统的难点与重点，在硬件不允许的情况下通过运用vc+6.0和c+语言描述了它们的功能与具体实现，对以后的学习有很大的帮助。关键词：操作系统 进程 进程调度算法 先来先效劳 短进程优先 高响应比银行家算法 平安算法 死锁 平安序列 平安状态第一章 绪论1课程设计的背景和意义11.1.1 课程设计的理论研究根底11.1.2 课程设计的意义11.2 课程设计环境1第二章 需求分析22.1 功能要求22.1.1进程调度算法22.1.2银行家算法22.2 问题的解决方案22.2.1进程调度算法22.2.2银行家算法3第三章 系统设计43.1 数据

3、设计43.1.1 结构体设计43.1.2 结构体之间的关系43.1.3 函数设计4第四章 系统实现24.1 结构体实现24.2 函数实现24.2.1 进程调度算法的函数实现24.2.2. 银行家算法的函数实现64.3 主函数实现44.3.1. 进程调度算法的主函数实现44.3.2. 银行家算法的主函数实现14.4 系统界面14.4.1 进程调度算法的运行界面14.4.2 银行家算法的运行界面1第五章 系统测试25.1 模块测试25.1.1 进程调度算法25.1.2 银行家算法45.2 课程设计过程中遇到的问题6总 结7致 谢8参考文献9第一章 绪论随着计算机的不断的更新换代，操作系统也越来越多

4、样化，复杂化，这就要求我们大学生掌握一些操作系统的根本知识，了解操作系统的根本原理，能够正确地使用操作系统，直到操作系统的作用，为此，我们列举了两个操作系统中常用的两个知识点，进程调度算法和银行家算法，帮助学生能够较快的了解并掌握这两个常用的知识点。1.1 课程设计的背景和意义1.1.1 课程设计的理论研究根底1.先来先效劳算法：每次调度都是从后备作业队列中选择一个或多个最先进入该队列的作业，将它们调入内存，为它们分配资源、创立进程，然后放入就绪队列，每次调度从就绪队列中选择一个最先进入该队列的进程，为之分配处理机，使之投入运行。短进程优先调度算法：从就绪队列中选出一个运行时间最短的进程，将处

5、理机分配给它，使它立即执行并一直执行到完成。高响应比调度算法：为每个作业引入动态优先权，并使作业的优先级随着等待时间的增加提高，那么长作业等待一定的时间后，必然有时机分配到处理机。2.银行家算法：要预防死锁，有摒弃“请求和保持条件，摒弃“不剥夺条件，摒弃“环路等待条件等方法。而最具代表性的防止死锁的算法，便是Dijkstra的银行家算法。利用银行家算法，我们可以来检测CPU为进程分配资源的情况，决定CPU是否响应某进程的的请求并为其分配资源，从而很好防止了死锁的产生1.1.2 课程设计的意义课程设计是学生学习完?操作系统?课程后，进行的一次全面的综合训练，通过课程设计，让学生更好地掌握操作系统

6、的原理及实现方法，加深对操作系统根底理论和重要算法的理解，加强学生的动手能力。1.2 课程设计环境软件环境：VC+6.0。硬件环境：图书馆5楼实验室第二章 需求分析2.1 功能要求2.1.1进程调度算法 编程实现进程调度算法的根本过程，设计要求：1能够选择进程调度算法先来先效劳、短进程优先算法和高响应比优先算法。2可以输入进程数目至少4个进程，以及各进程的提交时间和运行时间。3能够以下列图形式显示调度过程及平均周转时间和平均带权周转时间。2.1.2银行家算法编写一程序，能够模拟银行家算法和平安算法来防止死锁。假设系统资源有A、B、C三种，可以运行5个进程。该程序具备的根本功能为：1程序可以输入

7、3种资源的数目，5个进程对3种资源的最大需求量、已分配量和需求量。2能够判断某一时刻系统是否处于平安状态，如果处于平安状态能够给出平安序列。3当某进程提出资源申请时，能够判断是否能把资源分配给申请进程。2.2 问题的解决方案2.2.1进程调度算法 运用先来先效劳，短进程优先算法，高响应比算法来实现对操作系统进程的调度算法。其中运用数据结构中的排序知识便可轻易解决。2.2.2银行家算法银行家算法，平安算法查看平安序列，运用数组，循环判断是否存在平安序列，从而即可判断平安性，防止死锁。第三章 系统设计3.1 数据设计3.1.1 结构体设计1. 进程调度算法的结构体设计1struct PCBint

8、id;/进程idfloat ptime;/到达时间float starttime;/开始时间float waittime;/等待时间float finishtime;/完成时间float runtime;/运行时间float turntime;/周转时间float qtime;/带权周转时间;/进程控制块2typedef PCB ElemType;typedef structElemType elem100; int length; SqList;/顺序表，用于存储进程控制块3.1.2 结构体之间的关系 1. 进程调度算法SqList顺序表结构体，用于存储PCB进程控制块，以实现各种方法的进程

9、调度3.1.3 函数设计1. 进程调度算法的函数设计1int ListInsert_Sq(SqList &L,int i, ElemType e)/在顺序表第i个位置插入数据e2void bubble_sort(ElemType e,int n)/冒泡法排序3int ListInsert_Sq2(SqList &L,int i, ElemType e,int n)/按短进程优先法往顺序表中插入数组en4int ListInsert_Sq3(SqList &L,int i, ElemType e,int n)/按高响应比法往顺序表中插入数组en5void FCFS(ElemType e,int

10、n)/先来先效劳计算各个时间6void SJF(SqList &L)/短进程优先法计算各个时间7void FPF(SqList &L)/高响应比法计算各个时间8void Display(SqList &L)/输出函数，把顺序表中的数据输出2. 银行家算法的函数设计1void input(int available3,int max53,int allocation53,int need53,int finish5,string name5)/输入可利用资源数目，最大需求数目，以分配数目，需求数目，完成标记，进程名字2int fenpei(int available3,int allocatio

11、n53,int need53,int finish5,int xb5)/分配函数，检查分配是否平安3int request(int available3,int max53,int allocation53,int need53,string name5)/请求函数，输入进程名字和资源申请数目4int fanhui(int available3,int max53,int allocation53,int need53,string name5,string &name2)/申请资源不平安时 返还申请资源第四章 系统实现4.1 结构体实现1. 进程调度算法的结构体实现1struct PCBin

12、t id;/进程idfloat ptime;/到达时间float starttime;/开始时间float waittime;/等待时间float finishtime;/完成时间float runtime;/运行时间float turntime;/周转时间float qtime;/带权周转时间;/进程控制块2typedef PCB ElemType;typedef structElemType elem100; int length; SqList;/顺序表，用于存储进程控制块4.2 函数实现 进程调度算法的函数实现1int ListInsert_Sq(SqList &L,int i, El

13、emType e) /在顺序表第i个位置插入数据e if(iL.length+1) return 0; if(L.length=100) return -1; int j; for(j=L.length;j=i-1;j-) L.elemj+1=L.elemj; L.elemi-1=e; L.length+; return 1;2void bubble_sort(ElemType e,int n) /冒泡法排序ElemType t;int i,j,swap;for(i=1;i=n;i+)swap=0;for(j=0;jej+1.ptime)t=ej;ej=ej+1;ej+1=t;swap=1;i

14、f(swap=0)break;3int ListInsert_Sq2(SqList &L,int i, ElemType e,int n) /按短进程优先法往顺序表中插入数组enint j,q,swap,p;j=0;q=0;float t;ListInsert_Sq(L,i,ej);t=ej.ptime+ej.runtime;i+;j+;p=j;for(j;jt)ListInsert_Sq(L,i,ej);t=ej.ptime+ej.runtime;i+;p+;else if(ej.ptimet|(j+1)=n)swap=1;if(swap=1)if(p=q)ListInsert_Sq(L,i

15、,eq);t=eq.ptime+eq.runtime;i+;p+;if(qp)swap=0;ElemType x;for(q;qp;q-)if(eq.runtimeeq-1.runtime)x=eq;eq=eq-1;eq-1=x;if(swap=0)ListInsert_Sq(L,i,ep);t=t+ep.runtime;i+;p+;j=p-1;return 1;4int ListInsert_Sq3(SqList &L,int i, ElemType e,int n) /按高响应比法往顺序表中插入数组enint j,q,swap,p;j=0;q=0;float t;ListInsert_Sq

16、(L,i,ej);t=ej.ptime+ej.runtime;i+;j+;p=j;for(j;jt)ListInsert_Sq(L,i,ej);t=ej.ptime+ej.runtime;i+;p+;else if(ej.ptimet|(j+1)=n)swap=1;if(swap=1)if(p=q)ListInsert_Sq(L,i,eq);t=eq.ptime+eq.runtime;i+;p+;if(qp)swap=0;ElemType x;for(q;qp;q-)if(t-eq.ptime)/eq.runtime(t-eq-1.ptime)/eq-1.runtime)x=eq;eq=eq-

17、1;eq-1=x;if(swap=0)ListInsert_Sq(L,i,ep);t=t+ep.runtime;i+;p+;j=p-1;return 1;5void FCFS(ElemType e,int n) /先来先效劳计算各个时间int i=0;while(i=ei-1.finishtime)ei.starttime=ei.ptime; ei.finishtime=ei.starttime+ei.runtime;ei.turntime=ei.finishtime-ei.ptime;ei.qtime=ei.turntime/ei.runtime;elseei.starttime=ei-1.

18、finishtime;ei.waittime=ei.starttime-ei.ptime;ei.finishtime=ei.starttime+ei.runtime;ei.turntime=ei.finishtime-ei.ptime;ei.qtime=ei.turntime/ei.runtime;i+;6void SJF(SqList &L) /短进程优先法计算各个时间int i=0;while(i=L.elemi-1.finishtime)L.elemi.starttime=L.elemi.ptime; L.elemi.finishtime=L.elemi.starttime+L.elem

19、i.runtime;L.elemi.turntime=L.elemi.finishtime-L.elemi.ptime;L.elemi.qtime=L.elemi.turntime/L.elemi.runtime;elseL.elemi.starttime=L.elemi-1.finishtime;L.elemi.waittime=L.elemi.starttime-L.elemi.ptime;L.elemi.finishtime=L.elemi.starttime+L.elemi.runtime;L.elemi.turntime=L.elemi.finishtime-L.elemi.ptim

20、e;L.elemi.qtime=L.elemi.turntime/L.elemi.runtime;i+;7void FPF(SqList &L)/高响应比法计算各个时间int i=0;while(i=L.elemi-1.finishtime)L.elemi.starttime=L.elemi.ptime; L.elemi.finishtime=L.elemi.starttime+L.elemi.runtime;L.elemi.turntime=L.elemi.finishtime-L.elemi.ptime;L.elemi.qtime=L.elemi.turntime/L.elemi.runt

21、ime;elseL.elemi.starttime=L.elemi-1.finishtime;L.elemi.waittime=L.elemi.starttime-L.elemi.ptime;L.elemi.finishtime=L.elemi.starttime+L.elemi.runtime;L.elemi.turntime=L.elemi.finishtime-L.elemi.ptime;L.elemi.qtime=L.elemi.turntime/L.elemi.runtime;i+;8void Display(SqList &L)/输出函数，把顺序表中的数据输出int i=0;flo

22、at t1,t2;t1=0;t2=0;cout执行次序setw(10)提交时间setw(10)开始时间setw(10)等待时间setw(10)完成时间setw(10)运行时间setw(10)周转时间setw(14)带权周转时间endl;while(iL.length)coutL.elemi.idsetw(10)L.elemi.ptimesetw(10)L.elemi.starttimesetw(10)L.elemi.waittimesetw(10)L.elemi.finishtimesetw(10)L.elemi.runtimesetw(10)L.elemi.turntimesetw(10)L

23、.elemi.qtimeendl;t1=t1+L.elemi.turntime;t2=t2+L.elemi.qtime;i+;cout平均周转周期为：t1/L.lengthendl;cout平均带权周转周期为：t2/L.lengthendl;4.2.2. 银行家算法的函数实现1void input(int available3,int max53,int allocation53,int need53,int finish5,string name5) /输入可利用资源数目，最大需求数目，以分配数目，需求数目，完成标记，进程名字cout请输入3种资源的数目;for(int j=0;javail

24、ablej;for(int i=0;i5;i+)cout请输入第i+1namei;cout请输入第i+1个进程对3种资源的最大需求量;for(int j=0;jmaxij;cout请输入第i+1个进程对3种资源的已分配量;for(j=0;jallocationij;for(j=0;j3;j+)needij=maxij-allocationij;finishi=0;2int fenpei(int available3,int allocation53,int need53,int finish5,int xb5) /分配函数，检查分配是否平安int m=0,k=0,n=0;for(int i=0

25、;i5;i+)if(needi0=0&needi1=0&needi2=0)for(int j=0;j3;j+)availablej+=allocationij;finishi=1;m+;xbk+=i;while(m5)for(int i=0;i=needi0&available1=needi1&available2=needi2)for(int j=0;j5)return 0;return 1;3int request(int available3,int max53,int allocation53,int need53,string name5,string &name2)/申请资源，输入

26、申请资源的进程名字，申请数目int i;int flag;while(flag!=0)coutname2abc;for(int n=0;n5;n+)if(namen=name2)flag=0;i=n;if(flag!=0)cout进程不存在 请重新输入endl;if(a=needi0&b=needi1&c=needi2)if(a=available0&b=available1&c=available2)allocationi0+=a;allocationi1+=b;allocationi2+=c;available0-=a;available1-=b;available2-=c;needi0=

27、maxi0-allocationi0;needi1=maxi1-allocationi1;needi2=maxi2-allocationi2;cout各进程目前所需资源数目:endl;cout进程setw(10)资源Asetw(10)资源Bsetw(10)资源Cendl;for(int w=0;w5;w+)coutnamewsetw(10)needw0setw(10)needw1setw(10)needw2endl;if(needi0=0&needi1=0&needi2=0)cout进程namei得到运行所需资源，可以运行，释放资源。endl;available0+=allocationi0;

28、available1+=allocationi1;available2+=allocationi2;return 1;elsecout该进程资源请求数目大于可利用资源，让进程name2等待endl;return 0;else cout该进程资源请求数目大于该进程所需资源数目，进程name2不可以运行endl;return 0;4int fanhui(int available3,int max53,int allocation53,int need53,string name5,string &name2)/申请资源不平安时，返还资源int i;for(int n=0;n5;n+)if(namen=name2)i=n;allocationi0-=a;allocationi1-=b;allocationi2-=c;available0+=a;available1+=b;available2+=c;needi0=maxi0-allocationi0;needi1=maxi1-allocationi1;needi2=maxi2-allocationi2;cout各进程目前所需资源数目:endl;cout