Improved schedulability analysis for multiprocessor mixed-criticality systems

For mixed-criticality systems implemented upon multiprocessor platforms and scheduled by the popular global scheduling algorithm named fixed-priority and earliest deadline first by virtual deadline (fpEDF-VD), the issue how to determine their schedulability is studied, addressing the concern of multiple certification requirements. According to fpEDF-VD, the task's priority is determined by the combination of task utilization and virtual deadline, and the schedulability of the system depends on the existence of valid scaling factor for virtual deadline tuning. Considering that current approaches only verify finite scaling factor candidates, an improved schedulability analysis is proposed, which is capable of determining the feasible region of the scaling factor accurately. This approach investigates schedulability requirements at different criticality levels by exploiting the function graph of the schedulability condition derived for the regular (non mixed-criticality) fpEDF algorithm, and on this basis provides the accurate range of the parameter for tuning virtual deadlines. An illustrative example is presented to demonstrate its validity and efficiency. In accordance with theoretical analysis, extensive simulation experiments with randomly-generated task sets show the dominance of the proposed schedulability analysis over the existing ones in terms of acceptance ratio.