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

doi:10.16180/j.cnki.issn1007-7820.2024.08.012

Abstract

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

CLC Number:

TP316.2

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.

Figures/Tables 13

Figure 1.

Table 1.

Figure 2.

Figure 3.

Figure 4.

Figure 5.

Figure 6.

Figure 7.

Figure 8.

Figure 9.

Figure 10.

Figure 11.

Figure 12.

References 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

Real-Time Hybrid Task Scheduling Algorithm in Embedded Multicore System

RichHTML

PDF (PC)

Like

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 13

References 18

Related Articles 15

Metrics

Comments

Recommended 0

[1]	MAO Hang, ZHANG Fengdeng, LU Yu, ZHU Jiawei. Energy Saving Scheduling Algorithm of Mixed-Criticality System Based on Probability Analysis [J]. Electronic Science and Technology, 2024, 37(3): 91-97.
[2]	ZENG Xiangyi,LIU Wei,XIAO Hao. A Firmware Security Update Scheme for Embedded Devices [J]. Electronic Science and Technology, 2023, 36(8): 14-18.
[3]	ZHANG Haitao,ZHANG Tong,ZHANG Yuhui,GUAN Yinfeng,ZHANG Fengdeng. Task Partitioning Optimization Algorithm Based on MrsP Protocol [J]. Electronic Science and Technology, 2023, 36(3): 36-41.
[4]	GUAN Yinfeng,ZHANG Fengdeng,ZHANG Haitao,ZHANG Yuhui. Improvement of Earliest Deadline First Algorithm in CAN FD Bus [J]. Electronic Science and Technology, 2023, 36(2): 29-36.
[5]	LIANG Shiqi,ZHANG Wenbin. Design of VFTO Measuring System at the Metal Flange Hole [J]. Electronic Science and Technology, 2022, 35(6): 76-82.
[6]	ZHANG Fengyin,GAO Bo,JI Yawei. Multi-Task Traffic Management Algorithm Based on FPGA [J]. Electronic Science and Technology, 2022, 35(12): 43-48.
[7]	FENG Chong,WU Yaohui,WU Haozhen. Optimizing the Real-Time Kernel Interrupt Management Mechanism of μC/OS-III [J]. Electronic Science and Technology, 2021, 34(9): 7-11.
[8]	SHUI Jiusheng,WANG Ran. A On-Demand Multi-Node Priority Charging Scheduling Algorithm [J]. Electronic Science and Technology, 2021, 34(8): 43-49.
[9]	XU Tao,ZHANG Yi,ZHAO Nengwu,WANG Yuhao,LI Minyue,LU Hongmin. Design and Implementation of a Receiver for Leaky Cable Intrusion Detection System [J]. Electronic Science and Technology, 2019, 32(12): 6-10.
[10]	SUN Shuai, LI Chuanxi. Based on Linux Multithreaded Management Analysis and Implementation [J]. , 2017, 30(9): 27-.
[11]	SUN Bo,GUO Weisheng. The Method of Analog Quantity Measure and Calibrate of Mobile Frequency Convertor [J]. , 2017, 30(9): 82-.
[12]	LU Haoyang1, CHEN Shiping1,2, WANG Xundeng1. Research on Wireless Network Transmission Side Defining Priority-based Queuing Delay [J]. , 2016, 29(9): 41-.
[13]	LI Rongrong. (Institute of Electronic CAD, Xidian University, Xian 710071, China) [J]. , 2016, 29(8): 25-.
[14]	MEI Tao,HUANG Baolei,XU Xiaoguang. Design and Realization of Network Driver Model in Embedded System [J]. , 2016, 29(4): 111-.
[15]	XU Yang,PENG Long,ZHANG Shuai. Design and Production of a 5output Broadband Wilkinson Microstrip Power Divider [J]. , 2016, 29(4): 133-.