嵌入式多核系统中的实时混合任务调度算法

doi:10.16180/j.cnki.issn1007-7820.2024.08.012

摘要/Abstract

摘要：

针对由周期任务和零星任务形成的实时混合任务集进行合理调度问题,文中提出了一种基于零松弛度边界公平(Boundary Fair until Zero Laxity,BFZL)的实时混合任务算法。该算法在改进边界公平(Improved Boundary Fair,I-BF)实时混合任务算法基础上,通过引入最小松弛度优先(Least Laxity First,LLF)算法中的松弛度参数来改进判定任务的优先级,并提出基于松弛度与启发式策略相结合的启发式算法改进任务的分配策略。实验结果表明,BFZL算法能够满足系统实时性,并达到了算法优化目的。通过数据对比分析可知,该算法相比于原始算法,零星任务的平均响应时间降低了约26%,上下文切换减少了约28%,迁移减少了约50%。该算法在调度开销方面也具有一定优势。

关键词: 嵌入式系统, 多核处理器, 实时调度, 混合任务, 公平调度, 公平性, 划分, 优先级

Abstract:

In this study, an algorithm based on BFZL(Boundary Fair until Zero Laxit) is proposed to solve the problem of reasonable scheduling of real-time mixed task set formed by periodic task and sporadic task. Based on the I-BF(Improved Boundary Fair) real-time mixed task algorithm, the relaxation parameter of LLF(Least Laxity First) algorithm is introduced to improve the priority of decision task. A heuristic algorithm based on relaxation and heuristic strategy is proposed to improve task assignment strategy. The experimental results show that the BFZL algorithm can satisfy the real-time performance of the system and achieve the purpose of algorithm optimization. Through data comparative analysis, compared with the original algorithm, the proposed algorithm reduces the average response time of sporadic tasks by about 26%, reduces the context switch and migration by about 28% and 50%, respectively. Additionally, the algorithm also has advantages in scheduling overhead.

Key words: embedded system, multi-core processor, real-time scheduling, hybrid tasks, fair scheduling, fairness, divide, priority

中图分类号:

TP316.2

罗广, 冒航, 朱扬烁, 张凤登. 嵌入式多核系统中的实时混合任务调度算法[J]. 电子科技, 2024, 37(8): 84-91.

LUO Guang, MAO Hang, ZHU Yangshuo, ZHANG Fengdeng. Real-Time Hybrid Task Scheduling Algorithm in Embedded Multicore System[J]. Electronic Science and Technology, 2024, 37(8): 84-91.

图/表 13

图1

表1

图2

图3

图4

图5

图6

图7

图8

图9

图10

图11

图12

参考文献 18

[1]	张凤登. 分布式实时系统[M]. 北京: 科学出版社, 2014:237-258.
	Zhang Fengdeng. Distributed real-time system[M]. Beijing: Science Press, 2014:237-258.
[2]	Maia C, Yomsi P M, Nogueira L, et al. Semipartitioned scheduling of forkjoin tasks using work-stealing[C]. Porto: IEEE the Thirteenth International Conference on Embedded and Ubiquitous Computing, 2015:25-34.
[3]	Funk S, Nanadur V. LRE-TL:An optimal multiprocessor scheduling algorithm for sporadic task sets[C]. Porto: The Seventeenth International Conference on Real-Time and Network Systems, 2009:159-168.
[4]	Zhu D, Qi X, Mossé D, et al. An optimal boundary fair scheduling algorithm for multiprocessor real-time systems[J]. Journal of Parallel and Distributed Computing, 2011, 71(10):1411-1425.
[5]	周强, 李峭, 杨昕欣. 嵌入式实时系统—调度、分析和验证[M]. 北京: 北京航空航天大学出版社, 2015:33-67.
	Zhou Qiang, Li Qiao, Yang Xinxin. Embedded real-time system-scheduling,analysis and verification[M]. Beijing: Beihang University Press, 2015:33-67.
[6]	蒋小文. 多核实时系统的节能和可靠性优化调度研究[D]. 杭州: 浙江大学, 2018:14-18.
	Jiang Xiaowen. Multiprocessor real-time systems scheduling for energy and reliability optimization[D]. Hangzhou: Zhejiang University, 2018:14-18.
[7]	吴岳. 改进的Hadoop公平调度算法[J]. 电脑与信息技术, 2022, 30(6):39-41.
	Wu Yue. Improved fair scheduling algorithm of Hadoop[J]. Computer and Information Technology, 2022, 30(6):39-41.
[8]	王振江. 多核嵌入式实时系统中面向任务同步的调度算法研究[D]. 武汉: 华中科技大学, 2019:14-16.
	Wang Zhenjiang. The study on task synchronization oriented scheduling algorithm for multicore embedded real-time systems[D]. Wuhan: Huazhong University of Science and Technology, 2019:14-16.
[9]	梁秋玲. 基于多核处理器下的关联任务调度算法研究[D]. 桂林: 桂林电子科技大学, 2020:20-25.
	Liang Qiuling. Research on associated task scheduling algorithm based on multicore processor[D]. Guilin: Guilin University of Electronic Technology, 2020:20-25.
[10]	王通. 多核平台中针对DAG任务模型的全局EDF可调度性研究[D]. 兰州: 兰州理工大学, 2019:15-19.
	Wang Tong. Research on global EDF schedulability for DAG task model in multicore platfor[D]. Lanzhou: Lanzhou University of Technology, 2019:15-19.
[11]	赵凤军. 面向混合能源供应的移动边缘计算任务调度策略研究[D]. 北京: 北京信息科技大学, 2022:27-31.
	Zhao Fengjun. Research on moving edge computing task scheduling strategy formixed energy supply[D]. Beijing: Beijing Information Science and Technology University, 2022:27-31.
[12]	徐启泽. Xeon Phi众核处理器上BFS算法的优化技术[D]. 合肥: 中国科学技术大学, 2018:16-23.
	Xu Qize. Optimization techniques of BFS algorithm on X-eon Phi many-core processors[D]. Hefei: University of Science and Technology of China, 2018:16-23.
[13]	童辉辉. 面向异构多核处理器的混合式任务调度算法研究[D]. 桂林: 桂林理工大学, 2021:26-34.
	Tong Huihui. Research on hybrid task scheduling algorithmfor heterogeneous multicore processors[D]. Guilin: Guilin University of Technology, 2021:26-34.
[14]	陈刚, 关楠, 吕鸣松, 等. 实时多核嵌入式系统研究综述[J]. 软件学报, 2018, 29(7):2152-2176.
	Chen Gang, Guan Nan, Lü Mingsong, et al. State-of-the-art survey of real-time multicore system[J]. Journal of Software, 2018, 29(7):2152-2176.
[15]	雷振阳, 雷向东, 龙军. 多核系统中并行实时任务调度策略[J]. 信息技术, 2020, 44(9):15-20.
	Lei Zhenyang, Lei Xiangdong, Long Jun. Scheduling strategy of parallel real-time tasks in multicore systems[J]. Information Technology, 2020, 44(9):15-20.
[16]	Marouf M, George L, Sorel Y. Schedul ability analysis for a combination of nonpreemptive strict periodic tasks and preemptive sporadic tasks[C]. Krakow: Proceedings of IEEE the Seventeenth International Conference on Emerging Technologies and Factory Automation, 2012:1-8.
[17]	李辉, 刘志红. 基于半划分调度的Linux实时调度算法改进[J]. 计算机与数字工程, 2022, 50(7):1615-1619.
	Li Hui, Liu Zhihong. Improvement real-time scheduling algorithm of Linux based on semipartitioned scheduling[J]. Computer and Digital Engineering, 2022, 50(7):1615-1619.
[18]	王天一, 高博. 分布式实时系统数据分发服务DDS技术研究[J]. 电子科技, 2020, 33(8):40-45.
	Wang Tianyi, Gao Bo. Research on data distribution service of distributed real-time system[J]. Electronic Science and Technology, 2020, 33(8):40-45.

ID	R_i	C_i	D_i	m_i	Priority	o_i
1	0	3	5	3	5	0
2	0	8	10	4	4	0
3	0	1	10	0	3	0
4	0	5	15	1	1	1
5	1	1	6	0	2	1