Analyzing Global-EDF for Multiprocessor Scheduling of Parallel Tasks

Consider the problem of scheduling a set of constrained-deadline sporadic real-time tasks on a multiprocessor where (i) all processors are identical, (ii) each task is characterized by its execution requirement, its deadline and its minimum inter-arrival time, (iii) each task generates a (potentially infinite) sequence of jobs and (iv) the execution requirement of a job and its potential for parallel execution is described by one or many stages with a stage having one or many segments such that all segments in a stage have the same execution requirement and segments in the same stage are permitted to execute in parallel and a segment is only allowed to start execution if all segments of previous stages have finished execution. We present a schedulability test for such a system where tasks are scheduled with global-EDF. This schedulability test has a resource-augmentation bound of two, meaning that if it is possible for a task set to meet deadlines (not necessarily with global-EDF) then our schedulability test guarantees that all deadlines are met when tasks are scheduled with global-EDF, assuming that the system analyzed with our schedulability test is provided processors of twice the speed.