当前位置：网站首页>解读论文记录指出经典的RMS证明过程小错误的一个论文的解读

解读论文记录指出经典的RMS证明过程小错误的一个论文的解读

2022-04-21 16:47:00 【标biao】

众所周知，实时调度最经典的论文是C.Liu和Layland的RMS单调速率调度算法，是实时操作系统中最优的固定优先级调度算法

C.L. Liu, J.W. Layland, Scheduling algorithms for multiprogramming in a hard-real-time environment, J. ACM 20 (1) (1973) 46–61.

该论文的结论是正确的，但是该论文的证明过程存在两个瑕疵：

改论文对于利用率最小化证明那里的case 2那儿错了
对于最后的结论，任务集利用率小于那个上界，就可以调度，没有严格给出的证明

上述两个问题，被这篇论文指出以及都修正了。

Devillers, R., & Goossens, J. (2000). Liu and Layland’s schedulability test revisited. Information Processing Letters, 73(5-6), 157–161. doi:10.1016/s0020-0190(00)00016-8

该文章证明思路如下：

关于第一个问题：Devillers提出如下
C.Liu他们说了如果总利用率小于那个上界，则该任务集可调度，但是却没有给出证明，因此Devillers给出了如下定理的严格证明：

证明过程为：

原理就是：既然假设了Un<bn，任务集不可调度。为什么后面又存在Un'<bn，任务集又是可调度的了呢，这不就跟自己的假设矛盾了嘛。因此Un<bn，任务集一定是可调度的才对。