多核处理器中混合关键级任务可调度及半分区划分算法

doi:10.16180/j.cnki.issn1007-7820.2024.03.001

Abstract

Abstract:

At present, the schedulability analysis of mixed critical level tasks and semi-partition scheduling algorithms in most multiprocessors are focused on single-core utilization. However, due to the high complexity of task scheduling in multi-core systems, the existing research results have some problems, such as unbalanced load of each processor and unsatisfactory task schedulability. To solve this problem, the application scope of Dynamic Demand Boundary Function(DDBF) is extended to multi-core processor system in this study. DDBF is improved based on half-partition scheduling algorithm, and SDDBF(Super Dynamic Demand Boundary Function) is proposed by adding forward job and forward job analysis, which can calculate and utilize resources more accurately. Based on SDDBF, the schedulability analysis method of SDA(Stepper Dispatch Algorithm) and semi-partition algorithm MCWF(Mixed-Criticality Worist First) are proposed. The simulation results show that compared with AMC(Adaptive Mixed Criticality), AMC-MAX and XU algorithms, the schedulability analysis of SDA can be improved by 5%~10%. Compared with WF_MY(Worst First_My) and WF_NEW(Worst First_New) algorithms, MCWF makes the system have better CPU(Central Processing Unit) load balancing performance at any critical level.

Key words: mixed-criticality system, semi-partition partitioning algorithm, multi-core platform, task scheduling, dynamic demand boundary, schedulability analysis, real time system, load balancing

CLC Number:

TP316.2

ZHU Jiawei, MAO Hang, ZHANG Fengdeng. Research on Hybrid Critical-Level Task Scheduling and Semi-Partition Algorithm in Multi-Core Processor[J].Electronic Science and Technology, 2024, 37(3): 1-9.

Figures/Tables 9

Figure 1.

Figure 2.

Table 1.

Figure 3.

Table 2.

MCS divides the task set"

τ_i	L_i	C_i $L O$	C_i $H I$	D_i $T i$
τ₁	HI	2	3	4
τ₂	LO	3	3	8
τ₃	HI	5	9	32
τ₄	LO	2	2	16
τ₅	HI	2	6	32
τ₆	LO	1	1	16
τ₇	HI	1	3	8
τ₈	LO	4	4	32

Table 2.

Table 3.

Table 4.

Figure 4.

Table 5

The variance of each partition algorithm"

	s² $S D D B F L O$	s² $U (L O)$ /%	s² $S D D B F H I$	s² $U (H I)$ /%
MCWF	184.5	0.28	158.2	0.260
WF_MY	650.5	0.53	1261.5	0.610
WN_EW	1 285.6	0.71	3468.9	1.075

Table 5

References 20

[1]	李辉, 刘志红. 基于半划分调度的Linux实时调度算法改进[J]. 计算机与数字工程, 2022, 50(7):1615-1619.
	Li Hui, Liu Zhihong. Improved real-time scheduling al-gorithm of Linux based on semi-partitioned scheduling[J]. Computer and Digital Engineering, 2202, 50(7):1615-1619.
[2]	Liu L, Qi D. An independent task scheduling algorithmin heterogeneous multi-core processor environment[C]. Chongqing:IEEE the Third Advanced Information Technology,Electronic and Automation Control Conference, 2018:593-601.
[3]	陶鑫. 多核混合关键系统中的任务划分调度算法及实现[D]. 武汉: 华中科技大学, 2019:23-45.
	Tao Xin. Partitioned scheduling algorithm and implementation for multicore mixed-criticality systems[D]. Wuhan: Huazhong University of Science and Technology, 2019:23-45.
[4]	杨沧海. 多核混合关键级系统的实时调度算法研究[D]. 北京: 中国电子科技集团公司电子科学研究院, 2022:15-38.
	Yang Canghai. Research on real-time scheduling algor-ithm for multiprocessor mixed-criticality system[D]. B-eijing: China Academic of Electronics and Information Technology, 2022:15-38.
[5]	曾理宁, 徐成, 李仁发, 等. 一种基于动态需求边界的混合关键级作业调度算法[J]. 软件学报, 2020, 31(11):3657-3670.
	Zeng Lining, Xu Cheng, Li Renfa, et al. Scheduling algorithm for mixed-criticality jobs based on dynamical demand boundary[J]. Journal of Software, 2020, 31(11):3657-3670.
[6]	胡璧涛. 面向混合关键系统的多核实时调度算法研究与实现[D]. 成都: 电子科技大学, 2022:10-16.
	Hu Bitao. Research and implement of multi-core real- time scheduling algorithm for mixed-criticality system[D]. Chengdu: University of Electronic Science and Technology of China, 2022:10-16.
[7]	王雅琴. 基于多核系统的混合关键任务调度策略研究[D]. 武汉: 武汉理工大学, 2020:29-37.
	Wang Yaqin. Research on mixed-criticality task scheduling strategy based on multi-core system[D]. Wuhan: Wuhan University of Technology, 2020:29-37.
[8]	罗乐, 王春华, 张多利, 等. 一种多核系统改进型列表调度算法[J]. 电子科技, 2020, 33(6):52-57.
	Luo Le, Wang Chunhua, Zhang Duoli, et al. A multicore system improved list scheduling algorithm[J]. Electronic Science and Technology, 2020, 33(6):52-57.
[9]	张通, 郑浩, 朱长昊, 等. 混合关键级任务资源需求的概率性分析[J]. 软件导刊, 2022, 21(1):156-163.
	Zhang Tong, Zheng Hao, Zhu Changhao, et al. Probabilistic analysis of resource requirements for mixed-criticality tasks[J]. Software Guide, 2022, 21(1):156-163.
[10]	张玄, 张多利, 宋宇鲲. 异构多核SoC处理器内部存储架构优化[J]. 电子科技, 2022, 35(9):44-51.
	Zhang Xuan, Zhang Duoli, Song Yukun. Optimization of the internal memory architecture of heterogeneous multi-core SoC processors[J]. Electronic Science and Technology, 2022, 35(9):44-51.
[11]	谷传才, 关楠, 于金铭, 等. 多处理器混合关键性系统中的划分调度策略[J]. 软件学报, 2014, 25(2):284-297.
	Gu Chuancai, Guan Nan, Yu Jinming, et al. Partitioned scheduling policies on multi-processor mixed-criticality systems[J]. Journal of Software, 2014, 25(2):284-297.
[12]	赵清伟. 多核混合关键度实时系统中任务划分及实现[D]. 武汉: 华中科技大学, 2015:33-42.
	Zhao Qingwei. Partitioned schemes and implementation on multi-core mixed-criticality real-time systems[D]. Wuhan: Huazhong University of Science and Technology, 2015:33-42.
[13]	Xu H, Burns A. Semi-partitioned model for dual-core mixed criticality system[C]. Lille: The Twentythird International Conference on Real-Time Networks and Systems, 2015:934-945.
[14]	Díaz L J, García F D, Kim K, et al. Stochastic analysis of periodic real-time systems[C]. Austin:IEEE the Twentythird RTSS, 2002:893-901.
[15]	Sheikh S Z, Pasha M A. Energy-efficient multicore sc-heduling for hard real-time systems:A survey[J]. Association for Computing Machinery Transaction on Embedded Computing System, 2019, 17(6):1-26.
[16]	Simó J, Balbastre P. The role of mixed criticality technology in industry 4.0[J]. Electronics, 2021, 10(3):1-5. doi: 10.3390/electronics10010001
[17]	Savithry J, Pillai A S. Towards mixed-critical real-time scheduling[C]. Madurai: The Ninth IEEE International Conference on Computational Intelligence and Computing Research, 2018:592-600.
[18]	Lopez G D, Anguiano L R, Trevino A R, et al. A flexible framework for real-time thermal-aware schedulers using timed continuous petri nets[J]. Computacion Y Sistemas, 2019, 23(2):417-433.
[19]	张凤登. 分布式实时系统[M]. 北京: 科学出版社, 2014:56-70.
	Zhang Fengdeng. Distributed real-time system[M]. Beiji-ng: Science Press, 2014:56-70.
[20]	何博强. 面向异构多核平台的时间确定性实时任务调度研究[D]. 成都: 电子科技大学, 2022:27-50.
	He Boqiang. Research on time-deterministic real-time task scheduling on heterogeneous multi-core platform[D]. Chengdu: University of Electronic Science and Technology of China, 2022:27-50.

	核1	核2
MCWF	τ₁τ₄τ₈	τ₇τ₂τ₃τ₆τ₅
WF_MY	τ₁τ₂	τ₃τ₇τ₄τ₈τ₅τ₆
WF_NEW	τ₁τ₈τ₅	τ₂τ₃τ₇τ₄τ₆

	SDDBF^LO	U(LO)	SDDBF^HI	U(HI)
MCWF	(24,25)	(0.750 00, 0.781 25)	(24,27)	(0.750 00, 0.843 75)
WF_MY	(28,21)	(0.875 00, 0.656 25)	(24,27)	(0.750 00, 0.843 75)
WF_NEW	(22,27)	(0.687 50, 0.843 75)	(30,11)	(0.937 50, 0.656 25)

Research on Hybrid Critical-Level Task Scheduling and Semi-Partition Algorithm in Multi-Core Processor

RichHTML

PDF (PC)

Like

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 9

References 20

Related Articles 14

Metrics

Comments

Recommended 0

[1]	SHEN Xiaolong, MA Jinquan, HU Zeming, LI Na, LI Yudong. Quantum Scheduling Algorithm for Heterogeneous Signal Processing Platform [J]. Electronic Science and Technology, 2024, 37(3): 84-90.
[2]	LI Yudong,MA Jinquan,XIE Zongfu,SHEN Xiaolong. Research on Task Scheduling of Heterogeneous Platform Signal Processing [J]. Electronic Science and Technology, 2024, 37(1): 24-32.
[3]	SHEN Xiaolong,MA Jinquan,JI Yawei,XIE Zongfu,LI Yiting,LI Yudong. Sparrow Optimization Algorithm for Task Scheduling of Heterogeneous Processing Platform [J]. Electronic Science and Technology, 2024, 37(1): 33-40.
[4]	HU Yifei,BAO Ziqun,BAO Xiaoan. A Dynamic-Static Load Balancing Algorithm Based on Improved Genetic Algorithm [J]. Electronic Science and Technology, 2023, 36(9): 79-85.
[5]	ZHOU Qiping,HE Wei,JIA Lei,GUO Junkai,ZHAO Jianguo. Research on Internet of Vehicles Navigation Technology Based on BDS and Edge Computing [J]. Electronic Science and Technology, 2023, 36(1): 51-59.
[6]	LI Na,GAO Bo,XIE Zongfu. Research on Scheduling Method of Layered Heterogeneous Signal Processing Platform [J]. Electronic Science and Technology, 2022, 35(2): 7-13.
[7]	WANG Yang,WANG Xiaolei,YUAN Ziang,YUAN Ruming. A Matrix Multiplication Mapping Technology Based on NOC Multi-Core System [J]. Electronic Science and Technology, 2021, 34(5): 54-60.
[8]	JI Lili, LI Ye . Virtual Machine Cluster Optimization Based on Migration in Cloud Environment [J]. , 2016, 29(8): 117-.
[9]	LIU Hongyi. Research on Data Management Problems Based on DDS Communication Model [J]. , 2016, 29(11): 146-.
[10]	LI Kun. Server Load Balancing Algorithm Based on Dynamic Feedback [J]. , 2015, 28(9): 45-.
[11]	LIU Junwei,WU Zi'an. Load Balancing Algorithm Based on QoS for Call Admission Control [J]. , 2015, 28(7): 115-.
[12]	CHEN Maoqiang. A Task Scheduling Algorithm for Parallel System Based on DAG [J]. , 2014, 27(9): 29-.
[13]	XIANG Hong-Jiao, LV Guang-Hong, MENG Li-Hong. QoS Unicast Routing Algorithm Based on Ant Colony System [J]. , 2014, 27(1): 53-.
[14]	YANG Mei, LI Zhong-Ke, WANG Zhong. The Research on Rapidly Distribution of Moving Target Information based on OWL-S Semantic Grid [J]. , 12, 25(7): 6-.

τ_i	a_i	D_i	x	C_i(1)	C_i(2)
τ₁	2	8	1	2	2
τ₂	0	12	2	5	8