进程调度算法的模拟实现—毕业设计论文

1、 本科毕业论文（设计）题 目 进程调度算法的模拟实现 院 系 计算机科学与技术 专 业 计算机科学与技术 姓 名 学 号 指导教师 职称 讲师 申请学位 理学学士学位 2015年 5 月 5 日进程调度算法的模拟实现学生姓名： 指导教师： 摘 要：为了提高自己的综合编程能力，也为了能进一步熟练掌操作系统中进程调度算法的详细实现过程，该论文采用c语言中的链队列表示各进程，研究了进程调度算：先来先服务、非抢占式短进程优先、非抢占式高优先权优先以及时间片轮转算法的模拟实现,同时还研究了用c编写的系统，如何使界面更友好、更健壮。该模拟系统实现了预定的所有功能，结果正确、清晰，但对时间片轮转调度算法的模

2、拟实现中，其时间片固定为一，不能对比不同时间片的执行效果，有待改进。通过本模拟系统的实现，使作者对c语言的系统函数使用有了新的认识，对软件的测试过程及方法知识的应用有了更好的掌握，使作者的综合编程能力大大提高。关键字：进程调度；先来先服务；短进程优先；进程控制块；模拟实现the simulation implementation of process scheduling algorithmauthors name: he wen-long tutor: deng xi-huiabstract：in order to improve their own comprehensive progra

3、mming ability, but also in order to further skilled palm operating system process scheduling algorithm in the implementation process in detail, the paper adopts the c chain in the queue of each process, process scheduling is studied in this paper is: first come, first service and non preemptive shor

4、t process, high non preemptive priority priority priority and time slice rotation algorithm simulation, and also studies the system written in c, how to make the interface more friendly and more robust. achieved due to all the features of the simulation system, the results correct and clear, but the

5、 time slice rotation scheduling algorithm simulation implementation, its time slice is fixed for a, cant compare different time slices of implementation effect, needs to be improved. through the implementation of the simulation system, the author of the c language system function using a new underst

6、anding, the application of software testing process and method of knowledge have a better grasp and make the authors comprehensive programming ability is greatly increased.keywords：process scheduling；first come first serve；short process first；process control block；analog implementation目 录1 引言12 进程调度

7、及算法相关知识简介12.1 先来先服务算法12.2 短进程优先算法22.3 高优先权优先算法22.4 时间片轮转算法23 数据结构设计23.1 进程控制块pcb33.2 进程队列linkqueue33.3 全局变量的使用44 系统总体模块设计45主要界面的设计与实现55.1菜单设计55.2菜单的实现65.3 系统模拟动态效果的实现76 主要功能函数的实现86.1 创建进程createproc()函数的实现86.2显示已创建进程信息showproc()函数的实现86.3先来先服务算法fcfs()的实现96.4短进程优先算法与高优先权优先算法的实现96.5时间片轮转算法rr()的实现117 系统运

8、行结果128 结束语13致谢14参考文献151 引言操作系统是计算机的核心总控软件，是计算机系统的指挥和管理中心，是计算机系统的灵魂。在现代的计算机通信系统中，软件开发工作占了相当大的比重，而与通信系统有关的软件一般十分庞大，也相当复杂。这些软件还要大量地与操作系统内核作深层次的交互，以进行信息的传输、控制和实现各种通信协议。而进程管理是操作系统中的非常重要的部分，掌握进程管理部分的原理是为了更加深入的学好操作系统这门课程。本文讨论了进程最重要数据结构进程控制块的表示，进程不同状态队列的存储，在链队列的数据结构上实现先来先服务、短进程优先、高优先权优先和时间片轮转等四种进程调度算法的实现。同时

9、研究了用c编写系统，如何使系统界面友好健壮。2 进程调度及算法相关知识简介在操作系统中，进程调度也称为低级调度，其调度对象是进程。用户进程数一般都多于处理机数，系统进程也同样需要使用处理机，这将导致它们互相争夺处理机。这就要求进程调度程序按一定的策略，动态地把处理机分配给处于就绪队列中的某一个进程，以使之执行，这些策略就是进程调度算法1。常用的进程调度算法有先来先服务、短进程优先、高优先权优先和时间片轮转等。2.1 先来先服务算法先来先服务（fcfs）调度算法是一种最简单的调度算法，该算法既可以用于作业调度，也可用于进程调度。当在作业调度中采用该算法时，每次调度都是从后备作业队列中选择一个或多

10、个最先进入该队列的作业，将他们调入内存，为它们分配资源、创建进程，然后放入就绪队列。在进程调度中采用fcfs算法时，则每次调度是从就绪队列中选择一个最先进入该队列的进程，为之分配处理机，使之投入运行。该进程一直运行到完成或发生某事件而阻塞后才放弃处理机。22.2 短进程优先算法短进程优先（spf）调度算法，是从就绪队列中选出一个估计运行时间最短的进程，将处理机分配给它，使它立即执行并一直执行到完成，或发生某事件而被阻塞放弃处理机再重新调度。spf调度算法能有效地降低进程的平均等待时间，提高系统吞吐量。该算法对长进程不利，完全没考虑进程的紧迫程度。32.3 高优先权优先算法在批处理系统中，短进程

11、优先算法是一种比较好的算法，其主要不足之处是长进程的运行得不到保证。如果我们能为每个进程引入动态优先权，并使进程的优先级随着等待时间的增加而以速率提高，则长进程在等待一定的时间后，必然有机会分配到处理机。该动态优先权的变化规律可描述为：优先权=（等待时间+要求服务时间）/要求服务时间 ，即：优先权=响应时间/要求服务时间。2.4 时间片轮转算法时间片轮转算法中，系统将所有的就绪进程按先来先服务的原则排成一个队列，每次调度时，把cpu分配给队首进程，并令其执行一个时间片。当执行的时间片用完时，由一个计数器发出时钟中断请求，调度程序便据此信号来停止该进程的执行，并将它送往就绪队列的末尾；然后，再把

12、处理机分配给就绪队列中新的队首进程，同时也让它执行一个时间片。这样就可以保证就绪队列中的所有进程在一给定的时间内均能获得一时间片的处理机执行时间。换言之，系统能在给定的时间内响应所有用户的请求。本模似实现系统为了评价算法的优劣，主要以周转时间和带权周转时间为准则的。进程的周转时间是进程到达就绪队列，到进程完成为止的这段时间。进程的周转时间与系统为它服务的时间之比，则称为进程的带权周转时间。3 数据结构设计当我们使用计算机来解决一个具体问题时，一般需要经过下列几个步骤：首先要从该具体问题抽象出一个适当的数学模型，然后设计或选择一个解此数学模型的算法，最后编出程序进行调试、测试，直至得到最终的解答

13、，这个数学模型就是数据结构。3.1 进程控制块pcb为了描述和控制进程的运行，与进程相关的一个很重要的数据结构是进程控制块pcb（process control block），它是进程存在的唯一标志，是操作系统中最重要的数据结构。本系统为了模拟实现对并发执行进程的调度，为pcb设计的数据结构是一个结构体pcbnode，其类型定义是：typedef struct pcbnodecharnamename_max_len;/进程名intid;/进程号floatarrivetime;/进程到达的时间floatruntime;/进程需要执行的时间floatfinaltime;/该进程结束时间shorts

14、tatus;/进程状态struct pcbnode* next;/指向下一进程的指针pcbnode,*pcbpoint;3.2 进程队列linkqueue在操作系统中进程有多种状态，因为本系统主要模拟进程调度，是从就绪队列中选择一个进程，使其得到cpu运行，所以没涉及到阻塞状态。为记录不同状态的进程，该系统将不同状态的进程组织为链队列。进程队列的链队列结构为：typedef struct pcbpoint front; /队首指针pcbpoint rear; /队尾指针linkqueue;3.3 全局变量的使用为了实现各个进程调度算法，本系统使用了五个全局变量。因各种调度算法都是从就绪队列中选

15、择进程进行调度，故将就绪队列设计为linkqueue类型的全局变量，其变量名为readyqueue。为实现时间片轮转算法，本系统使用了三个指向结构体的指针：realq、runlq、finlq，realq表示当前时间尚未开始运行的就绪队列，runlq表示已开始运行但未结束的各个进程组成的队列，finlq则记录当前已经执行完的进程。各个进程调度算法，都涉及到时间，故将时间设为全局变量current，以秒为单位输入，其类型为float。在本系统中，current在先来先服务、短进程优先和高优先权优先算法中表示当前时间，而在时间片轮转算法中，current表示时间片。4 系统总体模块设计 系统总体可分

16、为四个大的模块，即创建进程、输出进程、进程调度算法以及显示系统信息，而进程调度算法又可分为先来先服务、短进程优先、高优先权优先和时间片轮转四个模块。其总体模块如图4-1所示。图4-1 系统总体模块图为实现系统以上各个模块，本模拟系统将功能相对完整的代码定义为一个函数。本系统中主要的函数及其功能如表4-1所示。表4-1 系统主要函数及其功能函数名功能说明showmainmenu()显示系统主菜单showsubmenu()显示进程调度子菜单createproc()创建一个不带有头结点的按到达时间有序的链队列showproc(lq)输出进程信息fcfs(lq)先来先服务算法spf_fpf(lq,fl

17、ag)短进程优先或高优先权算法，具体由flag确定rr(lq)时间片轮转调度算法copyqueue(lq1,lq2)复制进程队列refrashcon(phead,current,con)统计进程队列中到达时间大于current的进程数readyproc()将current之前到来的就绪进程全部插入执行队列slicerun()对满足执行条件的各个进程分配时间片并执行getlev(const pcbpoint &pcb)求进程的动态优先权5主要界面的设计与实现5.1菜单设计本模拟系统主要有两个菜单，一个主菜单，列出了系统具有的五项功能，可以输入相应字符进行选择操作，其界面如图5-1所示。图 5-1

18、 主菜单在主菜单是输入字符c就进入了选择调度算法子菜单，其界面如图5-2所示。图 5-2 选择调度算法子菜单在主菜单输入字符d就进入了系统信息子菜单，显示本系统的功能信息，其界面设计如图5-3所示。图 5-3 选系统信息子菜单5.2菜单的实现主菜单界面的实现方法主要是调用c语言中的系统函数system()，其参数不同实现不同功能。system(cls)实现清屏，system(color 1a)设置默认控制台前景和背景颜色，system(title 进程管理模拟器 version1.0) 设置界面的标题和版本信息。其它就是对菜单项的格式输出。showmainmenu()函数的实现代码如下所示。v

19、oid showmainmenu() /显示主菜单system(cls);coutendl;cout n;cout 进 程 管 理 器 n;cout n;coutn;cout - 欢迎使用该系统,请选择菜单！-n;coutendl;couta 创建进程nn;coutb 浏览进程信息nn;coutc 选择调度算法nn;coutd 系统信息nn;coute 退出程序n;coutn;cout 请您键入菜单字母代码：;子菜单的实现是利用showsubmenu()函数，其实现方法类似主菜单的实现。在此不再赘述。5.3 系统模拟动态效果的实现在创建进程，输入要创建的进程信息后，系统会有一个延时，以显示动态

20、效果。其实现方法主要调用c语言系统函数sleep()函数,其实现关键代码如下：sleep(200); /使程序暂停200秒printf(n 系统正在创建进程中，请稍候.n);sleep(500);printf(=r);/使光标回到本行行首printf( );for(i=0;i);6 主要功能函数的实现本系统中主要的功能函数有创建进程，显示已创建进程的信息，先来先服务调度算法，短作业优先调度算法，高优先权优先算法，时间片轮转算法。6.1 创建进程createproc()函数的实现因为各个调度算法都与进程到达的时间有关，所以本系统创建的进程是不带头结点的且按到达时间有序的链队列。在创建进程时，首先

21、设定创建的进程数目，然后分别输入进程的名称、到达时间、服务时间。创建进程的主要代码是：for(int i=1;i=no;i+) /no是输入的进程数pcbnode *temp=new pcbnode;cout 第 itemp-name;couttemp-arrivetime;couttemp-runtime;coutstatus=r;temp-next=null;/将新创建的temp结点插入就绪队列qp1使其依据arrivetime有序insert(qp1,temp); 6.2显示已创建进程信息showproc()函数的实现该函数是把已创建好的进程信息显示出来，其实现方法主要是使用c语言中的s

22、etw()函数来控制输出格式，然后通过一个指针，指针初始指向进程队列队首，不断移动指针直到队列尾，在移动过程中以指定位置格式输出各个指针的name、arrivetime以及runtime值即可。6.3先来先服务算法fcfs()的实现因就绪队列按到达时间有序排列，所以，先来先服务算法只需创建好的进程顺序输出即可模拟进程的执行，为使用户能直观看到算法执行效果，需求每个进程的周转时间和带权周转时间，运行结果同样由setw()函数控制格式输出，其主要代码如下：while(p1!=null)/遍历队列全部调度,并计算打印各个参数 float t1,t2,t3; float t4; t1=p1-arriv

23、etime; t2=p1-runtime; /t2 运行时间 current+=t2; t3=current-t1; /t3 周转时间 t4=float(t3)/t2; /t4 带权周转时间 coutsetw(6)namesetw(10)t1 setw(10)t2setw(10)currentsetw(10)t3setw(10)t4next;6.4短进程优先算法与高优先权优先算法spf_fpf(slq,flag)的实现进程调度的调度方式有抢占式和非抢占式，本模拟系统采用的是非抢占方式。在采用这种调度方式时，一旦把处理机分配给某个进程后，就让它一直运行下去，直到进程完成，自愿释放处理机或发生某事

24、件而被阻塞时，才把处理机分配给其它进程。短进程优先调度算法的每次调度是从就绪队列中选择服务时间最短的执行，而高优先权优先调度算法则是从就绪队列中选择优先权最高的执行，只是选择标准不同而其它过程类似，所以本模拟系统将二者定义为一个函数spf_fpf(linkqueue slq,int flag)，具体算法由第二个参数flag确定。高优先权优先调度，其优先权有两种：静态优先权和动态优先权。本系统采用调度性能较好的动态优先权。其动态变化规律是等待时间与要求服务时间的和除以服务时间。spf_fpf(linkqueue slq,int flag)函数中，根据flag的值决定具体算法，flag值为1是短进

25、程优先调度，flag值为2是高优先权优先算法。其关键代码如下：current=0.0; /系统时间清零 float t1,t2,t3,t4;while(phead-next!=null) /统计进程队列中到达时间大于current的进程数conint con=0;refrashcon(phead,current,con); /coutcon=connext; t1=pfront-arrivetime;t2=pfront-runtime;current+=t2;t3=current-t1;t4=t3/t2;coutsetw(6)namesetw(10)t1setw(10)t2setw(10)cu

26、rrentsetw(10)t3setw(10)t4next ; t1=pfront-arrivetime;t2=pfront-runtime;current+=t2;t3=current-t1;t4=float(t3)/t2;coutsetw(6)namesetw(10)t1setw(10)t2setw(10)currentsetw(10)t3setw(10)t4runtime;/p2初始指向就绪队列队首for(int i=0;iruntimeruntime; target=p1; p1=p2; p2=p2-next;else if(flag=2) /高优先权 float level=0; f

27、loat temp=getlev(p2); /求各个进程的动态优先权 for(int i=0;inext ;i+) /查找优先权最高的进程if(temp-level0) target=p1; p1=p2; p2=p2-next; level=temp; temp=getlev(p2); 6.5时间片轮转算法rr()的实现由于做毕业设计的时间限制和个人编程能力不足等原因，本模拟系统实现的是时间片为1的进程轮转调度算法。其实现思想是：首先对初始创建好的进程队列readyqueue复制得一全局变量链表realq，以便实现轮转，而不影整个模拟系统中的其它算法。然后动态地将满足某一时刻的所有进程移入另一

28、个全局变量链表runlq，此链表中记录了所有进入轮转执行的进程，本过程由函数readyproc()完成。再对runlq中的各个进程分配时间片并执行，执行结束的进程移入全局变量链表finlq，记录每个进程的完成时间，并将其登记在初始队列readyqueue中，以便最后计算并显示每个进程的周转时间和带权周转时间。7 系统运行结果假设有5个进程，它们的到达、服务时间如表7-1所示：表 7-1 进程的到达及服务时间进程名到达时间服务时间a04b13c25d32e44以表7-1为输入数据，各调度算法的运行结果分别如图7-1-图7-4所示。图7-1 先来先服务测试结果图7-2 短进程优先测试结果图7-3 最高优先权测试结果图7-4 时间片轮转测试结果8 结束