《进程调度算法的模拟实现—毕业设计论文》由会员分享，可在线阅读，更多相关《进程调度算法的模拟实现—毕业设计论文（21页珍藏版）》请在金锄头文库上搜索。
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 全局变量的使用为了实现各个进程调度算法，本系统使用了五个全局变量。因各种调度算法都是从就绪队列中选择进程进行调度，故将就绪队列设计为LinkQueue类型的全局变量，其变量名为readyQueue。为实现时间片轮转算法，本系统使用了三个指向结构体的指针：reaLQ、runLQ、finLQ，reaLQ表示当前时间尚未开始运行的就绪队列，runLQ表示已开始运行但未结束的各个进程组成的队列，finLQ则记录当前已经执行完
