支持缓存划分的全局EDF实时系统调度策略  

Scheduling and Analysis of Global EDF for Multi-core Real-time Systems with Cache Partitioning

作　　者：林宇晗 严健 王侃侃 邓庆绪 LIN Yu-han;YAN Jian;WANG Kan-kan;DENG Qing-xu(School of Computer Science and Engineering,Northeastern University,Shenyang 110819,China)

机构地区：[1]东北大学计算机科学与工程学院,辽宁沈阳110819

出　　处：《东北大学学报（自然科学版）》2021年第12期1673-1680,共8页Journal of Northeastern University(Natural Science)

基　　金：国家自然科学基金资助项目(62072085);辽宁省科技厅兴辽英才计划项目(XLYC1902017).

摘　　要：由于多核处理器争用共享缓存导致的不确定性为实时系统带来极大的挑战.为解决这个问题,现代处理器引入了缓存划分技术,通过隔离处理器核对缓存的访问从而提高了时间可预测性.但是,这种隔离技术可能导致实时任务因缓存分区的数量不足而被阻塞,而传统的实时调度算法与分析方法无法有效应对这种情况.因此,提出了支持缓存划分的可抢占全局最早截止期优先(EDF)实时调度算法gEDFca,并结合最新的缓存敏感调度理论针对这种调度算法进行了可调度性分析,提出了一种基于线性规划的可调度性判定条件.还提出了一种具有线性时间复杂度的优化算法,进一步提高了分析方法的性能.随机生成任务的仿真实验表明,提出的可调度性判定方法具有较高的效率.同时,优化算法提高了算法可调度性.Multi-core real-time systems are significantly challenging to analyze due to the unpredictability from extensive contention over shared caches.Therefore,an efficient method,cache partitioning,is introduced into modern multi-core platforms to avoid cache access from co-executing cores,by which the timing predictability are improved.However,the cache space isolation technique may result in unbounded blocking because of the insufficient number of cache partitions.Unfortunately,the existing scheduling and analysis techniques cannot be applied to this situation.gEDFca,a cache-aware preemptive global earliest deadline first(EDF)scheduling algorithm was proposed for multi-core systems.And its analysis method was presented based on linear programming.Besides,a novel optimization algorithm was introduced for further improving schedulability.Evaluations using generation tasks show the proposed analysis method is highly efficient.It also shows that the optimization algorithm yields a significant improvement in schedulability.

关 键 词：资源管理 实时嵌入式系统 最早截止期优先 多核 缓存划分 

分 类 号：TP316.2[自动化与计算机技术—计算机软件与理论]