异构多核实时系统中同步感知的可靠性调度算法研究及系统实现

With the rapid development of heterogeneous multicore embedded systems and ever-increasing demands of real-time applications for the system reliability, this research endeavors to address the critical problem of the reliability maintenance of both systems and applications under the limits of task synchronization, through investigating the scheduling theory, partitioning algorithm, energy management as well as the implementation for heterogeneous multicore real-time systems. This fundamental research plays an important role in optimizing the processing capability of heterogeneous multicores and improving the service performance of real-time activities. From the theoretical analysis of real-time scheduling, this study exploits the replica-based fault-tolerant scheme and derives the system utilization bound for synchronization-aware and reliability-based partitioned scheduling, where the relationships between the bound and system (and task) parameters are identified to guide the designs on the following scheduling algorithms. Next, we investigate efficient task partitioning algorithms, where the upper bounds on the synchronization overheads of tasks are tightened to increase the system schedulability and the workload balancing policy is proposed to reduce the run-time overheads. Based on these studies, we develop the reliability-aware energy management scheme under the constraints of task synchronization and system schedulability, where the energy-efficient techniques for the execution separation of multiple versions of a task and resource-aware online slack time management are explored. Furthermore, we build the library of performance evaluation and perform the rule mining to optimize the policies of online information processing. Finally, we implement these scheduling methods and technical plans in the kernel of Linux operating systems, and then validate and improve them based on real-life applications. This research can lay the theoretic and practical foundation for real-time applications running on heterogeneous multicore computing platforms with high efficiency, high energy-efficiency, high availability as well as high reliability.

面向异构多核嵌入式系统的发展以及实时应用可靠性需求的增长，针对任务同步问题，致力于研究异构多核实时系统中基于可靠性的调度理论、划分算法、能效管理与系统实现，解决系统及应用可靠性保障的难题，对优化异构多核处理效率和提升实时应用服务效能有重要价值。从实时调度理论出发，基于任务复制机制，论证同步感知的系统利用率上限及其与系统、任务参数的关系；基于此，设计高效任务划分算法，提出降低同步开销上限的计算方法以及系统负载均衡策略，以提高任务调度比例并降低运行时开销；进而开展可靠性能耗管理机制的研究，在任务同步限制和实时可调度前提下，探讨减少任务多版本重叠执行的可行途径，探索在线空闲时间管理的节能策略；建立性能测评库，挖掘规则以优化在线信息处理效率；最终在操作系统上实现并以实际应用来验证和完善提出的调度方法与解决方案，为构建异构多核计算平台上高效率、高能效、高可用、高可靠的实时应用系统奠定理论和实践基础。

本项目面向异构多核嵌入式系统的发展以及实时应用可靠性需求的增长，针对任务同步问题，致力于研究异构多核实时系统中基于可靠性的调度理论、划分算法、能效管理与系统实现，解决系统及应用可靠性保障的难题。研究内容主要包括：1）同步和可靠性感知的多核实时调度的任务划分机制。面向共享资源的同构多核系统，首次从理论上分析了系统利用率的上界，发现并论证了系统利用率上界的非单调性；基于系统利用率上界分析的理论基础，首次提出了一个可靠性和同步感知的实时任务划分算法RSA-TPA。模拟实验结果表明，与现有的仅考虑可靠性或者任务同步问题的划分算法相比，RSA-TPA具有更佳的可调度比例（50%以上。在Linux操作系统内核中实现了相关算法。实测结果表明，提出的算法可降低在线开销20%以上。2）面向资源共享的异构多核实时调度的任务划分机制。首次基于MSRP协议建立数学分析模型，据此给出最坏情况下的任务同步开销并推导任务集的可调度充分条件，进而近似估算系统利用率上界；以此为基础，首次提出了一种面向任务同步的异构多核实时任务划分算法SA-TPA-HM。模拟实验结果表明，与传统的同构多核系统任务划分算法相比，SA-TPA-HM可显著提高任务集合的可调度比例60%以上，且能产生较少的Linux内核在线开销（可降低15%以上）。3）弱实时应用的实时调度机制。面向弱实时任务不同的截止期限制条件，从全局上依据弱实时任务的紧迫度需求，设计弱实时任务的动态执行优先权，并推导新的WCRT可调度条件。模拟实验结果表明，与现有算法相比，提出的动态公平优先权制定策略可显著提高可调度比例50%以上，且产生可接受的Linux内核运行开销。