基于裁剪的弱硬实时调度算法

摘要：

针对当前弱硬实时调度算法无法保证超过窗口长度的执行序列的满足率达到一定比例的问题,基于弱硬实时约束,提出了一种基于裁剪的调度算法(cut-down based scheduling,简称CDBS).由于判断约束是否满足需要遍历任务的整个执行序列,因此判断复杂度很大.为此,提出一种高效的裁剪执行序列的算法,同时证明其正确性,并利用适当的数据结构,使得计算复杂度与序列长度无关,通过实验说明其降低计算复杂度的有效性.进一步与其他经典实时调度算法(EDF(earliest deadline first),DBP(distance-based priority),DWCS(dynamic window constraint schedule))进行比较,验证该算法与其他算法具有相当的性能.

关键词：弱硬实时、动态失效、执行序列、CDBS(cut-down based scheduling)、转折点

所属期刊栏目：19

分类号：TP316(计算技术、计算机技术)

资助基金：the National Natural Science Foundation of China under Grant Nos.60603032, 60604029;the NSFC-Guangdong Province of China under Grant No.U0735003

在线出版日期：2008-09-24（万方平台首次上网日期，不代表论文的发表时间）

页数：共10页

页码：1837-1846