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

doi:10.16180/j.cnki.issn1007-7820.2023.03.006

电子科技 ›› 2023, Vol. 36 ›› Issue (3): 36-41.doi: 10.16180/j.cnki.issn1007-7820.2023.03.006

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

张海涛,张通,张宇辉,管银凤,张凤登

上海理工大学光电信息与计算机工程学院,上海 200093

收稿日期:2021-09-01 出版日期:2023-03-15 发布日期:2023-03-16
作者简介:张海涛(1994-),男,硕士研究生。研究方向:分布式实时系统。|张通(1992-),男,硕士研究生。研究方向:分布式实时系统。|张凤登(1963-),男,博士,教授。研究方向:汽车电子与现场总线。
基金资助:
国家自然科学基金(71840003);上海市自然科学基金项目(15ZR1429300)

Task Partitioning Optimization Algorithm Based on MrsP Protocol

ZHANG Haitao,ZHANG Tong,ZHANG Yuhui,GUAN Yinfeng,ZHANG Fengdeng

School of Optical-Electrical and Computer Engineering,University of Shanghai for Science and Technology,Shanghai 200093,China

Received:2021-09-01 Online:2023-03-15 Published:2023-03-16
Supported by:
National Natural Science Foundation of China(71840003);Shanghai Municipal Natural Science Fund Project(15ZR1429300)

摘要/Abstract

摘要：

多处理器实时系统中,调度和资源共享是核心问题,与之相对应的调度算法和共享资源访问协议将直接影响系统的性能,这就要求调度算法和资源访问协议在保证实时性的基础上尽量发挥硬件平台的计算能力。然而,现有的调度算法多假设任务相互独立,没有考虑任务之间的资源共享,共享资源访问协议也多侧重于规则和最坏响应时间分析。对此,将P-RM算法和MrsP协议相结合,得出了多处理器实时系统的整体可调度性条件。文中根据MrsP协议的特性,提出了一种减小阻塞时间的任务划分算法,通过改进任务利用率的计算方式解决了关键区重复计算的问题,与之前的任务划分算法相比,也解决了关键区重复计算以及任务分类后拆分再分配的问题。实验表明,该算法所需要的处理器数目减少了15%~20%。

关键词: 多处理器, 实时系统, 共享资源访问协议, 可调度性分析, 实时调度, 最坏响应时间, 划分算法, 处理器数量

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

中图分类号:

TP316

张海涛,张通,张宇辉,管银凤,张凤登. 基于MrsP协议的任务划分优化算法[J]. 电子科技, 2023, 36(3): 36-41.

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.

图/表 5

图1

表1

实验参数范围"

参数	数值范围
处理器数量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]

表1

图2

图3

图4

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

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

Task Partitioning Optimization Algorithm Based on MrsP Protocol

RichHTML

PDF (PC)

赞

可视化

摘要/Abstract

引用本文

使用本文

图/表 5

参考文献 20

相关文章 3

Metrics

本文评价

推荐阅读 10

[1]	陆禹,张力,张凤登. 基于灰色预测容错时钟同步算法[J]. 电子科技, 2023, 36(3): 29-35.
[2]	王天一,高博. 分布式实时系统数据分发服务DDS技术研究[J]. 电子科技, 2020, 33(8): 40-45.
[3]	陈彬,苏宇逍. 基于多处理器的可识别方位引信信号处理系统[J]. , 2013, 26(1): 77-.