《RMS算法是最优算法的证明》由会员分享，可在线阅读，更多相关《RMS算法是最优算法的证明（5页珍藏版）》请在金锄头文库上搜索。
1、1.证明：RMS 是最优算法RMS 的由来是从硬实时环境的初始定义开始的：1,所有的任务都是周期性的，各个任务请求的 deadline 呈周期性，同时具有恒定的时间间隔；2,所有任务都必须在下一次任务请求（即 deadline）到来之前完成；3,所有的任务都是独立的，每一次任务请求不依赖于其他任务的执行或者初始化；4,每个任务都存在一个恒定且非时变的执行时间，即 CPU 不间断地执行该任务的时间；5,任何非周期的任务属于特殊任务，它们属于初始化或者是恢复错误的事件，仅当它们自身执行的时候才能取代周期性任务，同时非周期性任务不存在有 deadline.假设使用表示 m 个周期任务，任务申请周期和
2、运行时1,2,间分别表示为和。1,2,1,2,定理 1: 若所有进程在临界时刻启动的请求都能满足最后期限要求，则整个进程集可调度。即进程在临界时刻启动的请求响应时间最长。图 1：在执行之前的运行11证明：如图 1 所示，假定为优先级最低的任务，在时1,2,1刻任务发出了运行请求，显然在图 1 所示的时间间隔1到1+ 之间请求运行的周期性占先任务会推迟完成时刻，除非在到2来之前完成它。当向方向移动的时候，任务完成的时刻要么21不变，要么被推迟，所以断定，在向，直至与重21方向无线趋近1合的时候，能够做到完成任务的延时最长。根据定理 1 可以假定，有两个任务，对应的指定周期1和2。假设的优先级更高
3、，此时根据定理 1，可得：11 换的优先级之后，不难发现结果的任务依然是可行的。由于其对,任意式子都成立，于是命题成立。因此，单调速率调度算法在静态优先级调度算法中属于最优算法，所以该算法的 CPU 使用率必然大于等于其余的静态优先级调度算法。2.证明：如果n 为任务的个数，则 RMS 调度方案一定 = (21 1);存在；基于单调速率调度的算法中，定义 U 为 Processor Utilization.(CPU 的使用率)，由于为每一个任务 的 CPU 执行率，对系统有：; = = 1经推广到 n 个固定优先级的任务条件下，此时的最小上界为： = (21 - 1)由罗必塔法则，求得极限为
4、ln2。这就意味着，任何周期大小周期性任务一旦使用 RMS 调度算法均能满足调度要求，即在 deadline 之前完成。3.RMS 算法有哪些不足，如何改进？缺点：1，它的潜在 CPU 利用率小于动态优先级策略，在动态优先级的最优算法 EDF(Earliest Deadline First)中最坏情况下的可调度 CPU 使用率为 1.000。2，执行频率最高的任务并非最重要的任务。且较长周期的任务相对于较短周期的任务，更加容易错过 deadline。3，由于 RMS 算法的静态调度属性，它运行时灵活性较差，自适应性弱。现今常用的实时性的操作任务，常常具有较灵活的使用率需求，但同时具有严格 RM
5、S 算法完全建立在硬实时的条件下，主张所有被调度的周期性任务具有固定的优先级，这就显得强调在 deadline之前的必须完成任务的思想超出了必要限度。具体而言，在特殊场合，一些任务的 deadline 是可以被错过的，只要在 deadline 前完成任务的要求能在一定百分率下得到满足。这种高灵活性使得 RMS 的最小上界理论毫无提出之必要了。具体而言，在实时多媒体应用的调度之中，特点经常是：a，单个应用的执行次数常常是不定的；b，错过 deadline 尽管是不愿意出现的情况，但它确实是非致命的错误，这样在实时多媒体系统中使用过分强调在 deadline 之前任务的RMS 算法就多少显得有些不合时宜了，会导致较低的 CPU 使用率，从而浪费原本稀缺的资源；
