基于MrsP协议的任务划分优化算法

doi:10.16180/j.cnki.issn1007-7820.2023.03.006

Abstract

Abstract:

Scheduling and resource sharing are the core problems in multiprocessor real-time systems, the corresponding scheduling algorithm and shared resource access protocol will directly affect the performance of the system, which requires the scheduling algorithm and resource access protocol to maximize the computing power of the hardware platform on the basis of ensuring real-time performance. However, most existing scheduling algorithms assume that tasks are independent of each other and do not consider resource sharing among tasks. Besides, shared resource access protocols also focus on rules and worst-case response time analysis. In this regard, the whole schedule ability condition of multiprocessor real-time system is obtained by combining P-RM algorithm and MrsP protocol. According to the characteristics of the MrsP protocol, this study proposes a task division algorithm to reduce the blocking time. By improving the calculation method of the task utilization, the proposed method solves the problem of repeated calculation in the critical area. Compared with the previous task partitioning algorithm, the proposed algorithm also solves the key area of double-counting and splits the redistribution after task classification problem. Experiments resalts show that the number of processors required by the algorithm is reduced by 15% to 20%.

Key words: multiprocessor, real-time system, shared resource access protocol, schedule ability analysis, real-time scheduling, worst response time, partition algorithm, number of processors

CLC Number:

TP316

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.

Figures/Tables 5

Figure 1.

Table 1.

Range of experimental parameters"

参数	数值范围
处理器数量m	[2,32]
共享资源数量q	[1,10]
任务的数量n	[2,50]
任务周期T	[10 ms,1 000 ms]
每个任务关键区数量 $∑ r s ∈ F τ i$ N_i_,_s	[1,10]
共享资源访问时间C_s	[1 ms,10 ms]
访问某个共享资源的任务数\|G(r_s)\|	[2,20]

Table 1.

Figure 2.

Figure 3.

Figure 4.

References 20

[1]	Boutekkouk F. Real time scheduling optimization[J]. Journal of Information Technology Research, 2019, 12(4):132-152. doi: 10.4018/JITR
[2]	Back H, Lee J. Improved schedulability test for non-preemptive fixed-priority scheduling on multiprocessors[J]. IEEE Embedded Systems Letters, 2020, 12(4):129-132. doi: 10.1109/LES.4563995
[3]	Yang T, Deng Q. Global multiprocessor scheduling with job level priority assignment[J]. Journal of Circuits, Systems and Computers, 2019, 28(12):1-24.
[4]	Lopez J M, Diaz J L, Garcia D F. Minimum and maximum utilization bounds for multiprocessor rate monotonic scheduling[J]. IEEE Transactions on Parallel and Distributed Systems, 2004, 15(7):642-653. doi: 10.1109/TPDS.2004.25
[5]	Chen Z W, Lei H, Yang M L, et al. Improved task and resource partitioning under the resource-oriented partitioned scheduling[J]. Journal of Computer Science and Technology, 2019, 34(4):839-853. doi: 10.1007/s11390-019-1945-5
[6]	Zeng H, Di Natale M. An efficient formulation of the real-time feasibility region for design optimization[J]. IEEE Transactions on Computers, 2012, 62(4):644-661. doi: 10.1109/TC.2012.21
[7]	Burns A, Wellings A J. A schedulability compatible multiprocessor resource sharing protocol-MrsP[C]. Los Alamitos: Proceedings of IEEE the Twenty-fifth Euromicro Conference on Real-Time Systems, 2013.
[8]	陈刚, 关楠, 吕鸣松, 等. 实时多核嵌入式系统研究综述[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.
[9]	Zoubek C, Trommler P. Overview of worst case execution time analysis in single-and multicore environments[C]. Vienna: Proceedings of the Thirtieth International Conference on Architecture of Computing Systems, 2017.
[10]	Indrusiak L S, Harbin J, Burns A. Average and worst-case latency improvements in mixed-criticality wormhole networks-on-chip[C]. Lund: Proceedings of the Twenty-seventh Euromicro Conference on Real-Time Systems, 2015.
[11]	Block A, Leontyev H, Brandenburg B B, et al. A flexible real-time locking protocol for multiprocessors[C]. Daegu: Proceedings of IEEE the Thirteenth International Conference on Embedded and Real-Time Computing Systems and Applications, 2007.
[12]	王振江. 多核嵌入式实时系统中面向任务同步的调度算法研究[D]. 武汉: 华中科技大学, 2019.
	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.
[13]	Sha L, Rajkumar R, Lehoczky J P. Priority inheritance protocols: An approach to real-time ynchronization[J]. IEEE Transactions on Computers, 1990, 39(9):1175-1185. doi: 10.1109/12.57058
[14]	Lakshmanan K, De Niz D, Rajkumar R. Coordinated task scheduling, allocation and synchronization on multiprocessors[C]. Washington D.C.:Proceedings of IEEE the Thirtieth Real-Time Systems Symposium, 2009.
[15]	Nemati F, Nolte T, Behnam M. Partitioning real-time systems on multiprocessors with shared resources[C]. Berlin:International Conference on Principles of Distributed Systems, 2010.
[16]	余华兵. Linux内核深度解析[M]. 北京: 人民邮电出版社, 2019.
	Yu Huabing. Kernel analysis of Linux operating system[M]. Beijing: Posts and Telecommunications Press, 2019.
[17]	Brandenburg B B. Scheduling and locking in multiprocessor real-time operating systems[D]. Chapel Hill: University of North Carolina at Chapel Hill, 2011.
[18]	杨茂林. 共享资源约束下的多核实时调度算法研究[D]. 成都: 电子科技大学, 2016.
	Yang Maolin. Research on real-time scheduling algorithms with shared resources[D]. Chengdu: University of Electronic Science and Technology of China, 2016.
[19]	王兰, 张龙信, 满君丰, 等. 异构计算环境下基于优先队列划分的调度算法[J]. 小型微型计算机系统, 2020, 41(2):303-309.
	Wang Lan, Zhang Longxin, Man Junfeng, et al. Scheduling algorithm based on priority queue partition in heterogeneous computing environment[J]. Journal of Chinese Computer Systems, 2020, 41(2):303-309.
[20]	罗乐, 王春华, 张多利, 等. 一种多核系统改进型列表调度算法[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.

Task Partitioning Optimization Algorithm Based on MrsP Protocol

RichHTML

PDF (PC)

Like

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 5

References 20

Related Articles 2

Metrics

Comments

Recommended 10

[1]	LU Yu,ZHANG Li,ZHANG Fengdeng. Fault-Tolerant Clock Synchronization Algorithm Based on Grey Prediction [J]. Electronic Science and Technology, 2023, 36(3): 29-35.
[2]	WANG Tianyi,GAO Bo. Research on Data Distribution Service of Distributed Real-time System [J]. Electronic Science and Technology, 2020, 33(8): 40-45.