弱硬实时系统任意窗口约束调度研究  

Research on Any Window Constraint Scheduling in Weakly Hard Real-Time System

作　　者：吴彤[1] 金士尧[1] 陈积明[2] 

机构地区：[1]国防科学技术大学并行与分布处理国家重点实验室,湖南长沙410073 [2]浙江大学工业控制技术国家重点实验室,浙江杭州310027

出　　处：《电子学报》2008年第8期1564-1570,共7页Acta Electronica Sinica

基　　金：国家自然科学基金(No.60603032,60604029);NSFC-广东省联合基金(No.U0735003)

摘　　要：弱硬实时应用中的QoS在过载情况下会不同程度地退化.本文针对因仅考虑无限区间或者某一固定有限区间上的任务丢失率而导致重度过载情况下服务不公平的情况,基于可变区间,提出(p,k)约束,给出任意窗口约束调度(Any Window Constraint Schedule,AWCS)算法及其简化算法K窗口约束调度(-KWindow Constraint Schedule,KWCS),实验表明KWCS与AWCS的性能相当,且开销大幅降低.通过分析算法特性,给出具有QoS保证的时延上界通用表示方法.实验结果表明在重度过载情况下,AWCS(KWCS)优于其它弱硬实时算法.In overload conditions, the QoS of applications with weakly hard real-fine constraint is degraded diversely. To deal with the unfairness case caused by only considering an infinite interval or a fixed finite window loss-rate,this paper brings up a concept with a （ p, k）constraint, which is based on variable interval.Based on the （p, k） constraint, an algorithm is proposed, named as AWCS（Any Window Constraint Scheduling）.A simple version of AWCS is put forward, which is called KWCS（K-Window Constraint Schedule） .Extensive experiments show that KWCS can supersede AWCS,and not only achieve comparative performance but also get lower complexity. The properties of two algorithms are addressed, and a general representation of delay bound of the scheduling algorithms is brought forward. Results show that both AWCS and KWCS can provide better performance than other weakly hard real-time schedule algorithms in heavily overload circumstances.

关 键 词：任意窗口约束调度 弱硬实时 K窗口约束调度 区间最小成功率 时延 

分 类 号：TP316[自动化与计算机技术—计算机软件与理论]