[优秀毕业设计精品] 进程模拟调度程序.doc

《[优秀毕业设计精品] 进程模拟调度程序.doc》由会员分享，可在线阅读，更多相关《[优秀毕业设计精品] 进程模拟调度程序.doc（36页珍藏版）》请在三一办公上搜索。

1、数学与计算机学院课程设计说明书课 程 名 称: 操作系统原理-课程设计 课 程 代 码: 题 目: 进程调度模拟程序 年级/专业/班: 09级 计科 5班 学 生 姓 名: 学 号: 开 始 时 间: 2011 年 12 月 9 日完 成 时 间: 2011 年 12 月 23 日课程设计成绩：学习态度及平时成绩（30）技术水平与实际能力（20）创新（5）说明书撰写质量（45）总 分（100）指导教师签名： 年 月 日摘 要随着计算机的普及，在计算机上配置合适的操作系统，已成为不可或缺的因素，操作系统时配置在计算机硬件上的第一层软件，时对硬件系统的首次扩充，其他的诸如汇编程序，编译程序，数据库

2、管理系统等系统软件，以及大量的应用软件，都将依赖于操作系统的支持，取得它的服务。OS作为用户与计算机硬件之间的接口，作为系统资源的管理者，实现了对计算机资源的抽象，因此，不断提高计算机资源的利用率，方便用户，以及器件的不断更新换代，计算机体系结构的不断发展，已经成为推动计算机操作系统发展的主要因素，为了达到这些目的，了解操作系统的发展过程，熟悉操作系统的内部结构，掌握操作系统的运行，已经成为当代大学生，特别是计算机专业的学生所必不可少的知识。操作系统的主要任务是为多道程序的运行提供良好的运行环境，并能最大程度的提高系统中各种资源的利用率和方便用户，为了实现这些功能，操作系统还应该具有处理机管理

3、，存储器管理，设备管理和文件管理等功能。关键词：操作系统；资源利用率；处理机；文件管理目 录 1 引 言11.1 问题的提出11.2任务与分析12 程序的主要函数22.1建立将要模拟进程调度的所有进程PCB链表22.2模拟CPU运行进程32.3显示42.4排序52.5建立先来先服务调度算法的就绪队列72.6建立最高优先数优先调度算法的就绪队列82.7进程模拟调度92.8主函数123 程序运行平台144 总体设计145 程序结构体的说明146 程序运行结果157 结论228 参考文献239 附录241 引 言 1.1 问题的提出随着现在操作系统的日趋成熟，用户对计算机的需求越来越多，处理机在同一

4、时刻处理资源的能力是有限的，从而导致各种任务随时随地的争夺使用处理机，因而此对程序的并发能力提出了更高的要求。引进并发技术后，为了更好地说明并发现象（尤其是动态进程），引入了进程的概念。进程是一个具有一定独立功能的可并发执行的关于某个数据集合一次运行活动的程序。一个程序的启动执行，便是一个进程的建立；一个程序执行结束（正常或者是不正常），便是一个进程的撤销。由于同时处于就绪态（争夺使用CPU资源）的进程通常比较多，因此需要CPU调度算法来决定由哪个进程获得CPU使用权进入运行状态，即进程调度算法。1.2任务与分析本课题主要的目的是编写并调试一个有N个进程并发的进程模拟调度程序。进程调度算法：采

5、用最高优先数优先的调度算法（即把处理机分配给优先数最高的进程）和先来先服务算法。每个进程有一个进程控制块（ PCB）表示。进程控制块可以包含如下信息：进程名、优先数、到达时间、需要运行时间、已用CPU时间、进程状态等等。 进程的优先数及需要的运行时间可以事先人为地指定（也可以由随机数产生）。进程的到达时间为进程输入的时间。 进程的运行时间以时间片为单位进行计算。等待I/O的时间以时间片为单位进行计算，可随机产生，也可事先指定。每个进程的状态可以是就绪 R（Ready）、运行R（Run）、等待（Wait）或完成F（Finish）四种状态之一。 就绪进程获得 CPU后都只能运行一个时间片。用已占用

6、CPU时间加1来表示。 如果运行一个时间片后，进程的已占用 CPU时间已达到所需要的运行时间，则撤消该进程，如果运行一个时间片后进程的已占用CPU时间还未达所需要的运行时间，也就是进程还需要继续运行，此时应将进程的优先数减1（即降低一级），然后把它插入就绪队列等待CPU。 每进行一次调度程序都打印一次运行进程、就绪队列、等待进程以及各个进程的 PCB，以便进行检查。重复以上过程，直到所要进程都完成为止。2 程序的主要函数2.1建立将要模拟进程调度的所有进程PCB链表算法思想：要建立的进程个数n作为函数参数，头指针作为返回，在函数内部由一重循环建立每个进程PCB的各个数据项，其中进程需要运行时间

7、、到达时间以及优先数全部采用随机生成。代码：plist *creatpro(int n) /建立所有将要进行N个模拟调度的进程int j;plist *p, *q, *head;p= (plist *) malloc(sizeof(plist);head = p; for(j=0;jname = j+1; p-needtime = 1+(int)(10.0*rand()/(RAND_MAX+1.0);p-arrivetime = (int)(10.0*rand()/(RAND_MAX+1.0);p-pri = 1+(int)(9.0*rand()/(RAND_MAX+1.0);p-state

8、= 0;p-cputime =0;p-next = (plist *) malloc(sizeof(plist);p=p-next; q-next = NULL;return head;流程图： p= (plist *) malloc(sizeof(plist); head = p; for(j=0;jname = j+1; p-needtime = 1+(int)(10.0*rand()/(RAND_MAX+1.0); p-arrivetime = (int)(10.0*rand()/(RAND_MAX+1.0); p-pri = 1+(int)(9.0*rand()/(RAND_MAX+1

9、.0); p-state = 0; p-cputime =0; p-next = (plist *) malloc(sizeof(plist); p=p-next;q-next = NULL;return head;2.2模拟CPU运行进程算法思想：需要运行进程的PCB作为函数参数，先修改进程状态，然后修改再修改进程已运行时间和还需运行时间。代码：void action(plist * nowpro)/模拟CUP运行进程的过程nowpro-state = 2; /设置进程状态为运行态printf(now is process %d ,nowpro-name);nowpro-needtime-;

10、 /修改进程还需运行时间nowpro-cputime+; /修改进程已运行时间nowpro-state = 1;if(nowpro-needtime=0)/进程运行结束printf(tthe process %d is endn,nowpro-name); nowpro-state = 4; /进程运行结束，设置进程状态为结束态elseprintf(tprocess %d needtime is %dn,nowpro-name,nowpro-needtime);printf(-n);流程图：nowpro-state = 2; nowpro-needtime-; nowpro-cputime+;

11、 nowpro-state = 1; nowpro-needtime=0？真 假printf(tthe process %d is endn, printf(tprocess %d needtime is %dn,nowpro-name); nowpro-name,nowpro-needtime);nowpro-state = 4;2.3 显示算法思想：先判断链表借点是否为空，然后利用循环输出各PCB信息代码：void show(plist * process) /显示if(!process)printf(there is no process nown);while(process&proc

12、ess-state!=4)printf(name of process %d,process-name);printf(tneedtime %d,process-needtime);printf( arrivetime %d,process-arrivetime);printf( pri %d,process-pri);printf( state %d,process-state);printf( cputime %dn,process-cputime);process = process-next;流程图：if(!process) 真 假printf(there is no 当process

13、&process-state!=4 process nown); printf(name of process %d,process-name); printf(tneedtime %d,process-needtime); printf( arrivetime %d,process-arrivetime); printf( pri %d,process-pri); printf( state %d,process-state); printf( cputime %dn,process-cputime); process = process-next;2.4排序算法思想：利用两层循环，比较相邻

14、两个元素的大小，第一遍将最大的数排到最末，第二遍将次大的数排到最末的数的前面，经N-1遍后将满足排序的要求。代码：plist *sort(plist *head) /将进程队列按到达先后顺序排序plist *p,*p1,*p2,*p3,*temp;p=head;while(p-next!=NULL) p=p-next;while(p!=head)p3=p1=head;p2=p1-next;while(p1!=p & p1-next!=NULL)if(p1-arrivetime)(p2-arrivetime)if(p1=head)head=p2;elsep3-next=p2;temp=p2-ne

15、xt;p2-next=p1;p1-next=temp;temp=p1;p1=p2;p2=temp; p3=p1;p1=p1-next;p2=p1-next;p=p3;return head;2.5建立先来先服务调度算法的就绪队列算法思想：先来先服务调度算法中的就绪队列是按到达时间的先后排序的，当就绪队列为空时，直接将作为将要添加的进程PCB temp作为队头，如果就绪队列不为空，则将temp添加到队列末尾。添加到就绪队列后再修改进程状态为就绪态。代码：plist *fcfs_creatready(plist *ready_queue,plist *temp) /将进程temp添加到就绪队列re

16、ady_queue的尾部plist *q;q=ready_queue;if(ready_queue) /当就绪队列不为空时，新进入的进程添加到就绪队列末尾while(q-next)q=q-next; /使指针P指向就绪队列中最后一个进程q-next=temp;temp-state=1;/修改进程状态temp-next=NULL;else /当就绪队列为空时，新进入的进程作为就绪队列头部ready_queue=temp;ready_queue-state = 1; /将进程状态设为就绪状态temp-next=NULL;return ready_queue;流程图：q=ready_queue;re

17、ady_queue=NULL？真 假q-next ready_queue=temp; q=q-next; ready_queue-state=1; q-next=temp; temp-next=NULL;temp-state=1; temp-next=NULL; return ready_queue;2.6建立最高优先数优先调度算法的就绪队列算法思想：最高优先数优先调度算法中的就绪队列是按进程优先数递减排序的，当就绪队列为空时，直接将作为将要添加的进程PCB temp作为队头，如果就绪队列不为空，则将temp添加到队列合适位置。然后再修改进程状态为就绪态。代码：plist *hrrn_crea

18、tready(plist *ready_queue, plist *temp)/按优先数递减的顺序将进程temp添加到就绪队列ready_queue的合适位置plist *q, *p;p=q=ready_queue;if(ready_queue & ready_queue-pritemp-pri) /按优先数递减的顺序将进程temp添加到就绪队列ready_queue的合适位置while(q&q-pri=temp-pri)p=q;q=q-next; /使指针P-next指向就绪队列中进程temp的插入位置p-next=temp;temp-next=q;temp-state=1;/修改进程状态e

19、lse /当就绪队列为空时，新进入的进程作为就绪队列头部temp-next=ready_queue;ready_queue=temp; ready_queue-state = 1; /将进程状态设为就绪状态return ready_queue;流程图：p=q=ready_queue; ready_queue-pritemp-pri 真 ready_queue 假 q&q-pri=temp-pri ready_queue=temp; p=q; temp-next=NULL; ready_queue-state=1; temp-next=NULL;q=q-next; q-next=temp; te

20、mp-state=1; return ready_queue;2.7进程模拟调度算法思想：1.先来先服务调度算法先来先服务调度算法是一种最简单的调度算法，该算法既可以用于作业调度，也可用于进程调度。当在作业调度中采用该算法时，每次调度都是从后备作业队列中选择一个或多个最先进入该队列的作业，将他们调入内存，为它们分配资源、创建进程，然后放入就绪队列。在进程调度中采用FCFS算法时，则每次调度是从就绪队列中选择一个最先进入该队列的进程，为之分配处理机，使之投入运行。该进程一直运行到完成或发生某事件而阻塞后才放弃处理机。FCFS算法比较有利于长作业（进程），而不利于短作业（进程）。2.最高优先数调度

21、算法优先数调度算法常用于批处理系统中。在进程调度中，每次调度时，系统把处理机分配给就绪队列中优先数最高的进程。它又分为两种：非抢占式优先数算法和抢占式优先数算法。在非抢占式优先数算法下，系统一旦把处理机分配给就绪队列中优先数最高的进程后，这个进程就会一直运行，直到完成或发生某事件使它放弃处理机，这时系统才能重新将处理机分配给就绪队列中的另一个优先数最高的进程。在抢占式优先数算法下，系统先将处理机分配给就绪队列中优先数最高的进程度让它运行，但在运行的过程中，如果出现另一个优先数比它高的进程，它就要立即停止，并将处理机分配给新的高优先数进程。本次模拟采用抢占式最高优先数调度算法。如果调用此函数时是

22、process_simulation(process,fcfs_creatready);则此时是先来先服务算法模拟调度。如果调用此函数时是 process_simulation(process,hrrn_creatready);则此时是最高优先数优先算法模拟调度。代码：void process_simulation(plist * process,plist *creatready(plist *,plist *)int time; /模拟CPU时钟 plist *temp; plist *ready_queue=NULL; /定义就绪队列，并初始化time = 0; /初始化CPU时序whi

23、le(process|ready_queue) /当进程队列不为空，或者就绪队列不为空while(process & time = process-arrivetime) /进程到达时进入就绪队列temp = process;process = process-next;ready_queue=creatready(ready_queue, temp);if(ready_queue = NULL) /如果没有进程运行，打印CPU空转信息printf(The time sequence is :%dn,time);printf(The ready queue is :n);printf(ther

24、e is no process nown);printf(-n);time+;Sleep(500);else/如果有进程需要运行，则模拟进程运行过程printf(The time sequence is :%dn,time);printf(The ready queue is :n); show(ready_queue-next);/打印就绪队列action(ready_queue); /模拟进程运行if(ready_queue -needtime = 0) /进程运行结束，此时将此进程从就绪队列中删除ready_queue=ready_queue-next;time+;Sleep(1000)

25、;printf(The time sequence is :%dn,time); /先来先服务模拟调度结束printf(there is no process nown);printf(-n);流程图：plist *ready_queue=NULL; time = 0; process|ready_queue process & time = process-arrivetime) temp = process;process = process-next;ready_queue=creatready(ready_queue, temp); ready_queue = NULL 真 假 pri

26、ntf(The time sequence is :%dn,time); printf(The time sequence is :%dn,time); printf(The ready queue is :n); printf(The ready queue is :n); printf(there is no process nown); show(ready_queue-next); printf(-n); action(ready_queue); time+; ready_queue -needtime = 0 Sleep(500); 真 假 ready_queue=ready_que

27、ue-next; time+; Sleep(1000); printf(The time sequence is :%dn,time);printf(there is no process nown); printf(-n);2.8主函数算法思想：先建立所有需要模拟调度的PCB链表，然后采用冒泡法将链表按进程到达时间递增的顺序排序，然后采用switch-case 选择结构进行菜单选择需要模拟的调度模拟。代码：void main()int n; /*the number of process*/int k; plist *process; printf(please input the numb

28、er of process: ); scanf(%d,&n); process = creatpro(n);process = sort(process);/* 利用冒泡法将进程按到达时间排序 */ show(process); printf(please choose the what you want to use:n); printf(t1 先来先服务nt2 最高优先数优先n); scanf(%d,&k); switch(k) case 1: process_simulation(process,fcfs_creatready); /* 先来先服务 */ break;case 2: pr

29、ocess_simulation(process,hrrn_creatready); /* 最高优先数算法 */break;default : printf(请输入正确选项！n);break; 3 程序运行平台Windows xp Microsoft Visual C+ 6.04 总体设计 开始先来先服务算法模拟调度最高优先数优先算法模拟调度退出 系统总体框架图5程序结构体的说明typedef struct pcbint name; /进程名int needtime; /进程所需运行时间int arrivetime; /进程到达时间int pri; /进程优先数 int state; /进程状

30、态：0表示未到达 1表示就绪 2表示运行 3表示等待 4表示结束int cputime; /已用CPU时间struct pcb *next;plist; 6 程序运行结果先来先服务模拟调度运行结果：最高优先数优先调度模拟运行结果：7 结论这次课程设计的题目是模拟进程调度，课程设计的任务书要求实现模拟作业调度的两个算法：先来先服务调度算法，最高优先数优先算法。这次的课程设计我采用的是C语言来编写的，首先编写一个结构体用来存放进程的相关信息，即PCB。然后将要模拟调度的进程PCB放在队列中。通过不断的调试与优化，程序很好的模拟了进程的调度过程，先来先服务，最高优先数优先。在编写实现最高优先数优先算

31、法的时候，刚开始由于没有考虑到后到达的进程的优先数，和当前运行的进程的优先数有高低之分，导致调度得不到预想的结果，经过改正之后就得到了正确的结果。他们的调度结果都不一样，但是对于进程调度而言，这几个算法各有个的优点和缺点。先来先服务算法有利于长进程而不利于短进程；最高优先数优先算法既照顾了长进程，又考虑了进程的优先级，不会使长进程长期得不到服务，该算法实现了比较好的折中。通过本次课程设计加深了我对进程调度算法的理解并且还明白了调度的过程。在上操作系统课的时候对这几个算法并不是很理解，通过实现了这几个调度算法的模拟之后我，我就明白了这几个算法的本质，并且理解了这几个算法。在做课程设计的时候自己还

32、是存在不足之处，在考虑算法的时候考虑的不够周全，在编写最高优先数优先的时候刚开始由于没有考虑到后到达的进程与之前的进程的优先数不一样造成调度的结果与预想的不一样，通过仔细的检查与思考之后发现了这个问题并且改正了之后就可以得到正确的结果了。这次课程设计还让我明白了只有多实践才能发现自己的问题所在才能够很好的掌握知识。8 参考文献1 张尧学等编著. 计算机操作系统教程.北京：清华大学出版社，2006.022 汤子瀛等编著.计算机操作系统.西安：西安电子科技出版社，1996.123 陈向群 编著.操作系统教程.北京：北京大学出版社，2007.014 罗宇 等编著.操作系统课程设计.北京：机械工业出版

33、社，2005.9附 录程序源代码：#include#include#include#includetypedef struct pcbint name; /进程名int needtime; /进程所需运行时间int arrivetime; /进程到达时间int pri; /进程优先数int state; /进程状态：0表示未到达 1表示就绪 2表示运行 3表示等待 4表示结束int cputime; /已用CPU时间struct pcb *next;plist;plist *creatpro(int n) /建立所有将要进行N个模拟调度的进程int j;plist *p, *q, *head;

34、p= (plist *) malloc(sizeof(plist);head = p; for(j=0;jname = j+1; p-needtime = 1+(int)(10.0*rand()/(RAND_MAX+1.0);p-arrivetime = (int)(10.0*rand()/(RAND_MAX+1.0);p-pri = 1+(int)(9.0*rand()/(RAND_MAX+1.0);p-state = 0;p-cputime =0;p-next = (plist *) malloc(sizeof(plist);p=p-next; q-next = NULL;return h

35、ead;void action(plist * nowpro)/模拟CUP运行进程的过程nowpro-state = 2; /设置进程状态为运行态printf(now is process %d ,nowpro-name);nowpro-needtime-; /修改进程还需运行时间nowpro-cputime+; /修改进程已运行时间nowpro-state = 1;if(nowpro-needtime=0)/进程运行结束printf(tthe process %d is endn,nowpro-name); nowpro-state = 4; /进程运行结束，设置进程状态为结束态elsepr

36、intf(tprocess %d needtime is %dn,nowpro-name,nowpro-needtime);printf(-n);void show(plist * process) /显示if(!process)printf(there is no process nown);while(process&process-state!=4)printf(name of process %d,process-name);printf(tneedtime %d,process-needtime);printf( arrivetime %d,process-arrivetime);p

37、rintf( pri %d,process-pri);printf( state %d,process-state);printf( cputime %dn,process-cputime);process = process-next;plist *sort(plist *head) /将进程队列按到达先后顺序排序plist *p,*p1,*p2,*p3,*temp;p=head;while(p-next!=NULL) p=p-next;while(p!=head)p3=p1=head;p2=p1-next;while(p1!=p & p1-next!=NULL)if(p1-arrivetime)(p2-arrivetime)if(p1=head)head=p2;