摘要
针对混合关键性系统的多重认证需求,研究多核处理器平台中全局调度算法fixed-priority and Earliest Deadline First by Virtual Deadline(fp EDF-VD)的可调度性分析问题。fp EDF-VD结合处理器利用率和虚拟截止期两个方面来计算任务优先级,系统可调度性取决于是否存在可行的虚拟截止期调整参数。考虑到现有可调度分析方法仅测试有限数量的调整参数候选值,不能有效地判定系统可调度性,故提出了一种改进的判定方法。该方法基于传统(非混合关键)任务调度算法fp EDF的可调度利用率约束条件,利用函数图像分析研究不同关键性级别的系统可调度性需求,并在此基础上给出有效虚拟截止期调整参数的确切范围。通过实例分析及与现有判定方法的比较,验证了该方法的正确性和高效性。与理论分析一致,基于随机生成任务集的仿真实验结果表明改进后的方法具有更优越的可调度性能,能显著地提高任务集的可调度接受率。
For mixed-criticality systems implemented upon muhiprocessor 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 pro- posed schedulability analysis over the existing ones in terms of acceptance ratio.
作者
陈瑶
李峭
鲁俊
熊华钢
CHEN Yao LI Qiao LU Jun XIONG Huagang(School of Electronic and Information Engineering, Beijing University of Aeronautics and Astronautics, Beijing 100083, China)
出处
《北京航空航天大学学报》
EI
CAS
CSCD
北大核心
2016年第9期1918-1926,共9页
Journal of Beijing University of Aeronautics and Astronautics
基金
国家自然科学基金(61301086)
航空科学基金(20131951027)
中央高校基本科研业务费专项资金(YWF-14-DZXY-018)~~
关键词
实时系统
混合关键性
多处理器
全局调度
最早截止时间优先
可调度性分析
real-time system
mixed-criticality
multiprocessor
global scheduling
earliest deadline first
schedulability analysis