王会歌
【摘 要】CPU调度在操作系统中占据着非常重要的位置，是多道程序系统实现的核心技术，是进程状态转换可实现的先决条件。但是目前CPU调度问题的课程设计还存在诸多问题，例如课程内容过于理论，远远偏离了实际应用。本文我们利用理论结合实际浅谈本科生《操作系统》课程中CPU调度课程设计的教学环节。
【关键词】操作系统；CPU调度；进程
中图分类号： TP316 文献标识码： A 文章编号： 2095-2457（2017）23-0069-002
【Abstract】CPU scheduling occupies a very important position in the operating system and is the core technology of multiprocessor system implementation.It is a precondition for the process state transition to be realized.However，there are still many problems in the curriculum design of CPU scheduling.For example，the content of the course is too theoretical and deviates far from the practical application.In this paper，we use theory and practice to discuss the teaching process of CPU scheduling course design in undergraduate "operating system" course.
【Key words】Operating system；CPU scheduling；Process
CPU调度是多道程序操作系统的设计基础。通过在进程之间切换CPU，操作系统可以提高单位时间内CPU处理进程的数量。本文我们将根据理论结合实践的教学方法浅谈CPU调度中的课程设计环节。在课程讲授过程中，我们不建议一开始直接讲授教学内容，建议在讲解核心问题之前首先巧妙地引导，具体方法和内容如下：首先通过CUP-I/O执行周期讲述为什么要进行CPU调度。我们知道进程的执行过程是由CPU执行周期与I/O等待周期组成的，是两者交替的过程。在交替过程中会出现进程由于发生I/O操作或者异常而引起进程主动或者被迫放弃CPU，从而出现CPU调度问题。为了使学生更加深入的理解这个环节，我们将结合下图，从短CPU执行时间的出现频率较高，长CPU执行时间出现频率较低，以及输入/输出型程序会产生很多短CPU执行时间，计算型程序可能会产生少量的长CPU执行时间这个环节进一步说明产生CPU調度的原因。
为了帮助学生更好的理解CPU调度，我们首先向学生讲解CPU调度程序这个重要的概念。具体的说，CPU调度程序指的是，当CPU空闲时，由CPU调度程序从就绪队列中选择一个进程并将CPU分配给它，使这个进程运行。然后通过下面的实现代码并结合上机过程进一步详细讲解。
接下来，我们将进入到CPU调度讲解的具体环节，其课程设计安排如下。首先通过下图回顾进程状态之间的转换原理，然后介绍CPU调度的两种类型，即抢占式调度和非抢占式调度。通过进程状态转换区分可抢占式调度和非可抢占式调度。具体内容如下：
非抢占式调度指的是一旦将CPU分配给某一个进程，该进程将会一直占有CPU直到进入到终止状态（指情况4）或切换到等待状态（指情况1）时自动释放CPU的使用权限。从上面分析易知，当出现情况1、4时，会发生非抢占式调度，在这种情况下进程是主动放弃CPU的。
抢占式调度指的是优先级高的进程可以抢占占有CPU的优先级较低的进程。当出现情况2、3时，会发生抢占式调度。另外，为了保持代码执行的原子性，进而实现进程的同步，可以对进程设计关中断和开中断来实现，即当执行到不允许被中断的代码段时，进入这段代码时需要关中断，执行完这段代码后再开中断。
接下来，我们介绍分派程序。分派程序指的是将CPU使用权交给调度程序所选择的进程。特别要强调的是，分派程序和调度程序是两个不同的概念，从分派程序的含义我们能够清楚的理解这一点：在CPU调度中，分派程序主要负责分配CPU，而调度程序则根据某种特定的算法从内存空间中选择将要分配CPU的进程。为了更深刻的理解这一问题，我们通过下面的代码进行演示。
最后，进入到CPU调度算法环节的讲解。在学习该内容之前我们先理解CPU调度所遵循的几条准则。具体地说，CPU一般按照如下准则进行调度。1）CPU使用率：反映CPU计算机系统中使用的百分率。2）吞吐量：一个单位时间内系统完成的进程数量。3）周转时间：从进程提交到进程完成的时间间隔，包括等待进入内存时间。4）在就绪队列中的等待时间、在CPU上的执行时间以及执行I/O时间的和。5）等待时间：指的是进程在就绪队列中的等待时间。6）响应时间：从提交请求到产生第一响应的时间。一般情况下，等待时间是CPU最常用的调度准则。在理解了这些概念之后，进一步讲解CPU常用的调度算法。具体地说，CPU调度算法主要有以下几种：先来先服务、最短作业有限调度算法、优先权调度算法，轮转法调度，多级队列调度和多级反馈队列调度算法。其中最短作业优先和多级反馈队列调度算法是教学的难点。我们分别采用算法和图示的方法对这两个难点进行分析。首先，因为在最短作业优先调度算法中，主要困难在于不知道如何确定下一个CPU 区间的长度。
另外，对于多级反馈队列调度算法，我们采用的方法是，首先讲解该算法的基本实现思想：1）将就绪队列分解成多个队列，并为每个队列赋不同的优先级。第一个队列，优先级最高。2）为每个队列中的进程设置不同的时间片大小，优先级越高，其时间片越小。3）当一个新进程进入内存后，首先将它放入第一个就绪队列的未尾，按先来先服务的原则进行排列并等待调度。当轮到该进程执行时，如果它能在该时间片内完成，便可准备撤离系统，如果它在一个时间片不能完成，则将它转入第二个队列的未尾，继续等待调度。4）仅当第一个队列为空时，调度程序才调度第二个队列中的进程运行。为更好的帮助学生理解该实现思想，我们将结合下图进行讲解。
【参考文献】
[1]Abraham Silberschatz，Peter Baer Galvin和Greg Gagne著，郑扣根译.操作系统概念第七版.高等教育出版社，2017年1月.
[2]刘珂男，童薇，冯丹，刘景宁，张炬.一种灵活高效的虚拟CPU调度算法，软件学报，2017年2月.
[3]周思林，谢从华.基于FLS的多级队列CPU调度系统仿真研究.计算机仿真，2015年7月.endprint
