2017/12/13 by Niklas Ueter, Ueter, Niklas, Georg von der Brüggen +7
Computer Science · #Distributed #FOS: Computer and information sciences #Operating Systems (cs.OS) #Parallel #and Cluster Computing (cs.DC) #cs.DC #cs.OS
paper · pdf · doi:10.48550/arxiv.1712.05040
arxiv created 2017/12/13 · arxiv updated 2017/12/15
This paper considers the scheduling of parallel real-time tasks with arbitrary-deadlines. Each job of a parallel task is described as a directed acyclic graph (DAG). In contrast to prior work in this area, where decomposition-based scheduling algorithms are proposed based on the DAG-structure and inter-task interference is analyzed as self-suspending behavior, this paper generalizes the federated scheduling approach. We propose a reservation-based algorithm, called reservation-based federated scheduling, that dominates federated scheduling. We provide general constraints for the design of such systems and prove that reservation-based federated scheduling has a constant speedup factor with respect to any optimal DAG task scheduler. Furthermore, the presented algorithm can be used in conjunction with any scheduler and scheduling analysis suitable for ordinary arbitrary-deadline sporadic task sets, i.e., without parallelism.