基于高速缓存动态锁定的多核实时嵌入式系统任务调度算法研究

Task scheduling has become a significant research direction in the area of embedded systems. In real-time embedded systems, the current embedded software consists of a set of concurrent tasks which subject to timing constraints. The primary objective of the task scheduling algorithm is to construct a feasible schedule such that all the constraints can be satisfied; meanwhile the total response time of the task set is minimized. A basic requirement for finding a feasible schedule is to know the WCET (Worst Case Execution Time) of each task. However, caches make it significantly harder to compute the WCET of a task as it is difficult to know at compile time whether the corresponding data or instruction of each memory access is in the cache or not. To alleviate this problem, modern embedded processors provide hardware support for cache locking, a mechanism used to facilitate the WCET calculation of a task. However，integrating cache locking and task scheduling is more challenged for the reason that we need to consider the selection of locked cache contents, the allocation of the cache space and the determine of the addresses of the selected cache contents. This research will investigate the problem of integrating cache locking and task scheduling for real-time embedded systems. We will propose an optimal approach to select a set of instructions and data as locked cache contents for instruction cache and data cache, respectively. In addition, we will propose an approach to construct a feasible schedule in order to satisfy all the constraints and minimize the total response time. Furthermore, we will also study the cache allocation problems for two level caches. Lastly, we will implement the algorithms and use aiT to analyze the performance.

任务调度是实时嵌入式系统领域一个重要的研究热点。高效的任务调度算法能够确保满足实时嵌入式系统时间约束，并提高其的执行效率。然而高速缓存（cache）的应用使得任务的最差运行时间（WCET）无法精确预估，通常会造成任务WCET的过量估计，降低调度算法的有效性。高速缓存动态锁定（DCL）可以有效的解决这个问题。然而将其整合于任务调度算法之中会带来cache空间分配、被锁定内容的选取、被锁定内容的存储等问题，目前尚未有完善的相关算法。本项目拟研究基于DCL的多核实时嵌入式系统任务调度算法，最大程度提高系统执行效率。将分别针对指令缓存和数据缓存提出高效的锁定算法，减少单个任务的WCET；针对多核处理器，整合DCL，建立最优化的实时任务调度算法，满足任务时间约束并减少整体运行时间；对两级cache分别提出高效的空间分配和地址确定算法，提高cache的利用率；实现算法并用aiT软件进行仿真分析。

随着实时嵌入式系统的广泛应用，对其处理能力的要求也在日益提高，迫切的需要提升嵌入式系统执行效率。因此任务调度成为实时嵌入式系统领域的一个重要的研究热点。然而，进行任务调度的前提是能够精确的估计任务的最差执行时间，高速缓存的使用使得任务最差运行时间难以估计。因为难以估计被调用的内容是否存储于高速缓存之中，而从主存和从高速缓存调用所需时间相差较大。高速缓存动态锁定算法（Dynamic Cache Locking， DCL）能够解决这一问题。废除高速缓存自身的替换机制，将某些内容锁定在高速缓存中，存储状况被固定，调用时间也就相对固定，方便预测任务的最差执行时间。除此之外，通过最优化的选择锁定的内容，将最常用的内容锁定，可以有效的减少任务的执行时间。本项目主要研究基于DCL的多核实时嵌入式系统任务调度算法。主要研究内容分为三个部分：1）DCL算法设计；2）基于DCL的单核实时嵌入式任务调度算法；3）基于DCL的多核实时嵌入式系统任务调度算法。本项目的主要目的是将DCL方法与传统的任务调度算法相结合，设计合理的调度方法，提升实时嵌入式系统的执行效率。本项目完成了全部研究目标，通过仿真实验进行了算法性能的测试。在测试实验中，DCL算法平均减少任务执行时间8.3%，最高减少20%。针对单核实时嵌入式系统，系统的执行效率平均提升13.5%，最高提升19.12%。针对多核实时嵌入式系统，能够平均减少系统执行时间14.96%，最高21.15%。在工程应用当中，实时嵌入式系统对安全性的要求高于执行效率，需要设置合理的截止时间，保证任务能够在截止时间内完成。因此往往会做冗余设计，通过过量估计任务的最差运行时间，进行任务调度的设计，从而通过牺牲系统执行效率来保障系统的安全性。基于DCL的任务调度算法能够解决这一问题，极大的提升系统的执行效率。