论文部分内容阅读
为适应日益增长的设计复杂性及成本,具有不同认证需求的应用共享计算平台,构建混合关键(Mixed-Criticality,MC)系统已成为嵌入式系统的发展趋势。混合关键系统的调度研究已有丰富成果,其中任务划分算法因其实用性(较低的运行时开销)得到了广泛的关注。现有多核混合关键系统的划分算法仅针对两个关键级别,且难以同时满足高可调度比率以及实用性。因此,多核混合关键系统划分算法的研究及其系统实现具有重要的理论及应用价值。针对多核混合关键系统中的任务划分调度,基于EDF-VD(Earliest-Deadline-First with Virtual Deadline)可调度条件,理论推导关键感知的利用率上界,并给出它与其它系统参数的数学性质。此上界的悲观性分析表明:任务在不同关键级别的利用率对任务划分调度的质量将产生重要的影响。为弥补此悲观性,针对多关键级别任务,提出基于EDF-VD的任务划分算法:关键感知的任务划分算法(Criticality-Aware Task Partition Algorithm,CA-TPA)。CA-TPA综合考虑MC任务在各个关键级别上的利用率对系统利用率的影响:首先,根据任务对系统的利用率的贡献进行任务的优先级排序;其次,在任务划分时,通过合理的划分策略最小化系统利用率的增长,从而提高可调度比率;最后,为均衡系统负载,定义负载失衡因子及其阈值,以减少系统运行时的开销。模拟实验结果表明:CA-TPA与传统的划分算法相比,具有更好的任务可调度比率(可提高35%以上),且与WFD算法具有近似的负载均衡性。为比较多种划分策略下的系统运行时开销,在LINUX操作系统内核上实现了EDF-VD调度器以及所有测试的划分算法。实测结果显示:得益于CA-TPA的负载均衡策略,其运行时开销与WFD性能相近,但明显优于其它划分算法(可降低20%以上)。