多核嵌入式实时系统中面向任务同步的调度算法研究

发布时间：2020-03-25 08:15

【摘要】：随着多核/众核处理器系统以及嵌入式实时应用的发展,多核实时系统的关键技术研究已成为热点,实时任务调度算法是其核心研究内容。在多核计算环境下,共享资源访问竞争所导致的任务同步问题将会延长任务的执行时间,并可能严重影响任务的实时可调度,从而对实时调度算法的设计提出了新的挑战。因无需任务的动态迁移,划分调度算法与全局调度算法相比,可产生较小的运行时开销,从而具有较好的运行时性能并具备更好的实用性。另一方面,基于锁机制的资源访问协议,例如MSRP(Multiprocessor Stack Resource Policy)等,与悬挂机制相比具有避免死锁、实现简单、性能良好等优势,已被广泛应用于实时系统中。面向嵌入式异构多核系统的发展趋势以及实时应用对可靠性日益增长的需求,采用划分EDF(Earliest Deadline First)算法以及MSRP协议,研究面向任务同步的同构多核系统容错划分调度以及异构多核系统划分调度中的实时调度理论、任务映射算法以及操作系统内核实现,旨在解决任务同步限制下的多核实时调度中的关键问题。面向资源共享和可靠性需求的同构多核实时系统,理论探讨系统利用率的上界,发现并从原理上验证了系统利用率的非单调性,即更多的处理器核有可能导致系统利用率的下降。以系统利用率上界的理论分析为基础,基于PB(Primary/Backup)容错机制,提出了一种系统可靠性和任务同步感知的划分算法RSA-TPA(Reliability and Synchronization Aware Task Partitioning Algorithm)。首先,对任务同步干扰的本质特征进行分析,提出处理器核数下降的策略以及一种以资源为导向的新的计算方法,以降低任务同步开销上界;估算未划分任务的利用率,并据此进行未划分任务(包括主任务和备份任务)优先级的动态排序;设计高效的任务映射策略,使得系统利用率的增长最小化,从而提高任务集的可调度比例以及系统的负载均衡能力。另外,为降低算法的时间复杂度,提出了一种简化的任务划分算法RSA-TPA-efficient。模拟实验结果表明,与现有的仅考虑系统可靠性或者任务同步的划分算法相比,RSA-TPA具有更高的可调度比例(可提升60%以上)以及更均衡的系统负载。面向共享资源的异构多核实时系统,首先给出最坏情况下的任务同步开销并推导可调度充分条件,据此求解近似的系统利用率上界,从中同样发现系统利用率非单调性的规律。以系统利用率的悲观性分析为启发,提出一种同步感知的异构多核实时系统任务划分算法SA-TPA-HM(Synchronization Aware Task Partitioning Algorithm for Heterogeneous Mmulticores)。首先,提出异构计算平台上降低任务同步开销上界的新的计算方法,以提高任务的调度比例;动态计算未划分任务的优先权,确定任务划分顺序以提高任务集合调度的可行性;基于此,多次试探并计算系统利用率,确保每次任务划分可最小化系统利用率的增长以均衡系统负载。模拟实验结果表明,与传统的同构多核系统中任务划分算法相比,SA-TPA-HM能明显提高任务集合的可调度比例(可提升60%以上)。为进一步验证提出的划分算法的实用性,在Linux操作系统内核中实现了提出的算法以及其它测试算法。实测结果表明,与现有算法相比,RSA-TPA和SA-TPAHM划分算法可生成系统负载更为均衡的划分,减少处理器核上在EDF调度下的上下文切换次数,从而产生较少的在线开销(可减少15%以上),因此具备更好的应用价值。
【图文】：

流程图,任务划分,多核,流程

同的临界区多次访问同一种资源。假设任务i 有in 个临界区，第 x 个临界区（ 1,...,ix n ）记为i ,xz ，该临界区访问的资源记为 ( )i ,xr R 且基于最低处理核速率1f的临界区执行时间记为i ,xc 。具体的任务参数如图 2-1 所示。在多核实时系统中，访问共享资源的任务划分至处理器核的基本流程如图 2-2 所示。整个过程包含两个步骤：首先确定任务集合Ψ中所有未划分任务的划分优先权，然后选择具有最高划分优先权的任务，挑选合适的处理器核并将该任务映射至该处理器核。任务划分完毕后，每个处理器核上的所有任务遵循 EDF 算法以及 MSRP 资源访问协议执行。图 2-1 单个任务的参数说明

单个任务,参数说明

华中科技大学博士学位论文界区多次访问同一种资源。假设任务i 有in 个临界区，，第 x 个临,...,in ）记为i ,xz ，该临界区访问的资源记为 ( )i ,xr R 且基于最低处理核区执行时间记为i ,xc 。具体的任务参数如图 2-1 所示。在多核实时系统资源的任务划分至处理器核的基本流程如图 2-2 所示。整个过程包含先确定任务集合Ψ中所有未划分任务的划分优先权，然后选择具有最的任务，挑选合适的处理器核并将该任务映射至该处理器核。任务划个处理器核上的所有任务遵循 EDF 算法以及 MSRP 资源访问协议执行
【学位授予单位】：华中科技大学
【学位级别】：博士
【学位授予年份】：2019
【分类号】：TP332;TP301.6

【参考文献】