A Novel Partitioned Scheduling Algorithm of Constrained-deadline Sporadic Task Systems on Multiprocessors

Abstract

In this paper, a novel efficient DBF (eDBF^c) partitioned scheduling algorithm of constrained-deadline sporadic task systems on multiprocessors is proposed. A criterion which tracks the demand bound function exactly as needed is used in the novel algorithm. The using of the new criterion in eDBF^c avoids the incorrect judgment made by density algorithm and DBF* algorithm in determining whether a processor can accommodate an additional task. We give the pseudo code of the new algorithm on least-number processors and fixed-number processors respectively, and derive the sufficient and necessary conditions for success of our algorithm. The experimental results show the superiority of the proposed algorithm over density algorithm and DBF* algorithm.