|
|
论文:2022,Vol:40,Issue(4):935-943 |
|
|
引用本文： |
|
|
黄姝娟, 李天森, 马志昊, 肖锋. 线性树模型的Sporadic任务多核调度方法研究[J]. 西北工业大学学报 |
|
|
HUANG Shujuan, LI Tiansen, MA Zhihao, XIAO Feng. Research on multi-core scheduling method for Sporadic task by line tree mode[J]. Northwestern polytechnical university |
|
|
|
|
|
|
|
| 线性树模型的Sporadic任务多核调度方法研究 |
|
| 黄姝娟, 李天森, 马志昊, 肖锋 |
|
| 西安工业大学 计算机科学与工程学院, 陕西 西安 710021 |
| 摘要: |
| 当前大多数的实时周期任务的调度模型都是以相互独立的固定周期任务为中心,很少考虑周期允许变化的任务模型以及处理器在调度过程中的模型。针对Sporadic实时周期任务,设计了一种基于线性树(line tree,LT)的任务模型和处理器模型,并提出了任务线性树(task line tree,TLT)模型到处理器线性树(processer line tree,PLT)模型的转化算法。该算法将所有实时周期任务的最小公倍数作为层数基准,根据完整job替换法则,利用迁移job的节点替换同层的非迁移job的空节点,利用任务周期可变,job可提前发布的情况达到最优的多核调度结果。实验结果表明,所提方法相比PEDF、GEDF以及RMFF算法,不仅具有较高的核利用率和较低的时限丢失率,同时减少了上下文切换次数和迁移次数。 |
| 关键词:
多核
实时调度
线性树
调度模型
调度算法
|
|
| Research on multi-core scheduling method for Sporadic task by line tree mode |
|
| HUANG Shujuan, LI Tiansen, MA Zhihao, XIAO Feng |
|
| School of Computer Science and Engineering, Xi'an Technological University, Xi'an 710021, China |
| Abstract: |
| At present, most of the scheduling models for real-time periodic tasks are established based on independent fixed periodic tasks and few by considering the task model with period allowed to change and the processor model in the scheduling process. In this paper, a task model and processor model based on line tree(LT) for sporadic real-time periodic tasks are designed, and a transformation algorithm from task line tree(TLT) model to processor line tree(PLT) model is proposed. The algorithm takes the least common multiple of all real-time periodic tasks as the benchmark of layer number, and based on the complete job replacement rule, the minimum common multiple of all real-time periodic tasks is used as the reference of layer number. In order to achieve the optimal multiprocessor scheduling result, the method of replacing the empty node of non-migrating job with the node of migrating job and the condition of allowing job to publish tasks ahead of time with variable cycle are used. Experimental results show that comparing with PEDF, GEDF and RMFF, the present method not only has higher core utilization and lower time loss rate, but also reduces the number of context switching and migration. |
| Key words:
real-time scheduling
line tree
scheduling model
scheduling algorithm
|
|
| 收稿日期: 2021-10-13
修回日期:
|
| DOI: 10.1051/jnwpu/20224040935 |
| 基金项目: 国家自然科学基金面上项目(62171361)、陕西省重点研发计划(2022GY-119)与陕西省西安市未央区科技项目(201925)资助 |
| 通讯作者: 肖锋(1976-),西安工业大学教授、博士,主要从事智能信息处理研究。e-mail:xffriends@163.com
Email：xffriends@163.com |
| 作者简介: 黄姝娟(1975-),西安工业大学副教授,主要从事嵌入式与分布式计算研究。
|
|
|
|
|
|
|
|
参考文献: |
|
|
[1] LIU C L, LAYLAND J W. Scheduling algorithms for multiprogramming in a hard-real-time environment[J]. Journal of Association for Computing Machinery, 1973, 20(1): 46-61
[2] 王涛,刘大昕. 多处理器单调速率任务分配算法性能评价[J]. 计算机科学, 2007, 34(1): 272-277 WANG Tao, LIU Daxin. The performance evaluation of rate monotonic tasks assignment algorithms on multiprocessor[J]. Computer Science, 2007, 34(1): 272-277 (in Chinese)
[3] BERTOGNA M, CIRINEI M, LIPARI G. Schedulability analysis of global scheduling algorithms on multiprocessor platforms[J]. IEEE Trans on Parallel and Distributed Systems, 2009, 20: 553-566
[4] 张忆文, 王成, 张惠臻. 基于RM策略的资源受限偶发任务调度算法[J]. 华中科技大学学报, 2017, 45(7): 115-121 ZHANG Yiwen, WANG Cheng, ZHANG Huizhen. Sporadic tasks scheduling algorithm with resources constraints based on RM scheme[J]. Journal of Huazhong University of Science and Techndogy, 2017, 45(7): 115-121 (in Chinese)
[5] ZHANG Shaohui. Research on rate monotonic algorithm and schedulability analysis in real-time system[J]. American Journal of Computer Sciences and Applications, 2019, 2(20): 1-6
[6] YANG K, ANDERSON J. On the soft real-time optimality of global EDF on uniform multiprocessors[C]//Processing of 2017 IEEE Real-Time Systems Symposium, Paris, France, 2017: 319-330
[7] ZHANG Y, GUO Z, WANG L, et al. Integrating cache-related preemption delay into GEDF analysis for multiprocessor scheduling with on-chip cache[C]//Processing of 2017 IEEE Trustcom/ BigData- SE/ICESS, Sydney, Australia, 2017: 815-822
[8] 王浩, 张凤登. CAN总线中改进的EDF调度算法可调度性分析[J]. 计算机测量与控制, 2020, 28(8): 238-241 WANG Hao, ZHANG Fengdeng. Schedulability analysis of improved EDF scheduling algorithm in CAN-bus[J]. Computer Measurement ＆ Control, 2020, 28(8): 238-241 (in Chinese)
[9] HOBBS C, TONG Z, BAKITA J, et al. Statically optimal dynamic soft real-time semi-partitioned scheduling[J]. Real-Time Systems, 2021,57(1/2): 97-140
[10] TIAN Yuchu, DAVID Charles Levy. Handbook of real-time computing[M]. Singapore: Springer Singapore, 2019
[11] ZHANG F. Improvement to semi-partitioned cyclic executives for mixed-criticality scheduling on multiprocessor platforms[J]. IEEE Access, 2020, 8(223): 606-617
[12] MAJUMDER S, NIELSEN J F D, BAK T. PaRTAA: a real-time multiprocessor for mixed-criticality airborne systems[J]. IEEE Trans on Computers, 2020, 69(8): 1221-1232
[13] MEDINA R, BORDE E, PAUTET L. Generalized mixed-criticality static scheduling for periodic directed acyclic graphs on multi-core processors[J]. IEEE Trans on Computers, 2021,70(3): 457-470
[14] SUN J, GUAN N, JIANG X, et al. A capacity augmentation bound for real-time constrained-deadline parallel tasks under GEDF[J]. IEEE Trans on Computer-Aided Design of Integrated Circuits and Systems, 2018, 37(11): 2200-2211
[15] SUN J, GUAN N, CHANG S, et al. Capacity augmentation function for real-time parallel tasks with constrained deadlines under GEDF scheduling[J]. IEEE Trans on Computer-Aided Design of Integrated Circuits and Systems, 2020,39(12): 4537-4548
[16] JIANG X, GUAN N, LIU D, et al. Analyzing GEDF scheduling for parallel real-time tasks with arbitrary deadlines[C]//Processing of in 2019 Design, Automation & Test in Europe Conference & Exhibition, Florence, Italy, 2019: 1537-1542
[17] WANG Y, JIANG X, GUAN N, et al. Partitioning-based scheduling of openmp task systems with tied tasks[J]. IEEE Trans on Parallel and Distributed Systems, 2021, 32(6): 1322-1339
[18] MASCITTI A, CUCINOTTA T, MARINONI M, et al. Dynamic partitioned scheduling of real-time tasks on ARM big.LITTLE architectures[J]. Journal of Systems and Software, 2021, 173(1): 1-14
[19] 黄姝娟, 朱怡安, 李兵哲, 等. 具有依赖关系的周期任务实时调度方法研究[J]. 计算机学报, 2015, 38(5): 999-1005 HUANG Shujuan, Zhu Yian, LI Bingzhe, et al. Real-time scheduling method for dependency period tasks[J]. Chinese Journal of Computers, 2015,38(5): 999-1005 (in Chinese) |
|
|
|
相关文献: |
|
|
1．黄姝娟, 朱怡安, 刘白林, 肖锋.嵌入式多核系统中三维立体调度模型的研究[J]. 西北工业大学学报, 2018,36(5): 1020-1025 |
|
|
|
|
|
|
