计算机操作系统式教学

摘 要：在教学实践中“操作系统”的教学不易落到实处,即原理容易讲,但要让学生“体验”这些原理却并不容易.文章通过一个启发式教学设计的实例,阐述对于该问题的一些思考.

关 键 词：启发式教学；实时调度；操作系统；最早截至时间优先；最低松弛度优先

文章编号：1672-5913（2013）03-0062-04

中图分类号：G642

“操作系统”是计算机相关专业的一门核心专业课,而实时调度算法是“操作系统”课程中的一个重要内容,在多数的“操作系统”教科书中主要介绍了两种实时调度算法,即最早截止时间优先算法（EarliestDeadlineFirst,EDF）和最低松弛度优先算法（LeastLaxityFirst,LLF）.这两个算法看上去并不难理解,然而问题往往并不像看起来那样简单.事实上,在操作系统的教学中有一个很大的困难,即操作系统的教学不易落到实处,即原理容易讲,但要让学生“体验”这些原理却并不容易.操作系统课程中涉及大量算法,如进程调度算法、死锁避免算法、页面置换算法等.表面上这些算法看起来比较容易,但要让学生理解算法后面蕴含的深刻道理,并从这些算法中发现一些问题就绝非易事了.

对于这个困难,我们希望通过一些启发式的教学设计,引导学生从程序员、从算法设计者的角度去分析和思考算法中的一些问题,从而将抽象的原理转化为具体的问题和解决方案,加深对这些原理的理解.下面结合实时调度算法的例子来阐述对于启发式教学设计的思考.

1实时调度算法的启发式教学设计

1.1调度算法问题定义

很多“操作系统”教科书中都介绍了两个重要的实时调度算法,一个是EDF,另一个是LLF.这两个实时调度算法的调度准则都很简单,课堂讲授时学生并不难理解.然而,这两个不同的调度算法在应用中的效果如何,教科书中并没有给出进一步的分析和讨论.事实上,这是一个很好的启发式教学的切入点,我们就从这里出发来设计问题.首先来看一看EDF算法和LLF算法的思想.

EDF算法是根据任务的开始截止时间来确定任务的优先级.截止时间愈早,其优先级愈高.该算法要求在系统中保持一个实时任务就绪队列,该队列按各任务截止时间的早晚排序；当然,具有最早截止时间的任务排在队列的最前面.调度程序在选择任务时,总是选择就绪队列中的第一个任务,为之分配处理机,使之投入运行.截止时间可以是开始截止时间,也可以是完成截止时间.一般来说,完成截止时间等于开始截止时间加上任务处理时间.

LLF算法是根据任务紧急（或松弛）的程度,来确定任务的优先级.任务的紧急程度越高,越优先执行.例如,一个任务在200ms时必须完成,而它本身所需的运行时间就有100ms,因此,该任务的紧急程度（松弛程度）为100ms.又如,另一任务在400ms时必须完成,它本身需要运行150ms,则其松弛程度为250ms.调度程序总是选择就绪队列中松弛度最小的任务执行.LLF算法主要采用抢占调度方式.

1.2发现问题

按照教科书的描述和给出的示例,在LLF算法中,当有新任务到达时,并不马上比较当前所有任务的松弛度（包括正在执行的任务）,而是等到某个在等待的任务的松弛度降为零才进行切换,即选择这个松弛度已经降为零的任务运行.按照这个原则,我们在启发式教学设计中提出的第一个问题.

第一个问题：按照教科书给出的LLF算法调度原则,是否会存在不可调度的情况?

经过分析,很容易找出问题,如图1中给出的示例.

通过上面的示例可知,在某些情况下,当某个任务在执行过程中,若某个（或某些）正在等待的任务的松弛度减至0s,则可能会导致任务无法成功调度,而实际上系统能力是允许成功调度的.

1.3提出改进

针对前面提出的问题,可以引导学生对LLF算法的调度准则进行改进.通常比较容易想到的改进是,修正松弛度的计算和任务切换时机,即松弛度不需要随时计算,而在如下两种情况时进行计算：

1）当前任务正在执行时新任务到达,可能会引起抢占和任务切换,此时需要计算并比较松弛度；

2）当前任务完成时可能会引起新的任务调度和切换,此时计算松弛度.

进程在执行时松弛度会不断变化,但是不用进行跟踪计算和比较.

修正后,可以对学生提出第二个问题.

第二个问题：修正后的LLF算法,是否存在着不可调度的情况?

回答依然是存在问题,可以看一看图2中给出的另一个示例.

1.4证明猜想

若发现改进后的LLF算法还是存在问题,这时可以引导学生再作改进,并进行讨论.事实上,无论如何改进LLF的调度和切换时机,都无法解决问题.那么我们可以引导学生逐步转到EDF算法上来,即EDF算法也会存在类似问题吗?因此我们提出的第三个问题如下.

第三个问题：按照完成截至时间调度的EDF算法,是否存在不可调度的情况?

通过启发学生寻找反例会发现无法找到反例,这时学生也许会想到,EDF是一个最优的算法,即可以得出以下的猜想.

猜想：给定一系列的任务,只要这些任务是可调度的,即存在某种序列使得所有任务都在完成截至时间之前完成,则使用EDF算法一定能成功调度这些任务.

有了猜想,如何证明呢?这显然要比设计反例困难得多.我们可以引导学生深入研究这个问题,这逐步进人了这个实验的关键部分,即发现问题,以及问题背后的问题,给出猜想,并分析和证明自己的猜想.

对此,我们也给出了这个猜想的一个证明.

证明：

1）检测设一系列任务是可调度的,并且安排出来的任务调度顺序不等同于EDF算法所安排的序列.

2）那么,此安排顺序中至少有两个任务A、B,其中A的截止时间比B的早,但A安排在B后面（如图3（a）所示）.则只需将B移至A后面一位即可（如图3（b）所示）.3）在之前的序列中A没有超时,则移走B,A更不会超时；而B的新位置的完成时刻等于原来序列时A的完成时刻；而A的截止时刻小于B的截止时刻,所以B肯定不会超时.

4）重复以上过程,可以得到一个符合EDF规则的任务序列.所以EDF一定能找到成功序列.

证明了按完成截止时间调度的EDF算法的最优性之后,还可以启发学生进一步思考,若是按开始截止时间调度的EDF算法,会有什么不同吗?另外,EDF算法和LLF算法之间有什么联系吗?

通过进一步分析和比较可以得到下面的结论.

EDF算法和LLF算法的比较结论：按开始截止时间调度的EDF算法并不能像按完成截止时间调度的EDF算法那样得到最优的结果.事实上,按开始截止时间调度的EDF算法的调度结果和按LLF算法的调度结果是一样的.也就是说,给定一个任务序列,按开始截止时间排序的结果和按松弛度排序的结果是一样的.

证明：因为开始截止时间和松弛度分别满足如下关系.

开始截止时间等于完成截止时间-运行时间①松弛度等于完成截止时间-当前时间-运行时间②

比较式①和式②可得：

松弛度等于开始截止时间-当前时间

注意到对所有任务来说,其“当前时间”都是一样的,因此将任务按开始截止时间排序和按松弛度排序得到的结果是一样的.这同时也就说明了,若按松弛度优先进行调度无法得到最优的结果,那么按开始截止时间调度的EDF算法也无法得到最优结果.

1.5新的问题

通过上面的证明可知,若给出的一系列任务是可调度的,则使用按完成截止时间调度的EDF算法一定可以成功调度这些任务,在这种意义下EDF是一个最优的算法.但是我们还可以再启发学生作进一步的思考.若给出的一系列任务是不可能全部调度成功的,那么EDF还是“最优”的吗?当然,需要重新定义“最优”的标准.这自然就得出下面这个新的问题.

第四个问题：检测设当前存在n个任务,用mi表示（1≤i≤n,下同）,每个任务包含三个参数,一是任务的运行时间ti,第二个是任务的完成截止时间di,第三个是成功安排该任务可以获得的收益ri.请问按EDF进行调度能获得最大收益吗?若不能,请设计一个调度算法使得最终的调度能获得最大收益.

对于这个问题可以引导学生进行讨论.事实上,这个问题要困难得多,运用一些直观、朴素的原则很难得到理想的解决方案.对此,可引导学生进一步运用算法和最优化方法中的一些技巧来分析该问题.下面是运用动态规划来求解该问题的一个方案.

第四个问题的动态规划分析：

1）首先可以考虑的是,我们的目标是在n个任务中选取若干个任务来获得最大收益,若选出了这些任务（即这些被选中的任务是可以安排好的）,则可以按照EDF的规则来安排执行,即把被选出的任务按各自的完成截止时间排序,则这些任务一定都可以在各自的完成截止时间之内完成,这就是前面的猜想证明的结论.所以我们可以考虑将所有的n个任务按完成截止时间排序.检测设按完成截止时间排好序后的n个任务用m1,m2,等,mn表示.

2）其次考虑,在n个任务中选取若干个任务来获得最大收益,与在n-1个任务中选取若干个任务来获得最大收益之间有什么关系?可以看出,按完成截止时间排序后的第n个任务mn若不在最终选定的若干个任务之列,则问题可以转化为在n-1个任务,即m1,m2,等,mn-1中选取最优的任务序列；若任务mn在最终选定的若干个任务之列,则问题可以转化为在截止时间T-tn之前,从m1,m2,等,mn-1.中选取最优的任务序列.若用f（n,dn）表示在截止时间dn前,从n个任务中选取满足条件的最优序列所获得的最大收益,则可以得到如下的递归表达式：

3）依据递归式③可以很容易地写出一个自底向上的动态规划算法,其时间复杂度为O（n×T）.其实,递归式③与0/1背包问题动态规划求解的递归式极其相似,求解的时间复杂度也类似.所以提出的第四个问题是一个NP完全问题.

2结语

从前面的启发式教学设计中可以看出,通过精心的教学设计,安排一些具有启发性的问题,可以有效地引导学生深入思考问题背后的问题,从而加深对一些原理的理解,把握其中的本质.通过提出问题和猜想,引导学生深入研究.启发式的教学不仅可以让学生更深刻地理解系统原理,同时对于培养学生的逻辑思维能力,培养独立思考的习惯都有着重要的意义.在某些问题的设计上,适当引入一些研究性的思路,对学生提出更高的要求,而不仅仅局限在教材上,有利于培养学生的钻研精神和探索精神,为今后的学习和工作打下坚实的基础,培养良好的习惯.

（见习编辑：刘丽丽；编辑：白杰）