改进的多处理器混合关键性系统可调度性分析

针对混合关键性系统的多重认证需求，研究多核处理器平台中全局调度算法fixed-priority and Earliest Deadline First by Virtual Deadline（fpEDF-VD）的可调度性分析问题。fpEDF-VD结合处理器利用率和虚拟截止期两个方面来计算任务优先级，系统可调度性取决于是否存在可行的虚拟截止期调整参数。考虑到现有可调度分析方法仅测试有限数量的调整参数候选值，不能有效地判定系统可调度性，故提出了一种改进的判定方法。该方法基于传统（非混合关键）任务调度算法fpEDF的可调度利用率约束条件，利用函数图像分析研究不同关键性级别的系统可调度性需求，并在此基础上给出有效虚拟截止期调整参数的确切范围。通过实例分析及与现有判定方法的比较，验证了该方法的正确性和高效性。与理论分析一致，基于随机生成任务集的仿真实验结果表明改进后的方法具有更优越的可调度性能，能显著地提高任务集的可调度接受率。

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.