在处理机调度教学中引入模拟就绪队列

谢晓东 刘艳

【摘要】处理机调度是操作系统的重要内容。然而当调度算法及调度输入趋向复杂时，学生难以理解相关内容，容易发生错误。本文提出在教学中不仅需要引入时空图来反映CPU的使用，还需要引入模拟就绪队列来描述进程的排队情况，以完整地描述操作系统的调度过程。在教学实践中，该方法发挥了良好的效果，帮助学生理解各种调度算法的具体运行方式。

【关键词】处理机调度教学 模拟调度算法 模拟就绪队列

【中图分类号】G42 【文献标识码】A 【文章编号】2095-3089（2018）19-0225-02

一、引言

处理机调度是操作系统课程中重要的内容。在操作系统发展历史上，由于操作系统应用目标不同，产生了多种大相径庭的调度策略和众多的调度算法。大部分操作系统教材也都会介绍先来先服务、短作业优先、时间片轮转调度、最小松弛度优先等经典的调度算法[1-3]。

模拟调度算法的运行过程，观察算法对CPU的使用情况是理解相关策略和算法的重要一环。然而笔者在教学中发现，当调度情况趋向复杂，例如参与调度进程数目多，调度算法复杂，处理机切换频繁时，学生对一些需要深入理解和仔细辨析的内容产生混淆，理解错误。从教学实践看，先来先服务及短作业优先调度算法比较容易被学生接受和理解，而时间片轮转调度和最小松弛度优先算法的出错概率大增。事实上，部分教材给出的调度示例结果也有错误。

目前大部分教材一般使用时空图来分析调度过程。时空图主要用来描述CPU运行情况，可以观察并计算各进程的周转时间、响应时间等重要参数。然而，时空图只关注CPU的运行情况，忽视了处理机调度中另一重要工作：进程/作业的排队过程。这导致学生在理解调度算法时的困难，对调度过程中的复杂情形不能准确理解。因此在教学过程中引入模拟就绪队列，并给出就绪队列在调度过程中的变化是非常必要的。

二、模拟就绪队列及其应用示例

将各时刻就绪队列中进程按队列顺序写出就是模拟就绪队列。模拟就绪队列可以与时空图合二为一。图1给出了用时空图-模拟就绪队列来描述一个简单的先来先服务调度过程的示例。图中上半部分是时空图，横坐标为时间轴，纵坐标为进程，中间短线代表对应进程占用的CPU时间；图的下半部分是模拟就绪队列，靠近横坐标的进程是就绪队列的头，队列按顺序从上而下书写；当系统发生调度事件时，将在对应时刻的位置重写模拟就绪队列。使用模拟就绪队列可以很好地描述在调度过程中就绪队列的变化情况，结合时空图可以完整地呈现整个调度过程中的细节，从而能更好地理解调度的相关问题。

表1是教材[2]在P102中给出的一个时间片轮转调度的例子，该教材没有用时空图进行演示和说明。请注意表中粗体标识的内容，即时间片为1的完成时间，该结果是错误的。通过该结果可以逆推出如图2的时空图。然而，从图中可以看到，进程C在时刻2刚到达系统时就被分配了CPU，而不是根据FSCS的原则排在就绪队列的后面。事实上，在时刻2之前，进程A已经排在就绪队列的最前面，因而C只能排在A的后面并要等A完成一个时间片之后才会被调度并获得CPU的使用权。类似的错误，凭空思考或仅仅通过时空图是难以发现和理解，需要引入模拟就绪队列以给出清晰的思路。

图3给出了表一例子正确的时空图及对应的模拟就绪队列。从图中可以很清楚地看到，当进程C到达时，就绪队列中已经有进程A了；当进程B的时间片用尽，从CPU中切换出来时，CPU将被分配给进程A而不是C。因此进程C的第一次运行的开始时间不是如图2中的时刻2而是时刻3。事实上，由于时刻2同时发生了进程C到达和进程B被切换两个事件，这两个事件的先后会影响就绪队列的顺序。一般我们约定进程到达事件先于运行进程退出CPU事件发生，因此在时刻2-3之间，就绪队列的顺序是C-B。这个约定细节在很多教材中付之阙如。

由于调度策略的复杂性和调度輸入（进程到达时刻及服务时间）的多变，调度过程推演的错误时有发生，如教材[1]P94中时间片轮转调度算法的例子，以及P102中最早松弛度优先算法的例子。因此在教学中引入模拟就绪队列是十分必要的。

三、结语

处理机调度是操作系统核心功能之一，是操作系统课程教学的重要内容。现有各类操作系统教材中，处理机调度部分重视使用时空图这一工具来描述和解释进程在CPU中的运行和切换过程，而忽视了作为调度策略实现的排队器的模拟。这导致学生难以准确理解调度的过程，事实上也使得部分教材在例子中给出了错误的答案。

本文提出引入模拟就绪队列这一工具，即写出各时刻系统就绪队列中各进程序列，以模拟排队器在处理机调度时的工作状态，从而弥补仅使用时空图带来的缺失。模拟就绪队列的引入可以准确地理解调度过程，避免相关错误，在教学中也取得很好的效果。

参考文献：

[1]汤小丹，梁红兵等编著《计算机操作系统》第四版，西安电子科技大学出版社2014年5月。

[2]曹先彬，陈香兰编著《操作系统原理与设计》机械工业出版社2009年9月。

[3]何炎祥，李飞，李宁编著《计算机操作系统》，清华大学出版社2004年1月。

作者简介：

谢晓东（1976年10月-），男，江西省赣州市人，汉族，现任福建省厦门市华侨大学计算机学院讲师，博士，研究方向：软件工程，数据库。