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

A Weakly Hard Real-Time Schedule Algorithm Based on Cutting Down

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

Existing weakly hard real-time scheduling algorithms can not guarantee the meeting ratio of executing sequence of which the length islarger than fixed window-size. Therefore, this paper, based on the （m,p） constraint, proposes an algorithm which is named as CDBS （cut-down based scheduling）. Since the discrimination of the satisfiability of （m,p） constraintneeds to go over the whole executing sequence of the task, it is very difficult and infeasible. For this reason, this paper introduces an efficient algorithm of cutting down the sequence, proves the correctness of the algorithm. This paper uses proper data structures so that the complexity of judgment is irrelevant to the length of sequence. Experimental results show the efficiency. Furthermore, this paper compares CDBS with other classical algorithms, such as EDF （earliest deadline first）, DBP （distance-based priority）, DWCS （dynamic window constraint schedule）, and the results show its competence.