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

来源 :华中科技大学 | 被引量 : 0次 | 上传用户:woaiyueyue1314
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
随着多核/众核处理器系统以及嵌入式实时应用的发展,多核实时系统的关键技术研究已成为热点,实时任务调度算法是其核心研究内容。在多核计算环境下,共享资源访问竞争所导致的任务同步问题将会延长任务的执行时间,并可能严重影响任务的实时可调度,从而对实时调度算法的设计提出了新的挑战。因无需任务的动态迁移,划分调度算法与全局调度算法相比,可产生较小的运行时开销,从而具有较好的运行时性能并具备更好的实用性。另一方面,基于锁机制的资源访问协议,例如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%以上),因此具备更好的应用价值。
其他文献
随着经济社会的发展,物权和债权两分的权利架构越来越受到质疑和挑战,不但"物权法定"无法跟上新型物权持续快速增加的趋势,甚至连物权和债权的划分也不能够穷尽现实中所有的
本文旨在从法治范式变革的视角研究司法的范式转换问题。“司法范式”体现的是法官默认的司法逻辑和价值取向,司法范式的变化是与法治范式的变革密切相关的。因为法治范式体
简要介绍了自主学习的定义以及培养自主学习能力对于外语教学的重要意义,展示了通过英语阅读课程教学对学生进行学习策略训练的对比实验研究。调查、访谈和测试结果表明,学习
随着社会的发展和科技的进步,高分子材料在生物医药领域发挥越来越大且不可替代的作用。具有抗污、缓释、靶向等功能的高分子材料成为高分子科学和高分子材料科学研究的前沿