提到调度算法, 就不得不提到RM调度算法. 1973年Liu和Layland发表的这篇文章的前半部分(参考[1])首次提出了RM调度算法在静态调度中的最优性. 不仅如此, 他们还把系统的利用系数(utilization factor)和系统可调度性联系起来, 推导出用RM调度所能达到的最小系统利用率公式. 同时, 这篇论文中透露出来的证明思想和方法也被人们所效仿. 下面就让我们来看看这篇文章中关于RM调度算法的重要结论.
任何一个结论都有一个模型假设, 让我们先列出这里的假设:
(A1) 所有的任务请求都是周期性的,必须在限定的时限内完成;
(A2) 任务的作业必须在该任务的下一个作业发生之前完成, 这样避免了考虑队列问题; 在这里, 我们对任务和作业不作特别的区分, 因为一个任务请求就是一个作业.
(A3) 任务之间都是独立的,每个任务的请求不依赖于其他任务请求的开始或完成;
(A4) 每个任务的运行时间是不变的,这里任务的运行时间是指处理器在无中断情况下用于处理该任务的时间;
(A5) 所有的非周期性任务都在特殊的情况下运行,比如系统初始化或系统非正常紧急处理程序.
(A6) 其它一些假设, 比如, 单处理器, 可抢占调度, 任务切换的时间忽略不计等等.
一个任务的响应时间(response time)是指一个任务请求, 这个任务实际完成的时间跨度. 在静态调度中, 任务的临界时刻(critical instant)这个概念被首先提出来. 它被定义为一个特定的时刻, 如果在这个时刻有这个任务的请求, 那么这个任务就会需要最大的响应时间. 由此得出定理1:
一个任务的临界时间就是比这个任务优先级高的所有任务同时发出请求的时刻.
证 明: 由于一个任务的响应时间是它自己的负载时间加上被其它优先级高的任务所打断的时间. 由于自己的负载时间是固定的, 我们考虑在什么时候任一高优先级的任务会有最长的打断时间. 显然, 只有当这一高优先级的任务与该任务同时请求处理时, 才能可能产生最大的打断时间.
定理1的价值在于它找到了一个证明一个调度算法能否调度任一任务集充分必要条件, 那就是所有任务同时请求执行的时的情况下每个任务仍能满足各自的期限, 那么这个任务集就可以被这个调度算法调度.
有了这个推论, 我们就可以证明RM调度的最优性了.
定理2: 如果一个任务集能够被静态调度, 那么RM调度算法就能够调度这个任务集. 从这个意义上说, RM调度是最优的静态调度算法.
这个定理的证明方法就是有名的交换法. 证明思路如下:
假设一个任务集S采用其他静态优先级算法可以调度,那么总有这样两个优先级相邻的任务i和j, 有Ti>Tj,而Pi≤Pj.把Ti和Tj的优先级Pi和Pj互换,明显可以看出这时S仍然可以调度, 因为在所有任务同时请求的情况下, 交换这两个任务不会影响其它任务的完成时间, 同时这两个任务都可以在各自期限内完成. 按照这样的方法,其他任何静态优先级调度最终都可以转换成RM调度.
0 件のコメント:
コメントを投稿