Improved Multiprocessor Global Schedulability Analysis of Sporadic DAG Task Systems

Bonifaci et al have recently introduced some novel analytical techniques in order to derive a speed-up bound for the multiprocessor global EDF scheduling of systems of recurrent tasks that are represented using the sporadic DAG task model, and have applied these techniques to obtain a pseudo-polynomial time sufficient schedulability test. In this paper, these techniques are further generalized to yield an improved pseudo-polynomial time sufficient schedulability test for global EDF scheduling of systems of sporadic DAG tasks. It is shown that this new test strictly dominates the one by Bonifaci et al, in addition, schedulability experiments demonstrate that the improvement can be quite substantial for certain kinds of task systems.

I. Introduction

Multiprocessor real-time scheduling theory started out considering the scheduling of recurrent task systems that are represented using relatively simple task models such as Liu & Layland [8] or 3-parameter sporadic [6], [9] tasks. One important characteristic of these early models is that the work generated by each individual recurrent task is assumed to be completely sequential: any particular task is allowed to execute upon at most one processor at each instant in time. This research has, by and large, been very successful; encouraged by the success in these initial endeavors, more expressive models, that are able to represent the parallelism that may be present within each individual recurrent task, are beginning to be considered. One particularly powerful such model in the sporadic DAG model for recurrent real-time tasks [3].