进程调度算法磁盘调度算法银行家算法操作系统课程设.docx

《进程调度算法磁盘调度算法银行家算法操作系统课程设.docx》由会员分享，可在线阅读，更多相关《进程调度算法磁盘调度算法银行家算法操作系统课程设.docx（46页珍藏版）》请在三一办公上搜索。

1、操作系统课程设计说明书学院名称： 专业班级： 姓 名： 学 号： 2013年1月1日评分标准优秀：有完整的符合标准的文档，文档有条理、文笔通顺，格式正确，程序完全实现设计要求，独立完成；良好：有完整的符合标准的文档，文档有条理、文笔通顺，格式正确；程序完全实现设计要求，独立完成，但存在少量错误；中等：有完整的符合标准的文档，有基本实现设计方案的软件，设计方案正确；及格：有完整的符合标准的文档，有基本实现设计方案的软件，设计方案基本正确；不及格：没有完整的符合标准的文档，软件没有基本实现设计方案，设计方案不正确。没有独立完成，抄袭或雷同。成绩评定为： 。 指导教师： 年 月 日目 录 一进程调度

2、算法 4-23 页二银行家算法 24-34 页三磁盘调度算法 35-46页进程调度算法1设计目的 在多道程序设计中，经常是若干个进程同时处于就绪状态，必须依照某种策略决定哪个进程优先占有处理机，因而必须解决进程调度的问题，进程调度算法就是要解决进程调度的问题。2. 任务及要求2.1 设计任务 设计程序来模拟进程的四种调度算法，模拟实现调度的基本功能。2.2 设计要求 产生的各种随机数要加以限制，如alltime限制在40以内的整数。进程的数量n不能取值过大。3. 算法及数据结构3.1算法的总体思想（流程） 每个用来标识进程的进程控制块PCB用结构来描述，包括以下字段：（1）进程优先数ID，其中

3、0为闲逛进程，用户进程的标识数为1，2，3。（2）进程优先级Priority，闲逛进程（idle）的优先级为0，用户进程的优先级大于0，且随机产生，优先数越大，优先级越高。（3）进程占用的CPU时间CPUtime，进程每运行一次，累计值等于4。（4）进程总共需要运行时间Alltime，利用随机函数产生。（5）进程状态，0：就绪态；1：运行态；2：阻塞态。 利用链表将数据连接起来，实现数据的存储。3.2 链表模块3.2.1 功能 实现链表的存储功能，以及实现存储的查找功能。3.2.2 数据结构 构造链表这个数据结构，以及链表的初始化，链表的插入，链表的长度。3.2.3 算法 typedef st

4、ruct ElemType *elem; int length; int listsize; SqList;Status InitList(SqList &l)l.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType);if(!l.elem) exit(OVERFLOW);l.length=0;l.listsize=LIST_INIT_SIZE;return OK;int ListLength(SqList l)return(l.length);Status ListInsert_Sq(SqList &L,int i, ElemType e

5、)/在顺序表L的第i个位置前插入元素e,i的合法值为1.L.length+1 if(iL.length+1) return ERROR; if(L.length=L.listsize) ElemType*newbase=(ElemType *)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType); if(!newbase) exit(OVERFLOW); L.elem=newbase; L.listsize+=LISTINCREMENT; ElemType *q=&L.elemi-1, *p=&L.elemL.length-1;

6、while(p=q) *(p+1)=*p; -p; /插入位置后的元素右移 *q=e; +L.length; return OK;Status GetElem(SqList L,int i,ElemType &e)if(iL.length)return ERROR;elsee=*(L.elem+i-1);return OK;void Outputlist(SqList &L)if(0=L.length)printf(空集!);else for(int i=0;iL.length;+i) printf(%c,*(L.elem+i);3.3 主函数模块3.3.1功能 实现进程调度的四种算法，以及人

7、机交互的菜单。3.3.2 数据结构 主要包括五个部分，分别是四种算法，和进程的输入和菜单部分，功能分别实现。3.3.3算法void main()for(1;)int number; PCB pcb100 ;srand(time(0);int max;int ppp100;int time=0;int time1;int m;int a100;a0=0;printf(n*进程调度算法的模拟*n);printf(* 1.先到先服务调度 2.最短作业优先调度 *n);printf(* 3.优先权调度 4.轮转发调度 *n);printf(*);printf(n请选择调度的方法: );scanf(%d

8、,&m);if(m!=1&m!=2&m!=3&m!=4) printf(输入错误! 重新输入: ); scanf(%d,&m); if(m!=1&m!=2&m!=3&m!=4) printf(输入错误! 重新输入: ); scanf(%d,&m); if(m!=1&m!=2&m!=3&m!=4) printf(输入错误! 重新输入: ); scanf(%d,&m); if(m!=1&m!=2&m!=3&m!=4) printf(输入错误! 重新输入: ); scanf(%d,&m); printf(请输入进程的个数: );scanf(%d,&number);printf(n开始时用户进程均为就

9、绪状态,运行时间随机产生nn);SqList sq;InitList(sq);for(int r=0;rnumber;r+)pcbr.CPUtime=0;for(int i=0;inumber;i+) pcbi.Priority=rand()%50;while(1) if(pcbi.Priority20) pcbi.Priority=rand()%50; else break; pcbi.Alltime=rand()%40;while(1) if(pcbi.Alltime10) pcbi.Alltime=rand()%40;else break;for(int j=0;jnumber;j+)L

10、istLength(sq);ListInsert_Sq(sq,ListLength(sq),pcbi ); if(m=1) printf(n*程序演示开始*n); int coun=0; /计数变量 int wait100; /等待时间数组 wait0=0; int Allwait=0; for(int i1=0;i1number;i1+)printf(下面开始调用第%d个进程； n,i1); printf(开始时间为%d 执行时间为%dn,coun,pcbi1.Alltime); coun+=pcbi1.Alltime; if(i1!=0)waiti1=pcbi1-1.Alltime+wai

11、ti1-1; for(int i2=0;i2number;i2+)Allwait=waiti2+Allwait; printf(平均等待时间为:%dn,Allwait/number); if(m=2) int min=pcb0.Alltime; int wait1100; wait10=0; int in=0; int coun1=0; printf(*最短作业优先调度!*n); cout进程所需时间分别是:endl; for(i=0;inumber;i+) coutpcbi.Alltimeendl; printf(进程调度的顺序为: ); for(i=0;inumber;i+) min=50

12、; for(j=0;jnumber;j+) if(pcbj.Alltimemin) min=pcbj.Alltime; in=j; printf(%d ,in+1); pcbin.Alltime+=50; if(m=3) printf(ID 优先级 运行总时间 进程状态n); for(int k=0; knumber; k+) printf(%d %d %d 就绪n,k+1, pcbk.Priority, pcbk.Alltime); printf(n*程序调度演示开始*n); for(int f=1;f1000;f+) int count=0,count1=0; for(int i=0;in

13、umber;i+) pppi=pcbi.Priority; if(pcbi.Alltime!=0) count1+; count1-; time=time+count1*4; max=Max(ppp,number); if(pcbmax.Alltime=0) pppmax=-1; pcbmax.Priority=-1; max=Max(ppp,number); pcbmax.Priority-=4; pcbmax.Alltime-=4; pcbmax.CPUtime+=4; if(pcbmax.Alltime=0) pcbmax.Alltime=0; for(int w=0;wnumber;w

14、+) if(pcbw.Alltime=0) pppw=-1; pcbw.Priority=-1; for(int e=0; enumber;e+) pcbe.Priority+; printf(n#第%d个进程正在执行!#n,max+1); printf(n第%d次调度结束，运行结果为:nn,f); printf(ID 优先级 需要总时间 执行时间n); for(int k=0; knumber; k+) printf(%d %d %d %d n,k+1, pcbk.Priority, pcbk.Alltime,pcbk.CPUtime); for(int l=0;lnumber;l+) if

15、(pcbl.Alltime=0) count+; if(count=number) break; time1=time/number; printf(n*用户进程全部执行完毕!*); printf(nn平均等待时间是: ); printf(%dnn,time1); if(m=4) printf(ID 运行总时间 进程状态n); for(int k=0; knumber; k+)printf(%d %d 就绪n,k+1, pcbk.Alltime); printf(n*程序调度演示开始*n); for(int f=1;f1000;f+)int count=0; for(i=0;i0)pcbi.A

16、lltime-=4; pcbi.CPUtime+=4; if(pcbi.Alltime0)pcbi.Alltime=0; / printf(n#第%d个进程正在执行!#n,i+1); printf(n第%d次调度结束，运行结果为:nn,f); printf(ID 需要时间 执行时间n); for(int k=0; knumber; k+) printf(%d %d %d n,k+1, pcbk.Alltime,pcbk.CPUtime);/for(int l=0;lnumber;l+)if(pcbl.Alltime=0)count+; if(count=number)break;printf(

17、n*用户进程全部执行完毕!*); 4. 实验结果及分析4.1 实验结果 先到先服务算法的实验结果如下：最短作业优先调度的实验结果如下：优先权调度算法的实验结果如下：轮转法调度的实验结果如下：4.2 结果分析 本次试验基本实现了进程调度的四种算法，每一种算法都能模拟出算法的具体过程。相应的结果也完全符合预想的结果。同时，对于算法的实践编写进一步增加了编程的技巧，以及编程的熟练程度。银行家算法1设计目的 银行家算法是避免死锁的一种十分重要的方法，通过编写一个模拟的动态的银行家算法的程序，能够进一步加深对死锁的理解，以及产生死锁的必要条件。并掌握通过银行家算法来避免死锁。2. 任务及要求2.1 设计

18、任务 根据银行家算法的基本思想来设计程序，模拟银行家算法的过程。用程序来实现银行家算法的具体动态过程。2.2 设计要求 根据银行家算法的基本思想，编写和调试一个能实现动态的分配资源的模拟程序。并能够有效的防止死锁的发生。3. 算法及数据结构3.1算法的总体思想（流程） 银行家算法的基本思想是，系统中的所有进程放入进程集合，在安全状态下系统受到进程的请求后会试探性的把资源分配给他，现在系统将剩下的资源和进程集合中其他进程还需要的资源作对比，找出剩余资源能满足的进程，从而保证进程运行完并释放资源继续满足剩下进程对资源的需要。最后检查集合为空集时表明本次申请可行，系统继续处于安全状态，可以实施本次分

19、配。否则不能实施本次分配。3.2 显示资源矩阵 showdata() 模块3.2.1 功能 主要是显示资源的矩阵，包括输入的已分配的的资源矩阵，以及输出的资源矩阵。3.2.2 数据结构 最大需求矩阵max以及已分配矩阵allocation，分别定义为m*n阶的矩阵，利用二维数组来存储。3.2.3 算法void showdata() /显示资源矩阵 int i,j; cout系统目前可用的资源Avaliable:endl; for(i=0;iN;i+) coutnamei ; coutendl; for (j=0;jN;j+) coutAvaliablej ; /输出分配资源 coutendl;

20、 cout Max Allocation Needendl; coutendl; cout进程名 ; for(j=0;j3;j+) for(i=0;iN;i+) coutnamei ; cout ; coutendl; for(i=0;iM;i+) cout i ; for(j=0;jN;j+) coutMaxij ; cout ; for(j=0;jN;j+) coutAllocationij ; cout ; for(j=0;jN;j+) coutNeedij ; coutendl; 3.3 申请资源判定模块3.3.1功能 利用银行家实现对申请的资源进行判定。3.3.2 数据结构 对已经存

21、储的矩阵进行比较。3.3.3算法void share() /利用银行家算法对申请资源对进行判定 char ch; int i=0,j=0; ch=y; cout请输入要求分配的资源进程号(0-M-1i; /输入须申请的资源号 cout请输入进程 i 申请的资源:endl; for(j=0;jN;j+) coutnamejRequestj; /输入需要申请的资源 for (j=0;jNeedij) /判断申请是否大于需求，若大于则出错 cout进程 i申请的资源大于它需要的资源; cout 分配不合理，不予分配！Avaliablej) /判断申请是否大于当前资源，若大于则 cout进程i申请的资

22、源大于系统现在可利用的资源; cout 分配出错，不予分配!endl; ch=n; break; if(ch=y) changdata(i); /根据进程需求量变换资源 showdata(); /根据进程需求量显示变换后的资源 safe(); /根据进程需求量进行银行家算法判断 3.4 主函数模块3.4.1功能 实现银行家算法对资源的增加、删除、修改。3.4.2 数据结构 对已经完成的模块进行功能集成。3.4.3算法int main() int i,j,number,choice,m,n,flag; char ming; coutendl; cout* 银*行*家*算*法 *endl;cout

23、endl; coutn;coutendl; N=n; for(i=0;in;i+) cout资源i+1ming; namei=ming; coutnumber; Avaliablei=number; coutendl; coutm; M=m; cout请输入各进程的最大需求量(m*n矩阵):endl; for(i=0;im;i+) for(j=0;jMaxij; doflag=0; cout请输入各进程已经申请的资源量(m*n矩阵):endl; for(i=0;im;i+) for(j=0;jAllocationij; if(AllocationijMaxij) flag=1; Needij=

24、Maxij-Allocationij; if(flag) cout申请的资源大于最大需求量，请重新输入!nendl;while(flag); showdata(); /显示各种资源 safe(); /用银行家算法判定系统是否安全 while(choice)cout*银行家算法演示*endl; cout 1:增加资源 ; cout 2:删除资源 endl; cout 3:修改资源 ; cout 4:分配资源 endl; cout 5:增加进程 ; cout 0:离开 endl; cout*endl; coutchoice; switch(choice) case 1: addresources();break; case 2: delresources();break; case 3: changeresources();break; case 4: share();break; case 5: addprocess();break; case 0: choice=0;break; default: cout请正确选择功能号(0-5)!next; for(int i=0;idata-f); f=l-data; l=l-next; num=num/c; cout先来先服务的寻道顺序是:endl; print(head); cout平均寻道长度:numen