操作系统课程设计进程调度模拟.doc

计算机科学与工程学院计算机科学与工程学院 综合设计报告 设计名称：设计名称：操作系统软件综合设计操作系统软件综合设计 设计题目：设计题目：进程调度算法模拟进程调度算法模拟 学生学号：学生学号： 专业班级：专业班级： 学生姓名：学生姓名： 学生成绩：学生成绩： 指导教师（职称）：指导教师（职称）： 课题工作时间：课题工作时间： 2013-6-17 至至 2013-6-28 说明： 1、报告中的第一、二、三项由指导教师在综合设计开始前填写并发给每 个学生；四、五两项（中英文摘要）由学生在完成综合设计后填写。 2、学生成绩由指导教师根据学生的设计情况给出各项分值及总评成绩。 3、指导教师评语一栏由指导教师就学生在整个设计期间的平时表现、设 计完成情况、报告的质量及答辩情况，给出客观、全面的评价。 4、所有学生必须参加综合设计的答辩环节，凡不参加答辩者，其成绩一 律按不及格处理。答辩小组成员应由 2 人及以上教师组成。 5、报告正文字数一般应不少于 5000 字，也可由指导教师根据本门综合设 计的情况另行规定。 6、平时表现成绩低于 6 分的学生，取消答辩资格，其本项综合设计成绩 按不及格处理。 7、此表格式为武汉工程大学计算机科学与工程学院提供的基本格式（适 用于学院各类综合设计） ，各教研室可根据本门综合设计的特点及内容 做适当的调整，并上报学院批准。 成绩评定表 学生姓名： 学号： 班级： 类别 合计 分值 各项 分值 评分标准 实际 得分 合计 得分 备注 平时 表现 1010 按时参加综合设计，无旷课、迟到、 早退、违反实验室纪律等情况。 20 按设计任务书的要求完成了全部任 务，能完整演示其设计内容，符合 要求。 完成 情况 30 10 能对其设计内容进行详细、完整的 介绍，并能就指导教师提出的问题 进行正确的回答。 10 报告文字通顺，内容翔实，论述充 分、完整，立论正确，结构严谨合 理；报告字数符合相关要求，工整 规范，整齐划一。 5 课题背景介绍清楚， 综述分析充 分。 5 设计方案合理、可行，论证严谨， 逻辑性强，具有说服力。 5 符号统一；图表完备、符合规范要 求。 5 能对整个设计过程进行全面的总结， 得出有价值的结论或结果。 报告 质量 35 5 参考文献数量在 3 篇以上，格式符 合要求，在正文中正确引用。 10 在规定时间内能就所设计的内容进 行阐述，言简意明，重点突出，论 点正确，条理清晰。 答辩 情况 25 15 在规定时间内能准确、完整、流利 地回答教师所提出的问题。 总评成绩： 分 补充说明： 指导教师： （签字） 日 期： 2013 年 6 月 28 日 答辩记录表 学生姓名： 学号： 班级： 答辩地点： 答辩内容记录： 合计 分值 各项 分值 评分标准 实际 得分 合计 得分 备注 10 在规定时间内能就所设计的内容 进行阐述，言简意明，重点突出， 论点正确，条理清晰。 答 辩 成 绩 25 15 在规定时间内能准确、完整、流 利地回答教师所提出的问题。 答辩小组成员（签字）： 2013 年 6 月 28 日 指导教师评语 指导教师： （签字） 日 期： 2013 年 6 月 27 日 一、综合设计目的、条件、任务和内容要求： 目的 设计程序来模拟进程调度的四种调度算法。通过进程调度程序的设计，熟悉和了 解进程控制块、进程队列、调度算法等概念，从而加深和理解处理机管理的核心内容， 加深对操作系统原理课程的理解，巩固已经学过的基础课及专业课知识，开阔学生的 视野，锻炼学生的自学能力及独立动手能力等。 条件 计算机，Visual C+或者 JDK 开发平台（MyEclipse） 任务 1 .用语言来实现对 n 个进程采用不同调度算法的调度进程 2. 每个用来标识进程的进程控制块 PCB 用结构来描述，包括以下字段： （1）进程优先数 ID，其中 0 为闲逛进程，用户进程的标识数为 1，2，3。 （2）进程优先级 Priority，闲逛进程（idle）的优先级为 0，用户进程的优先级 大于 0，且随机产生，优先数越大，优先级越高。 （3）进程占用的 CPU 时间 CPUtime，进程每运行一次，累计值等于 4。 （4）进程总共需要运行时间 Alltime，利用随机函数产生。 （5）进程状态，0：就绪态；1：运行态；2：阻塞态。 3. 优先数改变的原则 （1）进程在就绪队列中每呆一个时间片，优先数增加 1。 （2）进程每运行一个时间片，优先数减 3。 4.。内容要求 （1）提示用户选择想要模拟的进程调度算法，并输入待执行的进程的数目 n。 （2）由系统自动创建 n+1 个进程控制块（第一个作为头结点暂且不用） ，为 每一个进程控制块进行初始化设置，并且链接成一个链表，作为一个就绪队列。 （3）按照用户的要求选择一个进程调度算法来执行。 （4）输出进程调度算法执行后的结果。 （5）提示用户进行下一轮的进程调度算法模拟。 指导教师签字： 2013 年 6 月 15 日 二、进度安排： 1.发题：2013 .6 .15 2.17 周完成基本设计。 3.18 周完成程序调试。 4.18 周完成说明书的书写,其中说明书的内容包括： 第一章、概述 第二章、进程调度设计思想和方法 第三章、进程调度程序和结果 第四章、结束语 第五章、参考文献 5. 18 周周四答辩。 三、应收集资料及主要参考文献： 1. 严蔚敏;吴伟民. 数据结构(C 语言版) M. 北京：清华大学出版社. 2007 年 4 月. 2. 严蔚敏;吴伟民. 数据结构教程学习指导M. 北京：清华大学出版社. 2005 年 4 月. 3. 叶核亚. 数据结构（Java 版） （第 2 版）M. 北京：电子工业出版社. 2008 年 7 月. 4. 汤子瀛. 计算机操作系统（修订版）M. 西安：西安电子科技大学出版社.2001 年 8 月. 5. 谭耀铬. 操作系统（2007 版）M. 北京：中国人民大学出版社.2007 年 7 月. 6. 张永常. Java 程序设计实用教程M. 北京：电子工业出版社. 2006 年 8 月. 7. 谭浩强. C 程序设计（第二版）M. 北京：清华大学出版社. 1999 年 12 月. 四、综合设计（课程设计）摘要（中文）： 在 OS 中调度的实质是一种资源分配，因而调度算法是指：根据系统的资 源分配策略所规定的资源分配算法。进程调度常用的算法有：先来先服务调 度、优先级调度、时间片轮转调度和多级反馈队列调度。本次课程设计将就 模拟先来先服务、时间片轮转、短作业优先、优先级和多级反馈队列五种调 度算法进行设计并对他们的性能进行比较，程序提供了创建进程，选择进程 调度算法的基本功能。 首先应该设计数据结构，创建进程结构体，然后认真设计每一个进程调度 的算法，并运用程序加以实现，算法设计完毕后调试整体程序并测试，比较 在不同环境下各种进程调度的优劣。 目前存在的多种调度算法中，有的短发适用于作业调度，有的算法适用于 进程调度；但也有些调度算法既可用于作业调度，也可用于进程调度。 关键词：进程；进程调度；数据结构；算法 五、综合设计（课程设计）Abstract（英文）： The OS scheduling is a kind of resource allocation in essence , and scheduling algorithm is a resource allocation algorithm based on the system of resource allocation algorithm principles. Process scheduling algorithms commonly used are: a first-come first-served scheduling, priority scheduling, round-robin scheduling and multi-lever feedback queue scheduling algorithms, and comparing their performance. Program provides the creation process, choosing the basic function of process scheduling algorithms. First, the data structure should be designed to create a structure. Then, scheduling algorithms should be designed carefully for each process, and use the program to achieve those process. Algorithms scheduling is completed after the whole program debugging, debugging is completed after the testing procedures, and comparing the different operating environments in the process of scheduling in pros and cons. There are many kinds of scheduling algorithms. Some is suitable for job scheduling, and some is for process scheduling. But there are some scheduling algorithms which are both suitable for job scheduling and process scheduling. Keywords：Process; Process Scheduling; Data Structure; Algorithm 武汉工程大学计算机科学与工程学院 综合设计报告 - I - 目录 摘要II ABSTRACTIII 第一章 课题背景.1 1.1 课题背景 1 1.2 进程调度简介 1 1.3 课题目的 3 1.4 课题意义 3 第二章 设计简介及设计方案论述.4 2.1 步骤简介 4 2.2 设计要点 4 2.3 具体方案 4 第三章 详细设计.7 3.1 设计数据结构 7 3.2 模拟进程调度 7 3.3 算法流程图 7 3.4 主要函数定义 12 第四章 设计结果及分析.13 4.1 创建进程 13 4.2 选择进程调度 13 4.3 先来先服务调度.13 4.4 时间片轮转调度 14 4.5 优先级调度.14 4.6 多级反馈队列调度 15 4.7 性能分析 15 总结.17 致谢.18 参考文献.19 附录.20 武汉工程大学计算机科学与工程学院 综合设计报告 - II - 摘要 在 OS 中调度的实质是一种资源分配，因而调度算法是指：根据系统的资源分配 策略所规定的资源分配算法。进程调度常用的算法有：先来先服务调度、优先级调 度、时间片轮转调度和多级反馈队列调度。本次课程设计将就模拟先来先服务、时 间片轮转、短作业优先、优先级和多级反馈队列五种调度算法进行设计并对他们的 性能进行比较，程序提供了创建进程，选择进程调度算法的基本功能。 首先应该设计数据结构，创建进程结构体，然后认真设计每一个进程调度的算 法，并运用程序加以实现，算法设计完毕后调试整体程序并测试，比较在不同环境 下各种进程调度的优劣。 目前存在的多种调度算法中，有的短发适用于作业调度，有的算法适用于进程调度； 但也有些调度算法既可用于作业调度，也可用于进程调度。 关键词：进程；进程调度；数据结构；算法 武汉工程大学计算机科学与工程学院 综合设计报告 - III - Abstract The OS scheduling is a kind of resource allocation in essence , and scheduling algorithm is a resource allocation algorithm based on the system of resource allocation algorithm principles. Process scheduling algorithms commonly used are: a first-come first- served scheduling, priority scheduling, round-robin scheduling and multi-lever feedback queue scheduling algorithms, and comparing their performance. Program provides the creation process, choosing the basic function of process scheduling algorithms. First, the data structure should be designed to create a structure. Then, scheduling algorithms should be designed carefully for each process, and use the program to achieve those process. Algorithms scheduling is completed after the whole program debugging, debugging is completed after the testing procedures, and comparing the different operating environments in the process of scheduling in pros and cons. There are many kinds of scheduling algorithms. Some is suitable for job scheduling, and some is for process scheduling. But there are some scheduling algorithms which are both suitable for job scheduling and process scheduling. Keywords：Process; process scheduling; data structure; algorithm 武汉工程大学计算机科学与工程学院 综合设计报告 - 1 - 第一章 课题背景 1.1 课题背景 在多道程序环境下，主存中有着多个进程，其数目往往多于处理机数目，要使这多 个进程能够并发地执行、这就要求系统能按某种算法，动态的把处理机分配给就绪队 列中的一个进程，使之执行。分配处理机的任务是由处理机调度程序完成的。由于处 理机时最重要的计算机资源，提高处理机的利用率几改善系统（吞吐量、响应时间） 在很大程度上取决于处理机调度性能的好坏，因而，处理机调度便成为操作系统设计 的中心问题之一1。 1.2 进程调度简介 进程调度的对象时进程（或内核级线程） ，它是一种基本的调度，在单批道处理、 分时和实现三种类型的 OS 中，都必须配置这级调度2。 1.2.1 进程调度的功能 (1)记录系统中所有进程的执行情况 作为进程调度的准备，进程管理模块必须将系统中各进程的执行情况和状态特 征记录在各进程的 PCB 表中。并且，根据各进程的状态特征和资源需求等、进程管 理模块还将各进程的 PCB 表排成相应的队列并进行动态队列转接。进程调度模块通 过 PCB 变化来掌握系统中存在的所有进程的执行情况和状态特征，并在适当的时机 从就绪队列中选择出一个进程占据处理机。 (2)选择占有处理机的进程 进程调度的主要功能是按照一定的策略选择个处于就绪状态的进程，使其获 得处理机执行。根据不同的系统设计目的，有各种各样的选择策略，例如系统开销 较少的静态优先数调度法，适合于分时系统的轮转法(Round RoLin)和多级互馈轮 转法(RoundRobin with Multip1e feedback)等。这些选择策略决定了调度算法的 性能。 (3)进行进程上下文切换 个进程的上下文(context)包括进程的状态、有关变量和数据结构的值、机 器寄存器的值和 PCB 以及有关程序、数据等。一个进程的执行是在进程的上下文中 执行。当正在执行的进程由于某种原因要让出处理机时，系统要做进程上下文切换， 以使另一个进程得以执行。当进行上下文切换时点统要首先检查是否允许做上下文 切换(在有些情况下，上下文切换是不允许的，例如系统正在执行某个不允许中断 武汉工程大学计算机科学与工程学院 综合设计报告 - 2 - 的原语时)。然后，系统要保留有关被切换进程的足够信息，以便以后切换回该进 程时，顺利恢复该进程的执行。在系统保留了 CPU 现场之后，调度程序选择一个新 的处于就绪状态的进程、并装配该进程的上下文，使 CPU 的控制权掌握在被选中进 程手中3。 1.2.2 引起进程调度的原因 (1)正在执行的进程执行完毕或因发生某事件而不能再继续执行； (2)执行中的进程因提出 I/O 请求而暂停执行； (3)在进程通信或同步过程中执行了某种原语操作如 P 操作、阻塞、挂起原语等； (4)在可剥夺式调度中，有比当前进程优先权更高的进程进入就绪队列； (5)在时间片轮转法中，时间片完4； 1.2.3 进程调度方式 进程调度有非抢占方式和抢占方式两种： 非抢占方式：一旦将处理机分配给某进程后，不管它要运行多长时间，都要一直让 他运行下去，绝不会因为时钟中断等原因而抢占正在运行的处理机，也不允许其他进 程抢占已经分配给他的处理机。直到该进程完成，自愿释放处理机。 抢占方式：这种调度方式允许调度程序根据某种原则去暂停某个正在执行的进程， 将已经分配给该进程的处理机重新分配给另一个进程。但抢占调度方式基于以下原则： 优先权原则、段作业进程优先原则、时间片原则5。 1.2.4 进程调度的功能 进程调度的具体功能可总结为如下几点： (1)记录系统中所有进程的执行情况 (2)作为进程调度的准备，进程管理模块必须将系统中各进程的执行情况和状态特征记 录在各进程的 PCB 表中。并且，根据各进程的状态特征和资源需求等、进程管理 模块还将各进程的 PCB 表排成相应的队列并进行动态队列转接。进程调度模块通 过 PCB 变化来掌握系统中存在的所有进程的执行情况和状态特征，并在适当的时 机从就绪队列中选择出一个进程占据处理机。 (3)选择占有处理机的进程 (4)进程调度的主要功能是按照一定的策略选择个处于就绪状态的进程，使其获得处 理机执行。根据不同的系统设计目的，有各种各样的选择策略，例如系统开销较 少的静态优先数调度法，适合于分时系统的轮转法(Round RoLin)和多级互馈轮转 武汉工程大学计算机科学与工程学院 综合设计报告 - 3 - 法(Round Robin with Multip1e feedback)等。这些选择策略决定了调度算法的性 能。 (3)进行进程上下文切换 个进程的上下文(context)包括进程的状态、有关变量和数据结构的值、机器寄存器 的值和 PCB 以及有关程序、数据等。一个进程的执行是在进程的上下文中执行。当 正在执行的进程由于某种原因要让出处理机时，系统要做进程上下文切换，以使另 一个进程得以执行。当进行上下文切换时点统要首先检查是否允许做上下文切换(在 有些情况下，上下文切换是不允许的，例如系统正在执行某个不允许中断的原语时) 。然后，系统要保留有关被切换进程的足够信息，以便以后切换回该进程时，顺利 恢复该进程的执行。在系统保留了 CPU 现场之后，调度程序选择一个新的处于就绪 状态的进程、并装配该进程的上下文，使 CPU 的控制权掌握在被选中进程手中6。 1.3 课题目的 通过课程设计, 加深对操作系统各资源管理模块的理解,掌握操作系统的基本原理及 功能, 具有初步分析实际操作系统、设计、构造和开发现代操作系统的基本能力。 1.4 课题意义 本次课程设计主要是进一步了解操作系统中的进程调度，能够熟练运用 C+编程 实现进程调度的基本功能。为之后的学习和实习打下了一定的基础。通过进程调度程 序的设计，熟悉和了解进程控制快、进程队列、调度算法等概念，从而加深和理解处 理机管理的核心内容，加深对操作系统原理课程的理解，巩固已经学过的基础课及专 业课知识，开阔学生的视野，锻炼学生的自学能力及独立动手能力等。 武汉工程大学计算机科学与工程学院 综合设计报告 - 4 - 第二章 设计简介及设计方案论述 2.1 步骤简介 （1）提示用户选择想要模拟的进程调度算法，并输入待执行的进程的数目 n。 （2）由系统自动创建 n+1 个进程控制块（第一个作为头结点暂且不用） ，为每一个进 程控制块进行初始化设置，并且链接成一个链表，作为一个就绪队列。 （3）按照用户的要求选择一个进程调度算法来执行。 （4）输出进程调度算法执行后的结果。 （5）提示用户进行下一轮的进程调度算法模拟。 2.2 设计要点 1 .用语言来实现对 n 个进程采用不同调度算法的调度进程 2. 每个用来标识进程的进程控制块 PCB 用结构来描述，包括以下字段： （1）进程优先数 ID，其中 0 为闲逛进程，用户进程的标识数为 1，2，3。 （2）进程优先级 Priority，闲逛进程（idle）的优先级为 0，用户进程的优先级大于 0，且随机产生，优先数越大，优先级越高。 （3）进程占用的 CPU 时间 CPUtime，进程每运行一次，累计值等于 4。 （4）进程总共需要运行时间 Alltime，利用随机函数产生。 （5）进程状态，0：就绪态；1：运行态；2：阻塞态。 3. 优先数改变的原则 （1）进程在就绪队列中每待一个时间片，优先数增加 1。 （2）进程每运行一个时间片，优先数减 37。 2.3 具体方案 2.3.1 设计数据结构 设计一种数据结构 Process，提供关于进程的一些有效信息：进程名，运行总时间， 武汉工程大学计算机科学与工程学院 综合设计报告 - 5 - 剩余时间，优先级。 typedef struct QNode string ProcessName：进程名 int Priority：进程优先级 int AllTime;/进程运行需要时间 int LeftTime：完成进程还需的时间 ) Node, ,kProcess： 2.4.2 调度算法及设计原理 1先来先服务调度算法： 先按照进入 CPU 的时间将所有进程一次存入队列（先进入 CPU 的存在靠近 队首位置） ，然后每次将队首位置的进程调入内存，为他分配资源，投入运行， 直到该进程完全运行完毕，再接着调入队首进程，直到队列为空。 2时间片轮转调度算法： 所有就绪进程按先来先服务的原则排成一个队列，将新来的进程加到就绪 对列的末尾，每当执行进程调度时，总是把处理机分配给队首的进程，各进程 占用 CPU 的时间片相同。也就是说 CPU 的处理时间划分成一个个相同的时间片， 就绪队列的所有进程轮流运行一个时间片。当一个时间片结束时，如果运行进 程用完它的时间片后还未完成，就强迫运行进程让出 CPU，就把它送回到就绪队 列的末尾，等待下一次调度。同时，进程调度又去选择就绪队列中的队首进程， 分配给它一时间片，以投入运行。直至所有的进程运行完毕。 3优先级调度算法： 进程调度每次是把 CPU 分配给就绪队列中优先数最高的进程。可以先将所 有就绪进程按照优先级由大到小的顺序排列，依次存入队列，然后每次优先运 行队首进程，直到队列为空。 4短作业优先调度算法： 先将所有就绪队列按照剩余时间由小到大的顺序排列，并依次存入队列， 再按照先来先服务方法执行下去。 5多级反馈队列调度算法： 允许进程在队列之间移动。在系统中设置多个就绪队列，每个队列对应一个 优先级，第一个队列的优先级最高，第二队列次之。以下各队列的优先级逐步降 低。各就绪队列中的进程的运行时间片不同，高优先级队列的时间片小，低优先 级队列的时间片大。进程并非总是固定在某一队列中，新进程进入系统后，被存 放在第一个队列的末尾。如果某个进程在规定的时间片内没有完成工作，则把它 转入到下一个队列的末尾，直至进入最后一个队列。系统先运行第一个队列中的 进程。当第一队列为空时，才运行第二个队列中的进程。依此类推，仅当前面所 有的队列都为空时，才运行最后一个队列中的进程。当处理器正在第 i 个队列中 武汉工程大学计算机科学与工程学院 综合设计报告 - 6 - 为某个进程服务时，又有新进程进入优先级最高的队列(第 1- (i-l)中的任何一个对 列） ，则此新进程要抢占正在运行进程的处理器，即由调度程序把正在运行的进程 放回第 i 队列的末尾，把处理器分配给新到的高优先级进程。除最低优先权队列 外的所有其他队列，均采用相同的进程调度算法，即按时间片轮转的 FIFO（先进 先出）算法。最后一个队列中的进程按按时间轮转或 FCFS 策略进行调度。它是 综合了 FIFO、RR 和剥夺式 HPF 的一种进程调度算法8。 武汉工程大学计算机科学与工程学院 综合设计报告 - 7 - 第三章 详细设计 3.1 设计数据结构 定义指针型结构体 tProcess(代替进程控制块 PCB) typedef struct QNode string ProcessName;/进程名 int Priority;/进程优先级 int AIITime;/进程运行需要时间 int LeftTime;/完成进程还需的时间 )Node，*Process; String 型的进程名，int 型的优先级、总时间和剩余时间。 3.2 模拟进程调度 基本功能： （1） 创建进程：输入进程的有效信息； （2） 进程调度：能够自由选择进程调度方式； （3） 输出状态：能够输出每一步所有进程的状态9； 3.3 算法流程图 3.3.1 先来先服务调度 根据设计的算法画先来先服务进程调度流程图如图 3.1 所示： 武汉工程大学计算机科学与工程学院 综合设计报告 - 8 - 图 3.1 先来先服务流程图 武汉工程大学计算机科学与工程学院 综合设计报告 - 9 - 3.3.2 优先级调度 根据设计的算法优先级调度进程调度流程图如图 3.2 所示： 图 3.2 优先级调度流程图 武汉工程大学计算机科学与工程学院 综合设计报告 - 10 - 3.3.3 时间片轮转调度 根据设计的算法画时间片轮转流程图如图 3.3 所示： 图 3.3 时间片轮转进程调度流程图 武汉工程大学计算机科学与工程学院 综合设计报告 - 11 - 3.3.4 多级反馈队列调度 根据设计的算法画多级反馈队列流程图如图 3.3 所示： Cpu 调度进程 进程 i 新进程插入？ 插入队列尾 进程 i 移队尾 CPU 调新进程 继续执行进程 i 时间片用完？ 进程 i 完成？ 是否是 3 号队列 插入队尾 将进程 i 插入下一级 队列尾 Y N Y N 撤离系统 Y N Y N 图 3.4 多级反馈队列调度流程图 武汉工程大学计算机科学与工程学院 综合设计报告 - 12 - 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, int num, int Timepice);/优先级算法 void QueueProcess(Process process, int num, int Timepice, Process a1,Process a2,Process a3);/多级反馈队列调度 武汉工程大学计算机科学与工程学院 综合设计报告 - 13 - 第四章 设计结果及分析 4.1 创建进程 用户创建进程的界面如图 4.1 所示： 图 4.1 创建进程 4.2 选择进程调度 用户选择进程调度算法界面如图 4.2 所示： 图 4.2 选择进程调度算法 4.3 先来先服务调度 先来先服务调度算法运行情况如图 4.3，图 4.4，图 4.5 所示： 图 4.3 所有进程都在队列中 图 4.4 其中一个执行完毕 武汉工程大学计算机科学与工程学院 综合设计报告 - 14 - 图 4.5 所有的进程都执行完毕 4.4 时间片轮转调度 时间片轮转调度算法运行情况如图 4.6，图 4.7 所示： 图 4.6 其中一个进程执行完毕 图 4.7 所有进程都执行完毕 4.5 优先级调度 优先级调度算法运行情况如图 4.8，图 4.9，图 4.10 所示： 图 4.8 所有的进程都在队列中 图 4.9 其中一个进程执行完毕 武汉工程大学计算机科学与工程学院 综合设计报告 - 15 - 图 4.10 所有的进程都执行完毕 4.6 多级反馈队列调度 多级反馈队列调度算法运行情况如图 4.11 至 4.13 所示： 图 4.11 当前执行第一队列 图 4.12 第二队列执行完，当前执行第三队列 图 4.13 所有进程都已经执行完毕 4.7 性能分析 进程调度虽然是在系统内部的低级调度，但进程调度的优劣直接影响作业调度的 性能。反映作业调度优劣的周转时间和平均周转时间只在某种程度上反映了进程调度 武汉工程大学计算机科学与工程学院 综合设计报告 - 16 - 的性能，例如，其执行时间部分中实际上包含有进程等待(包括就绪状态时的等待)时 间，而进程等待时间的多少是要依靠进程调度策略和等待事件何时发生等来决定的。 因此，进程调度性能的商量是操作系统设计的一个重要指标。我们说进程调度性能的 衡量方法可分为定形和定量两种。在定形衡量方面，首先是调度的可靠住。包括一次 进程调度是否可能引起数据结构的破坏等。这要求我们对调度时机的选择和保存 CPU 现场十分谨慎。另外，简洁性也是衡量进程调度的一个重要指标，由于调度程序的执 行涉及到多个进程和必须进行上下文切换，如果调度程序过于繁琐和复杂，将会耗去 较大的系统开销。这在用户进程调用系统调用较多的情况下，将会造成响应时间大幅 度增加。进程调度的定量评价包括 CPU 的利用率评价、进程在就绪队列中的等待时间 与执行时间之比等。实际上由于进程进入就绪队列的随机模型很难确定，而且进程上 下文切换等也将影响进程的执行效率，LL 而对进程调度进行解析是很困难的。一般情 况下，大多利用模拟或测试系统响应时间的方法来评价进程调度的性能10。 分析测试结果知：FCFS 算法比较有利于长作业（进程） ，而不利于短作业（进程） ； 短作业优先调度算法对长作业不利，可能导致长作业长时间不被调度；优先及调度算 法 则保证了紧迫进程，而那些优先级较低的则可能长时间得不到调度；时间片轮转算法 则 算是对每个进程都是公平的，减少了进程的等待时间；综合考虑，多级反馈队列调度 算 法则是综合 FCFS，短作业优先，时间片轮转和优先级调度算法的优点，故多级反馈队 列 调度对大多数进程调度来说是一种最佳的调度算法，但具体算法则应根据实际需求选 择。 武汉工程大学计算机科学与工程学院 综合设计报告 - 17 - 总结 经过本次课程设计让我感受很深的是对 C+语言的运用，由于对 C+语言在平时 运用的不够，在对 c+语言的使用尤其是在编写方面很欠缺，在组织语言时出错不断。 在设计过程中，需要大量的相关资料，为了本次课程设计我在网上和图书馆查阅了大 量资料，不断的发现问题、提出问题、解决问题，在变成和调试的过程中，进程会出 现意想不到的问题，并非每个问题都可以从相关资料中找到解决方法，有些问题是无 法预料的，这就需要通过自己理性的分析得出问题的解决方案。 我对操作系统中的进程和进程调度有了更进一步的认识和了解，能够熟练掌握常 用的进程调度算法。能够正确运用操作系统中所学的基本理论和知识，加深了对进程 调度基本概念的理解，认识到多级反馈队列调度一般来说是最佳的算法，但也有例外， 我们应该根据实际需求确定最佳的进程调度算法。 本次课程设计大量运用到了数据结构中的知识，数据结构中的一些算法我也能灵 活 运用在操作系统的设计。回顾本次课程设计，我运用了多个学科的知识，这给了我一 些 启发，在今后的学习中我们要多多将各科的知识融会贯通，综合运用。 虽然本次课程设计我已经完成了，但我还觉得不足，这也是我知识所限，我要更 加努力。 武汉工程大学计算机科学与工程学院 综合设计报告 - 18 - 致谢 本次课程设计我能够顺利完成要感谢好多人：操作系统的胡宏银老师在课堂上详 细 给我们介绍了进程调度的算法，这是完成本次实验的基础。也要感谢数据结构的姚峰 老 师，他教授了我大量关于数据结构的知识，对本次课程设计也很重要。感谢老师在这 两周的时间里一直不厌其烦的回答我们同学们的疑惑，为我们讲解疑难之处，找出我 们的错误并教我们改正，最后我还要感谢我的同学朋友们，他们在我遇到问题时耐心 的帮我解决，为我讲解，提出我没有想到的问题，没有这些人，我恐怕不可能完成这 一课程设计，在此表示感谢。 武汉工程大学计算机科学与工程学院 综合设计报告 - 19 - 参考文献 1汤小丹，梁红兵，等计算机操作系统（第三版）M.西安：西安电子科技大学 出版社，2007 年 2严蔚敏，吴伟明数据结构（C 语言版）M北京：清华大学出版社，2007 年 3陈锐，零基础学数据结构M北京：机械工业出版社，2010 年 4张尧学，计算机操作系统教程（第 2 版）习题与实验指导M北京： 清华大学 出版社，2009 年 5严蔚敏;吴伟民. 数据结构教程学习指导M. 北京：清华大学出版社. 2005 年 4 月. 6叶核亚. 数据结构（第 2 版）M. 北京：电子工业出版社. 2008 年 7 月. 7汤子瀛. 计算机操作系统（修订版）M. 西安：西安电子科技大学出版社.2001 年 8 月. 8谭耀铬. 操作系统（2007 版）M. 北京：中国人民大学出版社.2007 年 7 月. 9张永常. Java 程序设计实用教程M. 北京：电子工业出版社. 2006 年 8 月. 10谭浩强. C 程序设计（第二版）M. 北京：清华大学出版社. 1999 年 12 月. 武汉工程大学计算机科学与工程学院 综合设计报告 - 20 - 附录 主要程序代码： #include #include #define SIZE 100 #define OVERFLOW NULL using namespace std; typedef struct QNode string ProcessName;/进程名 int Priority;/进程优先级 int AllTime;/进程运行需要时间 int LeftTime;/完成进程还需的时间 Node, *Process; /函数声明 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, int num, int Timepice); /优先级算法 void QueueProcess(Process process, int num, int Timepice, Process a1, Process a2,Process a3);/多级反馈队列 /主函数 void main() int a; Process *process=new Process SIZE; Process *a1= new Process SIZE;/用数组模拟队列的功能 Process *a2= new Process SIZE; Process *a3= new Process SIZE; for(int i=0;inum; for (int j=0;jname; cinCpuTimeLeval; processj-ProcessName=name; processj-AllTime=CpuTime; processj-Priority=Leval; for (int k=0;kLeftTime=processk-AllTime;/对进程剩余时间初始化 couta; int TimePice;/时间片大小 coutTimePice; system(“pause“); system(“cls“); if(a=1) FCFS(process,num,TimePice); 武汉工程大学计算机科学与工程学院 综合设计报告 - 22 - else if(a=2) TimeTurn(process,num,TimePice); else if(a=3) Sort(process,num); PriorityProcess(process,num,TimePice); else if(a=4)/最短作业算法，先按时间从小到大排序，再调用 FCFS 算法即可 sort1 (process,num); FCFS(process,num,TimePice); else if(a=5) QueueProcess(process,num,TimePice,a1,a2,a3); /按优先级从大到小排列 void Sort ( Process process, int size) /直接插入排序 for(int i=1;i0 j-; processj=temp; /直接插入排序后进程按优先级从小到大排列 for(int d=size-1;dsize/2;d-) 武汉工程大学计算机科学与工程学院 综合设计报告 - 23 - Process temp; temp=processd; processd=processsize-d-1; processsize-d-1=temp; /以进程时间从低到高排序 void sort1(Process process,int size) /直接插入排序 for(int i=1;i0 j-; proces