计算机操作系统启发式教学研究

1、计算机操作系统启发式教学研究计算机操作系统启发式教学研究操作系统是计算机相关专业的一门核心专业课，而实时调度算法是操作系统课程中的一个重要内容，在多数的操作系统教科书中主要介绍了两种实时调度算法，即最早截止时间优先算法EarliestDeadlineFirst，EDF和最低松弛度优先算法LeastLaxityFirst，LLF。这两个算法看上去并不难理解，然而问题往往并不像看起来那样简单。事实上，在操作系统的教学中有一个很大的困难，即操作系统的教学不易落到实处，即原理容易讲，但要让学生体验这些原理却并不容易。操作系统课程中涉及大量算法，如进程调度算法、死锁防止算法、页面置换算法等。外表上这些算

2、法看起来比较容易，但要让学生理解算法后面蕴含的深化道理，并从这些算法中发现一些问题就绝非易事了。对于这个困难，我们希望通过一些启发式的教学设计，引导学生从程序员、从算法设计者的角度去分析和考虑算法中的一些问题，从而将抽象的原理转化为详细的问题和解决方案，加深对这些原理的理解。下面结合实时调度算法的例子来阐述对于启发式教学设计的考虑。1实时调度算法的启发式教学设计1.1调度算法问题定义EDF算法是根据任务的开始截止时间来确定任务的优先级。截止时间愈早，其优先级愈高。该算法要求在系统中保持一个实时任务就绪队列，该队列按各任务截止时间的早晚排序；当然，具有最早截止时间的任务排在队列的最前面。调度程序

3、在选择任务时，总是选择就绪队列中的第一个任务，为之分配处理机，使之投入运行。截止时间可以是开始截止时间，也可以是完成截止时间。一般来说，完成截止时间等于开始截止时间加上任务处理时间。LLF算法是根据任务紧急或松弛的程度，来确定任务的优先级。任务的紧急程度越高，越优先执行。例如，一个任务在200s时必须完成，而它本身所需的运行时间就有100s，因此，该任务的紧急程度松弛程度为100s。又如，另一任务在400s时必须完成，它本身需要运行150s，那么其松弛程度为250s。调度程序总是选择就绪队列中松弛度最小的任务执行。LLF算法主要采用抢占调度方式。1.2发现问题按照教科书的描绘和给出的例如，在L

4、LF算法中，当有新任务到达时，并不马上比较当前所有任务的松弛度包括正在执行的任务，而是等到某个在等待的任务的松弛度降为零才进展切换，即选择这个松弛度已经降为零的任务运行。按照这个原那么，我们在启发式教学设计中提出的第一个问题。第一个问题：按照教科书给出的LLF算法调度原那么，是否会存在不可调度的情况？经过分析，很容易找出问题，如图1中给出的例如。通过上面的例如可知，在某些情况下，当某个任务在执行过程中，假设某个或某些正在等待的任务的松弛度减至0s，那么可能会导致任务无法成功调度，而实际上系统才能是允许成功调度的。1.3提出改进针对前面提出的问题，可以引导学生对LLF算法的调度准那么进展改进。通

5、常比较容易想到的改进是，修正松弛度的计算和任务切换时机，即松弛度不需要随时计算，而在如下两种情况时进展计算：1当前任务正在执行时新任务到达，可能会引起抢占和任务切换，此时需要计算并比较松弛度；2当前任务完成时可能会引起新的任务调度和切换，此时计算松弛度。进程在执行时松弛度会不断变化，但是不用进展跟踪计算和比较。修正后，可以对学生提出第二个问题。第二个问题：修正后的LLF算法，是否存在着不可调度的情况？答复仍然是存在问题，可以看一看图2中给出的另一个例如。1.4证明猜想假设发现改进后的LLF算法还是存在问题，这时可以引导学生再作改进，并进展讨论。事实上，无论如何改进LLF的调度和切换时机，都无法

6、解决问题。那么我们可以引导学生逐步转到EDF算法上来，即EDF算法也会存在类似问题吗？因此我们提出的第三个问题如下。第三个问题：按照完成截至时间调度的EDF算法，是否存在不可调度的情况？通过启发学生寻找反例会发现无法找到反例，这时学生也许会想到，EDF是一个最优的算法，即可以得出以下的猜想。猜想：给定一系列的任务，只要这些任务是可调度的，即存在某种序列使得所有任务都在完成截至时间之前完成，那么使用EDF算法一定能成功调度这些任务。有了猜想，如何证明呢？这显然要比设计反例困难得多。我们可以引导学生深化研究这个问题，这逐步进人了这个实验的关键部分，即发现问题，以及问题背后的问题，给出猜想，并分析和

7、证明自己的猜想。对此，我们也给出了这个猜想的一个证明。证明：1假设一系列任务是可调度的，并且安排出来的任务调度顺序不等同于EDF算法所安排的序列。2那么，此安排顺序中至少有两个任务A、B，其中A的截止时间比B的早，但A安排在B后面如图3a所示。那么只需将B移至A后面一位即可如图3b所示。3在之前的序列中A没有超时，那么移走B，A更不会超时；而B的新位置的完成时刻等于原来序列时A的完成时刻；而A的截止时刻小于B的截止时刻，所以B肯定不会超时。4重复以上过程，可以得到一个符合EDF规那么的任务序列。所以EDF一定能找到成功序列。证明了按完成截止时间调度的EDF算法的最优性之后，还可以启发学生进一步

8、考虑，假设是按开始截止时间调度的EDF算法，会有什么不同吗？另外，EDF算法和LLF算法之间有什么联络吗？通过进一步分析和比较可以得到下面的结论。EDF算法和LLF算法的比较结论：按开始截止时间调度的EDF算法并不能像按完成截止时间调度的EDF算法那样得到最优的结果。事实上，按开始截止时间调度的EDF算法的调度结果和按LLF算法的调度结果是一样的。也就是说，给定一个任务序列，按开始截止时间排序的结果和按松弛度排序的结果是一样的。证明：因为开始截止时间和松弛度分别满足如下关系。开始截止时间=完成截止时间-运行时间松弛度=完成截止时间-当前时间-运行时间比较式和式可得：松弛度=开始截止时间-当前时

9、间注意到对所有任务来说，其当前时间都是一样的，因此将任务按开始截止时间排序和按松弛度排序得到的结果是一样的。这同时也就说明了，假设按松弛度优先进展调度无法得到最优的结果，那么按开始截止时间调度的EDF算法也无法得到最优结果。1.5新的问题通过上面的证明可知，假设给出的一系列任务是可调度的，那么使用按完成截止时间调度的EDF算法一定可以成功调度这些任务，在这种意义下EDF是一个最优的算法。但是我们还可以再启发学生作进一步的考虑。假设给出的一系列任务是不可能全部调度成功的，那么EDF还是最优的吗？当然，需要重新定义最优的标准。这自然就得出下面这个新的问题。第四个问题：假设当前存在n个任务，用i表示

10、1in，下同，每个任务包含三个参数，一是任务的运行时间ti，第二个是任务的完成截止时间di，第三个是成功安排该任务可以获得的收益ri。请问按EDF进展调度能获得最大收益吗？假设不能，请设计一个调度算法使得最终的调度能获得最大收益。对于这个问题可以引导学生进展讨论。事实上，这个问题要困难得多，运用一些直观、朴素的原那么很难得到理想的解决方案。对此，可引导学生进一步运用算法和最优化方法中的一些技巧来分析该问题。下面是运用动态规划来求解该问题的一个方案。第四个问题的动态规划分析：1首先可以考虑的是，我们的目的是在n个任务中选取假设干个任务来获得最大收益，假设选出了这些任务即这些被选中的任务是可以安排

11、好的，那么可以按照EDF的规那么来安排执行，即把被选出的任务按各自的完成截止时间排序，那么这些任务一定都可以在各自的完成截止时间之内完成，这就是前面的猜想证明的结论。所以我们可以考虑将所有的n个任务按完成截止时间排序。假设按完成截止时间排好序后的n个任务用1，2，n表示。2其次考虑，在n个任务中选取假设干个任务来获得最大收益，与在n-1个任务中选取假设干个任务来获得最大收益之间有什么关系？可以看出，按完成截止时间排序后的第n个任务n假设不在最终选定的假设干个任务之列，那么问题可以转化为在n-1个任务，即1，2，n-1中选取最优的任务序列；假设任务n在最终选定的假设干个任务之列，那么问题可以转化为在截止时间T-tn之前，从1，2，n-1。中选取最优的任务序列。假设用fn，dn表示在截止时间dn前，从n个任务中选取满足条件的最优序列所获得的最大收益，那么可以得到如下的递归表达式：3根据递归式可以很容易地写出一个自底向上的动态规划算法，其时间复杂度为nT。其实，递归式与0/1背包问题动态规划求解的递归式极其相似，求解的时间复杂度也类似。所以提出的第四个问题是一个NP完全问题。2结语从前面的启发式教学设计中可以看出，通过精心的教学设计，安排一些具有启发性的问题，可以有效地引导学生深化考虑问题背后的问题