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

doi:10.16180/j.cnki.issn1007-7820.2024.03.001

摘要/Abstract

摘要：

当前,多数多处理机中混合关键级任务可调度性分析以及半分区调度算法均针对单核利用率展开研究。但由于多核系统任务调度复杂性较高,现有研究结果存在各处理器负载不均衡以及任务可调度性不理想等问题。针对该问题,文中将动态需求边界函数(Dynamic Demand Boundary Function,DDBF)的应用范围扩展至多核处理器系统。根据半分区划分调度算法对DDBF改进,并加入了结转作业和前接作业分析提出了SDDBF(Super Dynamic Demand Boundary Function),可更精确地计算与利用资源。文中基于SDDBF提出了SDA(Stepper Dispatch Algorithm)可调度性分析法与半分区划分算法MCWF(Mixed-Criticality Worist First)。仿真结果表明,相较于AMC(Adaptive Mixed Criticality)、AMC-max以及XU算法,SDA可调度性分析判定提升了5%~10%,相较于WF_MY(Worst First_My)、WF_NEW(Worst First_New)算法,MCWF可使系统在任意关键等级下的CPU(Central Processing Unit)负载具有更良好的均衡性能。

关键词: 混合关键级系统, 半分区划分算法, 多核平台, 任务调度, 动态需求边界, 可调度性分析, 实时系统, 负载均衡

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

中图分类号:

TP316.2

朱嘉炜, 冒航, 张凤登. 多核处理器中混合关键级任务可调度及半分区划分算法[J]. 电子科技, 2024, 37(3): 1-9.

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.

图/表 9

图1

图2

表1

图3

表2

MCS划分任务集"

τ_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

表2

表3

表4

图4

表5

各划分算法方差"

	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

表5

参考文献 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)