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