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

doi:10.12068/j.issn.1005-3026.2021.12.001

东北大学学报（自然科学版） ›› 2021, Vol. 42 ›› Issue (12): 1673-1680.DOI: 10.12068/j.issn.1005-3026.2021.12.001

• 信息与控制 • 下一篇

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

林宇晗，严健，王侃侃，邓庆绪

(东北大学计算机科学与工程学院，辽宁沈阳110819)

修回日期:2021-03-29 接受日期:2021-03-29 发布日期:2021-12-17
通讯作者: 林宇晗
作者简介:林宇晗(1988-)，男，福建福清人，东北大学博士研究生；邓庆绪(1970-)，男，河南南阳人，东北大学教授，博士生导师.
基金资助:
国家自然科学基金资助项目(62072085)；辽宁省科技厅兴辽英才计划项目(XLYC1902017).

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.

Revised:2021-03-29 Accepted:2021-03-29 Published:2021-12-17
Contact: DENG Qing-xu
About author:-
Supported by:
-

摘要/Abstract

摘要： 由于多核处理器争用共享缓存导致的不确定性为实时系统带来极大的挑战.为解决这个问题，现代处理器引入了缓存划分技术，通过隔离处理器核对缓存的访问从而提高了时间可预测性.但是，这种隔离技术可能导致实时任务因缓存分区的数量不足而被阻塞，而传统的实时调度算法与分析方法无法有效应对这种情况.因此，提出了支持缓存划分的可抢占全局最早截止期优先(EDF)实时调度算法gEDFca，并结合最新的缓存敏感调度理论针对这种调度算法进行了可调度性分析，提出了一种基于线性规划的可调度性判定条件.还提出了一种具有线性时间复杂度的优化算法，进一步提高了分析方法的性能.随机生成任务的仿真实验表明，提出的可调度性判定方法具有较高的效率.同时，优化算法提高了算法可调度性.

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

Abstract: 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.

Key words: resource management; real-time embedded systems; earliest deadline first; multi-core; cache partition

中图分类号:

TP316.2

林宇晗，严健，王侃侃，邓庆绪. 支持缓存划分的全局EDF实时系统调度策略[J]. 东北大学学报（自然科学版）, 2021, 42(12): 1673-1680.

LIN Yu-han， YAN Jian， WANG Kan-kan， DENG Qing-xu. Scheduling and Analysis of Global EDF for Multi-core Real-time Systems with Cache Partitioning[J]. Journal of Northeastern University(Natural Science), 2021, 42(12): 1673-1680.

参考文献

[1]Xu M，Phan L，Choi H，et al.Analysis and implementation of global preemptive fixed-priority scheduling with dynamic cache allocation［C］// IEEE Real-Time and Embedded Technology and Applications Symposium.Vienna，2016:1-12.
[2]Guan N，Stigge M，Yi W，et al.Cache-aware scheduling and analysis for multicores［C］// Proceedings of the 7th ACM International Conference on Embedded Software.New York:ACM Press，2009:245-254.
[3]Kessler R，Hill M.Page placement algorithms for large real-indexed caches［J］.ACM Transactions on Computer Systems，1992，10(4):338-359.
[4]Mancuso R，Dudko R，Betti E，et al.Real-time cache management framework for multi-core architectures［C］// IEEE Real-Time and Embedded Technology and Applications Symposium.Philadelphia，2013:45-54.
[5]Xu M，Phan L，Choi H，et al.Holistic resource allocation for multicore real-time systems［C］// IEEE Real-Time and Embedded Technology and Applications Symposium.Montreal，2019:345-356.
[6]Ward B C，Herman J L，Kenna C J，et al.Making shared caches more predictable on multicore platforms［C］// Euromicro Conference on Real-Time Systems.Paris，2013:157-167.
[7]Xu M，Phan L，Choi H，et al.vCAT:Dynamic cache management using CAT virtualization［C］//IEEE Real-Time and Embedded Technology and Applications Symposium.Pittsburgh，2017:211-222.
[8]Bertogna M，Cirinei M.Response-time analysis for globally scheduled symmetric multiprocessor platforms［C］// IEEE Real-Time Systems Symposium.Tucson，2007:149-160.
[9]Baruah S，Fisher N.Global deadline-monotonic scheduling of arbitrary-deadline sporadic task systems［C］// Proceedings of the 11th International Conference on Principles of Distributed Systems.Berlin:Springer，2007:204-216.
[10]Sun Y，Lipari G.Response time analysis with limited carry-in for global earliest deadline first scheduling［C］// IEEE Real-Time Systems Symposium.San Antonio，2015:130-140.
[11]韩美灵，邓庆绪，张天宇，等.多核处理器限制性可抢占G-EDF调度策略研究［J］.计算机学报，2019，42(11):2355-2367.(Han Mei-ling，Deng Qing-xu，Zhang Tian-yu，et al.Limited preemption for G-EDF scheduling on multiprocessors［J］.Chinese Journal of Computers，2019，42(11):2355-2367.)
[12]Baker T P.Multiprocessor EDF and deadline monotonic schedulability analysis［C］// IEEE Real-Time Systems Symposium.Cancun，2003:120-129.

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

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

RichHTML

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 1

编辑推荐

Metrics

本文评价