A Weakly Hard Real-Time Schedule Algorithm Based on Cutting Down
基于裁剪的弱硬实时调度算法

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.