操作系统课程设计模拟进程调度功能的设计与实现.doc

《操作系统课程设计模拟进程调度功能的设计与实现.doc》由会员分享，可在线阅读，更多相关《操作系统课程设计模拟进程调度功能的设计与实现.doc（47页珍藏版）》请在三一办公上搜索。

1、武汉工程大学 计算机科学与工程学院综合设计报告设计名称： 操作系统综合设计 设计题目： 模拟进程调度功能的设计与实现 学生学号： 专业班级： 学生姓名： 学生成绩： 指导教师（职称）： 课题工作时间：2011年6月8日 至 2011年6月29日 说明：1、报告中的第一、二、三项由指导教师在综合设计开始前填写并发给每个学生；四、五两项（中英文摘要）由学生在完成综合设计后填写。2、学生成绩由指导教师根据学生的设计情况给出各项分值及总评成绩。3、指导教师评语一栏由指导教师就学生在整个设计期间的平时表现、设计完成情况、报告的质量及答辩情况，给出客观、全面的评价。4、所有学生必须参加综合设计的答辩环节，

2、凡不参加答辩者，其成绩一律按不及格处理。答辩小组成员应由2人及以上教师组成。5、报告正文字数一般应不少于5000字，也可由指导教师根据本门综合设计的情况另行规定。6、平时表现成绩低于6分的学生，其综合设计成绩按不及格处理。7、此表格式为武汉工程大学计算机科学与工程学院提供的基本格式（适用于学院各类综合设计），各教研室可根据本门综合设计的特点及内容做适当的调整，并上报学院批准。成绩评定表学生姓名： 学号： 班级： 类别合计分值各项分值评分标准实际得分合计得分备注平时表现1010按时参加综合设计，无旷课、迟到、早退、违反实验室纪律等情况。完成情况3020按设计任务书的要求完成了全部任务，能完整演示

3、其设计内容，符合要求。10能对其设计内容进行详细、完整的介绍，并能就指导教师提出的问题进行正确的回答。报告质量3510报告文字通顺，内容翔实，论述充分、完整，立论正确，结构严谨合理；报告字数符合相关要求，工整规范，整齐划一。5课题背景介绍清楚，综述分析充分。5设计方案合理、可行，论证严谨，逻辑性强，具有说服力。5符号统一；图表完备、符合规范要求。5能对整个设计过程进行全面的总结，得出有价值的结论或结果。5参考文献数量在3篇以上，格式符合要求，在正文中正确引用。答辩情况2510在规定时间内能就所设计的内容进行阐述，言简意明，重点突出，论点正确，条理清晰。15在规定时间内能准确、完整、流利地回答教

4、师所提出的问题。总评成绩： 分 补充说明： 指导教师： （签字）日 期： 年 月 日答辩记录表学生姓名： 学号： 班级： 答辩地点： 答辩内容记录：答辩成绩合计分值各项分值评分标准实际得分合计得分备注2510在规定时间内能就所设计的内容进行阐述，言简意明，重点突出，论点正确，条理清晰。15在规定时间内能准确、完整、流利地回答教师所提出的问题。答辩小组成员（签字）： 年 月 日指导教师评语指导教师： （签字）日 期： 2011 年 月 日一、综合设计目的、条件、任务和内容要求：课题目的：用java（或C+）编程实现操作模拟操作系统进程调度子系统的基本功能；实现先来先服务、时间片轮转、多级反馈轮转

5、法对进程进行的调度过程。课题条件：一台装有Windows95,Windows NT 4.0或更高的操作系统和某种高级语言开发环境（例如Java或VC+）的PC机，具体细节如下：1 JDK1.52 Eclipse3.3课题任务：一、 确定开发的项目名称，并熟悉相关知识，确定开发工具并实现开发环境的安装配置二、 实现用户界面的开发三、 实现进程调度子系统如下功能模块：1、进程概念：进程是被独立分配资源的最小单位。进程是动态概念，必须程序运行才有进程的产生。2、 进程的状态模型： （1）运行：进程已获得处理机，当前处于运行状态。（2）就绪：进程已经准备好，一旦有处理器就可运行。3、处理机调度：在多道

6、程序设计系统中，内存中有多道程序运行，他们相互争夺处理机这一重要的资源。处理机调度就是从就绪队列中，按照一定的算法选择一个进程并将处理机分配给它运行，以实现进程并发地执行。4、 进程调度算法的功能记录系统中所有进程的执行情况选择占有处理机的进程进行进程的上下文切换5、进程调度的算法：（1）先来先服务算法（2）优先数算法：即进程的执行顺序由高优先级到低优先级。系统或用户按某种原则为进程指定一个优先级来表示该进程所享有的确调度优先权。该算法核心是确定进程的优先级。（3）时间片轮转算法：固定时间片，每个进程在执行一个时间片后，轮到下一进程执行，知道所有的进程执行完毕。处理器同一个时间只能处理一个任务

7、。处理器在处理多任务的时候，就要看请求的时间顺序，如果时间一致，就要进行预测。挑到一个任务后，需要若干步骤才能做完，这些步骤中有些需要处理器参与，有些不需要（如磁盘控制器的存储过程）。不需要处理器处理的时候，这部分时间就要分配给其他的进程。原来的进程就要处于等待的时间段上。经过周密分配时间，宏观上就象是多个任务一起运行一样，但微观上是有先后的，就是时间片轮换。 (4) 多级反馈轮转法四、 调试并撰写报告 指导教师签字： 2011 年 6 月 29 日二、进度安排：12周周五13周周三，进行学生选题；1920周，师现场指导学生，完成设计任务和设计报告；20周五，综合设计答辩。三、应收集资料及主要

8、参考文献：著作：1 张尧学,史美林.计算机操作系统教程第2版.清华大学出版社2000年著作：2 张尧学.计算机操作系统教程第2版 习题与实验指导.2000年四、综合设计（课程设计）摘要（中文）：无论是在批处理系统还是分时系统中，用户进程数一般都多于处理机数、这将导致它们互相争夺处理机。另外，系统进程也同样需要使用处理机。但是处理机在某一时刻只能执行一个进程，这就引入了进程调度这一机制！进程调度程序按一定的策略，动态地把处理机分配给处于就绪队列中的某一个进程，以使之执行。进程调度的主要功能是按照一定的策略选择个处于就绪状态的进程，使其获得处理机执行。应根据不同的系统设计目的，选择最佳合适的进程调

9、度算法。常用的进程调度算法有：先来先服务调度算法，短作业优先调度算法，优先级调度算法，时间片轮转算法，多级反馈队列调度算法！五、综合设计（课程设计）Abstract（英文）：Whether in a batch system or time-sharing systems, user processes are generally more than the number of processors, which will lead them to compete for processor. In addition, the system processes also need to use

10、 the processor. But the processor can execute only one at a time process, which introduces the process of scheduling this mechanism! Process scheduler according to a certain strategy, dynamically assigned to the processor in a ready queue of a process to make it perform.The main function of process

11、scheduling strategy is based on certain selection - a process in the ready state to receive processor implementation. Depending on the system should be designed to select the best suitable process scheduling algorithm. The process commonly used scheduling algorithms are: a first-come first-served sc

12、heduling, priority scheduling short jobs, priority scheduling, round-robin algorithm, multi-level feedback queue scheduling algorithm!目 录摘 要 .IIAbstract . .第一章 课题概述. .11.1 课题背景.11.2 进程调度简介. .11.2 .1进程调度功能. 11.2 .2进程调度的三个基本机制.11.2 .3进程调度的方式. .11.2.4进程调度的原因. .21.3 课题目的.21.4 课题意义.2第二章设计简介及设计方案论述. .32.1

13、 设计构想.32.2 问题及技术要求.32.3 理论依据.32.4 方案论述.32.4.1 数据结构.32.4.2 算法设计.42.4.3 替换思想.5第三章详细设计. 63.1 数据结构.63.2 功能划分.63.3 算法流程图.63.3.1 先来先服务调度.63.3.2 优先级调度.73.3.3 时间片轮转调度.83.3.4 多级反馈队列调度.93.4 函数功能定义.9第四章设计结果及分析. 114.1 创建进程测.11 4.2 选择进程调度算法测试.11 4.3 先来先服务调度测.114.4 时间片轮转调度测试.124.5 优先级调度测试.134.6 多级反馈队列调度.134.1 测试分

14、析.15总 结 .16致 谢 .17 参考文献 .18 附录 主要程序代码 .19 摘 要本次课程设计主要是更进一步了解进程调度的实质和功能，能够运用面向对象的C+语言模拟进程调度的一些算法，为以后相关的学习和实习打下一定的基础。运用C+编写模拟进程调度算法的程序，加深对进程和进程调度的理解。进程调度常用的算法有：先来先服务调度，优先级调度调度，时间片轮转调度和多级反馈队列调度。本次课程设计就将模拟先来先服务，时间片轮转，短作业优先，优先级和多级反馈队列5中调度算法，并对他们的性能进行比较。程序提供了创建进程，选择进程调度算法的基本功能。首先应该设计数据结构，创建了进城结构体。然后认真设计每一

15、个进程调度的算法，并运用程序加以实现。算法设计完毕后就该调试整体程序，调试完毕后就测试程序，并比较在不同运行环境下各种进程调度的优劣。理论上多级反馈队列调度算法应该是一种比较好的调度算法，在最后的测试中也验证了这一点。关键词：进程； 进程调度； 数据结构； 算法AbstractThe courses are primarily designed to further understand the nature and function of process scheduling, to use object-oriented C + + language the process of sche

16、duling a number of simulation algorithms for future study and practice related to lay a foundation. C + + and simulated using the process scheduling program, to deepen the understanding of processes and process scheduling.Process scheduling algorithms commonly used are: a first-come first-served sch

17、eduling, priority scheduling scheduling, round-robin scheduling and multi-level feedback queue scheduling. The course design will be simulated first-come, first serve, round-robin, short job priority, priority and multi-level feedback queue scheduling algorithm 5, and compare their performance. Prog

18、ram provides the creation process, choose the basic function of process scheduling algorithms.First, the data structure should be designed to create a city structure. Then carefully designed scheduling algorithms for each process, and use the program to be achieved. Algorithm design is completed aft

19、er the whole program debugging, debugging is completed after the testing procedures, and compare the different operating environments in the process of scheduling all the pros and cons.Theoretical multi-level feedback queue scheduling algorithm should be a good scheduling algorithm, in the final tes

20、t also verified this.Keywords: process; process scheduling; data structure; algorithm朗读字典朗读显示对应的拉丁字符的拼音字典朗读显示对应的拉丁字符的拼音字典朗读显示对应的拉丁字符的拼音字典第一章 课题概述1.1 课题背景 在多道程序环境下，主存中有着多个进程，其数目往往多于处理机数目，要使这多个进程能够并发地执行，这就要求系统能按某种算法，动态地把处理机分配给就绪队列中的一个进程，使之执行。分配处理机的任务是由处理机调度程序完成的。由于处理机是最重要的计算机资源，提高处理机的利用率及改善系统必（吞吐量、响应时

21、间），在很大程度上取决于处理机调度性能的好坏，因而，处理机调度便成为操作系统设计的中心问题之一。1.2 进程调度简介 进程调度的对象是进程（或内核级线程），它是一种最基本的调度，在单批道处理、分时和实现三种类型的OS中，都必须配置这级调度。1.2.1 进程调度的功能 进程调度的主要功能如下： (1)保存处理机的现场信息 (2)按照某种算法选取进程 (3)把处理器分配给进程1.2.2 进程调度的三个基本机制 为了实现进程调度，应具有以下三个基本机制： (1)排队器:为了提高进程调度效率，事先将所有就绪进程按照一定的方式排成一个或者多个队列，方便查找。 (2)分派器:把由进程调度程序所选定的进程，

22、从就绪队列中取出来，然后施行上下文切换，将处理机分配给它。 (3)上下文切换机制:对处理机进行切换就能引发上下文切换操作。1.2.3 进程调度方式 进程调度有非抢占方式和抢占方式两种。 非抢占方式：一旦将处理机分配给某进程后，不管它要运行多长时间，都要一直让他运行下去，绝不会因为时钟中断等原因而抢占正在运行的处理机，也不允许其他进程抢占已经分配给他的处理机。直到该进程完成，自愿释放处理机。 抢占方式：这种调度方式允许调度程序根据某种原则去暂停某个正在执行的进程，将已经分配给该进程的处理机重新分配给另一个进程。但抢占调度方式基于以下原则：优先权原则、段作业(进程)优先原则、时间片原则。1.2.4

23、 进程调度原因 引起进程调度的原因有以下几类：(1)正在执行的进程执行完毕。这时，如果不选择新的就绪进程执行，将浪费处理机资源。 (2)执行中进程自己调用阻塞原语将白己阻塞起来进入睡眠等状态。 (3)执行中进程调用了P原语操作，从而因资源不足而被阻塞；或调用了v原语操作激活了等待资源的进程队列。 (4)执行中进程提出I/O请求后被阻塞。 (5)在分时系统中时间片已经用完。 (6)在执行完系统调用等系统程序后返回用户进程时，这时可看作系统进程执行完毕，从而可调度选择一新的用户进程执行。 (7)就绪队列中的某进程的优先级变得高于当前执行进程的优先级，从而也将引发进程调度1.3 课题目的用C+编程实

24、现操作模拟操作系统进程调度子系统的基本功能；实现先来先服务、时间片轮转、多级反馈轮转法对进程进行的调度过程。1.4 课题意义 本次课程设计主要是进一步了解操作系统中的进程调度，能够熟练运用C+编程实现进程调度的基本功能。为之后的学习和实习打下了一定的基础。第二章 设计简介及设计方案论述2.1 设计构想 程序能够完成以下操作：创建进程：先输入进程的数目，再一次输入每个进程的进程名、运行总时间和优先级，先到达的先输入；进程调度：进程创建完成后就选择进程调度算法，并单步执行，每次执行的结果都从屏幕上输出来。2.2 问题及技术要求问题1：进程结构体如何创建，应包含哪些有效信息问题2：各种进程调度算法如

25、何设计问题3：模块的划分，函数功能的定义技术要求：能够熟练掌握C+，数据结构也有基本的底子。操作系统关于进程调度的知识熟练掌握。2.3 理论依据为了描述和管制进程的运行，系统为每个进程定义了一个数据结构进程控制块PCB(Process Control Block),PCB中记录了操作系统所需的、用于描述进程的当前情况以及控制进程运行的全部信息，系统总是通过PCB对进程进行控制，亦即，系统是根据进程的PCB而不是任何别的什么而感知进程的存在的，PCB是进程存在的惟一标志。本次课程设计用结构体Process代替PCB的功能。2.4方案论述2.4.1 数据结构设计一种数据结构Process，提供关于

26、进程的一些有效信息：进程名，运行总时间，剩余时间，优先级。typedef struct QNodestring ProcessName;/进程名int Priority;/进程优先级int AllTime;/进程运行需要时间int LeftTime;/完成进程还需的时间Node, *Process; 2.4.2 算法设计 1.先来先服务调度算法： 先按照进入CPU的时间将所有进程一次存入队列（先进入CPU的存在靠近队首位置），然后每次将队首位置的进程调入内存，为他分配资源，投入运行，直到该进程完全运行完毕，再接着调入队首进程，直到队列为空。 2.时间片轮转调度算法： 所有就绪进程按先来先服务的

27、原则排成一个队列，将新来的进程加到就绪对列的末尾，每当执行进程调度时，总是把处理机分配给队首的进程，各进程占用CPU的时间片相同。也就是说CPU的处理时间划分成一个个相同的时间片，就绪队列的所有进程轮流运行一个时间片。当一个时间片结束时，如果运行进程用完它的时间片后还未完成，就强迫运行进程让出CPU，就把它送回到就绪队列的末尾，等待下一次调度。同时，进程调度又去选择就绪队列中的队首进程，分配给它一时间片，以投入运行。直至所有的进程运行完毕。 3.优先级调度算法： 进程调度每次是把CPU分配给就绪队列中优先数最高的进程。可以先将所有就绪进程按照优先级由大到小的顺序排列，依次存入队列，然后每次优先

28、运行队首进程，直到队列为空。 4.短作业优先调度算法： 先将所有就绪队列按照剩余时间由小到大的顺序排列，并依次存入队列，再按照先来先服务方法执行下去。 5.多级反馈队列调度算法：允许进程在队列之间移动。在系统中设置多个就绪队列，每个队列对应一个优先级，第一个队列的优先级最高，第二队列次之。以下各队列的优先级逐步低。各就绪队列中的进程的运行时间片不同，高优先级队列的时间片小，低优先级队列的时间片大。进程并非总是固定在某一队列中，新进程进入系统后，被存放在第一个队列的末尾。如果某个进程在规定的时间片内没有完成工作，则把它转入到下一个队列的末尾，直至进入最后一个队列。系统先运行第一个队列中的进程。当

29、第一队列为空时，才运行第二个队列中的进程。依此类推，仅当前面所有的队列都为空时，才运行最后一个队列中的进程。当处理器正在第i个队列中为某个进程服务时，又有新进程进入优先级最高的队列（第1（i-1）中的任何一个对列），则此新进程要抢占正在运行进程的处理器，即由调度程序把正在运行的进程放回第i队列的末尾，把处理器分配给新到的高优先级进程。除最低优先权队列外的所有其他队列，均采用相同的进程调度算法，即按时间片轮转的FIFO（先进先出）算法。最后一个队列中的进程按按时间片轮转或FCFS策略进行调度。它是综合了FIFO、RR和剥夺式HPF的一种进程调度算法2.4.3 替换思想 鉴于队列的输出比较麻烦，为

30、了便于随时输出每个就绪进程的有效信息，故在此次课程设计中用数组模拟队列的功能（主要是先进先出的功能），即用数组替换队列。每次都只运行数组中的第一个进程a0. 用指针型结构体*Process代替进程控制块PCB的功能。第三章 详细设计3.1 数据结构 定义指针型结构体*Process（代替进程控制块PCB）typedef struct QNodestring ProcessName;/进程名 int Priority;/进程优先级 int AllTime;/进程运行需要时间 int LeftTime;/完成进程还需的时间Node, *Process;String型的进程名，int型的优先级、总时

31、间和剩余时间。3.2 功能划分 模拟进程调度应该有以下基本功能：创建进程（输入进程的有效信息），进程调度（能够自由选择进程调度方式）和输出状态（能够输出每一步所有进程的状态）。3.3 算法流程图3.3.1先来先服务调度 根据设计的算法画先来先服务进程调度流程图如图3-1所示: 图3-1先来先服务流程图3.3.2 优先级调度根据设计的算法优先级调度进程调度流程图如图3-2所示: 图3-2优先级调度流程图3.3.3 时间片轮转调度根据设计的算法画时间片轮转流程图如图3-3所示 图3-3时间片轮转进程调度流程图3.3.4 多级反馈队列调度根据设计的算法画多级反馈队列流程图如图3-4所示 图3-4多级

32、反馈队列调度流程图3.4 函数功能定义 需要定义以下功能函数： void Sort( Process process, int size); / 按优先级从大到小排列void sort1(Process process, int size); / 按运行时间时间从小到大排列void FCFS( Process process, int num, int Timepice); / 先来先服务算法void TimeTurn(Process process, int num, int Timepice); / 时间片轮转算法void PriorityProcess(Process process,

33、int num, int Timepice); / 优先级算法void QueueProcess(Process process, int num, int Timepice,Process a1,Process a2,Process a3);/多级反馈队列调度第四章 设计结果及分析4.1 创建进程测试 用户创建进程的界面如图4-1所示. 图4-1 创建进程4.2 选择进程调度算法测试 用户选择进程调度算法界面如图4-2所示。 图4-2 选择进程调度算法 4.3 先来先服务调度测试 先来先服务调度算法运行情况如图4-3，图4-4，图4-5所示。 图4-3 所有的进程都在队列中 图4-4 其中一

34、个进程执行完毕 图4-5 所有的进程都执行完毕4.4 时间片轮转调度测试 时间片轮转调度算法运行情况如图4-6，图4-7，图4-8所示 图4-6 所有的进程都在队列中 图4-7 其中一个进程执行完毕 图4-8 所有的进程都执行完毕4.5 优先级调度测试 优先级调度算法运行情况如图4-9，图4-10，图4-11所示。 图4-9 所有的进程都在队列中 图4-10 其中一个进程执行完毕 图4-11 所有的进程都执行完毕4.6 多级反馈队列调度测试 多级反馈队列调度算法运行情况如图4-12到图4-15所示。 图4-12 当前执行第一队列 图4-13 第一队列执行完，当前执行第二队列 图4-14 第二队

35、列执行完，当前执行第三队列 图4-15 所有进程都已经执行完毕4.7 测试分析分析测试结果知：FCFS算法比较有利于长作业（进程），而不利于短作业（进程）；短作业优先调度算法对长作业不利，可能导致长作业长时间不被调度；优先及调度算法则保证了紧迫进程，而那些优先级较低的则可能长时间得不到调度；时间片轮转算法则算是对每个进程都是公平的，减少了进程的等待时间；综合考虑，多级反馈队列调度算法则是综合FCFS，短作业优先，时间片轮转和优先级调度算法的优点，故多级反馈队列调度对大多数进程调度来说是一种最佳的调度算法，但具体算法则应根据实际需求选择。总 结经过本次课程设计，我对操作系统中的进程和进程调度有了

36、更进一步的认识和了解，能够熟练掌握常用的进程调度算法。认识到多级反馈队列调度一般来说是最佳的算法，但也有例外，我们应该根据实际需求确定最佳的进程调度算法。本次课程设计大量运用到了数据结构中的知识，数据结构中的一些算法我也能灵活运用在操作系统的设计。回顾本次课程设计，我运用了多个学科的知识，这给了我一些启发，在今后的学习中我们要多多将各科的知识融会贯通，综合运用。虽然本次课程设计我已经完成了，但我还觉得不足。没能完成进程的阻塞和唤醒这两个功能，这也是我知识所限，我要更加努力。致 谢 本次课程设计我能够顺利完成要感谢好多人：操作系统的胡宏银老师在课堂上详细给我们介绍了进程调度的算法，这是完成本次实验的基础。也要感谢数据结构的姚峰老师，他教授了我大量关于数据结构的知识，对本次课程设计也很重要。最后要感谢刘玮和吕涛老师在课堂上对我的指导，也要感谢一些同学在课下对我的帮助。